Aggregation and the GROUP BY Clause

An aggregate function takes a multiset of values and returns a single value summarizing them. SQL's standard aggregates are `COUNT`, `SUM`, `AVG`, `MIN`, and `MAX`. Applied without `GROUP BY`, an aggregate function collapses the entire result of the `FROM`/`WHERE` clause into one row — for example, `SELECT AVG(price) FROM sales` returns a single number, the mean price across all rows. The `GROUP BY` clause generalizes this by first partitioning the rows into groups based on equality of one or more attributes (the grouping attributes), and then applying the aggregate function independently to each group, producing one output row per group. Formally, if `G` is the set of grouping attributes, `GROUP BY G` defines an equivalence relation on rows: two rows are in the same group if and only if they agree on every attribute in `G`. The output relation has exactly one row per equivalence class, and every expression in the `SELECT` list must be either (a) a grouping attribute, whose value is constant within a group, or (b) an aggregate expression, which reduces the group to a scalar. This restriction is not a stylistic preference — it is a semantic necessity, because any other expression would not have a well-defined single value per group. The `HAVING` clause is a post-aggregation filter: it evaluates a condition over the aggregated values of each group and discards groups that fail it, analogous to how `WHERE` discards individual rows before grouping happens. Because `HAVING` operates after aggregation, its condition may reference aggregate functions (`HAVING COUNT(*) > 5`), while `WHERE`, evaluated before any grouping, may not.

Conceptually, SQL defines the evaluation order of a query with `GROUP BY` as a strict pipeline, even though a real optimizer may reorder operations internally as long as the result is equivalent: 1. Compute `FROM` (joins, cross products) to build the working relation. 2. Apply `WHERE` to filter individual rows. 3. Apply `GROUP BY` to partition the surviving rows into groups by the grouping attributes. 4. Apply aggregate functions to each group, producing one summary row per group. 5. Apply `HAVING` to filter out groups whose aggregate values fail the condition. 6. Apply `SELECT` to project the final columns (and any final expressions), and `ORDER BY` to sort. Two dominant physical algorithms implement step 3–4 inside a real query engine.

Sort-based grouping. Sort all rows by the grouping attributes; then scan the sorted output once, and every time the grouping-attribute value changes, a new group boundary is detected. Because equal keys are contiguous after sorting, a single linear scan can accumulate the aggregate for each group as it goes.

Hash-based grouping. Build an in-memory hash table keyed by the grouping attributes; for each row, hash its group key, look up (or create) the accumulator entry, and update it incrementally (e.g., add to a running sum, increment a running count). At the end, each hash bucket holds one finished group. ``` // Hash-based GROUP BY + aggregate + HAVING function GROUP_BY_AGGREGATE(rows, groupCols, aggSpecs, havingPred): table = empty hash map // key: tuple of groupCols -> accumulator state for row in rows: // WHERE has already been applied to `rows` key = extract(row, groupCols) if key not in table: table[key] = init_accumulators(aggSpecs) // e.g. count=0, sum=0, min=+inf, max=-inf for spec in aggSpecs: update_accumulator(table[key][spec], row, spec) // COUNT(): count += 1 // SUM(x): sum += row.x (skip if row.x is NULL, except COUNT()) // AVG(x): sum += row.x; cnt += 1 (avg computed at finalize) // MIN(x): min = row.x if row.x < min // MAX(x): max = row.x if row.x > max results = [] for key, accs in table: finalValues = finalize(accs) // e.g. avg = sum / cnt if havingPred(key, finalValues): // HAVING filters groups results.append(build_row(key, finalValues)) return results ``` ``` // Sort-based GROUP BY + aggregate + HAVING (streaming variant) function GROUP_BY_SORTED(rows, groupCols, aggSpecs, havingPred): sortedRows = external_sort(rows, key = groupCols) // O(n log n) results = [] currentKey = null accs = null for row in sortedRows: key = extract(row, groupCols) if key != currentKey: if currentKey != null: emit_if_passes(currentKey, accs, havingPred, results) currentKey = key accs = init_accumulators(aggSpecs) for spec in aggSpecs: update_accumulator(accs[spec], row, spec) if currentKey != null: emit_if_passes(currentKey, accs, havingPred, results) return results ``` Both algorithms only ever hold one accumulator per group in memory (not the raw rows), which is why aggregation can process arbitrarily many rows using space proportional to the number of distinct groups, not the number of rows.

Time complexity.

• Sort-based grouping: dominated by the sort, so `O(n log n)` comparisons for `n` input rows, plus one linear pass `O(n)` to accumulate aggregates. If the sort must spill to disk (external merge sort, since aggregation is often used on tables far larger than memory), the cost is `O((n / B) log_{M/B}(n / B))` I/Os, where `M` is memory size and `B` is the block size — the standard external-sort bound.
• Hash-based grouping: expected `O(n)` time overall, since each row does `O(1)` expected work for a hash lookup/insert (assuming a good hash function and load factor bounded by a constant); worst case `O(n^2)` under adversarial hash collisions, though practical implementations resize and rehash to keep this from happening. If the table of groups does not fit in memory, a hash-based external algorithm partitions rows into buckets by a first-level hash (like external hashing used in hash joins), recursing until each partition's group table fits in memory.

