Checkpoint: Database Internals

You opened this section with a database as a box you send SQL to. It isn't a box anymore.

You followed one INSERT through the parser, the buffer pool, and the log, and learned that COMMIT is a log flush — the table file catches up later. You met the two structures the whole industry is built on: the B-tree, wide and shallow, three levels deep at ten million rows; and the LSM tree, which refuses to overwrite anything and merges its garbage later. You saw why a committed row survives a power cut, and why synchronous_commit is a dial with a loss window attached. You learned to aim a B-tree at your actual queries — and to count the write tax you just signed up for. You watched two transactions read the same row at the same instant and both be right. And you finally opened the planner's door and found that its famous intelligence is just arithmetic over a summary of your data.

Seven lessons, and one law running underneath all of them — though we never said it out loud until now:

Read amplification, write amplification, and space amplification are conserved. You can push any one of them toward zero only by shoving the slack onto the other two.

That's the RUM conjecture, and once you see it you can't unsee it. A B-tree buys fast, predictable reads and pays in write amplification. An LSM buys cheap writes and pays in reads and space. An index buys read speed and pays a write tax (~10× at five indexes). A covering index buys a skipped heap fetch and pays with a wider index. MVCC buys lock-free reads and pays in dead tuples and VACUUM. Nobody in this section ever got something for nothing.

So the question is never which one is faster. It is always: which amplification can this workload afford?

Two things to do before you move on. First, make that call three times, for real. Then take the exam.

Three real workloads, three sets of hard numbers — a required write rate, a p99 read budget, and a disk budget. Pick the storage engine for each and the lab prices it: the writes you can actually sustain, the read latency you'll actually see, the disk you'll actually consume, and the amplification you just agreed to pay.

Fair warning about the third one. It looks like a write problem. It is not. If you find yourself reaching for a database migration, stop and look at what the section actually measured.

Eight scenarios, each with a decision to make. These aren't definition questions — every one puts you in front of a real situation with real numbers and asks what you'd do.

The wrong answers are not random. Every distractor is a trap this section explicitly warned you about — so if one of them looks right, that's useful information: it tells you exactly which lesson to go back to, and the explanation will name it. Six out of eight to pass.

If you keep one page from Database Internals, keep this one.

• Durability is a log, not a table. COMMIT = one sequential WAL flush (~192 bytes, 0.568 ms). The data file lags on purpose. Recovery = repeat history from the redo point, then roll back everything with no COMMIT record.
• Fanout keeps trees shallow. 10M rows sit 3 levels deep; a lookup is ~4 page reads (0.018 ms) against 264 ms for the scan it replaced. Depth grows logarithmically — huge tables do not mean deep trees.
• The LSM is the mirror image, not the upgrade. Never overwrite, only append; merge later. It buys cheap writes with read and space amplification. Leveled = tidy space, more compaction work. Tiered = cheap writes, ~2× space. A delete adds a tombstone.
• Index for the reads, price the writes. Leftmost-prefix; covering (Heap Fetches: 0); partial (2.6 MB vs 13 MB). Five indexes made the same inserts ~10× slower. And creating an index does not mean the planner will use it — it correctly ignores a non-selective one.
• Versions, not locks. xmin/xmax + a snapshot decide what you see, so readers never block writers (5.8 ms vs a writer-on-writer block of 2,114 ms). The bill arrives as bloat and VACUUM, gated by the xmin horizon — an old snapshot, not merely an open transaction, is what pins your garbage.
• The planner is arithmetic over a summary. Cost is dimensionless, and the formula predicts EXPLAIN's number to the decimal. Three joins, and the winner is just whichever cost line is lower at your N. N is an estimate — and the estimate is the weak link (rows=1 where the truth was 2000). Read EXPLAIN for surprise, not for slowness. Fix the input, not the conclusion.

And the thread through all of it: nothing here is free. Every structure in this section is a bet about which amplification you can afford to pay. Say that out loud in an interview — "a B-tree trades write amplification for predictable reads; an LSM makes the opposite trade; and my workload is X, so I'd take Y" — and you are no longer reciting database trivia. You are reasoning about storage the way the people who build these engines do.

Next — Replication Topologies, and the whole game changes. Everything you just learned assumed one machine. One buffer pool, one log, one truth. Section 3 puts a second machine in the picture, and the moment there are two copies of your data, a new question appears that a single database never had to answer: which copy is right?