SQL & Data Modeling — Part 2: Internals & Execution

maang.io System Design Series

What is this?

Back to our town library. In Part 1 we filed every fact onto exactly one card. Now watch what a great librarian actually does when you ask for a book. They don't walk two million shelves — that would take all day. They go to the catalog drawer, whose cards are sorted, and use the sorted structure to jump near the right card in a handful of steps, then walk a few cards to the exact one. And when you ask them to match "every order card against its customer card," they don't compare all cards against all cards; they pick a strategy based on how big each drawer is and whether either is already sorted.

That catalog drawer is a B+tree index, the jump-in-a-handful-of-steps is its logarithmic depth, and the matching strategy is a join algorithm chosen by the query planner. This chapter is the machinery that makes the clean-but-split schema from Part 1 fast to read.

The one-line idea: a relational engine keeps a B+tree beside each indexed column so lookups and range scans are logarithmic instead of linear, and a cost-based query planner uses table statistics to pick how to execute your declarative query — which index to use, which join algorithm, in which order — so the same SELECT can run in microseconds or minutes depending on the plan it chooses.

Let's build it up: the index structure, the read path through the planner, the join algorithms, the write path, then the deliberate decision to denormalize.