Nested Loop, Hash Join, Merge Join

Join nodes combine row sets from two inputs. PostgreSQL 18.4 picks nested loop, hash, or merge join based on row counts, available memory, index opportunities, and sort order.

Recipe

Quick-reference recipe card - copy-paste ready.

EXPLAIN (ANALYZE, BUFFERS)
SELECT o.id, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.created_at >= now() - interval '1 day';

When to reach for this: Join-heavy queries spike CPU or I/O. Identify which join algorithm dominates the plan.

Working Example

CREATE TABLE customers (
  id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  name text NOT NULL
);
 
CREATE TABLE orders (
  id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  customer_id bigint NOT NULL REFERENCES customers(id),
  created_at timestamptz NOT NULL DEFAULT now()
);
 
CREATE INDEX orders_customer_id_idx ON orders (customer_id);
CREATE INDEX orders_created_at_idx ON orders (created_at);
 
INSERT INTO customers (name)
SELECT 'customer-' || i FROM generate_series(1, 50000) AS i;
 
INSERT INTO orders (customer_id, created_at)
SELECT (random() * 49999 + 1)::bigint, now() - (random() * interval '30 days')
FROM generate_series(1, 500000);
 
ANALYZE customers;
ANALYZE orders;
 
EXPLAIN (ANALYZE, BUFFERS)
SELECT o.id, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.created_at >= now() - interval '1 day';

What this demonstrates:

• Nested loop with index on inner side for small outer sets
• Hash join when building a hash table is cheaper than repeated index probes
• How selective filters shrink the outer input before the join

Deep Dive

How It Works

• Nested Loop - For each outer row, scan the inner input (often index-backed). Wins when outer is tiny or inner has a selective index.
• Hash Join - Build a hash table on the smaller input, probe with the larger. Needs work_mem; spills to disk if exceeded (Hash Buckets / Batches in plan).
• Merge Join - Both inputs sorted on join keys; merge like merge-sort. Needs presorted inputs or explicit sorts; excellent for large equi-joins on sorted data.

Algorithm Selection Signals

SQL Notes

-- Reveal join order and type
EXPLAIN (VERBOSE, ANALYZE)
SELECT count(*)
FROM orders o
JOIN customers c ON c.id = o.customer_id;
 
-- Hash spill indicator
-- Look for: "Buckets: ...  Batches: 2" in Hash Join node
SET work_mem = '64MB';

Gotchas

• Nested loop with seq scan inner - Disaster at scale: O(n*m). Fix: Index the inner join key or rewrite to hash join via better stats.
• Hash join disk spill - Batches > 1 means work_mem too low for that node. Fix: Raise work_mem for the reporting role only, or reduce rows earlier with filters.
• Cross join disguised as nested loop - Missing join condition. Fix: Verify ON/USING clauses in ORM-generated SQL.
• Merge join plus double sort - Two expensive sorts when neither input is ordered. Fix: Index leading columns to match join keys and ORDER BY.
• Stale stats flipping join type - Plan changes after ANALYZE without code changes. Fix: Capture plans in CI; alert on regressions.

Alternatives

FAQs

Related

• Sort & Hash Aggregates - work_mem spills
• Bad Plan Case Studies - Join order failures
• Index Design Basics - Join column indexes
• work_mem tuning - Per-node memory

Stack versions: This page was written for PostgreSQL 18.4 (stable 18, maintenance 17), pgvector 0.8+, PgBouncer 1.x, Patroni 3.x, and PostGIS 3.5+.