The three join algorithms
Nested loop, hash and merge. Each wins somewhere, and the plan tells you which one you got and what it cost.
12 min · runs against the shop dataset
A *nested loop* reads the inner side once per outer row. It is the only algorithm that works with any join condition at all, and it is the right answer when the outer side is tiny or the inner side has an index to seek into. It is catastrophic when neither is true — and loops= in the plan is exactly how many times it happened.
An inequality, so nothing can be hashed. Look at the loops.
plan
| node | est | actual | loops | pages | share |
|---|---|---|---|---|---|
| Nested LoopJoin Filter: (o.customer_id > c.id)Rows Removed by Filter: 1,225 | 720 | 935 | 1 | 0 | |
| → Seq Scan on c | 24 | 24 | 1 | 1 | |
| → Seq Scan on o | 90 | 90 | 24 | 24 |
A *hash join* builds a table from one side and probes it once with the other — one pass over each. It needs an equality to hash on, and memory proportional to the side it builds. Past work_mem it partitions to disk and processes the join in batches, and the plan says how many.
An equality, so it hashes. One pass over each side.
plan
| node | est | actual | loops | pages | share |
|---|---|---|---|---|---|
| Hash JoinHash Cond: (c.id = o.customer_id)Buckets: 20 Batches: 1 Memory Usage: 12kB | 24 | 903.8x over | 1 | 0 | |
| → Seq Scan on c | 24 | 24 | 1 | 1 | |
| → Hash | 90 | 90 | 1 | 0 | |
| → Seq Scan on o | 90 | 90 | 1 | 1 |
A *merge join* walks both sides in step, which requires both to arrive sorted. It wins when they already are — under an index, or below a sort someone was going to pay for anyway — and loses when they are not, because two sorts to save one hash table is a bad trade.
Did it land?
- Give it something to hash
Return each customer's name alongside their order totals, ordered by name then total. Only customers who have orders. Two columns: name and total.