In-memory case

  • Build a hash table keyed on the group-by key; the value is whatever the aggregate needs (running total, sum, min, max) 52:36.
  • Scan the table once, probe the hash table, and act per aggregate — for DISTINCT, if the key already exists, throw the incoming key away 52:36.
  • One scan, done. The problem is only when the hash table grows too large 53:10.

The two-phase external algorithm

flowchart TD
    A["Input table"] --> B["Phase 1 — Partition<br/>hash h1 into B−1 output buckets<br/>spill full buckets to disk"]
    B --> C["Phase 2 — ReHash<br/>read partitions back in<br/>build in-memory hash table with h2"]
    C --> D["Emit result for those partitions,<br/>discard table, repeat"]

Phase 1 — Partition 53:29 53:56 54:29:

  • Scan the data once, hash each tuple on the aggregation key with hash function h1, write into unordered buckets.
  • When a bucket fills, spill it to disk and reuse the frame. Once written out, that data is never revisited during phase 1 56:02.

Phase 2 — ReHash 53:56 56:16 56:29:

  • Bring partitions back in one group at a time, hash them again with h2 into an in-memory hash table sized to fit the available buffers.
  • Emit that group's portion of the final result, discard the hash table, allocate a new one, and continue with the next partitions 57:13 57:50.

Buffer allocation is the mirror image of external merge sort

External merge sortExternal hash aggregation
Input buffersB − 11
Output buffers1B − 1
Data shapeFan-in: many runs collapse to one strideFan-out: one stride splits into many partitions

54:29 54:54 55:17

The correctness guarantee

  • Once a group of partitions is processed, it never needs revisiting: another matching key cannot exist on some other page, because h1 would have placed it in the same bucket. No stray record can corrupt the aggregate 56:54 58:59 59:24.
  • The net effect: replace random I/O over a giant hash table with sequential I/O over memory-sized chunks 58:28.

Aggregate values in the hash table

  • For DISTINCT the hash table is effectively a set — the value is nothing, just "does this key exist" 57:13 58:28.
  • For real aggregates, the key points at a running value that gets updated on each probe, or installed if absent 1:00:23.
  • Example — AVG(GPA) GROUP BY cid: store (count, running sum) per key, then divide sum by count at output time 1:00:52 1:01:15.
  • MIN/MAX keep the lowest/highest seen; SUM accumulates; COUNT increments by one. All aggregations can be computed this way 1:01:40.

Q&A

  • Why throw away the phase-2 hash table and build a new one? Because you no longer need that memory, and the table may be large 59:24.
  • Multiple rehashing rounds? Yes — if many keys hash into the same buckets (data skew), pick another hash function and repartition again. This is recursive hashing, covered next class 59:40 1:00:08.
  • Must phase-1 buckets hold one distinct key each? No — collisions are fine in both phases. It's an ordinary linear-probe hash table (or cuckoo, or whatever you prefer); the hashing scheme handles collisions exactly as in earlier lectures 1:02:50 1:03:20 1:04:00.
  • Where does the final result live? Not in the hash table — the client can't consume that. Each operator in the plan gets output buffers. Some systems stream results as soon as they're available, but most block until the output buffer is full, then return 1:04:11 1:04:44.
  • SELECT * FROM table on a billion rows will start paging as it writes buffers over the wire protocol — this is why systems ship built-in export functions that stream instead 1:05:12.

Closing takeaway and what's next

  • Hashing beats sorting when you must spill, because divide-and-conquer converts what would be random I/O into sequential I/O 1:01:40 1:02:09.
  • Next class: joins, where the sorting-vs-hashing distinction matters most — joins on very large tables are where databases spend most of their time 1:02:09.
  • The optimizations from this lecture — chunking to amortize cost, double buffering — carry over to hashing, joins, and other computations 1:02:34.