Hash Join vs Merge Join vs Nested Loop: When Each One Wins

All of it is measured below except the sort in merge join’s failure row, which is documented behavior these tests never triggered.

So here is how a join works, in outline. Looking up each row of one table in the other is the natural first answer, and with an index on the second table’s join column (a sorted copy of that column with pointers back to the rows) it is a good one, because each lookup goes straight to the few rows that match. But every lookup is a separate trip, into the index and then out to wherever those rows sit in the table, and a join that needs a large share of the table makes one such trip per row. Past some point it is cheaper to read the whole table once, front to back, and match rows as they go by. Databases do that in two ways: hold one side in a lookup table in memory and stream the other side past it, or read both sides in the same sorted order and pair them off. Counting the lookup, that makes three algorithms, called nested loop, hash join and merge join, and before each query PostgreSQL’s planner, the part that picks how a query runs, estimates the rows each step will produce, prices the options and runs the cheapest.

A quick reminder about query plans

The planner’s choice is printed in the query plan, the tree of steps the database runs to answer a query. EXPLAIN shows the plan, and EXPLAIN ANALYZE runs the query and adds what actually happened. Each step is a node, indented under the node that uses its output, and each carries two estimates: rows, how many rows the planner expects it to produce, and cost, a number in arbitrary units that only means something next to the cost of another plan. A join is a node with two children, the two inputs it matches. The habit this post leans on is reading the estimated rows against the actual ones, because the planner chose its join from the estimate; the how-tos for PostgreSQL and MySQL cover the rest of the output (MySQL calls its planner the optimizer).

Three ways to join two tables

Each of the three needs something different from its inputs, and what it needs decides how its cost grows as the inputs grow. That growth is what the planner is really comparing when it prices them.

The tests ran on PostgreSQL 18.6 and MySQL 8.4.13 in Docker with default settings, each container limited to 4 CPUs and 4 GB of memory, on the same tables as the two EXPLAIN posts: 200,000 customers and 5,000,000 orders, each order belonging to a random customer, with an index on orders.customer_id. A third table, shipments, holds one row for each of the 4,950,073 shipped orders, keyed by order id and written in order id order. PostgreSQL can split one join across several processes, and it can compile parts of a query at run time (JIT); I turned both off, as in the EXPLAIN post, so parallel joins are simplified away here. Every join is also an inner join on one equality, such as o.customer_id = c.id; outer joins and other conditions change which of the three are allowed, which this post leaves aside. Timings are medians of five runs (three for the biggest joins) with the tables already read once. Run-to-run noise between sessions was up to about 20 percent, so smaller differences mean nothing.

The query for most of this post totals the orders of the first N customers:

1
2
3
4

SELECT count(*), sum(o.total)
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE c.id <= 1000;

Nested loop

A nested loop is the lookup from the outline, and what it needs is an index on the second input’s join column, because it searches that input once for every row of the first. Without one, each search would have to read the whole orders table. With 1,000 customers PostgreSQL picks it (plan trimmed to the join and its two inputs):

1
2
3
4
5
6
7

 Nested Loop  (cost=0.85..93322.60 rows=24625 width=6) (actual time=0.010..54.458 rows=24899.00 loops=1)
   Buffers: shared hit=8343 read=19558
   ->  Index Only Scan using customers_pkey on customers c  (cost=0.42..29.66 rows=985 width=4) (actual time=0.004..0.068 rows=1000.00 loops=1)
         Index Cond: (id <= 1000)
   ->  Index Scan using orders_customer_id_idx on orders o  (cost=0.43..94.45 rows=26 width=10) (actual time=0.003..0.053 rows=24.90 loops=1000)
         Index Cond: (customer_id = c.id)
 Execution Time: 55.356 ms

The first child is called the outer side, and here it produces 1,000 customers. The second child, the inner side, runs once per customer (loops=1000), and each run uses the index to find that customer’s 25 or so orders. So the work grows with the outer side: twice the customers, twice the index lookups. Buffers counts pages, the 8 KB blocks PostgreSQL stores a table in, and this join touched 27,901 of them, because each customer’s orders are scattered across the table and almost every order lives on a different page.

Hash join

A hash join needs no index at all. What it needs is memory, for a hash table: a lookup structure, keyed on the join column, that it builds from one input before reading the other. Raise the limit to 20,000 customers and the plan changes to one:

