Join algorithms

Nested loop, hash and merge joins: how each works, what it costs, and when the planner picks it.

Draft. This page is new and has not yet been reviewed by a second person. Every query output on it was produced by a real run on PostgreSQL 18.6 (PGlite 0.5.9). If something looks wrong, report it.

Before thisReading EXPLAIN
On this page
  1. Nested loop
  2. Hash join
  3. Merge join
  4. How the planner chooses, and how to argue with it
  5. Quick reference
  6. In MySQL
  7. Sources

Almost every interesting query joins tables, and the join method often decides whether a query takes a millisecond or a minute. PostgreSQL has three, and it picks one per join from its row estimates. Knowing what each one costs tells you what a plan is doing and why it might be the wrong choice.

Nested loop#

For each row from the outer input, run the inner input once. With no index on the inner side, that means reading all of it for every outer row, so the cost grows as outer rows × inner rows. With an index on the inner side's join key, each outer row costs one index lookup, and it becomes the fastest join there is for a small outer side.

sql
create index orders_user_id_idx on orders (user_id);

One user and their orders: one outer row, one index lookup on the inner side.

sql
select u.email, o.id, o.total
from users u
join orders o on o.user_id = u.id
where u.id = 42;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
Nested Loop  (cost=4.92..156.21 rows=44 width=31) (actual time=0.071..0.156 rows=44.00 loops=1)
  Buffers: shared hit=45 read=4
  ->  Index Scan using users_pkey on users u  (cost=0.29..8.30 rows=1 width=25) (actual time=0.032..0.033 rows=1.00 loops=1)
        Index Cond: (id = 42)
        Index Searches: 1
        Buffers: shared hit=1 read=2
  ->  Bitmap Heap Scan on orders o  (cost=4.63..147.46 rows=44 width=14) (actual time=0.033..0.093 rows=44.00 loops=1)
        Recheck Cond: (user_id = 42)
        Heap Blocks: exact=44
        Buffers: shared hit=44 read=2
        ->  Bitmap Index Scan on orders_user_id_idx  (cost=0.00..4.62 rows=44 width=0) (actual time=0.017..0.017 rows=44.00 loops=1)
              Index Cond: (user_id = 42)
              Index Searches: 1
              Buffers: shared read=2
Planning:
  Buffers: shared hit=19 read=1
Planning Time: 0.742 ms
Execution Time: 0.196 ms

Look at loops on the inner node: it is how many times the inner side ran. Multiply its rows and time by it to get the real work.

Hash join#

Read the smaller input once and build a hash table on the join key in memory, then read the other input once and look each row up in the table. Each input is read once, which makes it the usual choice for joining many rows to many rows when neither side is sorted.

sql
select u.country, count(*) as orders
from orders o
join users u on u.id = o.user_id
group by u.country;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
HashAggregate  (cost=3231.56..3231.64 rows=8 width=11) (actual time=146.702..146.710 rows=8.00 loops=1)
  Group Key: u.country
  Batches: 1  Memory Usage: 32kB
  Buffers: shared hit=1019
  ->  Hash Join  (cost=659.00..2731.56 rows=100000 width=3) (actual time=13.777..105.769 rows=100000.00 loops=1)
        Hash Cond: (o.user_id = u.id)
        Buffers: shared hit=1019
        ->  Seq Scan on orders o  (cost=0.00..1810.00 rows=100000 width=4) (actual time=0.008..26.574 rows=100000.00 loops=1)
              Buffers: shared hit=810
        ->  Hash  (cost=409.00..409.00 rows=20000 width=7) (actual time=13.676..13.678 rows=20000.00 loops=1)
              Buckets: 32768  Batches: 1  Memory Usage: 753kB
              Buffers: shared hit=209
              ->  Seq Scan on users u  (cost=0.00..409.00 rows=20000 width=7) (actual time=0.006..6.401 rows=20000.00 loops=1)
                    Buffers: shared hit=209
Planning:
  Buffers: shared hit=9 read=3
Planning Time: 0.397 ms
Execution Time: 146.761 ms

The Hash node shows the table it built: Buckets, Batches and Memory Usage. Batches: 1 means it fitted in work_mem. More than one batch means the table was split and part of it written to temporary files, which is much slower.

Merge join#

Sort both inputs on the join key, then walk them side by side, like merging two sorted lists. It shines when both inputs are already sorted, for example because each one can be read from an index on the join key, and when both are large.

In the sample database a hash join is usually cheaper, so to see a merge join, switch hash joins off for a moment. This is an investigation tool, never something to leave on:

sql
set local enable_hashjoin = off;
sql
select u.country, count(*) as orders
from orders o
join users u on u.id = o.user_id
group by u.country;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
HashAggregate  (cost=4616.58..4616.66 rows=8 width=11) (actual time=144.545..144.550 rows=8.00 loops=1)
  Group Key: u.country
  Batches: 1  Memory Usage: 32kB
  Buffers: shared hit=218 read=191
  ->  Merge Join  (cost=0.58..4116.58 rows=100000 width=3) (actual time=0.061..100.882 rows=100000.00 loops=1)
        Merge Cond: (o.user_id = u.id)
        Buffers: shared hit=218 read=191
        ->  Index Only Scan using orders_user_id_idx on orders o  (cost=0.29..2076.29 rows=100000 width=4) (actual time=0.006..32.749 rows=100000.00 loops=1)
              Heap Fetches: 14
              Index Searches: 1
              Buffers: shared hit=6 read=138
        ->  Index Scan using users_pkey on users u  (cost=0.29..740.29 rows=20000 width=7) (actual time=0.011..9.540 rows=20000.00 loops=1)
              Index Searches: 1
              Buffers: shared hit=212 read=53
