When an operator runs out of room, what does a sort write to local disk, and how does a grouping table differ?

## Two operators, two working sets Spilling means an operator that cannot hold its working set writing part of it out to disk attached to the worker and reading it back to finish the step. What it writes depends entirely on what the operator was holding and why. A **sort** must hold every record in this unit of work's share before it can emit the first one in order. Its working set grows with the **number of records**. A **grouping table** — the in-memory table an aggregation builds, one entry per distinct key seen so far — only has to hold one accumulator per key. Its working set grows with the **number of distinct keys**, not with the number of records. A billion records over fifty keys is nothing; ten million records over ten million keys is the same size as the input. ## How a sort spills 1. Fill the space the operator can borrow with incoming records. 2. Order what is held and write it out as one **ordered run** on local scratch disk. 3. Empty the space and carry on, producing run after run. 4. At the end, read the runs **together**: keep one record from each in memory and repeatedly emit the smallest, refilling from whichever run it came from. Step 4 is the important one. The final pass does not need to hold all the data — only a read buffer per run and one record from each. That is why sorting far more data than memory is an ordinary operation rather than an impossible one, and why a sort that spills usually writes each record once and reads it once. ## How a grouping table spills 1. Build entries, one per distinct key, updating the accumulator for a key already present. 2. When the table no longer fits, write the entries it currently holds as **partial results** for those keys, then start an empty table. 3. Carry on. The same key can now appear in several flushed batches, because after a flush the table no longer knows it was seen. 4. At the end, bring together the partials for each key and apply a merging function to them. The difference that matters is step 4. It is cheap when two partial results for a key can be merged into one — a running sum, a count, a minimum, a sum and a count carried together for a mean. It is expensive when the accumulator is large, and it does not work at all when the aggregation needs every value for a key present at once, such as an exact median over the whole group. Where an aggregation cannot be expressed as merged partials, the operator has nothing useful to flush, and the shortfall becomes a failure rather than a slowdown — that is a separate subject from spilling. | | A sort | A grouping table | |---|---|---| | Working set grows with | records in this unit of work's share | distinct keys seen | | What is written out | ordered runs | partial results for the keys held so far | | What the final pass does | reads runs together, taking the smallest next record | merges partials for the same key | | Cheap when | always, given enough room for one buffer per run | partial results merge pairwise | | Badly behaved when | the room per run buffer is too small for one pass | the aggregation needs all values for a key at once | ## What varies between engines The shapes above are the class's shapes, but the trigger and the accounting differ: - Where a single pool is divided dynamically between operator working memory and results the job was told to keep, the point at which either operator spills moves during the run, depending on what else is held. - Where the engine reserves a block it manages itself as packed bytes, the spill point is stable and the records written out are already in a compact layout. - Where the operator spills out of a buffer whose size is fixed before the job starts, the spill point does not move at all and is the author's to set. - Some engines partition the grouping table by key before flushing so that each key's partials land together; others sort the flushed entries instead. Both end at the same place by different routes. - A continuously running job usually aggregates into what it remembers per key between records rather than into a transient grouping table — a different store with different sizing, owned by the state subject, not this one. ## The practical reading When a sort spills, expect roughly one write and one read of the data, and suspect trouble when the volume read back is several times what was written. When a grouping table spills, ask about distinct keys first: adding memory helps for a while, whereas an aggregation whose partials merge pairwise stays comfortable at almost any key count, because it never has to hold more than one accumulator per key per flush.