Internals · Query Enginejoinnested loophash joinmerge joinbuild

Join Algorithms: Nested Loop, Hash, Merge

Three ways to pair rows from two inputs: loop over both (quadratic, needs nothing), hash one and probe with the other (linear, needs memory), or sort both and walk two cursors (linear after the sort, needs order). The planner picks by input sizes, available indexes and memory.

▶ Interactive Try queries Interview question

Progress

Why this exists

The mechanism as the answer to a problem — read this before the name.

Problem
orders JOIN users ON users.id = orders.user_id: for each of 3,200 orders find the one matching user among 900. Naively that is 3,200 × 900 = 2.9 million comparisons for 3,200 results.
↓
Naive solution
Nested loop: for each order, scan all users and compare ids.
↓
Why it breaks
The work is outer × inner. At a million orders and a million users that is 10¹² comparisons. The inner table is rescanned once per outer row, and its pages are re-read from the buffer pool every time.
↓
Better idea
Stop scanning the inner side. Either make the inner lookup O(1) (a hash table on the join key), O(log n) (an index), or make both sides sorted so one pass over each suffices.
↓
Internal mechanism
Hash join: build a hash table from the smaller input, then probe it once per row of the larger — linear in both. Merge join: sort both inputs on the key, then advance two cursors, emitting on equality — linear after the sort, output already ordered. Index nested loop: the inner scan becomes a B-tree descent — outer × log(inner).
↓
Trade-offs
Hash needs memory for the build side and an equality condition; if the build side exceeds work_mem it is batched to disk. Merge needs sorted inputs, which cost n log n unless an index provides them. Nested loop needs nothing and is the only option for non-equality joins.
↓
Real database
PostgreSQL implements all three (nodeNestloop.c, nodeHashjoin.c, nodeMergejoin.c) and costs each per join. MySQL/InnoDB historically had only nested loop (block nested loop with an index) and added hash join in 8.0.18. This platform’s engine uses a hash join for equality conditions and a nested loop otherwise.

Choose your depth

The same mechanism at four altitudes. Start where you are; come back deeper.

Three shapes of pairing

A join has to find, for rows on one side, the matching rows on the other. You can look for each one by scanning (nested loop), look each one up in a hash table (hash join), or line both sides up in order and walk them together (merge join).

The result is the same; the work differs by orders of magnitude, and the planner chooses per join.

Nested loop

The simplest join is two loops. For each row of the outer input, scan the inner input and emit every pair that satisfies the condition. It needs no memory beyond one outer row, no sorting, no equality — any predicate works, which makes it the only algorithm for a.x < b.y, a.name LIKE b.pattern or a cross join. Its cost is outer_rows × inner_cost, and when the inner is a full scan that is quadratic: 6 × 8 = 48 comparisons for the interactive’s toy tables, 10¹² for a million × a million.

The index nested loop is the same outer loop with a different inner: instead of scanning, descend a B-tree on the inner’s join key. The inner cost becomes height × random_page + 1 heap read — five or six page reads — and the join is outer_rows × log(inner_rows). For a small outer side (the ten orders on a page) joined to a large indexed table (users by primary key) this is the fastest join there is, and it is the shape of nearly every OLTP join. The plan shows it as Nested Loop with an Index Scan child whose loops equals the outer row count.

Nested loop and index nested loop

NESTED LOOP                              INDEX NESTED LOOP
for each row a in outer:                 for each row a in outer:
  for each row b in inner:                 for each b in index_lookup(inner, a.key):   -- B-tree descent
    if a.key = b.key: emit (a, b)            emit (a, b)

cost  = outer_cost + outer_rows × inner_scan_cost          cost = outer_cost + outer_rows × (height × 4.0 + 2.4)
       6 × 8   →     48 comparisons                               6 × 2   →  12 comparisons
       1M × 1M →  10¹² comparisons (never)                        1M × 3  →  ~14 M cost units

Hash join

Replace the inner scan with a lookup. Build: read the smaller input once and insert each row into an in-memory hash table keyed on the join column — the Hash Table from DSA, with chaining for duplicate keys. Probe: read the larger input once; for each row hash its key, jump to the bucket, compare against the few entries there, emit matches. Each side is read exactly once, so the join is linear: build_rows + probe_rows plus the two scans. For a million × a million it is roughly 30,000 cost units against 14 million for the index nested loop.

