Join Algorithms: Nested-Loop, Hash and Sort-Merge

A join combines rows of two tables whose key columns match: every order with the customer who placed it, every employee with their department. The result is the same whichever way you compute it. What differs is the work done and, in this lesson, the order in which the matching pairs come out.

JOIN HASH emp.dept = dept.code

The output has all columns of the left table, then all columns of the right table, each written table.column, then one line per matching pair.

What counts as a match

Two rows match when their key cells are equal and neither is NULL. NULL is "unknown", so it equals nothing, not even another NULL. The same value order as in the rest of the engine applies: an integer never equals text, so 1 and 1x do not match. These rules hold for every algorithm.

1. Nested-loop join

For every row of the left table, scan the whole right table and keep the pairs that match.

for each row L of the left table, in order            (outer loop)
    for each row R of the right table, in order       (inner loop)
        if L.key matches R.key: emit the pair (L, R)

It works for any condition and needs no preparation, but it compares n * m pairs: 1,000 rows by 1,000 rows is a million comparisons. The output order is simply left order, and within a left row, right order.

2. Hash join

Pay a small price up front to avoid the inner loop.

1. Build: walk the left table once and put each row into a hash table keyed by its join key, a bucket of rows per key, keeping the original order inside a bucket. Rows with a NULL key are left out.
2. Probe: walk the right table once, in order. For each row, look its key up in the hash table (one lookup, not a scan) and emit a pair with every left row of that bucket.

The cost is about n + m instead of n * m. The output comes out grouped by right row: all pairs of the first right row, then of the second, and so on. That is why a hash join's result order differs from a nested loop's, even though it holds exactly the same pairs. (When the table is small, build on the smaller side; in this lesson the left table is always the build side.)

3. Sort-merge join

Sort both sides by the join key, then walk them together like the merge step of merge sort, with one index on each side:

• left key smaller than right key: advance the left index;
• left key larger: advance the right index;
• equal: find the whole run of equal keys on each side and emit every combination of the two runs (left rows in the outer loop), then continue after both runs.

Duplicates need that run handling: three rows with key 5 on the left and two on the right make six pairs. The sort must be stable (equal keys keep their original order) so that the output is deterministic, and rows with NULL keys are dropped before sorting. The result comes out in key order, ascending by the value order (so 9 before 10). The sort costs n log n + m log m; the merge walk itself is linear. A sort-merge join shines when the inputs are already sorted, for example because they come from an index.

Comparing the three

Real databases choose between them from statistics, the way the previous planner lessons chose between scans.

The protocol

TABLE dept code,name           declare a table
ROW dept d1|Sales              add a row (a cell is NULL if empty or NULL; an integer if it looks like one; else text)
JOIN HASH emp.dept = dept.code        print the join
JOIN SMJ emp.dept = dept.code COUNT   print only the number of matching pairs

The algorithm is NL, HASH or SMJ. Joining a table with itself is refused.

What you build

The starter parses commands, validates names and prints results. You write the three algorithms: nl_join, hash_join and merge_join, each returning the matching pairs in the order described above.

Common mistakes

• Letting NULL match NULL.
• Hash join emitting in left order, or reversing the order of rows inside a bucket.
• Merge join forgetting the runs: advancing both indexes after one pair loses the cross product of duplicates.
• An unstable sort, so equal keys come out in a different order than the contract says.
• Comparing keys as text, which puts 10 before 9 in the merge.

Your exercise

You implement nl_join, hash_join and merge_join. The mistake to avoid: handling duplicate keys in the merge join by advancing both sides after a single pair.