Join Algorithms — Nested Loop, Hash & Sort-Merge

Three ways to combine two tables

A JOIN isn't one operation — the optimizer picks one of three algorithms based on table sizes, indexes, and whether sorted output is needed. Knowing them turns a mysterious slow join into an obvious "wrong algorithm / missing index" diagnosis.

The three algorithms

The trap to recognise in EXPLAIN

A Nested Loop over two large tables with no index on the join key is the classic catastrophe — millions × millions. The fix is almost always: add an index on the join column, or let the planner pick a hash join (check your stats are fresh).

EXPLAIN ANALYZE SELECT * FROM orders o JOIN users u ON o.user_id = u.id;
--  Hash Join  (hash table on users; probe with orders)          <- good for big o, small u
--  vs  Nested Loop -> Index Scan on users_pkey                   <- good when o is small
--  vs  Merge Join  (both already ordered by the join key)

The Sort-Merge Join Duplicate Key Trap (Backtracking)

A standard sort-merge join operates in $O(N \log N + M \log M)$ to sort, followed by a linear $O(N + M)$ pass using two cursors to merge the rows. However, a naive two-cursor linear pass fails when duplicate keys exist on both sides.

Equality vs theta: who can run which algorithm

Hash join and sort-merge join require an equality (equi-join) predicate on the join keys: ON a.k = b.k (or a conjunction of equalities). They hash or sort on those keys. A theta join uses a non-equality comparison — ON a.score > b.threshold, ON a.ts BETWEEN b.start AND b.end, band joins, etc. Those force nested loop (possibly with an index range scan on the inner side if one exists). Seeing Nested Loop on a huge join is not always a bug: if the predicate is not equi, the planner has no hash/merge option.

-- Equi-join: hash or merge eligible
SELECT * FROM orders o JOIN users u ON o.user_id = u.id;

-- Theta / non-equi: nested loop only (index on inner may still help)
SELECT * FROM events e JOIN windows w
  ON e.ts >= w.start_ts AND e.ts < w.end_ts;

Hash spill mechanism: grace / hybrid hash join

"Spills to disk" is not a single sequential dump. When the build side does not fit in work_mem, engines use a partitioned (grace / hybrid) hash join:

1. Partition pass. Hash each build row by the join key into P partitions (batches) written to temp files so each partition is aimed to fit in memory. Probe-side rows are partitioned with the same hash function into matching files.
2. Per-partition join. For each partition i: load build partition i into an in-memory hash table; scan probe partition i and probe. Output matching pairs. Discard the table; move to i+1.
3. Recursive spill. If a single partition still exceeds memory (skew: one popular key hashes alone into a huge bucket), the engine re-partitions that partition with another hash (or falls back to nested loop for that slice). Heavy skew is why "raise work_mem" alone sometimes fails.

In Postgres EXPLAIN ANALYZE, Batches > 1 (and growing Batches mid-execution) signals this path. Cost becomes multi-pass disk I/O proportional to data size × number of partition rounds — far more than an in-memory O(A+B) hash join.

-- Healthy: Batches=1 (fits in work_mem)
-- Hash  (Batches=1  Memory Usage=8192kB)
-- Unhealthy spill:
-- Hash  (Batches=32  Memory Usage=4096kB)  -- 32 partition pairs hit disk

When-NOT summary

• Do not expect hash/merge for non-equality joins — nested loop is the only general algorithm.
• Do not hash-join a huge build side hoping memory appears; filter first, or ensure the smaller input is the build side (planner usually swaps, but wrong stats prevent it).
• Do not use nested loop on two large unindexed inputs for equi-joins — add an index or let hash win after ANALYZE.

Pitfalls

• Hash join spills via grace partitioning if the build side exceeds work_mem — watch Batches; raise memory, shrink the build side, or fix key skew.
• The optimizer's choice depends on row-count estimates — stale stats → wrong join algorithm. ANALYZE.
• Join order matters as much as algorithm; for many-table joins the planner searches orderings (and can get it wrong on skewed data).
• Sort-Merge Backtracking: High duplicate cardinality on the join key forces extensive cursor backtracking, increasing CPU time due to cache-unfriendly pointer resets.
• Theta join misread: Nested Loop on a large join may be mandatory because the predicate is not equi — rewrite to equi when possible (e.g. precompute buckets) rather than only adding indexes.

Takeaways

• Nested loop (small + indexed, or any theta join) · hash join (big equi-join) · sort-merge (sorted/ordered equi-join).
• Hash and sort-merge need equality; non-equi predicates force nested loop.
• Spill = grace/hybrid partition-to-disk, not a vague slowdown; Batches>1 is the tell.
• Nested loop on two big unindexed equi-tables = the disaster; index the join key.
• The planner chooses by cost from stats — verify with EXPLAIN, keep stats fresh.

Re-authored for this guide; hash-join diagram hand-authored as SVG. Follows CMU 15-445 and DDIA ch. 3. See also: How a Query Executes, How Indexes Work.