1
2
3
4
5
6
7

 Hash Join  (cost=804.18..145898.06 rows=489805 width=6) (actual time=1.398..387.738 rows=500284.00 loops=1)
   Hash Cond: (o.customer_id = c.id)
   ->  Seq Scan on orders o  (cost=0.00..131968.48 rows=5000048 width=10) (actual time=0.066..179.694 rows=5000000.00 loops=1)
   ->  Hash  (cost=559.28..559.28 rows=19592 width=4) (actual time=1.328..1.328 rows=20000.00 loops=1)
         Buckets: 32768  Batches: 1  Memory Usage: 960kB
         ->  Index Only Scan using customers_pkey on customers c  (cost=0.42..559.28 rows=19592 width=4) (actual time=0.005..0.658 rows=20000.00 loops=1)
 Execution Time: 407.853 ms

Read it from the bottom. The Hash node collects the 20,000 customer ids into the hash table, which took 960 kB and a millisecond. Then Seq Scan on orders reads all 5,000,000 orders once, and for each one the join checks the hash table for its customer_id. Nothing runs more than once (loops=1 everywhere), and the index on orders.customer_id is not used at all. Most of the cost is that one scan of the orders table, and it is the same whether the hash table holds 20 customers or 20,000: with only 10 customers a forced hash join still took 268 ms. The memory limit comes from work_mem in PostgreSQL and join_buffer_size in MySQL, and Batches: 1 means the hash table fit inside it. That line comes back below.

Merge join

A merge join needs both inputs sorted on the join column, either read from an index in that order or sorted first, and in return it reads each input once. The customers-and-orders query cannot get its orders in that order cheaply, as the next section shows. The shipments join can, because both it and orders have primary keys on the order id:

1
2
3

SELECT count(*), sum(s.weight_g)
FROM orders o
JOIN shipments s ON s.order_id = o.id;

1
2
3
4
5

 Merge Join  (cost=12.71..366817.13 rows=4950090 width=4) (actual time=0.017..967.736 rows=4950073.00 loops=1)
   Merge Cond: (o.id = s.order_id)
   ->  Index Only Scan using orders_pkey on orders o  (cost=0.43..129849.15 rows=5000048 width=8) (actual time=0.004..188.127 rows=5000000.00 loops=1)
   ->  Index Scan using shipments_pkey on shipments s  (cost=0.43..162601.78 rows=4950090 width=12) (actual time=0.011..337.965 rows=4950073.00 loops=1)
 Execution Time: 1083.770 ms

Both inputs come out of their primary key indexes already in order id order. The join reads one row from each side. If the ids match, that is a result row; if not, it moves the side with the smaller id forward. Each table is read once, front to back, with no hash table and no sort, and the Merge Cond line gives it away.

This is the case merge join exists for: two big tables, every row needed, both already in key order. Forcing the other two algorithms onto the same join shows why the planner picked it:

The hash join has to load 4,950,073 shipments into its hash table before it can match anything, and at the default work_mem that table did not fit, so PostgreSQL split it into 64 batches written to temporary files (Batches: 64 under the Hash node). The nested loop is less awful than its 4,950,073 lookups suggest, because it scans shipments in order id order, so consecutive lookups into the orders primary key land on the same index pages.

Where the choice goes wrong, and two fixes that backfire

The planner prices the three from estimates, and on the customers-and-orders query the break-even point it worked from was about a third of the one measured. To find the real one, I ran that query at 17 sizes, from 10 customers to all 200,000, and forced each algorithm in turn with enable_hashjoin, enable_mergejoin and enable_nestloop set to off for the session.

The two cost shapes from the plans explain the whole table. Nested loop pays per customer, about 0.06 ms for each one’s index lookup and page reads, so its line is straight. Hash join pays mostly for one scan of the orders table, so its line is flat. They cross near 5,000 customers, which is 125,000 orders, 2.5 percent of the table. At 200,000 customers the nested loop does 200,000 lookups to fetch every row of a table that a single scan reads in under a second.

Merge join tracks nested loop here, and for the same reason. To get orders in customer_id order it walks the same index, fetching scattered pages one at a time. It came out slightly ahead between 1,000 and 4,000 customers, probably because it walks the index once instead of starting a new search for each customer, and it stops as soon as the customer side runs out, so it never reads the rest of the orders index.

