Join Algorithms — Nested-Loop, Hash, Sort-Merge

Join Algorithms — Nested-Loop, Hash, Sort-Merge

Every query touching more than one table needs a join, and how you compute it has enormous performance consequences. This lesson implements the three classic join algorithms every real database engine (Postgres, MySQL, SQL Server) chooses between at plan time: nested-loop, hash, and sort-merge. They all produce the same result set for an equality join — the differences are entirely about algorithmic cost and, for this exercise, the exact order in which matches are emitted.

Nested-Loop Join (NL)

The simplest possible join: for every row in the left (outer) table, scan every row in the right (inner) table and emit a match when the join keys are equal.

Cost: O(n × m). No preprocessing needed, works for any join condition (not just equality), but scales terribly for large tables. Its big advantage here is that the emission order is trivially defined: outer-left-order × inner-right-order.

Hash Join

Build a hash table on one side (conventionally the smaller one — here, the left), keyed by the join column, then probe it once per row on the other side:

Cost: O(n + m) on average — each side is visited once. The tradeoff is memory (you materialize a full hash table for one side) and that it only works for equality joins (you can't hash a < or > condition). Note the determinism contract for this exercise: you probe in right-row order, and within a matching bucket, left rows come out in their original insertion order — not hash-bucket-internal order, which would be non-deterministic across runs.

Sort-Merge Join (SMJ)

Sort both sides by the join key, then walk them in lockstep like the merge step of merge-sort, emitting the cross-product of every run of equal keys:

Cost: O(n log n + m log m) for sorting, then O(n + m) to merge (plus the size of the match runs). This is the algorithm of choice when both inputs are already sorted (e.g. arriving from an index scan on the join column) — in that case you skip the sort entirely and the join becomes near-linear. This exercise asks for a stable sort with original insertion order as tie-breaker — that's what sorted(enumerate(...), key=lambda x: (value, x[0])) gives you: ties on the join key fall back to the order rows were originally inserted, which keeps output deterministic even when many rows share a key.

Why the exact emission order matters here

Unlike a typical SQL engine (where join result order is technically unspecified unless you add ORDER BY), this exercise pins down precisely how each algorithm must order its output, because the goal is to make you actually implement the mechanics correctly — not just produce a correct set. Read the determinism contract for each algorithm carefully before coding; it's very easy to get a functionally-correct-but-order-wrong join that fails every test.

Edge cases to watch

• Duplicate join-key values on both sides — every algorithm must produce the full cross product of matching rows (if 2 lefts and 3 rights share a key, that's 6 output rows), not just one match.
• No matches at all — output should be just the header (or nothing, per the COUNT command's behavior) rather than erroring.
• The optional trailing COUNT command — when present, skip printing rows entirely and print only the match count, so don't build your row-emission logic in a way that makes counting require materializing and reformatting the full output first.