This is an acyclic query, and its join tree is just a line:

Remember that Yannakakis's algorithm requires 2 semijoin passes to reduce the relations, before a final pass to actually join them and output the results. Let's follow the execution in slow motion. We'll consider input relations such that every tuple successfully join with the next relation, e.g. R_1 = R_2 = R_3 = R_4 = \{(1, 1), (2, 2), \ldots, (n, n)\}. The bottom-up pass starts with building a hash table for R_4 (let's call that T4), mapping each x_4 value to the corresponding x_5's. It looks like this on our input:

T4[1] = [1]
T4[2] = [2]
...
T4[n] = [n]

Note that each key is mapped to an array of values, because in general the same key can appear in multiple tuples, but for our input every x_4 maps to a unique x_5.

Now, to compute R_3 \ltimes R_4, we'll loop over R_3 while probing into T4, and keep the tuples if the probe succeeds:

Here I'm already applying a small optimization: instead of collecting the semijoin result into a buffer R_3' and make another scan to build the hash table T3, I'm directly building T3 on-the-fly. I'm also abusing the notation a little bit and use T3[x3].push(x4) to mean "if x3 is already mapped to an array, insert x4 to it, otherwise map x3 to a new array containing just x4".

On our input instance, the semijoin doesn't really do anything - every tuple in R_3 survives, and T3 looks exactly like T4. The same will happen for the other two semijoins on the bottom-up pass, namely R_2 \ltimes R_3 and R_1 \ltimes R_2. In fact, the top-down pass will also be the same. Overall, we will run 6 useless semijoins, each requiring n probes and n inserts into a hash table. The final join pass will take n hash lookups per join. Overall the algorithm takes 6n + 3n = 9n lookups and 6n inserts. In contrast, regular hash join will only require building 3 hash tables (3n inserts) and probing into them (3n probes).

To be fair, the example above uses the worst possible input for the algorithm - because no tuple can be removed, the semijoin passes are completely useless. This points to a natural remedy: the main idea of the first enhancement is to reduce the semijoin overhead with Bloom filters.

Bloom filters

On our example, 6n of the total 9n lookups are now done on Bloom filters, and 3n of the inserts are into Bloom filters. If the filter fits in the cache, both lookups and inserts will be orders-of-magnitude faster than the corresponding operations on hash tables which likely requires memory accesses with bad locality. And on average cases, the semijoin passes will throw away bad tuples, further accelerating the final join pass.

For this query, we can squeeze all 3 passes of Yannakakis's algorithm into a single pass! The idea is that in stead of running semijoins, we push down the aggregation to run as we build the hash table for each relation. Starting with R4:

Note that x4 is now mapped to a single value instead of an array, because we only need to keep one max per group. We do the same for R3:

And also the same for R2:

Finally, the same for R1 before you get bored:

Overall, instead of adding 6 additional semijoins, we are running just 3 steps, each performing a join and a group-by together. Another advantage of this approach is that each step can be formulated as a SQL query, making it applicable to any database without touching the internal engine. To compute T4, we can create a view:

Then we join T4 with R3 for T3:

Of course, we can't do this for every query - we have no choice but to output all tuples for our SELECT * query. In general, this method requires the query to be relation-dominated, which basically says that the GROUP BY attributes must all come from the same relation. Another way to understand this approach is to think of aggregate pushdown as a way of "creating" new primary keys - after an aggregation, the GROUP BY attributes automatically becomes a primary key; and since joins on primary keys will always be O(n), the entire algorithm runs in linear time.

Join on the way up, unnest on the way down

While the GROUP BY trick only applies when there are enough aggregates, we will see a more general way to "squeeze together" the passes of Yannakakis's algorithm. But this method is better understood as an optimization of the classic hash join, so we will tweak our example a little. We'll use the same query, but now consider the input: \begin{aligned} R_1 &= \{(2, 0), (4, 0), \ldots, (2n, 0)\} \\ R_2 &= \{(0, 2), (0, 4), \ldots, (0, 2n)\} \\ R_3 &= \{(1, 0), (3, 0), \ldots, (2n-1, 0)\} \\ R_4 &= \{(0, 1), (0, 3), \ldots, (0, 2n-1)\} \end{aligned} On these relations, both R_1 \bowtie R_2 and R_3 \bowtie R_4 will produce n^2 tuples, but the final result is empty. Now suppose we join with the plan (R_1 \bowtie (R_2 \bowtie (R_3 \bowtie R_4))), meaning to first join R_3 with R_4, then join the result with R_2, and finally with R_1. We will spend O(n^2) time computing R_3 \bowtie R_4, only to realize nothing joins with R_2 and throw it all away. Let's look at the code:

Our mistake is that we are "expanding" the matching results from T4[x4] into T3 too early: every single tuple in R_3 shares x_4 = 0, so the entire R_4 will match and is duplicated for every entry in T3, causing the quadratic blowup. The key idea of our 3rd enhancement is to delay the expansion of matching results, and instead only store a pointer to the matches:

Now we no longer have 2 nested loops for the first join, and this join is guaranteed to run in linear time. We will repeat the same pattern for joining with R_2 and R_1, and eventually we will end up with a nested representation of the join results. For this example, we can stop right after the join with R_2 because the result is empty; in general, we will need to unnest by following the pointers in a top-down pass. This still requires 2 passes - a join pass and an unnest pass - but the unnest pass no longer touches any hash tables.

On-the-fly semijoin

The plan (R_1 \bowtie (R_2 \bowtie (R_3 \bowtie R_4))) we considered in the previous section is known as a right-deep plan, because if we draw out the operator tree, it goes down to the right. Most database however tend to favor left-deep plans because such a plan allows for a pipelined implementation without materializing intermediate results. For our example query, consider the left-deep plan (((R_1 \bowtie R_2) \bowtie R_3) \bowtie R_4), which means we first join together R_1 with R_2, then join the result with R_3, and finally with R_4. The execution engine will first build a hash table each for R_2, R_3, R_4, then iterate over them with nested loops:

Now the large intermediate results are implicitely hidden in the loop nests. Because there's nothing to materialize, we can't really create any nested representation either. Instead, we will "piggyback" semijoins on the loop nest:

Here we added code to check if a hash probe will fail, and delete the offending tuple from the iterating relation if so. Deletion is safe, because we know any future probes with the same tuple is doomed to fail again. This way we are essentially running the semijoins on-the-fly and by demand; the deletions are also fast thanks to good temporal locality, and most hash tables implement deletion by setting a single "tombstone" bit to indicate the entry is invalidated. It is easy to see why the algorithm runs in linear time: every time a tuple is visited, it either eventually contributes to an output result, or gets deleted; overall this leads to O(|\textsf{IN}|+|\textsf{OUT}|) complexity.

Conclusion