Costing a Parallel Plan: Workers, Gather, and the Serial Fraction

Parallelism is the one plan transformation that can make a query faster without doing less work. Two workers scanning disjoint ranges of a table perform the same page reads in aggregate as one worker performing them serially, and the wall-clock time halves if nothing else intervenes. The reason it does not simply halve is that the plan acquires new costs which the serial plan did not have: starting workers, distributing work, moving rows from workers to the leader, and combining partial results. The planner’s model of a parallel plan is therefore the serial cost divided by a degree of parallelism, plus a set of terms that do not divide.

The interesting engineering is in those extra terms, because they are what make the answer to “should this query be parallel” depend on the query’s size rather than only on the machine’s core count.

What gets divided and what does not

Consider a sequential scan of P pages feeding an aggregate. Serial cost is roughly P page reads plus N tuple operations. A parallel plan splits the scan into d workers, each reading P/d pages, and adds a Gather node that receives rows from all workers and passes them to the leader. The scan and the tuple work divide by d. The Gather does not: it must move every row that the workers produce across a process boundary, and it runs in the leader as a single consumer.

PostgreSQL models this with two constants, one for the cost of launching and shutting down a worker (parallel_setup_cost, default 1000 in cost units) and one for the cost of transferring a tuple from a worker to the leader (parallel_tuple_cost, default 0.1). The setup cost is a fixed charge per query, independent of the amount of work; the tuple cost is proportional to rows, and it is deliberately priced above the CPU cost of processing a tuple serially, because the transfer involves shared memory, a queue, and a context switch rather than a function call.

The consequence is a U-shaped decision. Small queries lose, because a thousand units of setup cost dwarfs the work. Medium queries lose on the tuple transfer, because the Gather’s serial consumption becomes the bottleneck: adding workers increases the rate at which rows arrive at a node that can only drain them at one row at a time. Large queries win, because the divided work term eventually dominates both penalties.

The model also explains why the degree of parallelism is capped by a cost-based calculation rather than set to the core count. The planner computes the cost at each candidate degree and picks the one that minimises it, so a query whose Gather cost grows faster than its scan cost shrinks will be assigned fewer workers than the machine has. Raising the maximum worker count does not change that arithmetic; it only widens the range the planner may consider.

The leader is a serial section

Amdahl’s argument applies in a specific form here. Any part of the plan that runs only in the leader is a serial fraction, and its cost is not divided. The Gather node is the obvious one, but it is not the only one: a hash join whose build side is not parallel-aware builds its hash table in the leader, a sort that must produce a globally ordered result merges worker outputs serially, and a limit must be applied in one place because the workers cannot coordinate a global count.

A parallel hash join has two forms. In the partial form, each worker builds its own hash table over a slice of the build side, and each probes with its own slice of the probe side; the tables are separate and no sharing occurs, so memory consumption multiplies by the degree. In the full form, workers cooperate on a single shared hash table, partitioned among them, and each row is routed to the partition that owns its key. The full form uses memory once and divides the build work, but it requires every worker to see the entire probe stream, which means the probe side cannot be partitioned and its scan does not benefit from parallelism.

That trade is a genuine cost-model decision and it is visible in plans: a full parallel hash join sits above a parallel scan on the build side and a serial scan on the probe side, or vice versa. Neither arrangement is universally better, and the planner’s choice is driven by which side is larger.

Gather versus redistribute

Moving rows between workers is not always routed through the leader. A repartitioning exchange sends each row to the worker that owns its key, so that a subsequent operator sees all rows for a key in one place. This is how a parallel aggregation or a parallel join on a partitioned input avoids a serial bottleneck.

The cost of a redistribute is different in kind from a Gather. Rows travel between workers, which on a single machine means shared memory or a socket pair, and the exchange must buffer when a destination is slower than its senders. Skew in the distribution key concentrates rows on one destination, and the exchange’s throughput becomes that of its slowest partition. A redistribute on a key with a dominant value therefore behaves like a serial plan with extra copying, and the cost model that assumed uniform hashing does not see it.

Distributed systems extend the same model across a network, where the transfer cost is no longer a shared-memory operation but a network round trip with its own latency and bandwidth terms. The accounting is structurally identical: divided work, undivided coordination, plus a transfer cost that grows with rows. The difference is only in the constants, and in the fact that a network transfer has a fixed latency component that a shared-memory transfer does not.

Why parallel plans appear and disappear with table size

Because the setup cost is fixed and the divided work is proportional to size, there is a table size below which a parallel plan is never chosen and above which it usually is. The threshold moves with the constants and with the query: a scan of a small table that feeds an expensive per-row expression can still benefit, because the per-row term is large and divisible, while a scan of a medium table feeding a cheap filter does not.

The practical consequence is that a plan can flip from serial to parallel as a table grows past the threshold, and flip back if the table is truncated or if statistics change the estimated size. That flip is not a regression in either direction; it is the model working. It becomes a problem only when the flip happens between planning and execution, which is the same estimate-versus-reality gap that affects every other cost decision, amplified here because both sides of the comparison are large numbers.

There is a second threshold that is easy to miss: the number of rows a parallel plan must produce before the Gather cost is amortised. A parallel plan with a LIMIT is often worse than a serial one, because the workers cannot know when the global limit is reached without coordinating, so they either over-produce or the leader stops them after they have already done the work. Some implementations propagate a stop signal; those that do not will scan more than the limit requires.

Memory and concurrency multiply

A parallel plan’s memory grant is not divided among workers. Each worker receives its own grant for its own hash table or sort, so a query with four workers can consume four times the memory of the serial plan for the same operator. Systems that cap the total memory per query do so by reducing the per-worker grant, which then causes spills at a degree of parallelism where the serial plan would not have spilled; the spill itself is priced as described in memory limits and spill.

The concurrency effect runs the other way. A parallel plan occupies several worker slots, and the pool of workers is finite and shared. A single parallel query on an otherwise idle server gets the whole pool; the same query running alongside nine others gets a fraction, and the plan’s cost model, which assumed the full degree, no longer describes reality. This is the omission described in the anatomy of planner costs: the model prices a plan in isolation, and parallelism is the case where isolation is least representative.

A server that runs many small parallel queries can therefore spend more time in worker startup and coordination than in useful work, and the fix is a policy decision rather than a costing one: raise the setup cost, lower the maximum degree, or restrict parallelism to statements above a size threshold. All three are ways of telling the planner that workers are not free, which is the same information the cost constants already encode, expressed at a coarser granularity.

The plan is still an estimate

Nothing in the parallel model escapes the cardinality problem. The tuple transfer cost is proportional to the estimated row count, so an underestimate makes a Gather look cheap and pushes the planner toward parallelism on a query that will transfer far more rows than priced. The worker count is chosen from that same estimate, so a query whose real output is a hundred times the estimate may be assigned one worker where eight were needed, and the plan that was costed as a parallel scan executes as a nearly serial one.

The diagnostic is the same as everywhere else in this cluster: compare the estimated rows at the Gather node against the actual, and compare the actual worker count against the degree the plan declared. A parallel plan that used fewer workers than it declared has hit a limit in the worker pool; one that transferred more rows than estimated has an estimate problem, and its cost was never what the optimizer thought.