The idea: three ways to find matching rows
A join pairs each row of one table with the matching rows of another. Here it is SELECT * FROM orders o JOIN customers c ON c.id = o.cust_id: 8 orders, 5 customers. A database can run it in three ways, and all three return exactly the same rows. They differ in how much work they do, and which one is cheapest depends on the input: how many rows, whether they are already sorted, whether there is an index, and how much memory the join may use. The page runs all three at once on the same tables and counts the work.
The scoreboard counts work = rows read + key operations (a comparison, an index probe or a hash) + rows written to or read back from temp files. One Step moves every lane by one event, so a lane that needs fewer events finishes first and shows ✓.
Nested loop join
For each row of the outer side (orders), look at the inner side (customers). Without an index that means reading every customer for every order: 8 × 5 = 40 tests. It needs no memory and no preparation, and it works for any join condition, even < or LIKE. With an index on the inner join key (customers_pkey), each order becomes one index lookup: a few probes down the sorted keys, then one row fetch. With only two outer rows that is the cheapest plan of all (Demo: small outer + index); take the index away and it loses to hash join (Demo: small outer, no index).
Hash join
First build a hash table on the smaller side: read each customer, hash its id and put it in a bucket (here bucket = id mod 4). Then probe: read each order, hash its cust_id and compare only with the few rows in that bucket. Each table is read once, so for big unsorted inputs it wins (Demo: big unsorted tables). It only handles equality joins, and the hash table must fit in memory: PostgreSQL's work_mem (times hash_mem_multiplier), MySQL's join_buffer_size.
When it does not fit, the join splits both inputs into batches by more bits of the hash. Batch 0 is joined in memory; the rows of the other batches are written to temp files and joined afterwards, one batch at a time (Demo: work_mem too small). Every spilled row is written once and read once more.
Merge join
Put both sides in join-key order, then walk them with one pointer each. Compare the two current keys: if they are equal, output the pair and move the order pointer; otherwise move the pointer with the smaller key. Every row is passed once. If the inputs already arrive sorted, because they come from an index or a table stored in key order, there is nothing to prepare and no memory to fill, so merge join is the cheapest (Demo: both already sorted). If not, it has to sort first, and on unsorted input the sorts cost more than a hash table. Merge join also handles range conditions like a.x <= b.y, and its output is sorted, which can save a later ORDER BY.
When to pick which
| Situation | Usually cheapest | Why |
|---|---|---|
| Few outer rows, index on the inner join key | Nested loop | A handful of index lookups; the rest of the inner table is never read |
| Large unsorted inputs, equality join, enough memory | Hash join | Each table read once, one small bucket per probe |
| Both inputs already sorted on the key (index, clustered table) | Merge join | One pass, no hash table, almost no memory; output stays sorted |
| Hash table larger than work_mem | Hash join, but slower | Batches go through temp files; sorts spill too |
Non-equality condition (<, BETWEEN, LIKE) | Nested loop (or merge for ranges) | Hashing only finds equal keys |
The query planner makes this choice from estimated row counts, so a bad estimate (stale statistics) can pick a nested loop over a table that turned out to be large. EXPLAIN ANALYZE shows the method it chose; How PostgreSQL executes JOIN and How MySQL executes JOIN show the real operators on a larger example.
What the page leaves out
The page counts events, not time. Real costs also depend on page reads versus rows, random versus sequential I/O, CPU caches and parallel workers. Merge join's sort is drawn as a simple insertion sort, and a spilled sort is counted as writing and reading every row once (real external sorts merge runs, sometimes in several passes). The inner customers table has unique ids, so merge join never needs to step back over duplicate keys (mark and restore). Also left out: outer, semi and anti joins; Materialize and Memoize nodes on the inner side of a nested loop; MySQL's block nested loop and batched key access; skewed keys that overflow one hash bucket; and join order for more than two tables.