How a database runs a join: nested loop, hash join, merge join
A database has three main ways to run a join. A nested loop looks up matches in the other table for each row of one. A hash join builds a hash table from one side and probes it with the other. A merge join walks two sorted inputs together. The optimiser picks one for each join.
Why it matters
In senior interviews you may be asked why a join is slow or what a plan line like "Hash Join" means. Knowing the three methods tells you which index or memory setting will help.
The idea
Nested loop: for each row of the outer table, find the matching rows in the inner table. It is fast when the outer side is small and the inner side has an index on the join key (that is what SQLite did in the last lesson).
Hash join: read the smaller table into a hash table keyed on the join column, then stream the bigger table past it, checking each row. It is great for big equality joins with no index, but it needs memory.
Merge join: if both sides are sorted on the key (by an index, or by sorting first), walk them side by side, like closing a zip. It is good for big inputs that are already in order.
Matching wedding guests to tables. Nested loop: take each guest and look their name up in the seating plan. Hash join: first make a quick lookup card per surname, then let every guest find their card. Merge join: line up the guests alphabetically and the seating list alphabetically, then walk down both together.
At a wedding you would pick the method by eye. A database picks it from estimates of how many rows each side has — wrong estimates are the main reason it picks badly.
How it works
- Nested loop: outer has N rows, and each inner lookup is an index search, so the cost is about N × log(M). Bad if there is no index on the inner side: N × M.
- Hash join: build a hash table on the smaller input (one pass), probe it with the larger (one pass): about N + M, using memory.
- Merge join: if both inputs are already sorted, one pass over each: about N + M; otherwise a sort first.
- Equality joins can use any method; only nested loops handle conditions like
a.x < b.y. - You influence the choice through indexes, statistics and (in PostgreSQL) memory settings like work_mem.
Key points
- Nested loop: best for a small outer input with an index on the inner join key.
- Hash join: best for large, unsorted equality joins; needs memory for the hash table.
- Merge join: best when both inputs are already sorted on the join key.
- The optimiser chooses using row-count estimates; stale statistics cause bad choices.
- Indexing join keys (especially foreign keys) is the single most useful join optimisation.
Common mistakes
- Thinking an index always makes a join faster: for a hash join over whole tables it may not be used at all.
- Ignoring a nested loop over two large tables without an index — it grows as N × M.
- Forcing a join method with hints instead of fixing the statistics or indexes.
Not true: An index on the join column speeds up a hash join over whole tables.
In fact: A hash join that reads whole tables may not use the index at all. An index helps most when only a few rows are looked up, as in a nested loop.
In the interview
There are three main physical join algorithms. Nested loop iterates the outer input and looks up matches in the inner — ideal when the outer side is small and the inner join key is indexed. Hash join builds an in-memory hash table on the smaller input and probes it with the larger — ideal for big equality joins without useful indexes. Merge join walks two inputs sorted on the key. The optimiser chooses based on estimated cardinalities, so bad statistics are a common cause of a poor join plan.
Part of Unit 7: Performance: indexes and query plans in the free SQL course.