Grouping, Duplicate Elimination, and Grouping Sets

GROUP BY looks like a single operator and is implemented as three different ones depending on what the query needs. The output is a set of groups, each identified by a key and each carrying the accumulated state of every aggregate in the select list. How that set is produced, and in what order, changes the cost and the plan shape.

The operator also carries a rule that surprises people: after grouping, the only columns available are the grouping columns and aggregate results. Every other column reference is an error, because there is no single value to return for a group. Products that permit it return an arbitrary member’s value, which is a nonstandard extension and a source of nondeterministic results.

What grouping computes, and why duplicates matter

Conceptually, grouping partitions the input rows by the grouping key and then applies each aggregate to each partition. The partition’s identity is the key; two rows with the same key are in the same group. NULL is a key value like any other, and all rows with a NULL key form one group. That is different from WHERE x = NULL, which never matches, and from the equality used in joins, which treats NULL as unknown.

Duplicate elimination is grouping with an empty aggregate list. SELECT DISTINCT a, b FROM t is equivalent to SELECT a, b FROM t GROUP BY a, b. Implementations often route DISTINCT to the same operator, which is why a DISTINCT over a large result set has the same memory profile as a group-by with the same key width.

The number of groups is what determines cost. Grouping ten million rows into ten groups needs ten states and can be done with a hash table of ten entries; grouping into ten million groups needs a table as large as the input, and the operator degenerates into a copy. This is why an aggregate over a high-cardinality key is expensive even when the aggregate function itself is trivial, and why the planner’s estimate of group count matters as much as its estimate of input rows.

Sort-based grouping and the ordered-output bonus

The sort-based form sorts the input on the grouping key, then walks it once, closing a group whenever the key changes. It needs memory only for one group’s aggregate states, plus whatever the sort needs. The sort’s cost dominates: O(N log N) comparisons and, if the input exceeds memory, the external merge passes described in external merge sort.

Its advantage is output order. Groups emerge in key order, so an ORDER BY on the grouping columns is free, and a downstream merge join on those columns can consume the output directly. The planner tracks this: a sort-group plan that happens to satisfy the query’s ordering requirement can be cheaper than a hash-group plan plus an explicit sort, even when the sort-group is more expensive in isolation.

A second advantage is bounded memory for the aggregate states. A group is closed as soon as its key changes, so an aggregate with an unbounded state, such as a distinct count or a median, holds only one group’s state at a time. The hash form must hold every group’s state simultaneously, which is where such aggregates spill.

Hash-based grouping and its spilling behaviour

The hash form keeps a table from key to aggregate state, updates it per input row, and emits at the end. It needs no sort, so its cost is linear in the input, and it emits groups in hash order, which is no order at all.

Its memory requirement is proportional to the number of groups times the state size. When that exceeds the grant, the operator partitions by key exactly as a hash join partitions its build side, processes each partition independently, and concatenates the results. The same skew problem applies: a dominant key makes one partition large, and recursive partitioning cannot fix a single hot key.

The hash form is preferred when the group count is small relative to the input and the query does not need ordered output. It is also preferred when the input is already unordered and the sort would be an extra pass, which is most cases. The planner’s choice between the two is a cost comparison, and the cost comparison depends on an estimate of the group count that comes from statistics on the grouping columns. The mechanics of the hash table itself are the same ones a hash join uses, including the partition-and-spill fallback.

A hybrid exists in some systems: hash the input into partitions, then sort each partition. This combines the linear pass with bounded memory per partition and is the standard fallback when the hash table does not fit.

ROLLUP, CUBE, and the union of group sets

A grouping set is a list of grouping columns. GROUP BY GROUPING SETS ((a), (b), ()) produces three sets of groups in one result: groups by a, groups by b, and one grand total. ROLLUP (a, b) is shorthand for the sets (a, b), (a), () — a hierarchy from most detailed to grand total. CUBE (a, b) is every subset of the two columns, so four sets: (a, b), (a), (b), ().

The naive implementation is a union of separate aggregations, each scanning the input. That is n scans for n grouping sets, which is the obvious approach and the one a planner will choose when the sets are few and the input is small.

The efficient implementation computes the most detailed grouping set first, then derives the coarser sets from it. If the input is grouped by (a, b), the groups by a are obtained by re-aggregating the (a, b) result: sums add, counts add, minimums take the minimum of the minimums, and averages need the sum and count kept separately. Each aggregate function must supply a combine function for this to work, and functions without one force a rescan.

-- three grouping sets, one scan of the input if the plan is good
SELECT region, product, sum(amount)
FROM sales
GROUP BY GROUPING SETS ((region, product), (region), ());

The order of the sets in the output is unspecified, and a row’s identity within a multi-set result is ambiguous without the GROUPING() function, which returns 1 for a column that is aggregated away in that set and 0 for one that is present. That distinction is what lets a query tell “total for region X” from “total for region X, product NULL”, which are different rows that would otherwise look identical.

Aggregates that do not decompose

Some aggregates are not expressible as a combine of two partial states. A median needs the full multiset of values; a count(distinct x) needs the set of distinct values; an ordered-set aggregate needs the ordering. For these, the grouping operator must either hold the entire group’s data or use an approximation.

The standard workarounds are structural. A count(distinct x) can be rewritten as a group-by on (group_key, x) followed by a count, which moves the distinctness into the key and lets the outer aggregate be an ordinary count. That rewrite costs an extra grouping stage but bounds memory per group. Approximate distinct counts use a sketch whose size is fixed and whose error is bounded, which trades exactness for a memory bound.

Ordered-set aggregates, such as a percentile computed by interpolation over sorted input, require the group’s values in order. The sort-based grouping form handles this naturally: the group’s rows arrive in key order and, within a key, in whatever order the sort produced. If the aggregate needs its own ordering, that ordering must be part of the sort key, which means the sort is on (group_key, aggregate_order_key) and the operator reads the group’s rows in the required sequence.

The interaction with HAVING and with parallel plans

HAVING filters groups, so it is applied after aggregation. The planner can push parts of a HAVING predicate below the aggregation when the predicate references only grouping columns, because those values are constant within a group and the filter is equivalent to a WHERE. That pushdown reduces the input to the aggregate, which is the same optimization as predicate pushdown anywhere else.

Parallel aggregation splits the input across workers, each producing partial aggregate states for its share of the groups, and then combines the partials. The combine step is a second aggregation over the partial results, keyed by the same group key. This works only for aggregates with a combine function; for the non-decomposable ones, the parallel plan must either repartition by group key so that each group is handled by one worker, or serialize the aggregation.

Repartitioning by group key is the general solution and costs a shuffle: every worker’s rows are routed to the worker that owns their key. The shuffle is a hash partition, so it inherits the skew problem, and a single hot group lands entirely on one worker. The alternative, partial aggregation followed by a combine, avoids the shuffle but requires the combine functions and can produce many more partial groups than final groups when the input’s key distribution is skewed.

Both strategies appear in plans as a pair of aggregate nodes, one below the exchange and one above, and reading that pair is the quickest way to tell whether a plan aggregates in parallel or serializes at the shuffle.