# DDIA Ch. 11: an aggregation's memory tracks distinct keys, not input size ## Concept Count how many times each URL appears in a log two ways: an in-memory hash table (`counts[url] += 1`) and the Unix pipeline `sort | uniq -c | sort -rn | head`. Both compute the same answer. Their *memory* does not scale with the same thing. Hold the input at **2,000,000 lines** and vary only the number of **distinct keys** — 1, then 1,000, then 100,000, then 1,000,000. A file of 2,000,000 *identical* lines costs the hash table exactly **one** dict entry (**20.8 MiB**, essentially interpreter baseline); push the distinct keys to a million and the same 2,000,000-line input now costs **156.1 MiB** — a **7.5×** swing driven purely by cardinality. The `sort` step over that same millionfold change in distinct keys moves only **1.34×** (264.4 → 354.4 MiB): its footprint is insensitive to how many distinct keys there are. A reader who expects "memory grows with the input" or "the hash table always needs less memory" has the wrong model. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 11 — *Batch Processing*, §"Sorting Versus In-Memory Aggregation". The book contrasts two ways a batch job groups-and-aggregates records: build a hash table of the aggregation state in memory, or sort the records so equal keys become adjacent and aggregate in one streaming pass. Its guidance: > If the working set... is smaller than the amount of memory available, [a hash > table] approach works fine... On the other hand, if the working set is larger > than the available memory, the sorting approach has the advantage that it can > make efficient use of disks. The exercise makes "working set" concrete: it is the count of **distinct keys**, and you watch the hash table's memory track exactly that while the line count stays fixed. ## Prerequisites The surprise is about *what* the working set of a GROUP BY actually is. Each line notes where the idea shows up. 1. **Hash aggregation vs. external sort** — the two GROUP BY strategies: keep one accumulator per group in a hash table, or sort so equal keys are adjacent and fold them in one pass. Shows up as the two ways the script counts the same file. *(DDIA §"Sorting Versus In-Memory Aggregation".)* 2. **Working set = distinct cardinality** — the memory a hash aggregation needs is one slot per *distinct* key, i.e. the GROUP BY cardinality, not the number of input rows. Shows up as the hash-table column tracking the distinct-keys column while the line count is pinned at 2,000,000. **This one carries the result.** *(Wikipedia, "Cardinality (SQL statements)".)* 3. **External merge sort spills to disk** — when the data exceeds RAM, sort reads it in chunks, sorts each chunk, writes sorted *runs* to disk, then merges them with a bounded buffer — so its memory is bounded by buffer size, not by input or cardinality. Shows up as the `sort` column staying flat in cardinality. *(Wikipedia, "External sorting".)* 4. **RSS measurement** — resident set size is the physical RAM a process holds; `resource.getrusage(RUSAGE_SELF).ru_maxrss` reports its peak (on macOS in **bytes**). Running each aggregation in a fresh subprocess isolates its peak. *(Python docs, `resource` module; `man getrusage`.)* ### Where to learn the prerequisites - **Hash vs. sort aggregation (#1):** DDIA §"Sorting Versus In-Memory Aggregation"; and any database-internals note on hash-aggregate vs. sort-aggregate operators. - **Working set / cardinality (#2):** DDIA's "working set" discussion — the single idea that, held against a fixed row count, explains the whole table. - **External sorting (#3):** Wikipedia, "External sorting" — the K-way merge and why a fixed merge buffer bounds RAM. If only one is new, make it **#2**: the working set of an aggregation is its distinct-key count, and that is the number the hash table's RSS follows. ## Environment macOS 26.5.2 (Darwin 25.5.0), arm64; Python 3.15.0a8, standard library only; BSD `sort`/`uniq`; no Docker; datasets are seeded and RSS is a real measurement (note: RSS varies slightly run-to-run and by allocator — the SCALING with distinct-key count is the reproducible result, exact bytes are approximate). `ru_maxrss` on macOS is in **bytes**; the script divides by 1024² and reports MiB. Each hash aggregation runs in its own subprocess so its `ru_maxrss` reflects just that run. BSD `sort` is measured under `/usr/bin/time -l`. ## Mental model Same file, two ways to group-and-count: - **Hash aggregation** — walk the file once, keep a dict `{url: count}`, and do `counts[url] += 1`. There is exactly **one slot per distinct key**, and all of them must stay resident until the pass ends (any future line could hit any key). So its memory is the size of the *set of distinct keys* — its cardinality — and is completely independent of how many times each key repeats. - **External sort** (`sort | uniq -c`) — sort the lines so equal keys become adjacent, then `uniq -c` counts each run in a single streaming pass needing only a one-key buffer. The sort itself doesn't hold the whole input as live accumulators: classic external merge sort spills sorted runs to disk and merges with a bounded buffer, so its RAM is governed by input size and buffer size, not by the number of distinct groups. The whole thing is one script, `code/sort_vs_hashtable.py`: it generates seeded datasets of a *fixed* line count and *varying* distinct-key count, runs each hash aggregation in a subprocess, and measures `sort` under `/usr/bin/time -l`. ### A measurement caveat, stated honestly macOS BSD `sort` **mmaps** its input, so its measured RSS reflects the mapped (file-backed, reclaimable) pages — bounded by the file's byte size, not by the distinct-key count. That is why its RSS here is a few hundred MiB and drifts up slightly with file size. It is *not* the coreutils spill-to-disk buffer, but it demonstrates the same load-bearing fact: **`sort`'s memory does not scale with cardinality.** The reproducible result is the scaling, not the absolute bytes. ## Setup ``` cd study/ddia/ch11/code python3 sort_vs_hashtable.py ``` The script builds ~50–58 MiB datasets in a temp dir (auto-cleaned) and takes about a minute end to end. Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — 2,000,000 identical lines **Predict.** The first dataset is 2,000,000 lines that are all the *same* URL (1 distinct key). The hash aggregation reads every line and does `counts[url] += 1`. Roughly how much peak RSS does that cost — does 2,000,000 records mean a big table? **Observe.** ``` distinct keys lines input hash-table RSS sort RSS ------------- ----------- --------- ---------------- ------------ 1 2,000,000 49.6 MiB 20.8 MiB 264.4 MiB ``` **20.8 MiB — essentially the bare interpreter.** Two million identical lines collapse to a dict with **one** entry. The records streamed past; only the *distinct* key stayed resident. Memory is not proportional to input size. ### Step 2 — hold the lines fixed, grow the distinct keys **Predict.** Every row below is the same 2,000,000 lines. Only the distinct-key count changes: 1 → 1,000 → 100,000 → 1,000,000. Does the hash table's RSS follow the (constant) line count, or the (growing) distinct-key count — and by how much from top row to bottom? **Observe.** ``` Peak memory vs. distinct-key count (input fixed at 2,000,000 lines): distinct keys lines input hash-table RSS sort RSS ------------- ----------- --------- ---------------- ------------ 1 2,000,000 49.6 MiB 20.8 MiB 264.4 MiB 1,000 2,000,000 52.1 MiB 21.2 MiB 301.2 MiB 100,000 2,000,000 55.7 MiB 35.8 MiB 308.5 MiB 1,000,000 2,000,000 58.2 MiB 156.1 MiB 354.4 MiB hash table: 20.8 MiB for 1 distinct key -> 156.1 MiB for 1,000,000 distinct (7.5x) -- tracks DISTINCT KEYS, same line count. ``` **The hash table follows the distinct-key column, not the line count.** Line count is pinned at 2,000,000 and input size barely moves (49.6 → 58.2 MiB), yet RSS climbs **20.8 → 156.1 MiB (7.5×)** — one resident dict slot per distinct key. The working set is the cardinality. ### Step 3 — the sort pipeline over the same cardinality swing **Predict.** The `sort RSS` column is BSD `sort` over the *same* four datasets. As the distinct keys span a millionfold range (1 → 1,000,000), does sort's memory climb like the hash table's, or stay roughly put? **Observe.** ``` sort: 264.4 -> 354.4 MiB over the same millionfold cardinality swing (1.34x) -- insensitive to distinct-key count; its RSS tracks input bytes (BSD `sort` mmaps the file). ``` **Sort barely moves — 1.34× against the hash table's 7.5×.** Its memory does not track how many distinct groups there are; the small drift it does show tracks the input's byte size (BSD `sort` mmaps the file). Cardinality is the hash table's cost, not sort's. ### Step 4 — do both methods actually agree? **Predict.** On the 1,000-key dataset, the hash table and the pipeline `sort | uniq -c | sort -rn | head` should rank the same top URLs. Will their top-5 *counts* be identical, or can the two routes disagree? **Observe.** ``` Both methods agree on the answer. Top 5 URLs of the 1,000-key dataset: hash: counts[url] += 1 sort | uniq -c | sort -rn | head -------------------------------- ---------------------------------- 200,322 0 200,322 0 51,931 1 51,931 1 36,539 2 36,539 2 28,954 3 28,954 3 24,460 4 24,460 4 identical top-5 counts: True ``` **Identical.** Same computation, two engines. The choice between them is never about the answer — it's about which resource each spends to get there. ## What you should see - 2,000,000 identical lines cost the hash table **one** entry — **20.8 MiB**, near interpreter baseline. - With the line count pinned at 2,000,000, hash-table RSS climbs **20.8 → 156.1 MiB (7.5×)** as distinct keys go 1 → 1,000,000. It tracks **distinct keys**. - Over that same millionfold cardinality swing, `sort`'s RSS moves only **1.34×** (264.4 → 354.4 MiB) — insensitive to cardinality; it tracks input bytes. - The hash table and the `sort | uniq -c | sort -rn | head` pipeline produce the **identical** top-5 counts. ## Why Grouping-and-aggregating is, mechanically, maintaining one *accumulator* per group: for "count hits per URL," the accumulator is an integer and there is exactly one per distinct URL. That is the irreducible state of the computation — the set of running totals you cannot yet finalize. The question is only where that state lives. **Hash aggregation keeps every accumulator resident.** The pass over the input is single, forward, and order-blind: at line *n* you cannot know whether key *k* will recur at line *n+1*, so every accumulator you have started must stay in the dict until the file ends. The resident state is therefore the *set of distinct keys seen so far*, which by the end is the full distinct-key set. This is why the line count drops out of the memory cost: a key that appears once and a key that appears two million times both occupy exactly one slot — `counts[url] += 1` mutates a slot, it never adds one. Memory = |distinct keys| × (per-slot cost). Two million identical lines → one slot → 20.8 MiB. A million distinct keys → a million slots → 156.1 MiB. The 7.5× is the million slots (plus their key strings) made resident; the 2,000,000 line count never enters the arithmetic. **Sort-based aggregation replaces resident state with adjacency.** If you first sort the lines, all copies of a key are contiguous, so `uniq -c` needs only *one* accumulator at a time: emit the count for the run that just ended, reset, move on. The distinct keys are never all live at once — they stream past finalized. The cost moves into the sort, and external merge sort is specifically the algorithm that bounds sort's RAM: chunk the input, sort each chunk in memory, spill sorted *runs* to disk, then K-way-merge them through a fixed buffer. RAM is governed by that buffer and the input's size, never by the number of distinct groups — which is why sort's column barely twitches (1.34×) while the hash table's swings 7.5× over the identical datasets. (On macOS the measured sort RSS is dominated by the mmapped input, which is bounded by file bytes for the same reason: still not cardinality.) **The boundary — when the hash table wins, it wins outright.** If the distinct keys fit comfortably in RAM, in-memory hash aggregation is both *simpler and faster*: one pass, no sort, no disk. Nothing here says "always sort" — at 1,000,000 distinct keys the hash table still used only 156 MiB and would beat sort on wall clock. The sort route earns its place only when the GROUP BY *cardinality* exceeds memory: that is the point where the hash table can no longer hold one slot per distinct key and would thrash or OOM, while external sort keeps streaming against disk. The deciding quantity is distinct-key count vs. available RAM — never the row count, which is exactly the intuition this exercise overturns. ### Go deeper 1. **Find the crossover.** Raise the distinct-key count (5M, 10M, …) on a machine where you can watch it, and find where the hash table's RSS crosses your free RAM. That threshold — not the line count — is where a query planner would flip from hash-aggregate to sort-aggregate. 2. **Hybrid hash aggregation with spill.** Real databases don't just pick one: they hash-aggregate until memory fills, then *spill* overflow partitions to disk and finish them separately. Sketch how you'd partition the keys by hash and recurse — you've rebuilt what Postgres and Spark do under memory pressure. 3. **Why planners estimate cardinality.** Because the choice hinges on distinct-key count, a cost-based optimizer must *estimate* GROUP BY cardinality before the query runs (from statistics/HyperLogLog sketches). Read how a planner decides between HashAggregate and GroupAggregate, and why a bad estimate is what makes an aggregation blow its memory grant.