Merge Join

Formula#

Running time, given the already sorted sequences:

where $n$ and $k$ are the numbers of rows and columns of the result, $C_M$ is the average cost of comparing or writing one element in the Zipper algorithm and $C_C$ the average cost of copying one value to the result.

Simplified estimate for query planning (same as for the hash join, constants ignored):

The row estimate assumes each row of the smaller table has exactly one match in the larger one.

Properties#

• Algorithm (two pointers $p$ in $L_X$, $q$ in $L_Y$): if $x_p < y_q$ advance $p$; if $x_p > y_q$ advance $q$; if $x_p = y_q = v$, determine the runs of pairs with value $v$ in both lists, output all combinations of the two runs, and advance both pointers past their runs.
• vs. hash join: asymptotically the same as the hash join $C_I n_1 + C_L n_2 + C_C n k$, but typically $C_M \ll C_I$ and $C_M < C_L$, so the merge join is faster, especially when both $n_1$ and $n_2$ are large. It needs sorted input, which the hash join does not.
• Worst case: if all join values are equal, $n = n_1 n_2$ and the merge join is as expensive as the Cartesian Product.
• Sorted input from indexes: scanning the linked leaves of an index B+ Tree yields all (value, row index) pairs in sorted order. With a B+ tree on both join columns this is exactly the input of the merge join.
• SQLite3 performs neither merge nor hash joins: it iterates over one join column and looks up each value in an index on the other (built temporarily if none exists), even when both columns have a B+ tree (“an interesting design decision”). A typical RDBMS supports both merge and hash joins, and choosing between them is part of query planning.

Example#

Sources#

• Slides 05, p. 13 (definition), p. 14 (example), p. 15 (running time), p. 16 (cost estimate), p. 17 (SQLite3)
• Slides 06, p. 11 (B+ tree leaves as merge-join input)
• DBIS_VL05 > Merge join, DBIS_VL05 > Cost estimates for ES5, DBIS_VL05 > Particularities of SQLite3, DBIS_VL06 > Index B+ tree