With --join merge, join on equality by sorting each input on its merge key unless it already arrives in that order, walking both in step, pairing every left row of a key with every right row of that key, and handing up rows in key order so that an ORDER BY on the key needs no sort.
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.
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.
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.
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.
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.
Make sure both inputs come sorted.
Two cursors, moving forward only.
These are the exact lines the tests check. The full definition is on the output contract page, section 72.
| Input | Output |
|---|---|
--join merge, users join orders, order by u.id | MergeJoin (on: u.id = o.user_id) over SeqScan (table=users, alias=u) and Sort (key=o.user_id ASC), and no Sort above it |
| a join on both tables' keys | [EXEC] rows_examined=<n> merge_comparisons=<c>, no sort_runs |
users join orders, --sort-memory 10 | ... merge_comparisons=<c> sort_runs=20 |
$droid --db merge.db --join mergeWelcome 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>.exitexiting.. 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.
Sort in the plan and sort_runs on the line.rows_examined shows it.The page above is the same for every language. These are the only language-specific hints.
std::vector<Row> for the right group, cleared and refilled per key.Vec<Row> for the group and Ordering from comparing key tuples drives the loop with a match.ArrayList(Row) for the group, reset with clearRetainingCapacity.