Nested Loop Hash Join and Merge Join Compared in Plans

Every join in a plan is one of three algorithms, and which one the planner picks says a lot about what it expected. A nested loop where you expected a hash join often explains a slow query in one line. A hash join with eight batches explains one more. This article describes how each algorithm works, what it costs, how to read each in a plan and what to do when the choice looks wrong. It belongs to the series that reading EXPLAIN ANALYZE output in PostgreSQL step by step opens, and the SQL-side view of joins is in PostgreSQL joins explained with realistic examples.

Nested loop

Nested Loop  (cost=0.85..55.0 rows=12 width=40) (actual time=0.05..0.4 rows=14 loops=1)
  ->  Index Scan using customer_pkey on customer c  (actual time=0.02..0.02 rows=1 loops=1)
        Index Cond: (id = 42)
  ->  Index Scan using app_order_customer_idx on app_order o  (actual time=0.02..0.3 rows=14 loops=1)
        Index Cond: (customer_id = c.id)

The algorithm: take each row of the outer input (the first child), look up matching rows in the inner input (the second child), emit the pairs. Cost is roughly outer_rows × cost_of_one_inner_lookup. With an index on the inner side's join column, each lookup is a few page reads, so the plan is excellent for a small outer set: one customer and their orders, a handful of rows from a filter. Without an index, the inner side is scanned fully for every outer row, which is quadratic and the classic source of queries that take hours.

PostgreSQL has two refinements. Memoize (version 14 and later) caches inner results keyed by the join parameter, so repeated outer values skip the inner lookup. Materialize stores the inner result in memory for rescanning when the inner side has no parameter. A nested loop is also the only method for non-equality conditions (a.x < b.y) and for lateral joins that depend on each outer row.

Read it by loops: the inner node's loops equals the number of outer rows actually processed. A plan with loops=50000 on the inner index scan is a nested loop over 50,000 outer rows; at 0.03 ms each that costs 1.5 seconds. That is acceptable at 50,000, painful at 5 million.

Hash join

Hash Join  (cost=35.5..1830.0 rows=10000 width=40) (actual time=0.9..19.8 rows=9650 loops=1)
  Hash Cond: (o.customer_id = c.id)
  ->  Seq Scan on app_order o  (actual time=0.02..11.5 rows=9650 loops=1)
  ->  Hash  (actual time=0.8..0.8 rows=1000 loops=1)
        Buckets: 1024  Batches: 1  Memory Usage: 70kB
        ->  Seq Scan on customer c  (actual time=0.01..0.4 rows=1000 loops=1)

The algorithm: read the smaller input (the inner side, under the Hash node) into a hash table keyed by the join column, then stream the larger input (the outer side) and look each row up in the table. Cost is roughly the sum of reading both inputs, with no per-row index probe. It needs an equality join condition (=), no sorted input and enough memory.

The memory is work_mem times hash_mem_multiplier (default 2.0 since version 15). If the hash table exceeds it, PostgreSQL splits the join into batches: it partitions both inputs by hash into temporary files and joins one partition at a time. The Hash node shows Batches: 8 and the plan has temp read/written buffers. Batching is correct and slower, since every row is written and read once more. Remedies, in order of preference: reduce the rows entering the hash (filter earlier, select fewer columns), then raise work_mem for the session after checking how many such operations can run concurrently.

A hash join prefers the smaller side as the build input. If the estimate of which side is smaller is wrong, the planner may build the larger one and use much more memory than expected. In PostgreSQL 11 and later, parallel hash joins let several workers share one hash table.

Merge join

Merge Join  (cost=0.85..2500.0 rows=100000 width=40) (actual time=0.05..210.0 rows=98000 loops=1)
  Merge Cond: (o.customer_id = c.id)
  ->  Index Scan using app_order_customer_idx on app_order o  (actual time=0.02..90.0 rows=100000 loops=1)
  ->  Index Scan using customer_pkey on customer c  (actual time=0.02..20.0 rows=100000 loops=1)

The algorithm: both inputs sorted on the join keys are walked in parallel, advancing the side with the smaller key and emitting matches, like merging two sorted lists. Cost is the cost of producing sorted inputs plus a linear pass. When both inputs arrive sorted from indexes, as above, it is cheap and uses almost no memory, and it can stream results without waiting for the full input. When an input needs an explicit Sort, the cost includes the sort, which can spill to disk.

Merge joins win for large inputs that are already ordered, for queries that need output ordered by the join key (the sort is not wasted) and for non-hashable equality comparisons. They are less common than the other two in everyday plans. A merge join can also be a sign that a hash join would have lost for lack of memory.

Side-by-side

The cost shape is the key idea. A nested loop's cost multiplies, a hash and merge join's costs add. That is why a wrong estimate hurts a nested loop most: if the planner thinks there are 10 outer rows and there are 1,000,000, the multiplication runs away.

Why the planner picks the wrong method

Almost always, because of estimated row counts. The decision turns on the sizes of the inputs. If the planner believes the outer side has 5 rows after a filter, it picks a nested loop, and if the filter in fact keeps 500,000, the inner index scan runs 500,000 times. Causes of the bad estimate: stale statistics, correlated columns, a condition on an expression with no statistics, a join between two skewed columns. Each is covered in why the planner estimates the wrong number of rows.

The second cause is cost settings. random_page_cost at its default 4.0 makes the index probes inside a nested loop look expensive, which pushes the planner toward hash joins, and on SSD it can be too pessimistic. work_mem too low makes hash joins and sorts look costly. effective_cache_size too low undervalues indexes.

The third cause is the absence of a good path. A nested loop with a sequential scan on the inner side is what you get when the inner join column has no index. Adding the index changes the cost enough that the plan improves.

Testing a hypothesis

To see what a different join method would cost, change the planner's options for the session:

SET enable_nestloop = off;
EXPLAIN (ANALYZE, BUFFERS) SELECT ...;
RESET enable_nestloop;

There are enable_hashjoin, enable_mergejoin and enable_nestloop. Turning one off adds a large penalty and does not forbid it. If the alternative plan is much faster, the original choice came from an estimate or a cost setting that is wrong, and that is what to fix. Leaving the setting off globally leads to bad plans elsewhere.

Join order

The planner also chooses the order of joins, trying alternatives up to join_collapse_limit (default 8) and from_collapse_limit tables, beyond which it follows the order you wrote. For queries with many joins, the order affects the intermediate result sizes, and a wrong estimate in the first join propagates. Writing joins in a sensible order (most selective first) helps when the limit is exceeded. For dozens of joins, genetic query optimization (geqo_threshold, default 12) takes over, and results can vary between runs. If a plan changes unpredictably with many joins, consider reducing the join count with CTEs or intermediate tables.

When the join method is not the real problem

If the join is fast and the query is slow, look elsewhere: a sort, an aggregate over many rows or the cost of fetching wide rows. If the join reads far too many rows, the cure is a filter earlier in the query, an index that prunes or a different query shape, not a different algorithm. If the join is executed thousands of times by an application loop, the plan is fine and the application needs a set-based query. And if the plan is good in isolation but slow in production, check contention, caching and work_mem under concurrency. The method choice reflects the data and the settings; it rarely needs forcing.

What to do next

Take a slow join in your workload and write down for each join node the method, the estimated and actual outer rows, the loops and the batches. The pattern will tell you which of the three failure types you have. The manual describes the planner's methods in planner/optimizer and the settings in planner method configuration. Then see reading BUFFERS output in EXPLAIN.