Spill is algorithm substitution

Why is spilling a change of algorithm rather than overflow, and what two problems does it buy?

CaseConstructed case · Amara at Voltara

5% spilled, 6 times slower

Yuki runs a join between one year of readings and the meter-owner table. The grant was too small, so the build side spilled. Only 5% of the build side went to disk. Amara expects a slowdown of about 5%. The query runs about 6 times slower.

Three more incidents follow in the same week:

A different join, on the column meter_id, never finishes. A faulty batch of meters reports the default id 0000000, and 300 million readings share that single key. The job spills, re-partitions, spills again, and keeps going.
During one bad hour, every query spills at once. The local NVMe drive is saturated, and everything slows down together, including queries that did not need to spill.

Finally, an executor (a worker process) is killed by the Linux OOM killer. Upstream stages that had already finished must run again, and the batch takes three times longer than normal.

None of this is a bug. It is what happens at the boundary where the grant runs out.

How it ends →

Everything so far was about fitting. This article is about the moment the grant runs out. First, fix the mental model:

The difference is quantitative. Suppose you "paged out part of the hash table." You would then generate random reads at page granularity against a structure designed for random access. That is precisely what swap does, and it is the worst access pattern the storage layer offers. Instead, a spilling operator abandons its algorithm and adopts a different one. The new algorithm's I/O is sequential by construction, because the operator partitions the data using a hash function it chose itself.

This is the theme of this mechanism for the fourth and last time, and its strongest quantitative case. The kernel cannot turn random access into sequential access, because it does not know the access pattern. The operator can, because it defined the pattern. The ratio between those two I/O patterns is about 20–50× on NVMe, and three orders of magnitude on the spinning disks this mechanism was designed for. That ratio is the entire reason database spill exists as something separate from operating-system paging.