Gather Merge and Ordered Parallel Output #

An aggregation over 400 million rows runs with four workers and finishes in nine seconds. Adding ORDER BY to the same query makes it serial and takes forty. Adding a matching index instead keeps it parallel and takes seven. Ordering interacts with parallelism through one node — Gather Merge — and whether the planner can use it decides which of those three outcomes you get.

Worker coordination is covered in parallel query execution. This page covers ordered output.

The Condition #

Two nodes collect rows from parallel workers:

So an ordered parallel plan has two shapes:

Gather Merge  →  Sort (per worker)  →  Parallel Seq Scan
Gather Merge  →  Parallel Index Scan            (order from the index; no sort at all)

The planner compares those against the serial alternatives — a serial index scan that needs no sort, or Gather followed by one big sort in the leader. Which wins depends on how many rows reach the leader and whether an index provides the order.

Two cases where ordering defeats parallelism:

Window functions are a special case: WindowAgg runs in the leader, so a query with a window function can parallelise its scan and even its sort, but everything above the Gather Merge is serial — see window functions and top-N plans.

Two ways to collect worker output Left, Gather: workers send rows in any order, so the leader must sort everything afterwards if the query needs ordering. Right, Gather Merge: each worker sorts its own share or reads an index in order, and the leader merges the sorted streams, so no full sort is needed. Gather + Sort in the leader workers send rows unordered leader sorts the whole result sort memory for all rows serial sort is the bottleneck Gather Merge each worker's output is sorted leader merges sorted streams sort memory per worker no full sort in the leader an index providing order removes the per-worker sorts too

Annotated EXPLAIN Evidence #

Parallel with per-worker sorts:

EXPLAIN (ANALYZE, BUFFERS)
SELECT customer_id, sum(total) FROM orders GROUP BY customer_id ORDER BY customer_id LIMIT 1000;
Limit  (actual time=18402.6..18404.1 rows=1000 loops=1)
  ->  Finalize GroupAggregate  (actual time=18402.6..18404.0 rows=1000 loops=1)
        Group Key: customer_id
        ->  Gather Merge  (actual time=18402.4..18403.2 rows=4120 loops=1)
              Workers Planned: 4  Workers Launched: 4
              ->  Sort  (actual time=18104.2..18194.6 rows=824 loops=5)
                    Sort Key: customer_id
                    Sort Method: external merge  Disk: 412208kB
                    ->  Partial HashAggregate  (actual rows=762408 loops=5)
                          ->  Parallel Seq Scan on orders  (actual rows=18804422 loops=5)
Execution Time: 18410.2 ms
-- each worker sorted its own partial aggregate; the merge itself is cheap

With an index providing the order:

  ->  Finalize GroupAggregate  (actual time=0.09..6104.2 rows=1000 loops=1)
        ->  Gather Merge  (actual rows=4120 loops=1)
              ->  Partial GroupAggregate  (actual rows=824 loops=5)
                    ->  Parallel Index Only Scan using orders_customer_total_idx on orders
                          (actual rows=18804422 loops=5)
Execution Time: 6110.4 ms
-- no Sort nodes at all: the index supplies customer_id order to every worker

And ordering that forces a serial plan:

EXPLAIN SELECT * FROM orders ORDER BY placed_at DESC LIMIT 20;

Limit  →  Index Scan Backward using orders_placed_at_idx on orders
-- serial, and correct: 20 rows from an ordered index beats any parallel plan
Where the ordering comes from Three items are annotated. A Sort node inside the parallel portion means each worker sorted its own share. Gather Merge means the leader merged already-sorted streams. A parallel index only scan feeding Gather Merge means the index supplied the order with no sort at all. Sort … loops=5 (inside Gather Merge) each worker sorts its share Gather Merge merges sorted streams Parallel Index Only Scan → Gather Merge order from the index, no sort per-worker sorts each use their own work_mem allowance

Step-by-Step Resolution #

  1. Check which node provides the ordering: a Sort inside the parallel portion, or an ordered index scan.

  2. If per-worker sorts spill, either raise work_mem for the session — remembering that each worker gets its own allowance — or provide the order with an index.

  3. Create an index matching the ORDER BY so both the sort and its memory disappear:

    CREATE INDEX CONCURRENTLY orders_customer_total_idx ON orders (customer_id) INCLUDE (total);

  4. Accept serial plans for small LIMIT queries on an ordered index; parallelism has nothing to contribute when twenty rows are needed.

  5. Watch the leader’s share. Gather Merge merges in the leader, so a query returning tens of millions of ordered rows is limited by that single process; reducing rows before the merge — aggregating, filtering, limiting — matters more than worker count.

  6. Re-check Workers Launched, since an ordered plan that assumed four workers behaves differently with none.

Ordering and parallelism together A serial plan with one sort takes 41 seconds. Gather with a leader-side sort takes 28 seconds. Gather Merge with per-worker sorts takes 18.4 seconds. Gather Merge over a parallel index-only scan takes 6.1 seconds. serial, one sort 41.0 s Gather + leader sort 28.1 s Gather Merge + worker sorts 18.4 s Gather Merge + index order 6.1 s removing the sorts matters more than adding workers

Before and After #

-- BEFORE: per-worker external sorts feeding Gather Merge
Gather Merge → Sort (external merge, 412 MB per worker) → Partial HashAggregate    Execution Time: 18410.2 ms

-- AFTER: covering index provides customer_id order
Gather Merge → Partial GroupAggregate → Parallel Index Only Scan                    Execution Time: 6110.4 ms

Cost of merging in the leader #

Gather Merge performs a k-way merge over the workers’ streams, which costs a comparison per row in the leader process. For aggregated output — a few thousand rows — that cost is invisible. For a query returning ten million ordered rows, the leader becomes the bottleneck: workers can produce rows in parallel, but every row passes through one process to be merged and then through the same process to be sent to the client.

That gives a simple rule for ordered parallel queries: parallelism helps in proportion to how much the workers reduce the data before the merge. Aggregates, filters and limits reduce; plain ordered scans of large results do not. When a query must return millions of ordered rows, the realistic options are to give the client an index-ordered serial scan (which streams without sorting), or to question whether the ordering is needed at all.

Common Pitfalls #

Per-worker sort memory. Each worker uses its own work_mem, so five participants can use five times what a serial plan would. Diagnostic signal: memory spikes during ordered parallel reports. Fix: budget the total, or remove the sorts with an index.

Expecting parallelism with a small LIMIT. Serial ordered index scans win. Diagnostic signal: a serial plan for a top-20 query. Fix: none needed.

Large ordered result sets. The leader merges every row. Diagnostic signal: workers idle while the leader is busy. Fix: reduce rows before the merge.

Assuming Gather preserves order. It does not, and relying on accidental ordering breaks intermittently. Diagnostic signal: unordered results from a query without ORDER BY. Fix: always state the ordering you need.

Frequently Asked Questions #

What is Gather Merge in PostgreSQL? #

It collects rows from parallel workers whose outputs are each already sorted on the same key, and merges them so the combined output keeps that order. Plain Gather does not preserve any ordering.

Why did adding ORDER BY make my parallel query serial? #

Because the planner found a serial ordered index scan cheaper than sorting in workers and merging — often correct when a LIMIT is present, since only a few rows are needed.

Does each parallel worker get its own work_mem? #

Yes. Every participant’s sort or hash uses its own allowance, so a parallel plan’s peak memory is roughly the per-node budget multiplied by the number of participants.

Up: Parallel Query Execution