The output does not grow with the input

Why is aggregation the one operator that can be done in pieces, and how do hash and sort aggregation spend memory?

Every operator so far produced output in proportion to its input. A filter shrinks the input by its selectivity. A join multiplies by how often keys repeat. A sort keeps the row count exactly. Aggregation is the first operator whose output size is almost independent of its input size. N rows go in, G groups come out. G is set by the domain of the data, not by its volume. A billion rows grouped by country produce about two hundred rows.

That single fact generates the whole article, because it allows something a join can never do. Since the output is a summary, the summarizing can happen before the data is brought together. Each machine collapses the rows it holds, and only the collapsed form travels over the network. A join cannot do this: you cannot "pre-join" one partition, because a matching row may live on any other machine. Aggregation is the only operator here that can be legally and profitably done in pieces before the pieces meet.

So the main question is not "hash or sort?" It is: can the reduction happen early, and if not, why not? The answer is almost entirely a property of the aggregate function, not of the engine. That is why the classification from the algebra of aggregate functions (distributive, algebraic, holistic) is used so heavily here.

---

The core tension, as one ratio

Let N be the number of rows, G the number of distinct groups, and P the number of partitions (here, executors).

• Without partial aggregation, the shuffle (the step that moves rows between executors so that equal keys meet) moves all N rows.
• With partial aggregation, each partition first reduces its local share to at most min(N/P, G) rows. The shuffle then moves at most min(N, P·G) rows.

The reduction factor is

which is the average number of rows per group per partition.

Production engines therefore do not decide this at plan time. They sample the first tens of thousands of rows, measure the hash table's hit rate (how often a row finds its group already in the table), and abandon partial aggregation if the reduction is not happening. This exploits an information gap. The planner had only an estimate of NDV (the number of distinct values), and NDV estimates are the least reliable statistic in any catalogue. The executor sees the real keys.

---

Hash aggregation, and the spill choice the algebra makes for you

A hash aggregation keeps one table entry per group: the key plus a fixed-size accumulator (the running value, such as a sum). For each input row it finds the group's entry and updates it in place.

Two properties distinguish it from the hash join you studied earlier. Both are easy to carry over wrongly.

1. State is O(G), not O(N). A hash join's build side holds every row of one input. A hash aggregation holds only each distinct key once. The table is also simpler: no chains for multiple matches, and fixed-width accumulators updated in place. So it is much more cache-friendly than a join's build table with the same number of entries. It also uses the other equality (grouping equality, where all NULLs fall into one group), so it is not even the same comparison function as a join's.

When memory fills, there is a choice a hash join does not have

A holistic aggregate cannot use the second strategy, because it has no mergeable partial result.

The third strategy produces a surprise. Under a skewed distribution of groups, a small resident set absorbs most rows. Suppose the top 1% of groups carry 60% of the input.

So skew, which was the enemy in every earlier article, is an asset here. The same Zipf distribution (a very uneven distribution where a few keys are huge and most are tiny) that caps a distributed join's speedup at 14x makes a hash aggregation's working set small.

This sharpens the "maximum, not mean" principle from the start of this mechanism. "Variance costs more than volume" is true when the work is proportional to the rows. It reverses when the work is proportional to the distinct values. A join's cost follows rows, so concentration hurts. An aggregation's cost follows groups, so concentration helps. The principle needs this boundary condition: concentration is expensive for operators that process rows and cheap for operators that reduce them.

---

Sort-based aggregation: O(1) memory, and the only cheap exact holistic

Sort-based aggregation sorts the input on the group key, then makes one pass holding a single accumulator and emits each group when it closes (when the key changes). Memory is O(1). The cost is the sort.

Two situations make this a good trade, not merely a safe one.

1. The query needs its output ordered by the grouping key. This is extremely common: GROUP BY x ORDER BY x is most of analytics. The sort was owed anyway, so the aggregation is free.
2. The input already arrives grouped. This happens with a clustered table layout, a bucketed table (a table stored pre-split by a key), or a previous merge join on the same key. Then the sort disappears and the aggregation costs only the pass.

A third situation is the one people miss. Sort by (group key, value), not by group key alone. Now every holistic aggregate becomes a position lookup:

• The median of a group is the row at the midpoint of the group.
• p99 (the value below which 99% of the values fall) is the row at 99% of the group's offset.
• The whole job is a counted scan.

Exact quantiles are the aggregate that hash aggregation handles worst, because it must keep every value of every group in memory. In the sorted plan they become the cheapest thing it does.

Sort-based aggregation is the only strategy that computes exact holistic aggregates without holding a group's full contents in memory. This is why it survived the hash era. It is not a legacy fallback. It owns two cases outright: exact holistic aggregates, and queries that need ordered output.