What this lecture is about
- Previous lectures covered how to run a plan (processing models, parallel execution, physical operators like hash join / nested loop join / index scan). This lecture covers where those plans come from (
2:20,2:48). - Goal: go from a SQL query to a physical plan that the execution engine can run (
3:21). - The catalog is the internal metadata database: tables, columns, types, indexes (clustered/unclustered), tuple counts, page counts (
3:40,3:59).
The running example
SELECT employee names joined with departments on department ID, filtered to the "toy" department (3:21).
A naive, literal translation of the SQL into relational algebra gives: scans → cartesian product → join-predicate filter → department-name filter → projection (3:59).
Cost walkthrough: 2,000,000 → 37 I/Os
Each step below is a single change to the plan, with the resulting estimated I/O count:
| Step | Change applied | Estimated I/Os |
|---|---|---|
| 1 | Naive plan: cartesian product + materialization to temp files | ~2,000,000 (6:00) |
| 2 | Replace cartesian product with a page/block nested loop join | 54,000 (7:03) |
| 3 | Replace nested loop join with a sort-merge join | 7,000 (7:44) |
| 4 | Switch materialization model → vectorized/pipelined model (removes intermediate writes+rereads) | 3,000 (8:44, 8:55) |
| 5 | Push the department-name predicate below the join, swap inner/outer, use the index on department name and the index on department ID | 37 (10:21, 11:00) |
Assumptions used in the back-of-envelope math: 500 page reads for employees, ~1M for departments, ~2,000 matching join records, 50 employees per department under a uniform distribution assumption (which "causes problems for us later on") (4:47, 5:45, 6:00).
Note on step 4: most systems implement only one processing model and cannot choose between materialization and vectorization at plan time; the win instead comes from choosing operator order so you avoid unnecessary spilling to disk (8:55, 9:12).
Three warnings about this topic
- This is hard. The in-joke: if you fail at query optimization, your backup career is rocket science, because optimizing a SQL database is harder (
12:33). - The lecturer's weakest area. He names Thomas Neumann (the "German" behind Umbra) as the real expert — he wrote his own optimizer and one of the best engines from scratch (
13:14). - It pays. Database companies asking CMU for hires consistently ask for query-optimizer people; demand will not go away, and LLMs will not make the problem disappear (
13:37,14:00).