Join Algorithms — Nested Loop, Hash & Sort-Merge
Three ways to combine two tables
A JOIN isn't one operation — the optimizer picks one of three algorithms based on table
sizes, indexes, and whether sorted output is needed. Knowing them turns a mysterious slow join into an obvious
"wrong algorithm / missing index" diagnosis.
The three algorithms
| Algorithm | How it works | Cost | Chosen when |
|---|---|---|---|
| Nested loop | for each row in A, find matches in B | O(A×B), or O(A×log B) with an index on B | A is small and B has an index on the join key |
| Hash join | build a hash table on the smaller side's key, probe with the larger | O(A+B), needs memory | large equi-join, no useful index, order not needed |
| Sort-merge join | sort both by the join key, then merge in one pass | O(A log A + B log B), or O(A+B) if pre-sorted | inputs already sorted (an index), or sorted output wanted |
The trap to recognise in EXPLAIN
A Nested Loop over two large tables with no index on the join key is the classic catastrophe — millions × millions. The fix is almost always: add an index on the join column, or let the planner pick a hash join (check your stats are fresh).
EXPLAIN ANALYZE SELECT * FROM orders o JOIN users u ON o.user_id = u.id;
-- Hash Join (hash table on users; probe with orders) <- good for big o, small u
-- vs Nested Loop -> Index Scan on users_pkey <- good when o is small
-- vs Merge Join (both already ordered by the join key)Pitfalls
- Hash join spills to disk if the build side exceeds
work_mem— slow; raise memory or reduce the build side. - The optimizer's choice depends on row-count estimates — stale stats → wrong join
algorithm.
ANALYZE. - Join order matters as much as algorithm; for many-table joins the planner searches orderings (and can get it wrong on skewed data).
Takeaways
- Nested loop (small + indexed) · hash join (big equi-join) · sort-merge (sorted/ordered output).
- Nested loop on two big unindexed tables = the disaster; index the join key.
- The planner chooses by cost from stats — verify with
EXPLAIN, keep stats fresh.
Re-authored for this guide; hash-join diagram hand-authored as SVG. Follows CMU 15-445 and DDIA ch. 3. See also: How a Query Executes, How Indexes Work.
🤖 Don't fully get this? Learn it with Claude
Stuck on Join Algorithms — Nested Loop, Hash & Sort-Merge? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
🎨 Explain it visually
Build the mental picture, not memorization.
I just read a lesson on **Join Algorithms — Nested Loop, Hash & Sort-Merge** (Databases) and want to truly understand it. Explain Join Algorithms — Nested Loop, Hash & Sort-Merge from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)
Socratic — adapts to where you're stuck.
Teach me **Join Algorithms — Nested Loop, Hash & Sort-Merge** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps
Active recall exposes what you missed.
Quiz me on **Join Algorithms — Nested Loop, Hash & Sort-Merge** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick
Intuition + hook + flashcards for long-term memory.
Help me remember **Join Algorithms — Nested Loop, Hash & Sort-Merge** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.