When Merge Join Beats Hash Join #

A hash join is the default answer for large equality joins, and usually the right one. But it has a hard requirement — the build side must fit in memory or it spills — and a hard limitation: it cannot produce sorted output or stop early. A merge join has neither property. When its inputs arrive already ordered, it holds almost nothing in memory, streams results, and can be stopped by a LIMIT.

This page identifies the three situations where the merge is the better shape and shows the plan evidence for each. The pair-wise comparison with nested loops is covered in merge join vs nested loop.

The Three Conditions #

1. Both inputs are already sorted on the join key. An index scan on the join column, or a GROUP BY that already ordered its output, supplies the ordering for free. The merge then costs a single interleaved pass — no build phase, no memory.

2. The hash build side would spill. A hash join with Batches: 32 writes and re-reads its build side, and its cost grows non-linearly. A merge over indexed inputs has predictable, mostly sequential I/O.

3. Sorted output is needed anyway. If the query ends in ORDER BY on the join key, a merge join delivers it, while a hash join forces a separate sort of the full result.

The counterweight is duplication. When many inner rows share a key, the merge join must mark its position and re-scan that group for each matching outer row, which is why high-cardinality keys such as identifiers favour merges and low-cardinality flags do not.

Hash join versus merge join, phase by phase The hash join column shows a blocking build phase, a probe phase, high memory proportional to the build side, and unordered output. The merge join column shows no build phase, an interleaved single pass, constant memory when inputs are sorted, and ordered output. Hash Join Merge Join phases build (blocking) probe phases one interleaved pass, streaming memory ∝ build side · spills past the allowance memory one key group output order unordered — needs a Sort for ORDER BY output order sorted on the join key, for free

Annotated Evidence #

The same join, forced both ways on a workload where the hash side spills:

-- Hash join: the build side does not fit
Hash Join  (actual time=18220.4..39810.1 rows=4120334 loops=1)
  Hash Cond: (e.session_id = s.session_id)
  ->  Seq Scan on events e  (actual rows=48000000 loops=1)
  ->  Hash  (actual rows=12000000 loops=1)
        Batches: 32  Memory Usage: 65536kB
  Buffers: shared read=182400, temp read=214880 written=214880
Execution Time: 39810.1 ms

-- Merge join over two index scans: no build, no temp files
Merge Join  (actual time=0.08..21402.6 rows=4120334 loops=1)
  Merge Cond: (e.session_id = s.session_id)
  ->  Index Scan using events_session_idx on events e  (actual rows=48000000 loops=1)
  ->  Index Scan using sessions_pkey on sessions s  (actual rows=12000000 loops=1)
  Buffers: shared hit=412088 read=98420
Execution Time: 21402.6 ms

Both indexes supply the ordering, so there are no Sort nodes and the join holds only the current key group. The temporary I/O disappears completely, which is what makes the merge 1.9× faster here despite touching more index pages.

The early-termination case is even more lopsided:

-- Same join with ORDER BY session_id LIMIT 100
-- Hash: must build the entire hash table before the first row can be emitted
Limit  (actual time=39810.2..39810.4 rows=100 loops=1)
  ->  Sort  (actual rows=4120334 loops=1)  Sort Method: external merge  Disk: 412880kB
Execution Time: 41204.8 ms

-- Merge: streams in key order, so the LIMIT stops the whole pipeline
Limit  (actual time=0.09..0.31 rows=100 loops=1)
  ->  Merge Join  (actual rows=100 loops=1)
Execution Time: 0.36 ms

Step-by-Step Comparison #

  1. Check what ordering already exists. An index on the join column of either side is the precondition for a free merge:

    SELECT indexrelid::regclass, pg_get_indexdef(indexrelid)
  FROM pg_index WHERE indrelid = 'events'::regclass;

  2. Look for spill evidence on the current hash plan. Batches > 1 plus temp written is the strongest argument for trying a merge.

  3. Force each method inside a transaction and measure:

    BEGIN;
SET LOCAL enable_hashjoin = off;    -- see the merge plan
EXPLAIN (ANALYZE, BUFFERS) SELECT … ;
ROLLBACK;

  4. Watch for injected Sort nodes. A merge plan containing two sorts of the full inputs is usually worse than the hash plan; the merge only wins when the ordering is supplied.

  5. Make the ordering free rather than forcing the join method:

    CREATE INDEX CONCURRENTLY events_session_idx ON events (session_id);

  6. Check inner-side duplication before committing. Many rows per key means repeated mark-and-restore work:

    SELECT count(*)::numeric / count(DISTINCT session_id) AS rows_per_key FROM sessions;

  7. Reset the diagnostic settings and confirm the planner now chooses the merge on its own. If it does not, the cost model still prefers hashing — investigate the estimates rather than pinning the method.

Choosing between the two join methods A decision tree: if both inputs are already sorted on the join key, prefer merge join. Otherwise, if the hash build side spills or the query needs ordered output, consider adding an index to enable a merge. Otherwise keep the hash join. large equality join inputs already sorted on the key? yes Merge Join no hash spills, or ORDER BY on the key? yes → index the key enable the merge keep the Hash Join

Before and After #

-- BEFORE: hash join, build side spills into 32 batches
Hash Join   Batches: 32   temp read=214880 written=214880
Execution Time: 39810.1 ms

-- AFTER: index on events(session_id) makes both inputs ordered
Merge Join  no Sort nodes, no temp figures
Execution Time: 21402.6 ms      -- and 0.36 ms with ORDER BY … LIMIT 100

The metric that changed is temporary I/O, not CPU. That matters because temporary traffic is the part of the cost that degrades fastest under concurrency.

Common Pitfalls #

Forcing a merge with enable_hashjoin = off in production. The setting applies to every join in every subsequent statement on that connection. Diagnostic signal: EXPLAIN (SETTINGS) reporting it. Fix: use SET LOCAL for diagnosis, then fix the underlying cost inputs.

Accepting a merge plan that sorts both inputs. Two full sorts usually cost more than one hash build and can spill just as badly. Diagnostic signal: Sort nodes with Sort Method: external merge under the merge join. Fix: supply the ordering with an index, or stay with the hash.

Ignoring inner-side duplication. Mark-and-restore over large duplicate groups is quadratic in the group size. Diagnostic signal: a merge join much slower than its input scans suggest. Fix: check rows per key, and prefer hashing on low-cardinality join columns.

Assuming the merge avoids all memory pressure. Only pre-sorted inputs give constant memory; injected sorts consume work_mem. Diagnostic signal: Disk: figures on the sorts. Fix: index the join keys.

Memory held over the life of each join The hash join line rises steeply during the build phase and stays at a plateau until the probe finishes. The merge join line stays flat and low throughout, holding only the current key group. execution time → memory Hash Join — build, then hold Merge Join — one key group at a time

Frequently Asked Questions #

Why does the planner rarely pick a merge join? Because it normally has to sort both inputs, and two sorts cost more than one hash build. It becomes competitive only when the ordering is free — from indexes or a previous operator — or when the hash side would spill heavily.

Does a merge join need less memory? With pre-sorted inputs, far less: it holds only the current key group from each side. If the plan has to add explicit sorts, those consume work_mem and can spill exactly like a hash table.

What is mark and restore? When several inner rows share a join key, the executor marks its position and re-scans that group for each matching outer row. Large duplicate groups make this costly, which is why merge joins suit high-cardinality keys.