Join Algorithms — Nested Loop, Hash Join & Merge Join

Materialize and Memoize — caching under a nested loop

Two plan nodes appear under nested loops to make the rescanning cheaper. Materialize caches the inner relation's rows once, so later iterations read from memory instead of re-running the scan. Memoize (Postgres 14 and later) caches results per parameter value, so a repeated outer value skips the inner scan entirely.

Memoize is the planner applying the same fix an application developer would apply to an N+1 problem: remember the answer for a repeated key. It pays off when outer values repeat often. The nested loop above is structurally identical to the application-level N+1 antipattern — fetch a list, then issue one lookup per element. The difference is entirely about where the loop runs.

Same loop, three orders of magnitude apart. That gap is why "push the join into the database" is advice, not dogma.

The row-estimate cliff

The planner's algorithm choice is only as good as its estimate of how many rows each side produces. Get that wrong, and the choice inverts from optimal to catastrophic.

Nested Loop  (cost=... rows=5 ...) (actual time=... rows=500000 ...)
                          ^^^^^^                          ^^^^^^^^^^
                        estimate                            reality

Batches > 1 has two causes, not one

A spilling hash join is a signal to investigate, not a diagnosis. It has two distinct causes with opposite fixes:

1. work_mem is genuinely too small for the workload.
2. The row estimate was wrong. The planner sized the hash table for the rows it expected; if it expected 10,000 and 4 million arrived, the table overflows regardless of how reasonable work_mem is.

Check the estimated-versus-actual row count on the build side before changing any configuration — otherwise memory gets tuned forever on what is really a statistics problem. And note that work_mem is granted per operation, per session, not per transaction: one query with three hash joins and two sorts can hold five separate grants at once, so the real multiplier is connections × operations-per-query.

Capability limit, not fallback

A hash table can only answer "which rows have exactly this key?" It cannot answer "which rows have a key less than this one?" A join condition using <, >, BETWEEN, or a range overlap is not hashable, so nested loop and merge join are the only options for a range join. When the planner picks one of them for a range condition, it has not degraded to a fallback — a hash join was never a candidate.

Postgres makes this explicit for one join type. A FULL OUTER JOIN has no cheap way, under a nested loop, to identify inner rows that never matched anything, so the condition must be hash-joinable or merge-joinable:

-- ERROR: FULL JOIN is only supported with merge-joinable or hash-joinable join conditions
FROM a FULL JOIN b ON a.x < b.y

An error that looks arbitrary becomes obvious once the capability limits of each algorithm are known.

What you actually control

The algorithm is not something to choose directly. It is a decision to shape by controlling the conditions the planner reasons about.

SET enable_nestloop = off;   -- "fixes" the one slow query...
-- ...and now discourages nested loops for every other query on this connection too.

A separate decision: join order and GEQO

The cost-based approach itself dates to Selinger et al.'s 1979 System R paper, which established the model every mainstream planner still uses: enumerate the plans, estimate a cost for each, pick the cheapest.

Choosing an algorithm for one join is not the whole problem. With N tables, the planner must also choose the order to combine them, and the number of possible orderings grows factorially. Below geqo_threshold (default 12 relations), Postgres runs a near-exhaustive search and prefers pairs of relations that share a WHERE join clause. Above the threshold, it switches to a genetic algorithm, and the search becomes heuristic.

Two consequences follow. Below the threshold, the order tables are written in does not matter — the planner reorders freely, so "smallest first" is folklore, not a rule. Above the threshold, planning becomes heuristic and non-deterministic, so a 15-way ORM-generated join can produce a different plan on different runs — the first thing to check when such a query has unstable performance.

Cost constants

The planner converts everything to one abstract unit, anchored on a sequential page read.

The 4:1 ratio between random and sequential access encodes a spinning disk. On SSDs that penalty is too high; lowering random_page_cost to roughly 1.1 is the standard adjustment, and it makes index scans — and therefore indexed nested loops — look correctly cheap.

Reading it in EXPLAIN

Everything above surfaces as three node names and a handful of numbers.

Hash Join
  Hash Cond: (t.merchant_id = m.merchant_id)
  ->  Seq Scan on transactions t   -- probe side
  ->  Hash
        Buckets: 1024  Batches: 1  Memory Usage: 40kB    -- Batches: 1 = healthy
        ->  Seq Scan on merchants m                      -- build side

1. Which of the three node names is it — Nested Loop, Hash Join, or Merge Join?
2. Does the estimated rows= match the actual rows=? A large gap is the root cause of most bad joins.
3. On a hash join, what does Batches: say? Above 1 means it spilled.
4. Under a merge join, is there a Sort node or an Index Scan? A sort means an index could remove it.
5. On a nested loop, is the inner side an Index Scan or a Seq Scan? A sequential scan on the inner side of a nested loop over a large outer relation is an emergency signal.