Join Strategies

Postgres has exactly three ways to join two relations, and each one owns a different regime. A nested loop is unbeatable when one side is a handful of rows and the other has a matching index. A hash join owns the case where both sides are large and neither is usefully sorted. A merge join wins when both inputs already arrive in order. There is no fourth option and no hierarchy — the planner prices all three and takes the cheapest.

Almost every catastrophic query in production is a nested loop that was priced against an outer side of one row and executed against an outer side of three hundred thousand. That asymmetry is what makes the join node worth understanding: hash and merge joins degrade gracefully when an estimate is wrong, and a nested loop degrades linearly into a query nobody waits for.

Nested Loop

For each row produced by the outer relation, look up the matching rows in the inner one. The cost is the outer row count multiplied by the cost of one inner lookup, plus almost nothing to start — there is no build phase, so the first result row comes out immediately. When the inner side has an index on the join key, one lookup is three or four page reads, and joining twenty outer rows costs essentially nothing. This is the right plan for Cartwheel's account screen: one customer, an index on orders (customer_id, placed_at), twenty-one orders.

The failure mode is in the multiplication and nowhere else. Nothing about a nested loop is slow at 20 loops and nothing about it changes at 300,000 loops except the number itself, which is why the plan gives no warning: the same node, the same per-loop time, three hundred thousand times. When you see a nested loop with a large loops count, the join type is the symptom and the estimate on the outer node is the disease. The planner will happily choose it when it believes the outer side has one row, and it has no mechanism for noticing at run time that the belief was wrong.

Hash Join

A hash join reads the smaller relation entirely, builds a hash table from the join key in work_mem, then streams the larger relation past it, probing once per row. Startup cost is the whole build. After that each probe is constant time regardless of how many rows match, and the join is completely indifferent to ordering and to how the data is distributed on disk. For two large inputs with no useful index between them, it is not close — this is the shape the planner should be choosing.

EXPLAIN (ANALYZE)
SELECT c.city, count(*) AS orders
  FROM orders o JOIN customers c ON c.id = o.customer_id
 WHERE o.placed_at >= date_trunc('month', now())
 GROUP BY c.city;                     -- aggregate node trimmed off

 Hash Join  (cost=98211.44..183904.02 rows=300615 width=14)
            (actual time=1904.331..3241.887 rows=300482.00 loops=1)
   Hash Cond: (o.customer_id = c.id)
   Buffers: shared hit=59218 read=22147, temp read=18204 written=18204
   ->  Bitmap Heap Scan on orders o  (actual rows=300482.00 loops=1)
   ->  Hash  (actual time=1893.002..1893.003 rows=1900000.00 loops=1)
         Buckets: 65536  Batches: 32  Memory Usage: 4737kB
         ->  Seq Scan on customers c  (actual rows=1900000.00 loops=1)

The Hash node reports what the build cost. All 1.9 million customers rows went into it, the peak memory used was 4.7 MB, and Batches: 32 is the important word: a single batch means the hash table stayed in memory, and thirty-two means Postgres split it into thirty-two passes and wrote thirty-one of them to temporary files. The temp read and written figures of about 18,000 blocks each are those files. This is a memory conversation and not an index one — no index on customers makes a hash table smaller. Chapter 10 covers what work_mem can and cannot be set to, and why the answer is never "raise it globally".

Merge Join

A merge join walks two sorted inputs in step, advancing whichever side is behind, and emits matches as it goes. Memory use is almost nothing regardless of input size, because neither side is ever held whole. When both inputs arrive already sorted, from index scans on the join keys or from an earlier sort the query needed anyway, it is the cheapest way to join two large relations there is. When either side has to be sorted first, that sort's cost lands entirely in the merge join's startup cost, and a hash join usually wins instead.

This is the join that rewards index design most directly, because "already sorted" is a property you can create. A composite index whose leading columns match the join key hands the merge join a pre-sorted stream for free. Since 13 there is a softer version of the same idea: Incremental Sort takes an input already sorted on the leading key and only sorts within each group of equal leading values, which turns a full sort of three hundred thousand rows into a few thousand tiny ones. Chapter 8 owns the index design. What a plan reader needs is one recognition: a Merge Join with a Sort underneath it is a different animal from one fed by two index scans, and the Sort node's total is the merge join's startup cost, printed on the line above it.

Memoize

Since 14 a Memoize node can sit on the inner side of a nested loop and cache the results of lookups it has already done. When the outer side repeats its join keys — a thousand order lines referencing fifty-seven distinct products — the inner index scan runs once per distinct key instead of once per row, and the rest are served from a small in-memory cache.

EXPLAIN (ANALYZE)
SELECT i.order_id, p.name, i.qty
  FROM order_items i JOIN products p ON p.id = i.product_id
 WHERE i.order_id BETWEEN 41200000 AND 41200500;

 Nested Loop  (actual time=0.038..3.914 rows=1840.00 loops=1)
   ->  Index Scan using order_items_order_id_idx on order_items i
         (actual rows=1840.00 loops=1)
   ->  Memoize  (actual time=0.001..0.001 rows=1.00 loops=1840)
         Cache Key: i.product_id
         Hits: 1783  Misses: 57  Evictions: 0  Overflows: 0  Memory Usage: 12kB
         ->  Index Scan using products_pkey on products p
               (actual rows=1.00 loops=57)
               Index Cond: (id = i.product_id)

Read the two loop counts against each other. The Memoize node was called 1,840 times, once per order line, but the index scan below it ran only 57 times, one per distinct product, and 1,783 calls were answered from a twelve-kilobyte cache. Memoize is why nested loops now appear at outer row counts that would once have been obviously wrong, and why "a nested loop over 1,840 rows" is no longer enough information to condemn a plan. Evictions and Overflows both at zero mean the cache never ran short; non-zero values there mean the distinct-key count was larger than the memory allowed and the node is doing less good than it looks.

Join Order Is the Bigger Decision

Choosing between three algorithms is the small half of the problem. With five tables in a query there are dozens of valid orders in which to join them, and the difference between the best and the worst is routinely three orders of magnitude, because an intermediate result of two thousand rows and one of two million cost very different amounts to feed into the next join. The planner searches that space exhaustively — and the space grows factorially, so at some point it has to stop.

That point is geqo_threshold, which defaults to 12. At twelve or more relations in one join problem, Postgres switches to a genetic algorithm that samples the space rather than covering it, and a sampled search does not return the same answer every time. A twenty-table reporting query that is fast today and slow after a restart is usually this, not a statistics problem. Two related settings shape how large the problem gets in the first place: from_collapse_limit and join_collapse_limit, both defaulting to 8, control how aggressively subqueries and explicit JOIN clauses are flattened into one flat list for the planner to reorder. Below the limit you get full search; above it, the join order you wrote is partly the order you get.

Outer Joins Constrain the Search

An inner join is symmetric, so the planner may put either side first and reorder freely against every other table. A LEFT JOIN is not: the preserved side has to be processed in a way that keeps its unmatched rows, which removes reorderings from the search space. Every unnecessary outer join in a query is therefore a set of plans the planner is not allowed to consider.

The common version of this in application code is a LEFT JOIN written defensively, followed by a WHERE clause on a column of the null-able side. That filter discards exactly the rows the outer join was preserving, so the query is an inner join semantically while still being an outer join structurally. Rewriting it as an inner join costs nothing and hands the planner back its options — one of the few rewrites that is unambiguously free. The counterpart is joining on an expression or across mismatched types, such as a bigint column against a text one: neither an index nor a hash strategy applies cleanly to a value the planner has to compute per row, and the plan collapses toward a sequential scan on both sides.