Cover

CMU Database Group · 1:17:56 · Watch on YouTube

Summary

Lecture 11 of CMU 15-445/645 (Fall 2024) moves up the stack from storage and indexes into query execution, covering the operator algorithms a DBMS uses when intermediate results are too large to fit in memory. Andy Pavlo works through top-N heap sort, external merge sort (its two-way form, its generalized B-way cost model, double buffering, and comparison-specialization optimizations), when a B+Tree index can replace sorting entirely, and then applies the same divide-and-conquer thinking to aggregations — contrasting sorting-based aggregation with external hash aggregation. The lecture closes with a guest talk from Drew, co-founder of dbt Labs, on bringing software-engineering practice — version control, lineage, CI/CD, testing, documentation — to data teams.

Type: university lecture (educational) + guest industry talk.

flowchart TD
    A["Query execution context<br/>operators can spill to disk"] --> B["Sorting"]
    A --> C["Aggregations"]
    B --> B1["Top-N heap sort<br/>ORDER BY + LIMIT"]
    B --> B2["External merge sort<br/>2-way → B-way"]
    B --> B3["Optimizations<br/>double buffering, comparison specialization"]
    B --> B4["B+Tree index<br/>skip sorting entirely"]
    C --> C1["Sorting-based<br/>free when ORDER BY exists"]
    C --> C2["External hash aggregation<br/>partition + rehash"]
    C2 --> D["Next class: joins"]
    A --> E["Guest talk: dbt"]

Topics

  1. Query Execution Context: Where Operators Fit — 0:27
  2. Why Sorting Is a DBMS Backbone — 5:33
  3. Top-N Heap Sort — 10:18
  4. External Merge Sort: Fundamentals and Materialization — 14:13
  5. Two-Way External Merge Sort — 21:19
  6. General B-Way Merge Sort and Its Cost — 29:58
  7. Sort Optimizations: Double Buffering and Cheaper Comparisons — 34:59
  8. Using B+Tree Indexes Instead of Sorting — 41:44
  9. Aggregations: Sorting vs Hashing — 48:32
  10. External Hash Aggregation — 52:36
  11. Guest Talk: Drew from dbt Labs — 1:05:39

Key takeaways

  • Operators must assume intermediate results spill to disk, so the DBMS reuses the buffer pool for temp data and deliberately picks algorithms that maximize sequential I/O and minimize random I/O — that single constraint drives every algorithm in this lecture 4:17 5:00.
  • Top-N heap sort sorts nothing and needs ~2 buffer frames: with ORDER BY + LIMIT, a single pass and a small priority queue produce the answer, skipping any value worse than the current heap maximum. Postgres implements it; leaderboards are the canonical workload 12:50 13:17 13:42.
  • External merge sort costs 2N × passes, with 1 + ⌈log₂ N⌉ passes at fan-in 2; widening the fan-in to B − 1 is what makes it viable at scale. Worked example: 108 pages with 5 buffers sorts in 4 passes (22 runs → 6 → 2 → 1) 28:23 28:54 33:37 34:14.
  • Fewer wide passes beat parallel narrow merges. Running many two-way merges in parallel still incurs many passes of re-reading and re-writing; spending all memory on one wide merge shrinks the tree and wins even with parallel I/O 31:35 32:07.
  • Double buffering halves usable memory to hide I/O latency — a large win when disk writes take tens (or hundreds, on S3) of milliseconds, and much less useful on fast disks. It requires non-blocking I/O in the disk manager 35:10 36:50 37:55.
  • Comparison cost is a real optimization target: function-pointer jumps executed a billion times are expensive. Postgres solves it at compile time with a Perl script that duplicates its sort implementation per data type — the C substitute for C++ templates; long strings can additionally be compared by prefix first 38:59 39:55 40:49.
  • An order-preserving index beats every sort algorithm, including top-N heap sort, because it fetches exactly the minimum pages instead of scanning all of them — but only if the index is clustered (or index-organized); unclustered indexes turn ordered retrieval into random I/O, except for small top-N results. Postgres requires an exact index match on the ORDER BY columns; Oracle and enterprise systems do not 42:07 43:19 44:58.
  • Hashing beats sorting for aggregation whenever the data must spill — the partition step guarantees matching keys land in the same bucket, so spilled data is never re-read to check for matches. The exception is a query that already has ORDER BY, where one sort satisfies both the aggregation and the ordering for free 49:16 51:50 1:02:09.
  • External hash aggregation is the exact buffer mirror of external merge sort: 1 input buffer + B − 1 output buffers (fan-out) versus B − 1 inputs + 1 output (fan-in). Every aggregate — AVG as (count, sum), MIN/MAX, SUM, COUNT — reduces to a running value in the phase-2 hash table 54:54 55:17 1:01:40.
  • dbt's core insight: Snowflake and most commercial data warehouses do not enforce uniqueness or not-null constraints — they only use them for query optimization — so dbt turns those into asserted, automatically run tests, and infers lineage automatically from Jinja ref/source calls rather than requiring manual declaration 1:12:27 1:13:26.
  • Those tests run on your warehouse bill, not dbt's — dbt executes the queries you tell it to, so inefficiency is expensive; mitigations like checking only the last seven days exist, and the justification is that bad data has cost companies millions to billions 1:16:06 1:16:28.