Sort-Merge Join

Why this stage exists

The hash join reads each input once but needs memory for one of them, and its output comes in no useful order. The merge join needs both inputs sorted on the key and then almost no memory at all. Its output is sorted on the key too.

When the inputs are already sorted, which is often the case when the join key is each table's own key, the sort is free. Then a merge join is the cheapest join there is: one pass over each side.

Two cursors

Put a cursor at the start of each sorted input and compare the keys under them. The smaller one cannot match anything still to come on the other side, so move it on. When they are equal, you have found a match.

Each comparison moves at least one cursor forward, so with unique keys a merge makes at most one comparison per row of either side: 2000 for two tables of 1000 rows. A nested loop would test a million pairs. The [EXEC] line counts comparisons as merge_comparisons.

Duplicates on both sides

This is where a naive merge goes wrong. With three rows of a and three rows of b all keyed 5, the right answer is nine pairs. A merge that moves both cursors on after a match gives three.

The fix is to treat equal keys as groups: on a match, collect the whole group of right rows with that key, then pair each left row of the group with all of them. When the left side moves to its next row with the same key, the right group is still there to pair with again.

NULLs and LEFT JOIN

NULL sorts first, so NULL keys sit next to each other on both sides, and a merge that only compares "equal or not" would pair them. They must never match: skip any row whose key holds a NULL. Under a LEFT JOIN a skipped left row is padded, as is any left row the right cursor passes with no partner, and every left row left over when the right side ends.

Order for free

The output comes in key order. So order by u.id on top of this join needs no Sort, because the rows already come in exactly the order a stable sort would give them. This is the one case where a join keeps the ORDER BY of a single table's key.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 72.

What you should see when done

$droid --db merge.db --join merge
Welcome to droid!
>create table a (id int primary key, k int);
Create table statement executed successfully
>create table b (id int primary key, k int);
Create table statement executed successfully
>insert into a (id, k) values (1, 5);
Insert statement executed successfully (1 rows)
>insert into a (id, k) values (2, 5);
Insert statement executed successfully (1 rows)
>insert into b (id, k) values (1, 5);
Insert statement executed successfully (1 rows)
>insert into b (id, k) values (2, 5);
Insert statement executed successfully (1 rows)
>select count(*) from a join b on a.k = b.k;
COUNT(*)
4
(1 rows)
[EXEC] rows_examined=4 merge_comparisons=4 sort_runs=2
>.exit
exiting.. good bye!

The number after merge_comparisons depends on how your merge walks its groups; this one compares each left row with each row of the right group.

Common bugs in this stage

• One pair per key. Both cursors must not move on together after a match.
• Matching neighbouring NULLs.
• Sorting an input that is already in key order. The rows are right, but there is a Sort in the plan and sort_runs on the line.
• Forgetting the left rows after the right side ends under a LEFT JOIN.
• Reading on after one side ends in an inner join. Nothing more can match, and rows_examined shows it.
• Keeping the Sort for ORDER BY the key. The merge already gives that order.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: hold the current right group in a growable array of rows; refill it when the key changes.
• C++: a std::vector<Row> for the right group, cleared and refilled per key.
• Rust: a Vec<Row> for the group and Ordering from comparing key tuples drives the loop with a match.
• Zig: an ArrayList(Row) for the group, reset with clearRetainingCapacity.