The conditions: an equality join predicate (hashing a.x < b.y is meaningless), and memory for the build side. PostgreSQL chooses the smaller input to build from; this platform’s engine always builds on the right-hand input, which is why its Hash node hangs under the second table. When the build side does not fit in work_mem, both inputs are partitioned by hash into batches on disk and joined batch by batch — every row written and read once more, visible as Batches: N and a jump in time. A hash join that spills is still usually better than a nested loop; it is just no longer the one-pass join the estimate promised.

Hash join: build then probe

-- build (smaller input: users, 8 rows)
H = {}
for each row b in inner:
  H[hash(b.id)].append(b)                 -- 8 inserts, 8 entries in memory

-- probe (larger input: orders, 6 rows)
for each row a in outer:
  for each b in H[hash(a.user_id)]:       -- one bucket, usually one entry
    if a.user_id = b.id: emit (a, b)      -- 6 probes, 5 matches

cost = outer_cost + inner_cost + inner_rows × (0.01 + 0.0025) + outer_rows × (0.01 + 0.005)
       1M × 1M → ~65,000 cost units, one pass each side
memory = build side; if > work_mem → partition both sides into batches on disk (Grace hash join)

Merge join

If both inputs are sorted on the join key, they can be joined in one pass with two cursors — the merge step of Merge Sort, and the Two Pointers (Same Direction) pattern exactly. Compare the keys under the cursors: if equal, emit the pair; if the outer key is smaller, advance the outer cursor (nothing further in the inner can match it); otherwise advance the inner. Because the inner key may repeat, the inner position is marked at the first match and rewound when the next outer row has the same key. Every row is read once, memory is one row per side, and the output is already ordered by the key.

The catch is the sort. If the inputs are not already ordered, each needs an n log n sort first — and a sort of a million rows costs about as much as the hash join’s entire work. Merge join wins when the order is free: both sides read from B+ tree indexes on the join columns (leaf order *is* key order), or one side sorted by a previous operator, or the query’s ORDER BY needs the same order anyway so the sort is paid once and reused. The planner tracks these “interesting orderings” precisely so it can find such cases.

Merge join over two sorted inputs

sort outer by key   (or read from an index in key order)
sort inner by key
i = 0; j = 0
while i < |outer| and j < |inner|:
  if outer[i].key = inner[j].key:  emit (outer[i], inner[j]); i++        -- (rewind j for repeated inner keys)
  elif outer[i].key < inner[j].key: i++                                  -- outer is behind: advance it
  else:                             j++                                  -- inner is behind: advance it

comparisons ≤ |outer| + |inner|   →   6 + 8 = 14 here, 2 M for 1M × 1M
cost = sort(outer) + sort(inner) + (outer + inner) × 0.0025    → sorts dominate unless an index supplies the order
output: sorted by key — reusable by ORDER BY / GROUP BY above

When the planner picks which

The choice is made per join by cost, but the pattern is stable enough to state. Index nested loop when the outer side is small — a handful to a few thousand rows — and the inner has an index on the join key: the lookup join of every transactional query. Hash join when both inputs are large, the condition is an equality, and the smaller side fits in memory: the default for reporting and analytics. Merge join when both inputs arrive sorted or the output must be sorted anyway, or when the build side is too large to hash comfortably. Plain nested loop when the outer side is tiny, or when the condition is not an equality and nothing else applies.

Two things flip these decisions in practice. Row estimates: a nested loop chosen for “10 outer rows” that turn out to be 100,000 runs the inner index scan 100,000 times — the loops column in EXPLAIN ANALYZE is where to look. And memory: a hash join costed for an in-memory build that spills into eight batches may lose to the merge join it beat on paper. The interview question on join algorithms (linked below) asks for exactly this reasoning.

The three algorithms compared (index nested loop shown separately)

	Nested loop	Index nested loop	Hash join	Merge join
