BOOKS DEEP-READ · DATABASE INTERNALS · CH 1
Database Internals · Ch 1 · Alex Petrov · 2019
You tap search in a shopping app and get results in a second; your colleague in finance runs a full-year report and waits half a minute. Both are "querying a database" — yet the machines behind them look nothing alike. Chapter 1 of Database Internals doesn't teach you to use a database. It takes the casing off so you can see, for the first time, which parts are inside and what each one does.
Think of a database as a large warehouse store. You hand in a shopping list: a greeter takes it; a clerk reads it and works out the least-walking route through the aisles; another clerk actually walks that route and picks the goods. And underneath all of that — the part that matters most — is how the shelves are arranged. That layer is called the "storage engine", and it is what the next several hundred pages of the book are about.
Here's the odd part: MySQL, Redis and ClickHouse all call themselves databases, but hand the reporting job to one and the checkout job to another and you can be a hundred times slower. The difference isn't the brand — it's how the goods are shelved.
One arrangement is packing each customer's basket together: everything about one order sits side by side, so looking up a single order is one reach — great for checkout. The other is shelving by category: every order's "amount" in one pile, every "date" in another. To total the year's revenue you sweep the "amount" pile and never touch another shelf — great for reports, and because everything in a pile looks alike, it also compresses beautifully.
Then there's where you keep it: spread across the counter (memory), within arm's reach but expensive and gone the moment the power cuts; or stacked in the warehouse (disk), cheap and still there after a blackout, at the cost of a walk every time.
The most valuable thing in this chapter is that the author hands you three "dials". Different settings give you essentially every storage design on the market.
One: batch it up, or not. Walk to the warehouse for every single item, or jot a few dozen on a sticky note and carry them over in one trip? Batching is far less work — but if that note goes missing you're in trouble, so you need a backstop.
Two: how you change things. Flip back to the original page and erase the old number, or write a new line at the end of the notebook and mark the old one void? The first saves space but you must find the page every time; the second is blazingly fast to write, at the cost of an ever-thicker notebook that needs periodic tidying.
Three: keep it sorted, or not. Alphabetised like a contact book, so everything starting with "S" is one continuous flip; or jotted down as it comes, found via an index. Sorted makes it easy to grab a whole stretch at once — but every new entry has to be slotted into the right place.
What this chapter really wants you to stop asking is "which database is best?" The question to ask instead is: does my job look at a handful of rows, or sweep a billion? Read-heavy or write-heavy? Is the hot data small enough to fit on the counter? The author also lands one uncomfortable warning: don't pick a database off someone else's benchmark — the workload they measured is almost certainly not yours.
The honest cost: none of the three dial settings is universally best — make writes faster and you generally pay it back in reads, in space, or in the tidying-up afterwards.
A database isn't a black box; it's four layers: take the request → plan the route → go fetch → and how things are shelved. The bottom layer decides what it's good at. And shelving comes down to three dials: batch before writing or not, erase-and-rewrite or append a new line, keep it sorted or not. Choosing a database is really choosing a setting for those three.
Want the real anatomy, the magnitudes and the case studies? → switch to Deep
You think you are choosing a database brand; you are really choosing a setting for three dials. This chapter first breaks the black-box word "database" into four layers — transport, query processing, execution, storage engine — then hands you three classification axes (memory vs disk, row vs column, data files vs index files), and finally collapses everything into the three variables that run through the whole book: buffering, mutability, and ordering. The remaining six hundred pages just fill in cells of that coordinate system.
8 KB, InnoDB to 16 KB).Alex Petrov is a contributor to Apache Cassandra. This chapter opens Part I, "Storage Engines", and doubles as the map for the entire book. In reading order it sits one level below DDIA: DDIA's Chapter 3 tells you what personalities LSM-trees and B-trees have; this book drills from here down into page layouts, splits and merges, and recovery protocols. It leads into Ch2–Ch7 (B-Tree basics, file formats, implementing B-Trees, transactions and recovery, B-Tree variants, log-structured storage) and then Part II on distributed systems.
"Database" is a worn-out black-box word: it covers PostgreSQL, Redis, ClickHouse and Cassandra at once — four systems whose internals differ more than a car does from a speedboat. Until you take the word apart, selection can only run on benchmarks and marketing.
The cost is concrete. A transaction system doing 20M orders a day, peaking at 5k QPS and touching one or two records per request, will degrade every single-row update into one write per column file if you put it on columnar storage. Conversely, a log table with 200 columns, 5B new rows a day, whose queries only ever aggregate three to five of them, will drag the other 197 columns off disk on every scan if you put it in a row store. Worse, this class of mistake hides during load testing — at small volumes the cache absorbs everything; only once you reach terabytes and the hit rate falls does it show its face in production.
So this chapter hands you a dissection grid. Petrov opens by admitting, honestly, that there is no single blueprint for database design — yet almost every system still fits one layered picture, and their real disagreements all reduce to three variables.
The part worth pausing on is the query optimizer: it estimates the cost of each route from table statistics and expresses the winner as a tree of dependent operations — the execution plan. The magnitude matters here: for a two-table join, "filter then join" versus "join then filter" can differ by orders of magnitude in rows scanned. What the optimizer saves is usually not 10%, it's 100×. The execution engine splits into local and remote, the latter being the part that fetches across nodes and stitches results back together — a foreshadowing of Part II.
Among the storage engine's five parts, the two most often conflated are the first two: the transaction manager guards logical consistency (both sides of a transfer succeed or neither does), while the lock manager guards physical integrity (bytes don't get mangled by two hands at once) — one is about business semantics, the other about concurrency safety. Access methods are the storage structures themselves (heap files, B-Trees, LSM-Trees); they decide what shape data takes on disk, and they are the entire subject of the next six chapters. That classic interview question — "walk me through how a SQL statement gets executed" — is answered by reciting these four layers.
Get the magnitudes straight first, because they are the reason this whole discipline exists: a random memory access takes about 100 ns; a random read from an NVMe SSD about 100 µs (~1,000× slower); a seek on a spinning disk about 10 ms (~100,000× slower). That three-order-of-magnitude gap is what forced pages, buffer pools and sequential writes into existence.
Disk-based systems keep data on disk and use memory only as a cache. Because disks can only be read and written in pages, you inherit a pile of problems that don't exist in memory — how to serialise a record into bytes, how to lay a page out, how to express a pointer as a file offset, how to get data that is "usually read together" onto the same page. The entire complexity of the B-Tree was forced out by exactly this. In-memory systems, by contrast, can use pointer-based structures directly (linked lists, skip lists) without contorting them to be disk-friendly — the implementation is actually simpler.
The commonest misconception is that in-memory databases aren't durable. Wrong: they persist via WAL plus periodic snapshots — writes are appended to an on-disk log, memory is dumped whole from time to time, and recovery loads the latest snapshot and replays the log after it. As for not fitting in memory: the disk-based answer is a buffer pool (memory holds copies of pages, the master copy is on disk); anti-caching inverts it — memory holds the master copy, and when it fills, the least recently used records are evicted to disk. The whole difference is in the phrase "which copy is authoritative".
Magnitudes for selection: hot data under 200 GB with a sub-millisecond p99 requirement — sessions, counters, leaderboards — makes in-memory a bargain. A 20 TB primary with heavily skewed access (5% of the data taking 90% of requests) does not: paying to hold 20 TB in RAM is buying what you don't need. Disk-based with a generous buffer pool is the answer.
Row-oriented: all of a record's fields sit adjacent on disk, so fetching a whole record takes one I/O — exactly what OLTP wants. Column-oriented: all values of a column sit adjacent, usually in their own file. A SELECT date, sum(amount) … GROUP BY date over a 200-column table needs to read 2 columns — theoretically 1% of the I/O of a row store. Better still, a single column's data is highly homogeneous — the same country code, the same date repeated endlessly — so it compresses an order better than row layout, saving both disk and the bytes dragged into memory.
The cost is equally concrete: a column store scatters one row across many files, so inserting or updating a single record becomes one write per file; and it needs an implicit positional id (the i-th value of every column belongs to row i) to put a row back together. Which is why column stores are almost always designed for bulk writes and very few updates.
Petrov goes out of his way here to correct a high-frequency misconception: BigTable / HBase / Cassandra — wide column stores — are not columnar databases. They organise data as a multidimensional map (row key → column family → column → timestamped version), and within a column family the layout is still row-contiguous. "Column" is in the name; the behaviour is closer to a row store. Calling Cassandra a "columnar database" is a classic interview deduction.
A database keeps two kinds of files: data files hold the records themselves, index files hold "how to locate a record fast". Data files come in three organisations: heap-organized — records piled in arrival order with no ordering maintained, fastest to write but unfindable without an index; index-organized (IOT) — the data lives inside the index structure, key-ordered, so a primary-key lookup lands in one shot and range scans are contiguous; hash-organized — bucketed by the hash of the key. The companion notion is clustered versus nonclustered: clustered means the physical order of records follows the index key order; nonclustered keeps data elsewhere, in unrelated order.
Then comes the most chewable trade-off in the chapter: what should a secondary index store?
PostgreSQL takes A, MySQL InnoDB takes B. This is not an academic disagreement — it directly determines how bad write amplification gets on a table carrying a dozen indexes, and Uber's evidence in the next section is the invoice.
The chapter closes on a sentence that turns out to be extremely useful: any storage structure can be described with three variables.
① Buffering — whether to accumulate a batch in memory before writing. The payoff is turning many small random writes into few sequential ones: on spinning disks sequential writes beat random ones by roughly two orders of magnitude, and on SSDs it cuts write amplification and spares the flash. The cost is that whatever is buffered vanishes on power loss, so it must be backed by a WAL. An LSM-Tree's memtable is the canonical example.
② Mutability — in-place update versus append-only. In-place saves space and keeps the read path short, at the cost of random writes, page fragmentation and concurrent writers on one page. Append-only writes extremely fast and is naturally sequential-I/O friendly, at the cost of space amplification plus the ongoing expense of background compaction — a record's many historical versions only disappear once merged away. A Copy-on-Write B-Tree (LMDB) is exactly the combination "B-Tree shape, immutable writes".
③ Ordering — whether records sit key-ordered on disk. Ordering buys range scans (WHERE date BETWEEN …) that read contiguously, at the cost of maintaining order on every write. Unordered (heap file plus hash index) writes fastest but only does point lookups.
These three are the book's coordinate system: for every structure that follows, ask first "where are its three dials set", then listen to the implementation. Far more useful than memorising names.
The chapter ends on something quite counterintuitive: comparing databases is far harder than it looks, and most public comparisons are untrustworthy. Three reasons — the benchmark's workload is almost certainly not yours; change the configuration, the hardware or the data distribution and the conclusion can invert; and the consistency and durability guarantees written in vendor documentation may simply not hold. Petrov's prescription: test with your own real workload (YCSB and TPC-C are a starting point, not a finish line); read the source, the issue tracker and the mailing lists to see what "known problems" look like; and for claims about distributed guarantees, look for independent third-party verification — he names Jepsen.
Table 1 · In-memory vs disk-based: where the master copy lives
| Disk-based | In-memory | |
|---|---|---|
| Master copy | On disk; memory holds a buffer pool of page copies | In memory; disk is for recovery (anti-caching evicts cold records) |
| Access latency | SSD random read ~100 µs, disk seek ~10 ms | ~100 ns — 10³–10⁵× faster |
| Structural complexity | High — page layout, serialisation, file offsets | Low — pointer structures work directly |
| Durability | Naturally on disk, plus WAL | Also durable: WAL + periodic snapshots, replay on restart |
| Cost ceiling | Cheap from TB to PB | Hard-capped by RAM capacity and price |
| Pick it when | Data is TB-scale and skewed (5% of data, 90% of requests) | Hot set <200 GB, sub-ms p99: sessions, counters, leaderboards |
Table 2 · Row vs column vs wide column — three things constantly conflated
| Row-oriented | Column-oriented | Wide column | |
|---|---|---|---|
| Disk layout | One row's fields contiguous | One column's values contiguous, own file | Row key → family; row-contiguous inside a family |
| Good at | Point reads, single-row writes (OLTP) | Wide aggregates over few columns (OLAP) | Keyed reads/writes over huge, sparse row sets |
| Typical I/O | One row = one I/O | 2 of 200 columns ≈ 1% of the bytes | One row ≈ one hop (per family) |
| Compression | Mediocre — mixed types per row | Strong — homogeneous, highly repetitive | Mediocre |
| Single-row update | Cheap | Expensive — one write per column file | Cheap |
| Examples | PostgreSQL, MySQL | ClickHouse, Vertica | BigTable, HBase, Cassandra |
| Common mix-up | — | — | Calling it a columnar database (wrong) |
Table 3 · Data file organisation and what the index references
| Heap-organized + direct reference | Index-organized (clustered) + PK indirection | |
|---|---|---|
| Where records live | A separate heap file, piled in arrival order | Inside the primary key index, key-ordered |
| Secondary index holds | The record's physical location | The record's primary key |
| Read via secondary index | 1 hop — faster | 2 hops — one extra primary index lookup |
| Updating one field | Record moves page → every index updated | Only the index whose field actually changed |
| Primary key range scan | Index ordered but data isn't → random I/O on lookup | Data itself is ordered → contiguous reads |
| Example | PostgreSQL | MySQL InnoDB |
| Where it hurts | Write amplification climbs sharply with index count | Longer secondary read path; a long PK fattens every index |
Table 4 · Common structures as dial settings
| Structure | Buffering | Mutability | Ordering | What you buy / what you pay |
|---|---|---|---|---|
| B-Tree | Low | In-place | Ordered | Steady reads, space-efficient; writes are random I/O, strains under heavy ingest |
| Copy-on-Write B-Tree | Low | Immutable | Ordered | Lock-free reads, simple crash recovery; every write copies the path's pages |
| LSM-Tree | Heavy | Append-only | Ordered | Huge write throughput, sequential I/O; reads consult many levels, compaction burns CPU and bandwidth |
| Heap file + hash index | None | In-place | Unordered | Cheapest writes, very fast point reads; no range scans at all |
Table 5 · Read it backwards: given a workload, where to set the dials
| Scenario | Defining load characteristics | Dial settings |
|---|---|---|
| Transactional primary | 5k QPS, 1–2 records per request, read:write ~10:1, many indexes | Row-oriented + disk-based + ordered; if write-heavy, prefer PK indirection |
| Ingest-heavy logs / events | Hundreds of thousands of appends per second, almost no updates | Heavy buffering + append-only (LSM family); avoid in-place B-Trees |
| Reporting / dashboards | 200 columns, 5B new rows a day, only 3–5 columns aggregated | Column-oriented; accept "bulk write, almost never update" |
| Sessions / counters / leaderboards | Hot set <200 GB, sub-millisecond p99 | In-memory; durability via WAL + snapshots — don't assume it isn't durable |
| Pure key lookups, no ranges | Only get(key) / put(key) | Unordered (heap + hash) is cheapest; ordering here is write cost paid for nothing |
The value of this chapter isn't its facts — it's that it gives you a grid that takes any database apart. Look at RocksDB: heavy buffering, append-only, ordered. LMDB: light buffering, immutable, ordered. Redis: master copy in memory, WAL plus snapshots underneath. Asked in an interview why Cassandra writes so fast but reads deserve caution, the answer isn't a memorised conclusion — it's reading its three dials aloud: writes are fast because of heavy buffering and append-only; reads deserve caution because one record may be spread across levels until compaction converges it. What follows are the invoices real companies have published for these trade-offs.
REPEATABLE READ exhibits lost updates and other anomalies, satisfying neither Adya's definition of repeatable read nor the ambiguous ANSI SQL one. An isolation level whose documentation says "repeatable read", measured and found otherwise: the hardest possible example of "don't trust vendor docs, look for independent verification". Jepsen, "MySQL 8.0.34", 2023 ↗CLUSTER command is a one-shot reordering of the table by an index; subsequent writes land unordered again. It maintains no continuously clustered structure.① This chapter is the book's map — it breaks the black box "database" into four layers, then collapses it into three variables.
② The anatomy: transport → query processing (parse + optimizer producing a plan) → execution engine (local / remote) → storage engine. Five parts inside the engine: transaction manager (logical consistency), lock manager (physical integrity), access methods (the structures themselves), buffer manager (page cache), recovery manager (WAL).
③ Memory vs disk is 100 ns against 100 µs against 10 ms — the page semantics of disk forced out the whole complexity of the B-Tree. In-memory systems are durable (WAL + snapshots); anti-caching differs from a buffer pool only in which copy is authoritative.
④ Row stores fetch a whole row in one shot; column stores touch only the columns used (2 of 200 ≈ 1% of the bytes) and compress better, at the price of expensive single-row updates.
⑤ Wide column ≠ columnar: inside a BigTable / HBase / Cassandra column family the layout is row-contiguous. The single most frequent misconception here.
⑥ Whether a secondary index stores a physical location or a primary key decides between a one-hop read and low write amplification — PostgreSQL and InnoDB sit at opposite ends, and Uber's 2016 migration was the invoice.
⑦ The book's coordinate system is three variables: buffering (random writes become sequential, must be WAL-backed), mutability (in-place saves space vs append-only writes fast but needs compaction), ordering (order buys range scans, disorder buys write speed).
⑧ Settings are structures: B-Tree = low buffering + in-place + ordered; LSM-Tree = heavy buffering + append-only + ordered; CoW B-Tree = low buffering + immutable + ordered; heap + hash = no buffering + in-place + unordered.
⑨ The author's warning: don't pick a database off public benchmarks — measure with your own workload, read the source and issues, and for distributed guarantees look for independent verification (Jepsen).
⑩ The caveat: there is no single blueprint for database design; the four-layer picture has already been pulled apart by disaggregated cloud architectures, but the three-variable taxonomy still holds.