Join algorithms and join order

conceptThe concept

Nested Loop: for each outer row, look up matches in the inner input, ideally through an index. Unbeatable when the outer side is small; catastrophic when the planner thinks it is small and it is not.

Hash Join: build a hash table from the smaller input, then probe it with each row of the larger one. Good for large, unsorted inputs joined on equality. Memory is limited by work_mem times hash_mem_multiplier; beyond that it splits into batches on disk (Batches: 4 in the plan).

Merge Join: walk two inputs sorted on the join key side by side. Good when both sides are already sorted (by an index) or the data is huge. With several tables, the planner also chooses the join order; above join_collapse_limit (8) tables it stops searching all orders, and above geqo_threshold (12) it uses a genetic search.

whyWhy it matters

The most common bad plan in production is a nested loop chosen because the planner estimated 1 outer row when there were 50,000. Recognising that pattern lets you fix the estimate rather than fighting the planner with settings.

Use caseReal-world scenario

A report that joins orders to customers for the whole year uses a hash join; the order details page that fetches 20 orders and their items uses nested loops over primary-key indexes. Both are right for their shapes.

Try itExamples

Run and edit these in the interactive lesson.

EXPLAIN
SELECT o.id, oi.line_no, oi.product_id
FROM orders o
JOIN order_items oi ON oi.order_id = o.id
WHERE o.id BETWEEN 100 AND 120;

EXPLAIN (ANALYZE, COSTS OFF)
SELECT c.country, sum(o.total)
FROM orders o
JOIN customers c ON c.id = o.customer_id
GROUP BY c.country;

Disabling the other algorithms for one transaction shows the plan the planner rejected and its higher cost. Never ship such settings globally.

BEGIN;
SET LOCAL enable_hashjoin = off;
SET LOCAL enable_nestloop = off;
EXPLAIN
SELECT o.id, c.name FROM orders o JOIN customers c ON c.id = o.customer_id;
ROLLBACK;

BEGIN;
SET LOCAL work_mem = '64kB';
EXPLAIN (ANALYZE, COSTS OFF)
SELECT count(*) FROM order_items oi JOIN orders o ON o.id = oi.order_id;
ROLLBACK;

Avoid / preferDo this, not that

ALTER SYSTEM SET enable_nestloop = off;

-- find the misestimate that made the nested loop look cheap:
-- ANALYZE, extended statistics, or a query rewrite

SELECT * FROM events e JOIN customers c ON c.id::text = e.payload ->> 'customer';

SELECT * FROM events e JOIN customers c ON c.id = (e.payload ->> 'customer')::int;

PitfallsCommon mistakes

• Turning off nested loops globally because one query had a bad one. Fix the estimate (statistics, rewrite) for that query instead.
• Assuming merge joins are bad because of the Sort. When both sides come from indexes in order, a merge join needs no sort at all.
• Raising work_mem globally to fix one spilling hash join. It applies per sort or hash node, per connection; set it per session or role.

LimitsWhen not to use it

Do not pin join order with join_collapse_limit = 1 unless you have a stable query whose planner choice you have proven wrong and cannot fix with statistics.

SecuritySecurity notes

enable_* settings and work_mem are user-settable, so any role can make its own queries slow or memory-hungry. Set sane per-role defaults with ALTER ROLE ... SET and watch pg_stat_statements.

ChallengeTry it yourself

SELECT pgm.plan_nodes('SELECT * FROM orders o JOIN customers c ON c.id = o.customer_id') AS nodes;

InterviewQuestions you should be able to answer

QuizCheck your understanding

4 questions with instant feedback in the interactive lesson; a wrong answer goes into your review deck.

Go deeperOfficial documentation

• Using EXPLAIN
• Planner and optimizer