Complexity	O(outer × inner) — quadratic	O(outer × log inner)	O(outer + inner) — linear	O(outer + inner) after sorting; sort is O(n log n)
Needs	nothing	index on inner join key	equality condition, memory for build side	both inputs sorted on the key
Memory	one outer row — tiny	one outer row — tiny	build side (spills to batches if > work_mem)	one row per side (sorts may spill)
Condition types	any (<, LIKE, cross)	equality / range on the index	equality only	equality (sortable types)
Output order	outer order	outer order	none	sorted by join key
Best when	outer tiny, or no equality	outer small, inner large and indexed — OLTP	both large, unsorted — analytics	inputs already sorted, or order needed above
Worst when	both large — never finishes	outer large — millions of random reads	build side exceeds memory — spills	inputs unsorted — two full sorts

Key points

Nested loop: outer × inner, needs nothing, handles any condition; with an index on the inner key it becomes outer × log(inner) and is the OLTP lookup join.
Hash join: build a hash table from the smaller side, probe with the larger — linear, equality only, needs the build side in work_mem or it batches to disk.
Merge join: two cursors over sorted inputs — linear after the sort, output ordered by the key; wins when indexes or an earlier sort supply the order for free.
The planner picks per join by estimated cost; wrong row estimates and memory limits are what make it pick wrong.
In EXPLAIN ANALYZE: loops on the inner node exposes a nested loop that ran too often; Batches > 1 exposes a hash join that spilled.

Nested loop, hash join, merge join

orders (6 rows) ⋈ users (8 rows) ON orders.user_id = users.id. Same result, four algorithms — count what each one touches.

orders (outer)

order 101 · user 3
order 102 · user 7
order 103 · user 1
order 104 · user 3
order 105 · user 9
order 106 · user 5

Nested loop: for each outer row, scan every inner row and test the join condition. No setup, no memory — and no way to skip anything.

No auxiliary structure: the inner table is simply rescanned for every outer row.

comparisons

rows read

memory (rows)

output rows

step

1/56

Output so far

—

users (inner)

user 1 · Ada
user 2 · Bo
user 3 · Cy
user 4 · Di
user 5 · Ed
user 6 · Fu
user 7 · Gil
user 8 · Hal

Estimated cost with the engine's helpers — this input, and one million × one million

Algorithm	Formula	6 × 8 rows	1M × 1M rows	Planner picks it when
Nested loop	outer × (full inner scan)	7.54	17813.0M	the outer side is tiny, or there is no equality to hash on (cross joins, inequalities)
Index nested loop	outer × (B-tree descent + 1 heap read)	39.55	14.4M	the outer side is small and the inner has an index on the join key — the OLTP lookup join
Hash join	scan both + build + probe	2.33	63,126	an equality join between large inputs and the build side fits in work_mem — the default for analytics
Merge join	sort both + one merge pass	2.37	239,942	both inputs are already sorted (index order, previous sort) or the output must be sorted anyway

Steps and counters are a simulation over two tiny tables. The cost columns use this repo's seqScanCost / indexScanCost / hashJoinCost / nestedLoopCost; the merge-join cost is modelled as two sorts plus one pass.

1/56

Try it in the playground

EXPLAIN ANALYZE
SELECT o.id, u.name
FROM orders o JOIN users u ON u.id = o.user_id
WHERE o.total > 3000;

Equality condition → Hash Join: users hashed once, orders probe. →

EXPLAIN ANALYZE
SELECT a.name, b.name
FROM users a JOIN users b ON b.country = a.country AND b.id > a.id
WHERE a.city = 'Berlin' AND b.city = 'Berlin';

A hash join on the equality, with the inequality as a residual filter. →

EXPLAIN ANALYZE
SELECT u.id, u.name
FROM users u
WHERE EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id AND o.total > 3000);

When to use — and when not

Use it when

Index nested loop fits point lookups joining a few rows to a big table; hash join fits large equality joins with memory to spare; merge join fits pre-sorted inputs and joins whose result must be ordered.

Avoid it when

A hash join does not fit non-equality conditions or a build side that cannot fit in memory; a merge join does not fit unsorted inputs without an index; a plain nested loop does not fit two large inputs.

Failure modes

Nested loop over a large outer side because the planner estimated it small — loops=1,000,000 on the inner index scan.
Hash join build side larger than work_mem: Batches: 16, temp files, a query that was fast in staging.
A join with no equality condition (ON a.id <> b.id, or a forgotten ON): the only option is a cross-product nested loop.
Expecting a hash join’s output to be ordered; it is not, and a Sort appears above it.
Building the hash table on the larger side (engines without side selection, or a misestimate): memory blows up on the wrong input.