What happens when you JOIN two tables?

JOIN is where SQL stops being a table operation and becomes an algorithm problem: the database must find matching pairs between two sets, and the choices it makes — which side first, which method — change the runtime by orders of magnitude on the same query. There are three canonical algorithms, one planner decision, and a memory limit that decides which of them spills to disk.

Step 1 — the planner's choice

For users JOIN orders ON users.id = orders.user_id, the planner first orders the joins (cheapest pair first, smallest-first hash builds, order explosion capped by join_collapse_limit), then for each pair picks a method from its cost model: nested loop, hash join, or merge join. The statistics that matter: relation sizes (reltuples), distinct values (n_distinct — huge for IDs, tiny for status), and work_mem (default 4MB), which determines whether the hash build fits in RAM.

Step 2 — hash join: build

The hash join's bet: hash the smaller side into a hash table in memory, then stream the larger side through it — O(n + m) with one pass over each input, no sorting, no index required.

Build: read all of users (or the filtered subset), compute hash(user_id) for each row, insert into a hash table in memory. Cost: one full read of the build side, ~µs per row, bounded by work_mem (4MB ≈ ~100k typical rows — its estimate of build size decides whether hash join is even chosen).
The build is where hash joins differ from intuition: it costs a full read of the smaller table before any output.

Step 3 — hash join: probe

Stream orders, compute hash(order.user_id), look up the bucket, and for each hash-table hit, compare the actual key (hash collisions are handled by equality checks — bucket chains). Matching pairs are emitted immediately. The probe is ~100-200ns per row in RAM. Total: two linear scans and a hash table. This is why hash joins are the workhorse for large, unindexed joins — no index, no sort, just memory.

Step 4 — the spill

The build side doesn't fit in work_mem? The hash join spills: both sides are partitioned by hash into temp files (the hash is "batched"), and the join runs one bucket at a time — reading bucket files back. This is a double read of both inputs and the single biggest join performance cliff: a join that fits in 4MB runs at RAM speed; one that needs 400MB runs at disk speed, and the planner's row estimate decides which reality you get. Raising work_mem (or hash_mem_multiplier) is the standard fix — with the standard warning that it's per-operation and multiplies across concurrent queries.

Step 5 — nested loop

The planner's other bet: for each row of the outer input, find matches in the inner input via an index (without one it's a quadratic cross-product, chosen only for tiny inputs). EXPLAIN shows the pattern:

plaintext

Nested Loop  (cost=0.56..4123.45 rows=90211 width=...)
  ->  Seq Scan on users
  ->  Index Scan using orders_user_id_idx on orders
        Index Cond: (user_id = users.id)

Per outer row: one index descent (~3-5 page fetches, ~5-20µs warm). For a 10k-row outer that's 10k probes — fast when warm, brutal when cold. Nested loops win when: the outer is small, the inner is indexed, and the join is selective — the classic "fetch this user's orders" shape. They lose when the outer is large and the index is cold: the probe cost per row doesn't amortize.

Step 6 — merge join

Both inputs sorted by the join key (by index order or explicit sort): walk both in lockstep, advancing the smaller key. One pass, no hash memory — O(n + m) but with the sort tax included. The planner picks it when sorted inputs already exist (an index provides order for free) or the output needs sorting anyway (the same sort serves ORDER BY). Hash joins destroy order; merge joins preserve it.

Step 7 — the sort tax

When the planner needs a sort and none exists, the executor runs an external sort: in-memory runs up to work_mem, then merge passes to temp files (in base/pgsql_tmp). A 10GB sort with 4MB work_mem is a different query than the same sort with 1GB — and both appear identically in SQL.

What it costs

Hash join in RAM: ~200-500ns per matched pair, linear scans.
Hash join spilled: disk-speed — 10-100x slower, dominated by temp file I/O.
Nested loop: outer × (probe cost); warm index probe ~5-20µs, cold ~100µs-1ms.
Merge join: scan costs + any sort; sort of N rows ≈ N log N comparisons plus spill I/O.

sql

EXPLAIN (ANALYZE, BUFFERS) SELECT ... FROM users JOIN orders ON ...;
 Hash Join  (cost=225.20..5120.00 rows=90211) (actual time=4.1..312.2 rows=90211)
   Hash Cond: (orders.user_id = users.id)
   ->  Seq Scan on orders  (actual time=0.01..180.4 rows=1.2M)
   ->  Hash  (actual time=3.9..3.9 rows=10k)
         Buckets: 16384  Batches: 1  Memory Usage: 512kB

The plan tells the whole story: 16k buckets, 1 batch, 512kB — everything fit in memory, one pass each side, 312ms for 90k matches out of 1.2M probes. When you see Batches: 8 and Memory Usage: 512kB (the spill warning), you've found the cliff: the same query, unbatched, is usually 10x faster. Join performance is decided by exactly three numbers — build size vs work_mem, index warmth, and selectivity.