Joins: nested loop, hash and merge

Nested loop

For every row from the outer input, scan the inner input for matches. That sounds slow, and it is if both sides are large. But if the outer side is small and the inner side has an index on the join column, each "scan" is one index lookup:

1EXPLAIN SELECT o.id, c.email2FROM orders o JOIN customers c ON c.id = o.customer_id3WHERE c.email = 'user42@example.com';

1Nested Loop  (cost=4.90..107.60 rows=25 width=29)2  ->  Index Scan using customers_email_key on customers c  (cost=0.29..8.30 rows=1 width=29)3        Index Cond: (email = 'user42@example.com'::text)4  ->  Bitmap Heap Scan on orders o  (cost=4.62..99.05 rows=25 width=16)5        Recheck Cond: (customer_id = c.id)6        ->  Bitmap Index Scan on orders_cust_cov_idx  (cost=0.00..4.61 rows=25 width=0)7              Index Cond: (customer_id = c.id)

One customer, one index lookup into orders. Nested loops are also the only method that works for conditions that are not equalities, such as ON a.ts BETWEEN b.start AND b.finish.

Hash join

Read the smaller input, build an in-memory hash table on the join key, then stream the larger input and probe the table for each row. Each input is read once. It needs an equality condition, and the hash table must fit in work_mem (times hash_mem_multiplier) or it is split into batches on disk.

1EXPLAIN SELECT c.country, sum(o.total_cents)2FROM orders o JOIN customers c ON c.id = o.customer_id3GROUP BY c.country;

1...2  ->  Hash Join  (cost=607.00..7303.32 rows=208333 width=7)3        Hash Cond: (o.customer_id = c.id)4        ->  Parallel Seq Scan on orders o  (cost=0.00..6149.33 rows=208333 width=12)5        ->  Hash  (cost=357.00..357.00 rows=20000 width=11)6              ->  Seq Scan on customers c  (cost=0.00..357.00 rows=20000 width=11)

The 20,000 customers become the hash table; the 500,000 orders stream past it, split across parallel workers.

Merge join

If both inputs are sorted on the join key, walk them together like merging two sorted lists. The sort can come from an index or from an explicit sort node. Asking for every order with its customer, sorted by customer_id (ORDER BY o.customer_id), makes this the cheapest plan here, because both indexes already deliver rows in that order:

1Merge Join  (cost=0.74..32472.70 rows=500000 width=24)2  Merge Cond: (o.customer_id = c.id)3  ->  Index Scan using orders_customer_idx on orders o  (cost=0.42..25644.42 rows=500000 width=16)4  ->  Index Only Scan using customers_pkey on customers c  (cost=0.29..528.29 rows=20000 width=8)

When the planner gets it wrong

The choice depends almost entirely on estimated row counts. The classic failure is a nested loop chosen for an outer side estimated at a handful of rows that turns out to be hundreds of thousands, each paying for an index lookup. Find the node where estimated and actual rows diverge and fix that: fresh statistics, extended statistics for correlated columns, or a rewrite the planner can estimate. Settings such as enable_nestloop = off exist for experiments in a session, to see what the alternative plan would cost; they are a diagnostic tool, not a fix to ship.

Index the foreign key columns you join on. PostgreSQL indexes the referenced primary key automatically, but not the referencing column.