Three Join Algorithms, and When Each Wins

How should a database join 50 million orders to 10 million users — and why is there more than one algorithm for it?

There are three join algorithms because the cheapest way to combine two tables depends on their sizes, available indexes, and whether the inputs are already sorted — the planner picks by cost, the same pages-and-random-I/O reasoning as a single-table scan.

Take orders (50M) JOIN users (10M) ON orders.user_id = users.id.

Nested loop: fine when the outer side is tiny

The brute-force nested loop join is: for each of the 50M orders, find its user. If that lookup is a full scan of 10M users, the total is 50M × 10M = 5×10¹⁴ comparisons — catastrophic.

Put a B-tree index on users.id and each lookup drops to ~4 page reads: the indexed nested loop join. Total ≈ 50M × 4 = 200M reads — dramatically better, but still 200M scattered index descents. So it’s the right choice only when the outer side is small or heavily filtered (1,000 orders → 4,000 reads, trivial), not when it’s all 50M rows.

Hash join: the default for two large tables

Read each table once. In the build phase, load the smaller table into an in-memory hash table keyed on the join column. In the probe phase, stream the larger table through, doing an O(1) lookup per row. Two sequential scans, no repeated index descents.

Gotcha — build on the smaller table. The hash table must fit in RAM, so build on users (10M), not orders (50M) — same result, 5× less memory. If even the smaller side exceeds RAM, the hash spills to disk (grace/hybrid hash join) and you pay I/O again.

Merge join: when both inputs are already sorted

If both tables are already sorted on the join key — e.g. read through a B-tree on that key — walk them together in a single simultaneous pass, advancing whichever cursor is behind. Almost no memory. It’s the exact “merge two sorted runs” move from LSM compaction. It wins when both tables are large, both sorted, and too big to hash comfortably.

Algorithm	How it works	Cost driver	Best when
Indexed nested loop	Probe inner index once per outer row	~4 reads × outer rows	Outer side small or filtered
Hash join	Build hash on smaller, probe with larger	Build side must fit in RAM	Two big tables, enough RAM
Merge join	Walk two sorted inputs in one pass	Inputs must be sorted on the key	Both big, both already sorted

⚠ Common misconception: "one join algorithm is simply the fastest." No single algorithm wins everywhere — a small, filtered outer side with an index beats a hash join, while two huge unsorted tables beat nested loop. The planner chooses by estimated cost, per query.

Recall checkpoint

1. Why build the hash on the smaller table? The hash table lives in RAM; the smaller input uses less memory and is likelier to fit without spilling to disk.

2. What must be true for a merge join to be cheap? Both inputs must already be sorted on the join key, so they can be walked together in one pass.

TL;DR

Indexed nested loop — ~4 reads per outer row; great for a small/filtered outer side, terrible at scale (50M × 4 = 200M scattered reads).
Hash join — read each table once; build a hash on the smaller input, probe with the larger; spills to disk if the build side exceeds RAM.
Merge join — one simultaneous pass over two inputs already sorted on the key; almost no memory.
The planner picks by cost from table sizes, indexes, and sort order — there is no universally best join.