Sort, Hash, and Materialize: Memory Limits and Spill to Disk

Every operator that must hold state between input and output has a memory requirement, and every plan that exceeds the memory granted to it converts a linear in-memory operation into a multi-pass external one. The cost model charges for this in the aggregate, through a per-operator term and a spill penalty, but the transition itself is sharp: a hash table that fits produces one row per probe, and a hash table that does not fit produces two partitioned passes, each of which may itself be re-partitioned. The plan that the optimizer chose did not change. Its actual cost did, by a factor that can exceed an order of magnitude.

The quantity that determines which side of the transition a plan lands on is the estimated row count times the estimated row width. Both are estimates, and the width estimate is usually the cruder of the two. A planner that assumes a fixed width per column type, without accounting for variable-length data stored out of line, can underestimate the memory a tuple occupies by a large factor on a table with wide text columns.

What a hash join needs and what it does when short

A hash join builds a hash table over one input, the inner or build side, and probes it with rows from the other. The build side must be fully consumed before the first output row is produced, which gives the operator a high startup cost, as discussed in the anatomy of planner costs. The memory required is proportional to the number of build rows times the size of each hash entry, plus the table’s bucket array, which grows with the row count to keep the load factor bounded.

When the estimated size exceeds the memory grant, the operator does not simply fail. It partitions both inputs into a fixed number of buckets by hashing the join key, writes each partition to a temporary file, and then processes one partition pair at a time, building a hash table only for the partition currently in memory. This is the Grace hash join design, and its cost is the cost of writing both inputs and reading them back, plus the cost of the in-memory passes.

If even a single partition is too large, the operation recurses: that partition is repartitioned, its inputs written again. Depth of recursion is bounded by the number of passes the implementation allows, and the practical effect is that a badly sized build side can cost several times the cost of a single spill. The number of partitions is chosen at execution time, from the estimated size and the available memory, so the operator’s behaviour depends on a number the planner supplied rather than on a measurement.

PostgreSQL’s hash join adds a specific optimisation for the boundary case: when the build side slightly exceeds memory, it keeps as much of one partition in memory as fits and spills the rest, so a small overshoot costs a small spill rather than a full repartition. That is the hybrid design, and it is why the cost of a hash join as a function of build size is not a step function but a ramp: the first spill is cheap, and subsequent ones are not.

Sort: quicksort in memory, merge on disk

An in-memory sort of n rows is O(n log n) comparisons and needs memory proportional to n times the tuple width, because the sort must materialise its input before it can emit the first row. When the input exceeds the memory grant, the operator switches to an external merge sort: it sorts runs of whatever fits in memory, writes each run to a temporary file, and then merges the runs.

The number of runs is the total input size divided by the memory per run, and the merge fan-in is limited by how many file descriptors or buffers the implementation will allocate. With a fan-in of k, a merge pass reads k runs and produces one, so the number of passes is logarithmic in the run count. A sort of a billion rows with a memory grant fitting a million rows produces a thousand runs, which a merge with fan-in around a few dozen handles in two passes.

The cost model reflects this as a comparison between two formulas. A sort that fits is priced at n log n CPU operations plus the cost of the input. A sort that spills adds the cost of writing n rows and reading them back, and the transition is priced by checking the estimated size against the memory limit. Since the estimate is a number the planner computed and the limit is a configuration value, the decision is made before execution and cannot adapt to the actual input size.

This is the mechanism behind a plan whose sort node shows an estimated row count well below the memory threshold and an actual row count well above it. The plan was priced as an in-memory sort, the sort spilled, and the query took far longer than the cost suggested. Nothing about the plan text reveals the spill; the number of temporary blocks written appears only in the execution statistics, and only if the system reports them.

The width estimate is where memory estimates fail

Row width enters the memory calculation directly, and the standard approach is to assume a fixed width per attribute based on its type: 4 bytes for an integer, 8 for a timestamp, a nominal average for a variable-length string. That nominal average is a guess, and it is frequently wrong in one direction: a text column holding long documents is assumed to be a fraction of its real size.

The consequence is that the planner believes a hash table will fit when it will not. Because the memory grant is derived from the same estimate, the operator is given less memory than it needs and spills even though the server has memory available. Raising the global work memory limit helps, and it is the wrong fix, because the limit is per operation and raising it for the whole server trades one query’s spill for another’s out-of-memory risk.

A second width-related failure is the opposite: a table with many columns where the query selects only two. The planner’s width estimate may be based on the whole row rather than the projected columns, in which case it overestimates and grants more memory than needed. That error is benign in isolation and harmful in aggregate, because it reduces the memory available to concurrent operations.

Why the estimate’s error is amplified here

In an access path choice, an estimate that is off by a factor of ten changes which index is used and costs perhaps a factor of two in execution time. In a memory-sensitive operator, the same error crosses a threshold: below the threshold the operator is linear and in memory, above it the operator writes to disk and reads back, and the ratio is not two but the ratio of memory bandwidth to device bandwidth, which on a spinning disk is in the thousands and on flash is in the tens.

This is why the worst plans in practice are usually hash joins and sorts with wildly underestimated inputs, rather than wrong index choices. The optimizer’s arithmetic was internally consistent; it simply priced an operation as in-memory when the actual input made it external.

The mitigation is not to raise memory limits globally but to give the specific operator a realistic grant. Several systems do this by tracking, per plan node, the peak memory that node actually used across executions and adjusting future grants accordingly; the mechanism is a feedback loop between the executor and the memory allocator, and it operates independently of the planner’s estimate. It is the same family of runtime correction described in adaptive re-optimization during execution, applied to a memory grant rather than to a join order. Where that feedback does not exist, the estimate stands, and the plan’s cost is only as good as the width model behind it.

Choosing between hash and sort-merge when both can spill

A join on an equality predicate can be implemented as a hash join or a sort-merge join, and both have a memory-sensitive regime. The hash join’s cost is dominated by the build side; the sort-merge join’s by sorting both inputs. When both inputs are large and neither fits, the two converge in cost, because both pay for writing and reading temporary data.

The difference is in the shape of the input. A sort-merge join produces output in join-key order, which can eliminate a later sort, and it handles inputs that are already sorted at a much lower cost, because the sort step can be skipped. A hash join cannot use pre-existing order at all, and it is strictly better when the build side is small relative to the probe side, because then the build fits in memory while a sort of the probe side would not.

That asymmetry is why the choice depends on which side is smaller, not on the total size, and why a plan that builds a hash table on the wrong side pays for it twice: once in memory, and once in the loss of the opportunity to avoid a sort. The optimizer decides which side to build on by comparing estimated sizes, so an error in either estimate flips the decision, and the resulting plan may spill a hash table that would have fit had the sides been swapped.

Materialisation nodes sit between these choices. A materialise node caches its input so that a parent which reads it multiple times does not re-execute it, and it costs the memory or disk to hold the result. A nested loop whose inner side is materialised once and scanned many times trades that storage for the repeated execution, and the trade is favourable exactly when the inner side is small enough to hold. The same estimate that governs the hash table governs this decision, with the same failure mode.