Join Algorithms: Nested Loop, Hash, Merge

You already know INNER JOIN as syntax. At senior level interviewers ask how the database physically executes a join. There are three algorithms:

• Nested Loop Join
• Hash Join
• Merge Join (sort-merge)

The logical join type (INNER, LEFT) is independent of the algorithm. The planner picks the algorithm based on table sizes, indexes, and sort order. Knowing when each wins is the heart of this lesson.

The Nested Loop is the simplest: for each row of the outer table, scan the inner table for matches. In pseudocode, two loops, one inside the other.

Naively this is O(outer * inner), terrible for big tables. But it becomes excellent when the inner side has an index on the join key: each outer row triggers a cheap index lookup instead of a full inner scan.

It is the planner's favorite when the outer table is small and the inner join column is indexed.

The giveaway of a nested loop is loops on the inner node. The example shows loops=3 because the outer side produced 3 rows, so the inner index scan ran 3 times.

The danger appears when the outer side is large. If the outer produces 2 million rows, the inner runs 2 million times. Even a fast 0.01ms lookup becomes 20 seconds.

In interviews, flag any nested loop where loops is large over an inner table without a good index, that is the slow query.

The Hash Join handles big unsorted tables well. It runs in two phases:

• Build: read the smaller table and load it into an in-memory hash table keyed on the join column.
• Probe: scan the larger table; for each row, hash the join key and look it up in the hash table.

Each table is read only once, giving roughly O(outer + inner). It needs no indexes and no sorted input, which is why it dominates large analytical joins on equality conditions.

Two things you must mention about hash joins:

• They only work for equality join conditions (a.id = b.id). A range condition like a.x < b.y cannot use a hash join.
• The build side must fit in work_mem. If it does not, Postgres spills batches to disk (you will see Batches: > 1 and disk usage), which slows the join badly.

So a hash join on a huge build side with tiny work_mem is a real-world performance bug to call out.

The Merge Join (sort-merge) requires both inputs sorted on the join key. It then walks both in lockstep, like merging two sorted lists, advancing whichever pointer is behind.

It is efficient when the inputs are already sorted, for example coming straight off an index in key order, because then no sort step is needed. It also supports range and inequality joins, unlike hash join.

If the inputs are not pre-sorted, the planner adds explicit Sort nodes, and that sort cost may make hash join cheaper instead.

Memorize when each algorithm wins:

• Nested Loop, small outer table and an indexed inner join key; also the only option for non-equality joins without sorted input.
• Hash Join, large unsorted tables joined on equality; no indexes needed.
• Merge Join, both inputs already sorted on the key (often via indexes), or for range joins; great for very large pre-sorted sets.

The planner estimates the cost of each and picks the cheapest given its row estimates.

Resource use differs sharply and interviewers probe this:

• Nested Loop, minimal memory; cost dominated by repeated inner lookups.
• Hash Join, needs memory for the hash table; spills to disk if too big.
• Merge Join, cheap to merge but expensive if it must sort first; sorts also use work_mem and can spill.

So tuning work_mem upward can flip a slow disk-spilling hash or sort into an in-memory one, a concrete optimization answer.

Classic scenario: a query was fast in dev, slow in prod. The plan shows a Nested Loop with loops=3000000.

The planner underestimated the outer row count (stale stats said 3 rows, reality is 3 million), so it chose a nested loop. With accurate stats it would have chosen a hash join.

Your interview answer: run ANALYZE so the estimate is correct; the planner will then switch to a hash join and the query speeds up dramatically.

You usually should not force algorithms, but you can in testing to compare. Postgres exposes per-method toggles:

SET enable_nestloop = off; and similar for enable_hashjoin and enable_mergejoin. Flip one off, re-run EXPLAIN ANALYZE, and observe whether the alternative is actually faster.

The proper fixes remain: fresh statistics, the right indexes, adequate work_mem, and selective predicates. Forcing is for diagnosis only.

Put it together for an analytics workload joining two large fact and dimension tables on an id:

• If the dimension fits in memory, expect a Hash Join, often the best.
• If both arrive sorted from indexes, a Merge Join can avoid the hash build.
• A Nested Loop here would be a red flag, usually caused by a bad estimate.

Reading which one the planner chose, and judging whether it should have, is exactly the senior signal these questions test.

You join two large unsorted tables on an equality condition a.id = b.id, neither has a useful index, and statistics are accurate. Which join algorithm will the planner most likely choose?

The three join algorithms:

• Nested Loop, outer row times inner lookup; great with a small outer and an indexed inner key, dangerous when loops is huge.
• Hash Join, build-and-probe; best for large unsorted equality joins, limited to equality and bounded by work_mem.
• Merge Join, lockstep over sorted inputs; ideal when data is already sorted or for range joins.

The planner picks by cost and statistics. A surprising nested loop with massive loops almost always means a bad row estimate, fix the stats.