Space complexity. The crucial fact is that grouping algorithms need space proportional to the number of distinct groups, `g`, not the number of rows `n`, because only one accumulator (a few numbers: running sum, count, min, max) is kept per group — never the raw member rows. So space is `O(g)` for hash-based in-memory grouping, and `O(g)` auxiliary plus `O(n)` for the sort buffer in sort-based grouping (or `O(M)` per pass if external sorting is used, with total I/O as above). Since typically `g ≪ n` (e.g., grouping millions of sales rows into a few hundred stores), aggregation queries are far cheaper than sorting all columns of the full table would suggest.

Correctness argument. The correctness of `GROUP BY` rests on it defining a genuine partition (equivalence relation) of the input rows:

• Reflexivity/symmetry/transitivity of "agrees on all grouping attributes" is immediate from equality being an equivalence relation, so the groups are well-defined, disjoint, and exhaustive — every row belongs to exactly one group.
• Because groups are disjoint and exhaustive, applying an aggregate function to each group independently and unioning the results is equivalent to applying it to the whole relation partitioned that way — no row is double-counted or omitted, provided every row that survives `WHERE` is assigned to some group (this holds by construction, since the group key is total over the surviving rows, with `NULL` grouping values treated as a distinguished group per the SQL standard, since two `NULL`s are considered equal for grouping purposes though not for `=` comparison elsewhere).
• The accumulator update rule (init identity element, then fold rows in) is a commutative, associative fold for `SUM`, `COUNT`, `MIN`, `MAX` (and `AVG` derived from `SUM`/`COUNT` at the end), so the order in which rows are streamed into an accumulator does not affect the final result. This is exactly why both the sort-based algorithm (rows arrive sorted) and the hash-based algorithm (rows arrive in arbitrary order) produce identical, correct answers — associativity and commutativity make the fold order-independent.
• The restriction that non-aggregated, non-grouping columns cannot appear in `SELECT` is a soundness requirement, not a stylistic rule: such a column generally has multiple distinct values within a single group, so no single well-defined value exists to output for that row.

Tradeoffs. Sort-based grouping is preferable when the input is already sorted (e.g., via an index on the grouping column) — then the sort step is free and the algorithm becomes a single linear scan. Hash-based grouping is preferable when no such order exists and the number of distinct groups is small enough to fit a hash table in memory, since it avoids the `log n` sorting factor entirely. When the number of distinct groups is very large (close to `n`), hash-based grouping loses its main advantage and may thrash memory with a huge hash table, at which point sort-based (or hybrid hash/sort) strategies become competitive again — real optimizers (e.g., PostgreSQL, SQL Server) choose between `HashAggregate` and `GroupAggregate` (sort-based) plans using estimated group cardinalities.

Consider a `sales` table:

Query: ```sql SELECT store, product, SUM(qty) AS total_qty, AVG(price) AS avg_price FROM sales WHERE qty > 0 GROUP BY store, product HAVING SUM(qty) >= 5; ```

Step 1 — `WHERE qty > 0`. All 7 rows satisfy `qty > 0`; none are filtered.

Step 2 — `GROUP BY store, product`. Partition rows by the pair `(store, product)`:

Step 3 — apply aggregates per group.

Step 4 — `HAVING SUM(qty) >= 5`. Keep groups with `SUM(qty) >= 5`: `(A, shoes)` with 5 ✓, `(A, socks)` with 5 ✓, `(B, shoes)` with 4 ✗ (dropped), `(B, socks)` with 2 ✗ (dropped), `(C, shoes)` with 9 ✓.

Final result:

Tracing the hash-based pseudocode on this input confirms the same result: processing the 7 rows in order, the hash table accumulates exactly these five entries, and only three survive the `HAVING` predicate at finalize time — matching the table above regardless of row-processing order, precisely because `SUM` is a commutative/associative fold.

Aggregation and grouping trace back to the relational model itself and to the first SQL implementations that needed to support business reporting, historically the dominant use case for databases.

`GROUP BY` and aggregation are the computational core of business intelligence and analytics platforms: every "revenue by region," "daily active users," or "average response time by endpoint" dashboard compiles down to a grouped aggregate query. OLAP systems and data warehouses (star-schema fact/dimension designs) are built almost entirely around efficient large-scale grouping, often precomputing aggregates via materialized Views in SQL so expensive `GROUP BY` queries need not be recomputed from scratch on every request. Columnar analytical engines (e.g., those used in modern data warehouses) are specifically optimized for exactly this workload, since scanning a single column and grouping it is far cheaper than reading full rows. Query optimizers in systems like PostgreSQL, MySQL, and SQL Server choose between hash-based and sort-based aggregation plans automatically, and understanding this choice helps developers write queries (and design indexes) that steer the optimizer toward the cheaper plan. Grouped queries also frequently appear as the inner query of a Nested Subqueries pattern — for example, filtering outer rows based on a computed per-group aggregate — making a solid grasp of `GROUP BY` a prerequisite for more advanced SQL composition.

Ask the tutor: How would this query's execution plan change if there were a B+-tree index on the grouping column?