The planner is the surprise. It switched to hash join at 1,721 customers, when its own estimate reached about 1,695, and at 2,000 customers that choice cost 312 ms against 126 ms for the nested loop it rejected. It had the rows right. What it overpriced was the pages: the default random_page_cost = 4 tells it that a page fetched by an index lookup costs four times as much as a page read by a sequential scan, which is roughly right when the page has to come from a disk. In these runs every page was already in memory, so the lookups were much cheaper than the planner assumed.

That miss cost about two and a half times the time at 2,000 customers. A wrong row estimate errs in the other direction: it can keep a nested loop running long past the line. The PostgreSQL EXPLAIN post showed one source of wrong estimates in this data: the planner treats country and city as unrelated, so it multiplies their selectivities, the fractions of rows each filter keeps. Every city belongs to exactly one country, so the second filter removes nothing the first did not already remove. Here are customers in four countries and those countries’ 40 cities, 16,000 customers in total:

1
2
3
4
5

SELECT count(*), sum(o.total)
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE c.country IN ('C00','C01','C02','C03')
  AND c.city IN ('C00-0','C00-1', /* ...all 40 cities of those countries... */ 'C03-9');

1
2
3
4
5
6
7

 Nested Loop  (cost=0.53..122891.10 rows=32325 width=6) (actual time=0.043..1090.030 rows=399572.00 loops=1)
   Buffers: shared hit=119775 read=329022
   ->  Seq Scan on customers c  (cost=0.10..5274.10 rows=1293 width=4) (actual time=0.019..15.588 rows=16000.00 loops=1)
         Rows Removed by Filter: 184000
   ->  Index Scan using orders_customer_id_idx on orders o  (cost=0.43..90.70 rows=26 width=10) (actual time=0.004..0.066 rows=24.97 loops=16000)
         Index Cond: (customer_id = c.id)
 Execution Time: 1109.897 ms

The planner expected 1,293 customers, under its 1,700 switch point, and picked a nested loop. It got 16,000, and the inner side ran 16,000 times. The tell is on the outer side: estimated rows=1293, actual rows=16000.00, and an inner side whose loops matches the actual figure, not the estimate.

The table is the crossover chart again, seen through the estimate. At two to four countries the estimate stays under about 1,700 and the planner keeps the nested loop, up to 2.7 times slower than the hash join. At five countries the estimate crosses 1,700, and the planner switches even though the estimate is still ten times too low. A wrong estimate costs nothing while it stays on the right side of the line.

The fix is to tell the planner the columns are related:

1
2

CREATE STATISTICS customers_country_city (dependencies) ON country, city FROM customers;
ANALYZE customers;

With that, the estimate for four countries went from 1,293 to 15,820 customers, the planner picked the hash join on its own, and the query took 376 ms. MySQL has no equivalent for two columns that share no index (its histograms cover one column each), and with an index on the join column it would not change the join method anyway, for the reason in the MySQL section below.

The quicker reaction to a slow Nested Loop is to turn nested loops off and see what happens. That is a good experiment and a bad fix, because the setting changes every query on the connection, and a nested loop that was slow for 16,000 rows is still the right plan for 16. Christophe Pettus puts it plainly (July 2026): “Diagnose with the switch, then fix the statistics and set it back.”

The other obvious fix is memory. Batches above 1 under a Hash node means the hash table spilled to temporary files, as it did in the shipments join, and the natural response is to give it room. I raised work_mem from 1 MB to 1 GB on that join with the hash join forced, and did the same with MySQL’s join_buffer_size:

On both engines, the join got slower as it got more memory. In PostgreSQL the single in-memory hash table peaked at 297,571 kB, and the query took 60 percent longer than with 64 small batches. In MySQL the fully in-memory join took more than twice as long as the run that wrote 128 temporary files. I repeated the PostgreSQL runs in a different order, ten runs per setting in all, and the ranking held.

The explanation that fits is the CPU cache. Each probe of a hash table lands at a random spot, and a 290 MB table is far larger than the processor’s cache, so nearly every probe waits on main memory, while a batch of a few megabytes stays in cache for as long as it is being probed. I did not measure cache misses, so treat that as the likely reason rather than a proven one. There is also a caveat that cuts the other way: the temporary files here never reached a disk, since the container had memory to spare and the operating system kept them in its cache. On a server short of memory, where those writes really hit storage, batching costs more.