Planning:
  Buffers: shared hit=12
Planning Time: 0.335 ms
Execution Time: 144.601 ms
sql
reset enable_hashjoin;

Both inputs come from indexes already in user_id order (the index created above, and the users primary key), so there is no Sort node: the merge walks the two lists once. Compare its total cost with the hash join version above; the planner chose the hash join because it estimated it to be cheaper.

How the planner chooses, and how to argue with it#

The planner estimates the cost of each method from its row estimates and picks the cheapest. When the estimates are wrong, so is the choice: a nested loop chosen because the planner expected one outer row is a disaster when there are 30,000 (the stale statistics exercise shows exactly this).

To see what an alternative would have cost, switch a method off for your session and explain again. A handful of users and their orders, which the planner joins with a nested loop over the index:

sql
select u.email, o.id, o.total
from users u
join orders o on o.user_id = u.id
where u.id between 40 and 45;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
Nested Loop  (cost=4.62..148.00 rows=30 width=31) (actual time=0.045..0.734 rows=335.00 loops=1)
  Buffers: shared hit=338
  ->  Index Scan using users_pkey on users u  (cost=0.29..8.41 rows=6 width=25) (actual time=0.008..0.012 rows=6.00 loops=1)
        Index Cond: ((id >= 40) AND (id <= 45))
        Index Searches: 1
        Buffers: shared hit=3
  ->  Bitmap Heap Scan on orders o  (cost=4.33..23.22 rows=5 width=14) (actual time=0.015..0.077 rows=55.83 loops=6)
        Recheck Cond: (u.id = user_id)
        Heap Blocks: exact=323
        Buffers: shared hit=335
        ->  Bitmap Index Scan on orders_user_id_idx  (cost=0.00..4.33 rows=5 width=0) (actual time=0.006..0.006 rows=55.83 loops=6)
              Index Cond: (user_id = u.id)
              Index Searches: 6
              Buffers: shared hit=12
Planning:
  Buffers: shared hit=12
Planning Time: 0.348 ms
Execution Time: 0.830 ms
sql
set local enable_nestloop = off;
sql
select u.email, o.id, o.total
from users u
join orders o on o.user_id = u.id
where u.id between 40 and 45;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
Hash Join  (cost=8.48..2081.04 rows=30 width=31) (actual time=0.140..49.629 rows=335.00 loops=1)
  Hash Cond: (o.user_id = u.id)
  Buffers: shared hit=813
  ->  Seq Scan on orders o  (cost=0.00..1810.00 rows=100000 width=14) (actual time=0.008..23.608 rows=100000.00 loops=1)
        Buffers: shared hit=810
  ->  Hash  (cost=8.41..8.41 rows=6 width=25) (actual time=0.020..0.022 rows=6.00 loops=1)
        Buckets: 1024  Batches: 1  Memory Usage: 5kB
        Buffers: shared hit=3
        ->  Index Scan using users_pkey on users u  (cost=0.29..8.41 rows=6 width=25) (actual time=0.010..0.015 rows=6.00 loops=1)
              Index Cond: ((id >= 40) AND (id <= 45))
              Index Searches: 1
              Buffers: shared hit=3
Planning:
  Buffers: shared hit=12
Planning Time: 0.333 ms
Execution Time: 49.737 ms
sql
reset enable_nestloop;

Without the nested loop the planner has to read far more of orders to join a few users; compare the buffers. In PostgreSQL 18 the enable_* settings do not forbid a method outright: plans with fewer disabled steps win first, then the cheapest, and a disabled step that could not be avoided is marked Disabled: true in the plan. That happens, for example, when a query fixes a single u.id = 42: the planner then knows o.user_id = 42 as well, no join condition is left, and only a nested loop can do the job.

Use these settings to compare costs and buffers while investigating, never in application code. Then fix the real cause, which is usually an estimate, a missing index, or a function on the join column.

Quick reference#

Nested loopHash joinMerge join
Best whenOuter side small, index on the inner keyLarge inputs, no useful orderLarge inputs already sorted on the key
Workouter rows × (one lookup or one scan)read each side oncesort both (unless sorted), then one pass
Memorylittlethe hash table (up to work_mem, then batches on disk)the sorts, if any
Join conditionsanyequality onlyequality (and ordering) only
Watch forlarge loops on the inner sideBatches greater than 1big Sort nodes feeding it

In MySQL#

Not run here; from the MySQL reference manual. MySQL has long used nested loops (with index lookups, plus block nested loop for joins without an index). Since 8.0.18 it can use a hash join for equality joins, and from 8.0.20 the hash join replaced block nested loop. MySQL has no merge join.

Sources#

Esc
↑ ↓ to move↵ to open