Count URL hits with an in-memory hash table (counts[url] += 1) and with sort | uniq -c. Hold the input at 2,000,000 lines and vary only the distinct keys: 2,000,000 identical lines cost the hash table one entry (20.8 MiB), but a million distinct keys cost 156.1 MiB — a 7.5× swing at the same line count. Over that same millionfold cardinality change, sort's memory moves just 1.34×.
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.
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.
The surprise is about what the working set of a GROUP BY actually is. Each line notes where the idea shows up.
sort column staying flat in cardinality. (Wikipedia, "External sorting".)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.)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.
Same file, two ways to group-and-count:
{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.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.
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.
cd study/ddia/ch11/code
python3 sort_vs_hashtable.pyThe 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.
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?
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.
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?
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.
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?
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.
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?
Identical. Same computation, two engines. The choice between them is never about the answer — it's about which resource each spends to get there.
sort's RSS moves only 1.34× (264.4 → 354.4 MiB) — insensitive to cardinality; it tracks input bytes.sort | uniq -c | sort -rn | head pipeline produce the identical top-5 counts.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.)
Sources: DDIA 2e, Ch. 11, §"Sorting Versus In-Memory Aggregation" · Wikipedia, "External sorting" · Python resource module docs.