Build sort and aggregate with a memory limit

The plan as a tree of steps, with the steps that must see every row before they can answer. Sort and aggregate are two of those steps; this lesson builds them with a limit on how much memory each may use.

Before you start. The plan, running watched Postgres sort and group with work_mem as the limit, and counted temp-file blocks as the sign of a spill. Sorting & Searching has merge sort in memory. This lesson builds the version that goes to disk, so you can see why the numbers in 0579 come out as they do. The code is in teaching/code/database-internals/02-sortagg; it reads Go.

The idea in 30 seconds

A sort that does not fit in memory writes sorted runs of memory size and merges them; each merge pass reads and writes every row once.
The number of passes grows with the number of runs divided by the fan-in, so ten times less memory means about one more pass, not ten times the work.
In the program, a million rows with memory for 1,000 took four merge passes and wrote 4,000,000 rows to temp files; with memory for all of them, nothing was written.
A LIMIT lets a sort keep only the N best rows in a small heap, with no temp file at all.
A hash aggregate whose groups do not fit writes the rows of groups it cannot hold into partitions by hash of the key, and aggregates each partition on its own; the spill is the share of data that did not fit.
AlphaSort’s point in 1994 still holds: if the data fits, a one-pass sort in memory beats any disk-based design.

Read the story · Skip to the numbers