Nested loop, hash join and merge join in PostgreSQL Intermediate

The problem

1,000 customers, 100,000 orders, joined on customer_id, grouped by region:

SELECT c.region, sum(o.amount)
FROM customer_demo c JOIN order_demo o ON o.customer_id = c.id
GROUP BY c.region;

PostgreSQL has three physical ways to execute this one join. This article forces PostgreSQL 17 to run each of them on the same data using enable_hashjoin, enable_mergejoin and enable_nestloop. These are diagnostic switches, not hints for production use.

Three algorithms in one table

	Nested Loop	Hash Join	Merge Join
How	For each outer row → look up the inner	Hash the small side, scan the large side to probe	Two sorted sequences, walked in parallel
Needs	Usually an index on the inner	An = condition, enough RAM for the hash table	An = condition, both sides ordered (or a Sort)
Wins when	The outer is tiny and the inner is indexed	Both sides are large, no existing order	Input already sorted from an index, or ordered output is needed
Loses when	Large outer, inner without an index	Hash table exceeds work_mem × hash_mem_multiplier (spills to disk)	Both sides must be sorted
Joins without = (<, BETWEEN)	Can do it	No	No

How it works

Hash Join: build, then probe

Hash Join: build a hash table from the small side, probe with the large side

Enlarge diagram

customer_demo → Hash tablehash id

◀ Prev▶ PlayNext ▶↺ RestartStep 1/3

Build: read the small side once, hash it on the join key (id), and load it into an in-memory hash table.

Without any hints, the planner picks Hash Join for this query on its own:

HashAggregate  (cost=2333.11..2333.14 rows=2 width=37) (actual time=18.918..18.922 rows=2 loops=1)
  Buffers: local hit=547
  ->  Hash Join  (cost=28.50..1833.11 rows=100000 width=11) (actual time=0.097..11.002 rows=100000 loops=1)
        Hash Cond: (o.customer_id = c.id)
        ->  Seq Scan on order_demo o  (rows=100000)
        ->  Hash  (cost=16.00..16.00 rows=1000 width=9) (actual time=0.088..0.089 rows=1000 loops=1)
              Buckets: 1024  Batches: 1  Memory Usage: 51kB
              ->  Seq Scan on customer_demo c  (rows=1000)
Execution Time: 18.956 ms

• The hash table is built from customer_demo (the small side): 1,000 rows, 51 kB.
• Batches: 1 means the hash table fits entirely in memory.
• Result: 547 buffer hits, 18.956 ms.

Nested Loop: Memoize rescues the repetition

Nested Loop with Memoize: one index lookup per customer_id

Enlarge diagram

order_demo → Memoizecustomer_id = ?

◀ Prev▶ PlayNext ▶↺ RestartStep 1/3

For each outer row, Nested Loop takes customer_id and asks the inner side: "who is this customer?".

Forcing Nested Loop, the planner inserts a Memoize node (available since PostgreSQL 14):

Nested Loop  (cost=0.29..4332.71 rows=100000 width=11) (actual time=0.024..19.495 rows=100000 loops=1)
  Buffers: local hit=3541
  ->  Seq Scan on order_demo o  (rows=100000)
  ->  Memoize  (cost=0.29..0.30 rows=1 width=9) (actual time=0.000..0.000 rows=1 loops=100000)
        Cache Key: o.customer_id
        Hits: 99000  Misses: 1000  Evictions: 0
        ->  Index Scan using customer_demo_pkey on customer_demo c  (rows=1) (loops=1000)
Execution Time: 27.886 ms

• customer_id has only 1,000 distinct values across 100,000 rows, so the inner index scan runs only 1,000 times (Misses); the other 99,000 come from the cache (Hits).
• As a result Nested Loop is only about 47% slower than Hash Join (27.886 ms vs 18.956 ms), not hundreds of times as the “nested loop” intuition suggests.
• It is still the slowest of the three because every one of the 100,000 rows has to look up the cache once.

Merge Join: two cursors over two sorted sequences

Picture Merge Join as merging two lists sorted by customer_id:

customer (sorted)     order (sorted)
  id=1   ◄──────────►  customer_id=1  (match)
  id=1   ◄──────────►  customer_id=1  (match)  ← order cursor advances, customer stays
  id=2   ◄──────────►  customer_id=2  (match)
  id=3   ◄ ─ ─ ─ ─ ─   customer_id=5          ← 3 < 5: advance the cursor with the smaller key

Each side is walked only once, but both must be ordered. If they are not, the planner has to Sort first, and that is Merge Join’s main cost.

