Databases & Storage · core
Join Algorithms
Nested-loop, hash, and merge joins — and why cardinality estimates decide which one you get.
Mental model
Three strategies with different shapes: nested-loop wins when one side is tiny or an index makes lookups cheap, hash join wins on large unsorted equijoins if the build side fits in memory, merge join wins when both inputs already arrive sorted. The planner picks using estimated row counts, which is why join performance collapses on bad statistics — a cardinality estimate off by 100x picks a nested loop over a hash join and turns seconds into hours.
How to study Join Algorithms
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use the linked roadmap and primary implementation references to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Join Algorithms with Secondary Indexes, Columnar Storage. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Pick the join the planner should pick and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
The single most common source of a query that was fast in staging and unusable in production.
Common mistakes
- Blaming the join when the real problem is a stale or missing statistic feeding the estimate
- Assuming hash join is always fastest; it degrades badly when the build side spills to disk
- Reading EXPLAIN's estimated rows as measured rows — run EXPLAIN ANALYZE to see both
- Adding an index to fix a join without checking whether the planner will actually choose it
Learn from primary sources
Use the linked roadmap context and practice prompt.
Practice and explain it back
Pick the join the planner should pick
Implement chooseJoin({ leftRows, rightRows, leftSorted, rightSorted, hasIndexOnRight, memoryRows }) returning 'nested-loop', 'hash', or 'merge'. Rules: if both inputs are already sorted on the key, merge. Otherwise if the smaller side exceeds memoryRows, fall back to merge (hash would spill). Otherwise if the right side has an index and the left is small (<= 100 rows), nested-loop. Otherwise hash.
Expected evidence: chooseJoin({leftRows:10,rightRows:1e6,leftSorted:false,rightSorted:false,hasIndexOnRight:true,memoryRows:1e5}) -> 'nested-loop'
Open the interactive drill →Review prompts
- A query was fast in staging and unusable in production with the same plan shape. Why do cardinality estimates explain this more often than the join algorithm itself?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.