Small spills still cost something. MySQL’s default 256 KB join buffer is tiny: in the customers-and-orders join it spilled from 8,000 customers on, with 24 temporary files, and took 804 ms against 549 ms with a 4 MB buffer. So a few megabytes helped and a gigabyte hurt. Batches: 64 in a plan says the hash table spilled, which by itself says little about why a query is slow, and Part IV of the queries series covers why raising work_mem server-wide is risky anyway.

MySQL has two of the three, and picks one

MySQL added hash joins in 8.0.18, and in 8.0.20 they replaced the block nested loop, the older method for joining without an index. There is no merge join. The 8.4 manual says when the hash join is used: “for any query for which each join has an equi-join condition, and in which there are no indexes that can be applied to any join conditions.” With an index on orders.customer_id, the optimizer chose the nested loop at every size I tried. To get a hash join I had to hide the index with hints:

1
2
3

SELECT /*+ JOIN_ORDER(c, o) NO_INDEX(o orders_customer_id_idx) */ count(*), sum(o.total)
FROM customers c JOIN orders o ON o.customer_id = c.id
WHERE c.id <= 20000;

The crossover lands near 5,000 customers again, the same place as in PostgreSQL. The difference is that MySQL never makes the switch on its own. Both plans at 20,000 customers:

1
2
3
4
5
6
7
8

-> Nested loop inner join  (cost=990339 rows=981020) (actual time=0.21..2149 rows=500284 loops=1)
    -> Covering index range scan on c using PRIMARY over (id <= 20000)  (cost=8022 rows=39992) (actual time=0.148..2.01 rows=20000 loops=1)
    -> Index lookup on o using orders_customer_id_idx (customer_id=c.id)  (cost=22.1 rows=24.5) (actual time=0.099..0.107 rows=25 loops=20000)

-> Inner hash join (o.customer_id = c.id)  (cost=19.8e+9 rows=981020) (actual time=2.75..884 rows=500284 loops=1)
    -> Table scan on o  (cost=1.39 rows=4.96e+6) (actual time=0.0958..502 rows=5e+6 loops=1)
    -> Hash
        -> Covering index range scan on c using PRIMARY over (id <= 20000)  (cost=8022 rows=39992) (actual time=0.149..1.39 rows=20000 loops=1)

The cost MySQL printed for the hash join it was forced into is 19.8e+9, against 990,339 for the nested loop. Those are 20,000 times apart, and the runtimes go the other way, 884 ms against 2,149. Whatever the optimizer’s model of a hash join is, it is not one it uses to compete with an index.

What MySQL does change at larger sizes is the join order, which table goes on the outer side. From 50,000 customers on, it starts from the orders table, scanning all 5,000,000 rows once and looking up each order’s customer by primary key. That is still a nested loop, but its cost now grows with the orders scanned instead of the customers selected, which is why 50,000 customers ran faster than 20,000. At 200,000 customers it took 2,876 ms against 1,237 ms for the hash join. (MySQL’s optimizer, to its credit, is very consistent.)

For a reporting query that joins a large share of two big tables, the lever in MySQL 8.4 is an index hint like the one above. Merge join is not available, so the shipments join ran either as a nested loop (2,614 ms) or as a hash join (1,417 to 3,349 ms depending on the buffer).

What to check when a join is slow

Start by naming the join. Each algorithm leaves the same marks in every plan above:

Then read its outer side. If estimated rows and actual rows differ by more than a few times, the planner may have chosen for a size it never got, and the inner side’s loops will match the actual number. In PostgreSQL, rerun the query in one session with SET enable_nestloop = off or enable_hashjoin = off. If the other plan is much faster, the algorithm choice was the problem, and the estimate is what to fix: ANALYZE, a higher statistics target on the column, or CREATE STATISTICS for columns that move together. In MySQL the same test is a NO_INDEX hint on the inner table, and with an index on the join column a hint is also the only way to get a hash join.

If the estimate is right and the join is still slow, look at how many rows go into it. A nested loop with 200,000 loops, or a hash join building on millions of rows, is often a query asking for more than the screen shows. Batches above 1 comes last: in these runs a few more megabytes helped and a gigabyte hurt.