Relational engines can implement grouping and duplicate elimination either by hashing on the grouping key or by sorting the input and collapsing adjacent equal rows. Compare the two strategies and explain when a planner picks each.

## Two ways to answer the same question Grouping (aggregate per key) and duplicate elimination (distinct) are the same underlying problem: partition rows into equivalence classes by a key and produce one output per class. There are exactly two mainstream physical strategies. ### Hash aggregation Build a hash table whose key is the grouping columns. For each input row: hash the key, look it up, and either create an entry with an initialized accumulator or update the existing accumulator (`count+1`, `sum+=x`, and so on). When the input ends, walk the table and emit one row per entry. - **CPU:** ~O(rows) — one hash and one probe per row, plus the aggregate update. - **Memory:** proportional to **distinct groups × per-group state size**. Not to input rows. Grouping a billion rows into 12 status values costs 12 entries. - **Ordering:** input order irrelevant; output order arbitrary. - **Blocking:** yes — nothing can be emitted until the last row is seen, because a new row could still join any group. - **Overflow:** partition by hash of the key, keep some partitions resident, write the rest to temp files, and process spilled partitions after the input pass. Correct because equal keys always land in the same partition. A sharp edge: aggregates with **unbounded per-group state** — collecting arrays, string aggregation, exact distinct counts inside each group — make each entry large, so the hash table can be huge even at modest group counts. ### Sort-based grouping Sort the input on the grouping key, then scan it once: rows with equal keys are adjacent, so you accumulate until the key changes, emit, and reset. - **CPU:** the sort, ~O(rows · log rows) comparisons, plus a cheap linear pass. - **Memory:** the sort's memory; the grouping step itself holds only the current group's accumulator. - **Ordering:** requires ordered input, produces ordered output — an *interesting order* the optimizer can reuse for a downstream ORDER BY, merge join, or a later grouping on the same prefix. - **Blocking:** the sort blocks; if input already arrives ordered, the grouping step is fully streaming and can emit each group as its key boundary passes. ### The decisive comparison | | Hash | Sort | |---|---|---| | Memory driver | number of distinct groups | rows being sorted | | Cost when input already ordered | same as always | nearly free | | Output order | arbitrary | ordered on the key | | Behaviour with huge group counts | large table, likely spill | sort cost, graceful | | Behaviour with few groups | ideal | wasteful (sorts everything) | | First row latency | after all input | after all input, unless pre-ordered | ## How the planner decides The optimizer estimates the number of distinct groups from column statistics (distinct-value counts, possibly multi-column statistics for composite keys), multiplies by an estimated per-group state size, and compares that with the operator's memory budget. Roughly: - **Estimated groups small relative to the budget** → hash aggregation, because it avoids the sort entirely. - **Input already ordered on the grouping key** (index scan, merge join output, prior sort) → sort/stream aggregation, because the expensive part is already paid. - **Estimated groups approaching the row count** (grouping by something near-unique) → the hash table would be as big as the data; sorting is safer. - **The query needs ordered output anyway** → sorting amortizes across both requirements. - **Some aggregates are not hashable** in a given engine (certain ordered-set or user-defined aggregates) → forced sort path. Duplicate elimination follows exactly the same fork, since distinct is grouping with no aggregate function. ## The failure mode you will be asked about The dangerous case is a **hash aggregate whose group count was under-estimated** — commonly because the grouping key is composite and the columns are correlated, or because statistics are stale after a data shift. The planner sizes the plan for, say, 50,000 groups; reality is 40 million. The hash table blows its budget and either spills heavily or, in engines/versions where the aggregate could not spill, drives memory far past the intended limit. The symptom is a plan whose estimated rows out of the aggregate are orders of magnitude below the actual, with large temp-file activity. Remedies, in order: fix the estimate (refresh statistics, add multi-column statistics for correlated grouping keys); reduce per-group state (avoid array/string accumulation over huge group counts); pre-aggregate or pre-filter so fewer rows and fewer groups reach the operator; provide an ordered input via an index so the engine can stream-aggregate with near-zero memory; and last, raise the memory budget for that specific workload. ## What a strong answer sounds like Say that the two strategies trade **memory proportional to group count** against **an O(n log n) sort plus the gift of ordered output**, that the planner's choice hinges on the estimated distinct-group count versus the memory budget, and that pre-existing order flips the decision decisively toward sorting. Mentioning that hash aggregation's memory depends on distinct groups rather than input rows is the single line that separates candidates who have read plans from those who have not.