Merge Join  (cost=0.57..5304.90 rows=100000 width=8) (actual time=0.011..15.001 rows=100000 loops=1)
  Merge Cond: (c.id = o.customer_id)
  Buffers: local hit=100014 read=81
  ->  Index Only Scan using customer_demo_pkey on customer_demo c  (rows=1000)
        Heap Fetches: 1000
  ->  Index Scan using order_demo_customer_idx on order_demo o  (rows=100000) (actual time=0.004..9.531)
Execution Time: 16.949 ms

The time (16.949 ms) matches Hash Join, but Buffers: hit=100014 vs 547 is 182x more. Read this number correctly:

• hit counts buffer accesses, not distinct pages.
• An index scan pins a buffer for each tuple fetched, so the same page is counted many times. The Seq Scan on the Hash Join side pins each page only once for a whole batch of tuples.
• So 182x reflects buffer touches (CPU), not 182x disk I/O.
• For real I/O, compare read (81 here) or rerun with a cold cache.

When Nested Loop wins outright

Change the query to fetch the orders of one customer:

Nested Loop  (cost=5.34..269.79 rows=100 width=4) (actual time=0.023..0.060 rows=100 loops=1)
  ->  Index Only Scan using customer_demo_pkey on customer_demo c  (rows=1)
        Index Cond: (id = 42)
  ->  Bitmap Heap Scan on order_demo o  (rows=100)
        Recheck Cond: (customer_id = 42)
Execution Time: 0.077 ms

0.077 ms, tens to hundreds of times faster than the full joins.

The two queries do different amounts of work (1 customer vs all), so do not read this as “Nested Loop is faster than Hash Join”.

The correct meaning: when the outer has 1 row, there is no need to build a hash table or sort a whole table just to fetch 1 row.

Which algorithm to choose?

The planner decides by cost; this is how to read its outcome:

Loading diagram…

Real-world example

Same two tables, two queries, two completely different plans

Query	Outer input	Plan the planner picks
API “view one customer’s orders” (WHERE customer_id = ?)	1 row	Nested Loop, ~0.08 ms
Nightly “revenue by region” job	~both tables in full	Hash Join

Do not “optimize” by forcing the same algorithm for both. Let the planner decide per query and only intervene when you have measured that it chooses wrong.

When to use, when not to

Pros

• Nested Loop is nearly free when the outer is small and the inner is indexed (0.077 ms in the demo)
• Hash Join needs no index or order, and has the fewest buffer accesses when both tables fit in cache (547 in the demo)
• Merge Join exploits existing order from an index, no Sort needed if the input is already sorted

Cons

• Nested Loop multiplies cost by the number of outer rows; Memoize softens this but does not remove it
• Hash Join builds a hash table in RAM; exceeding work_mem × hash_mem_multiplier splits into batches and writes temp files
• Merge Join often has to Sort both sides without a suitable index

Checklist when a join is slow

1. Run EXPLAIN (ANALYZE, BUFFERS) and compare estimated rows with actual rows at the join node. Estimates that are too low often make the planner pick Nested Loop wrongly (planner statistics).
2. Slow Nested Loop with large loops: check whether the inner has a Seq Scan or lacks an index on the join key.
3. Hash Join with Batches > 1: the hash table spilled to disk. Consider raising work_mem for the specific session or reducing the data fed into the join. hash_mem_multiplier defaults to 2.0 since PostgreSQL 15.
4. Merge Join with a large Sort: consider an index that yields rows already ordered by the join key.
5. Many small repeated queries from an ORM (N+1) are really a Nested Loop running in the application layer, without Memoize. Merge them into one join or WHERE id = ANY(...).
6. Only use enable_* for diagnosis in a separate session. Never set them in production.

Common mistakes

Common pitfall

Comparing two plans only by Execution Time on small, fully cached data. Hash Join and Merge Join take almost the same time (18.956 ms and 16.949 ms) but their buffer accesses differ by 182x.

When evaluating a plan for production, look at Buffers too (remember hit is accesses, not I/O) and re-measure with data and cache close to reality.

Summary

Key takeaways

• There is no universally best join algorithm; each wins on a particular data shape.
• Small outer + indexed inner → Nested Loop. Two large tables, = join, no existing order → Hash Join. Already sorted → Merge Join.
• Hash Join and Merge Join only work with = conditions; joins on < or BETWEEN only have Nested Loop.
• Buffers hit counts accesses, not I/O: for real I/O compare read or measure with a cold cache.
• Memoize (since PostgreSQL 14) makes Nested Loop much cheaper when join keys repeat, but does not make it the best choice for large joins.

References

• PostgreSQL 17 — Using EXPLAIN
• PostgreSQL 17 — Planner Method Configuration