What are the three join algorithms in PostgreSQL and when does the planner choose each?
Nested Loop probes the inner side once per outer row and suits small inputs or indexed lookups. Hash Join builds a hash table of one side and suits large unsorted equality joins. Merge Join walks two sorted inputs and suits large sorted ones.
Explain it simply
Matching exam hall tickets against a student list can be done three ways.
Nested Loop: for each ticket, search the list. Fine if there are 5 tickets, or if the list is indexed by roll number. Hash Join: first put the whole list in a lookup board by roll number, then scan tickets once. Good for big, unsorted inputs. Merge Join: if both piles are already sorted by roll number, walk down both together like closing a zipper.
Example
EXPLAIN
SELECT s.name, m.marks
FROM students s JOIN marks m ON m.student_id = s.id
WHERE s.id = 42;
-- Nested Loop
-- -> Index Scan on students (id = 42)
-- -> Index Scan on marks (student_id = 42)
EXPLAIN
SELECT s.name, m.marks
FROM students s JOIN marks m ON m.student_id = s.id;
-- Hash Join
-- Hash Cond: (m.student_id = s.id)
-- -> Seq Scan on marks
-- -> Hash -> Seq Scan on studentsHash Join needs memory (work_mem); if the hash table does not fit, it spills to disk in batches, which shows up as Batches: 4 or more.
What to say in the interview
"Nested Loop wins for few rows or an indexed inner side, Hash Join for large equality joins, Merge Join when both sides arrive sorted. If a plan picks a bad one, I check row estimates first, since that is usually the cause."
Common mistakes
- Assuming Nested Loop is always bad; it is ideal for small indexed lookups.