Database Storage Primer

Row 42 is not a thing the storage engine can address. What it can address is a page in the heap file and a slot inside it — which together are the tuple's whole identity. Walk the file:

Notice that the address is arithmetic, not a lookup: page 12 begins at byte 98,304, because every page is the same size. That is the constraint the rest of this section lives under — variable-length rows have to fit a fixed-length box, and every engine solves it the same way, the slotted page.

Drawn in true proportion, an 8 KB Postgres page is a 24-byte header, a slot array growing down from it, and the tuple data growing up from the far end. Drag the slider to pack 104-byte tuples in, and watch the two ends close:

Notice the invariant the header exists to hold: pd_lower ≤ pd_upper, and the free space is exactly their difference. Each tuple costs 108 bytes — 104 for itself, 4 for its slot — so 75 of them fit and 68 bytes are left stranded. Push past 75 and the insert does not fail; it goes to a different page, which is why a table is an array and not a file of rows.

Nothing on that page is ever edited, either. Under MVCC an UPDATE writes a whole new version and marks the old one dead; whether the new one fits here is decided by fillfactor. Set it, then update the row:

At the default fillfactor of 100 there is no room, so every update lands on another page and writes an entry into every index on the table. Drop fillfactor to 90 and the same eight updates all become HOT — the index still points at the old line pointer, which is redirected, so no index page is touched at all.

Why 8 KB? Because the page is the unit of I/O, of caching, of most locking, and of log records, so its size moves every one of those at once. Step the slider through the five sizes these engines actually ship and watch the point read and the scan pull in opposite directions:

Because the point read moves a whole page for one 104-byte row, 4 KB pages amplify it 39× and 64 KB pages amplify it 630×. The scan pulls the other way: the same ten thousand rows are 271 page fetches at 4 KB and 17 at 64 KB. 8 KB and 16 KB are where the two curves are both tolerable, which is why every engine on that slider lives there.

A tuple has to fit in one page, and a 64 KB JSON document does not. Postgres's answer is TOAST: past a threshold the value leaves the page, and what stays behind is an 18-byte pointer to chunks in a sibling table. Grow the attribute and watch it go:

Watch where the dashed threshold sits — 2032 bytes, a quarter of the page, not the page size. Past it the value is compressed, then sliced into 1,996-byte chunks; 64 KB becomes 33 chunk rows. Reads are transparent. An UPDATE of a TOASTed column is not: MVCC writes a new row version, so all 33 chunks are rewritten to change one byte.

That is the disk. The reason a database is not simply unusable is the buffer pool: a hash table on (relation, page) holding pages in RAM. Move the hit ratio and watch how much of the mean read is the misses rather than the hits:

Notice that at 99% the bar is almost entirely rose. A hit costs 0.1 µs and an NVMe miss costs 100 µs, so one miss in a hundred already makes the mean 1.10 µs — eleven times the all-cached path. Ninety-five percent "sounds high" and measures 5.10 µs: 4.6× worse than 99% for a four-point difference. Hit ratio is not a linear dial.

The pool is finite, so admitting a page evicts one. Postgres uses a clock sweep: a hand walks the buffers decrementing a usage counter, and takes the first buffer it finds already at zero. Step it round:

Watch how long it takes. Nothing is evicted on the first pass, because every buffer had been touched at least once; the hand has to go all the way round before a victim exists. That is the point — the sweep approximates LRU without maintaining an LRU list, which would need a lock on every single buffer access.

Approximating LRU has a famous failure. A one-off sequential scan touches every page it reads exactly once, and under plain LRU each of those scanned pages displaces a hot one. Lengthen the scan and watch the hot set die:

With head insertion a sixteen-page scan leaves zero of sixteen hot pages cached, and the failure is silent: writes are unaffected, the scan itself is fast, and the damage shows up as a latency step on unrelated queries minutes later. Switch to InnoDB's midpoint insertion and the same scan can only ever reach the old 37% of the list — eleven pages survive any scan length at all.

Writes do not go to disk when they happen. A modified page is marked dirty and left in the pool; a checkpoint is what eventually forces all of it out. checkpoint_completion_target decides how much of the interval that flush is allowed to use. Drag it down and watch the flush rate leave the device budget behind:

Four gigabytes of dirty buffers over the default 0.9 of a five-minute interval is 15 MB/s — inside the budget, and invisible. The same four gigabytes at 0.05 is 273 MB/s, and the device does not have it: the kernel blocks in fsync, and every foreground query blocks behind it. This is the classic Postgres checkpoint stall, and it is a configuration bug, not a hardware one.

A B+tree is not a binary tree with extra steps. It is a tree whose nodes are pages, and a node holds as many children as fit in a page. That matters because the cost of a lookup is the number of pages touched, not the number of comparisons made — which is where a binary index loses to a B+tree immediately:

Watch the gap open as the table grows. At a billion rows the binary index is 30 levels deep and the B+tree is 4 — 7.5 times the page reads for the same answer, because each binary level buys one bit and each B+tree level buys nine.

So the branching factor is arithmetic, not design. A key plus an eight-byte downlink plus a four-byte slot is one entry; the node holds as many as the usable page divides into. Move both sliders and watch the fan-out move:

A 16 KB InnoDB page and a 16-byte key give 584 entries per node. Notice how hard the key width hits it: 64-byte keys — a VARCHAR used as a primary key, say — drop the same page to 215. That is a third of the fan-out for the same bytes of index, and it is where a wide natural key turns into an extra tree level.

Because every level multiplies by the fan-out, depth grows as the logarithm of the row count in base 584. Raise the number of rows through twelve orders of magnitude and count how often a level gets added:

Four levels address 116 billion rows. That is the answer to "how deep does it get" in production: not deep. A billion-row table is four page reads from root to leaf, and the root plus the level below it are 585 pages — nine megabytes — that never leave the buffer pool — so in practice a lookup is three cached probes and one that might miss.

Which is exactly what the planner bought when it chose users_pkey. Step through the descent: the levels already crossed, the page being searched, and at the end the heap fetch that leaves the index entirely:

Watch the readout jump at the last step. Four cached probes are 0.60 µs; the heap fetch, if it misses, is 100 µs — 167 times the entire descent that preceded it. This is why EXPLAIN output that looks identical can differ by two orders of magnitude at runtime, and why a covering index that answers from the leaf is worth so much.

Which the index can buy back, by carrying the query's payload columns in its own leaves — an INCLUDE list. Add columns and watch the index pay for it:

Carrying all three columns turns a 100.6 µs lookup into a 0.60 µs index-only scan — and grows the index from 18.7 GB to 86.2 GB, because each leaf now holds 177 entries instead of 818. Internal nodes are untouched: INCLUDE widens only the bottom, so the tree does not get deeper, it gets fatter.

The plus in B+tree is that leaves are chained. A range query descends once and then walks sideways. Raise the upper bound and compare one descent plus a walk against what a hash index would have to do:

At two thousand rows the B+tree reads 15 pages and a hash index does 2,001 separate lookups, because a hash index has no notion of the next key. That is the entire argument for ordered indexes, and it is why ORDER BY, MIN, MAX and every keyset-pagination query are free on a B+tree and impossible on a hash.

Inserts are where it costs. An entry goes into a leaf that has room — until it does not. Push keys into a leaf with room for eight and watch the ninth force a split:

Because a torn page cannot be repaired from a delta, Postgres logs a full 8 KB image of every page it touches for the first time after a checkpoint. A plain insert is about 100 bytes of WAL; the insert that splits rewrites two leaves and the parent, and costs 16 KB — 165 times as much for the same one row.

Which turns key order into a throughput decision. Sequential keys land on the rightmost leaf over and over; random keys land everywhere. Raise the insert count and flip between sequential and random UUIDs:

Two thousand sequential inserts dirty 10 leaf pages and emit 275 KB of WAL. The same two thousand as random UUIDs dirty 1,648 — the coupon-collector expectation over a 5,000-leaf index — and emit 13 MB. That is 49× the log volume, 49× the replication bandwidth, and a buffer pool full of pages touched once. Use v7 UUIDs, or a bigint, or accept the bill.

One more thing has to work: a reader descending while a writer splits the node underneath it. Plain latch coupling holds the parent until the child is latched; that is safe, but it serialises the path. Step the reader down and switch trees:

Because Lehman and Yao's B-link tree gives every node a right-link, a reader that arrives after the split follows one pointer sideways instead of restarting from the root. Postgres's nbtree is a B-link tree for exactly this reason: the split never has to hold a latch on the parent, so writers stop blocking readers on the way down.

The two structures answer the same question — where does this key live — with opposite policies. The B+tree keeps one sorted structure and edits it in place; the LSM keeps many, never edits one, and merges them later. Issue the same twelve writes to both:

Notice where the writes land. In place, twelve writes scatter across nine distinct pages, and each of those is a seek and a page rewrite. Appended, all twelve are consecutive in one file — the same twelve facts, recorded in arrival order instead of key order.

So a write never seeks. It appends to the log, inserts into an in-RAM memtable, and returns; only when the memtable fills does anything reach the tree. Drag the write volume up and watch SSTables appear:

Notice that nothing on that path is random. RocksDB's default 64 MB memtable means one flush per 64 MB written, and a flush is a single sequential file write of an already-sorted structure. The ceiling on writes is the device's sequential bandwidth, not its random-write IOPS — which on the same NVMe is a difference of roughly an order of magnitude.

An SSTable is not just sorted bytes. It carries its own index block — one entry per 4 KB data block — and a filter block, and both scale with the file. Grow one:

Notice how little that metadata costs: on a 64 MB table the index and the filter together are 1.8% of the file, and they are what let a lookup find one 4 KB block out of 16,384 with a single read — or skip the file without reading anything at all.

Those files cannot accumulate forever, so they are organised into levels where each holds ten times the one above. Raise the dataset size and count how few levels that takes:

A terabyte is five levels below L0. That is the same logarithm the B+tree gave us, in base 10 instead of base 584 — which is exactly why an LSM read is more expensive than a B+tree read, and by how much. The LSM has to look in more places because it has more places.

So a read walks down. Memtable, then every L0 file, then one file per level — and at each stop a bloom filter either skips the file for free or costs a real disk read. Step the lookup down:

Watch which stops are free. A bloom filter cannot produce a false negative, so a "no" is final and costs nothing but a few hashes; only a "maybe" touches the disk. Without the filters every read would fetch a block from every level — the whole structure would be unusable at any depth.

Filters are not free either: they are RAM, sized in bits per key. Raise the false-positive rate by starving them and watch the free skips stop being free:

At RocksDB's default of 10 bits per key the rate is 0.82%, which across six levels wastes 49 disk reads per thousand lookups and costs 1.16 GB of RAM for a billion keys. At 5 bits the RAM halves and the rate goes to 9.1% — 543 wasted reads per thousand. The exponent is 0.6185 raised to the bits per key, so every extra bit divides the error by 1.6.

Compaction is where the deferred bill arrives. Merging one level into the next rewrites the lower level about T times over, so write amplification is T times the number of levels — and read amplification moves the other way. Move the multiplier and switch strategies:

Notice that the two bars move in opposite directions and there is no setting where both are small. Leveled at the default multiplier of 10 gives 52× write amplification and 10 files to probe; tiered gives 7× and 55 files. Real RocksDB measures 10–30× rather than 52 because dynamic level sizing keeps the intermediate levels far under their nominal capacity — but the shape of the trade is exactly this.

Which sets a hard ceiling on ingest, and the failure when you cross it is the LSM production incident. Push the write rate past what compaction can drain and watch L0 fill:

Because a 600 MB/s device paying 52× amplification can only absorb 11.5 MB/s of user writes, anything above that accumulates. At 50 MB/s L0 reaches level0_stop_writes_trigger in sixty seconds and writes block outright. Below that trigger the failure is silent and worse: write throughput still looks healthy while every point lookup quietly probes forty files instead of ten.

One last asymmetry. Because files are immutable, a delete cannot remove anything — it writes a tombstone saying the key is gone. Delete rows and watch the database get bigger:

The space comes back only when a compaction carries the tombstone all the way to the bottom level, which for cold data can be never. Worse, a range scan has to read every tombstone in its range: Cassandra aborts the query at tombstone_failure_threshold, 100,000 by default, which is how "we deleted some old rows" becomes "reads on that partition now throw".

The rule has one sentence and no exceptions: no modification to a data page may reach durable storage before the log record describing it is already there. The page may then flush late, out of order, or never — the log is the canonical truth.

That only pays off because recovery can tell what a page already contains. Every page carries the LSN of the last record applied to it, and redo skips anything at or below it. Drag recovery forward:

Because the four records the page already carries are skipped rather than reapplied, replaying the log twice produces the same page as replaying it once. That idempotence is what lets recovery itself crash and simply start again — otherwise a machine that failed during startup could never be brought up at all.

It is worth breaking the rule to see why it exists. Choose whether the log record or the dirty page hits the disk first, then move the crash between them:

Notice that page-first does not fail loudly. Recovery starts, finds nothing in the log about that page, and concludes the page is already correct — so a half-applied change is now the database's idea of the truth, and a checksum failure is the only chance you have of ever hearing about it. Log-first crashes are boring, which is the point.

Given the rule, one commit is four cheap steps and one expensive one — the work, then the flush. Step through it and watch where the time is:

Watch how much of the bar is the fsync. Modifying the page, building the record and appending the commit record are 0.6 µs together; the fdatasync is 30 µs on the best hardware in this article. Everything a database does to go faster on writes is an attack on that one segment.

And that segment is not a software number. It is a property of the device under the log — and it moves by two and a half orders of magnitude. Step through four of them and read the ceiling each one sets:

Because one session cannot commit faster than one fsync, the ceiling is 1 ÷ fsync: 33,333 per second on power-loss-protected NVMe, and 120 on a 7,200 rpm disk — which is one platter rotation, 8.33 ms, and no amount of tuning gets underneath it. Consumer NVMe without power-loss protection lands at 1,000, because its flush has to drain an on-board DRAM cache that enterprise drives can safely ignore.

A hundred and twenty commits a second would be unusable, so no engine accepts it. Commits that arrive while an fsync is in flight ride the next one. Raise the number of sessions and watch the fsync rate refuse to move:

Because the flush is shared and the wait is not, 64 sessions on that same disk retire 7,680 commits per second from 120 fsyncs — and every one of them still waited for its own data to be durable. Group commit buys throughput without touching semantics, which is why it is on by default and why synchronous_commit = off is almost never the right answer to a write bottleneck.

The log's other consumer is a standby, and synchronous_commit decides how far down that pipe a commit waits. Move the standby further away and switch the level:

Notice that local does not move at all: it never leaves the machine. remote_apply in the same region is 5.06 ms — 165× local — because the commit now waits for a round trip and for the standby to replay the record. That is what buys a read-your-writes guarantee on the replica, and it is the whole price of it.

The log has a second job: it is what a crash is repaired from. ARIES does it in three passes over the records since the last checkpoint — and only the last of them touches what never committed. Run them:

Notice that redo replays everything, committed or not. It has to: the pass restores the database to the exact state at the crash, and only then can undo roll back what never committed. Doing it in one pass would need to know each transaction's fate before reading the record that decides it.

So recovery time is set by how much log there is, not by how big the database is. max_wal_size is that dial. Raise it and watch the redo grow while the checkpoints thin out:

At the 1 GB default, redo is 13 seconds at 80 MB/s on the single core Postgres gives it. At 16 GB it is 205 seconds — three and a half minutes of downtime bought in exchange for a sixteenth as many checkpoints, and so a sixteenth as many full-page images. That is the real trade behind the knob, and it is a recovery-objective decision, not a performance one.

Which brings us to the knob people actually reach for. synchronous_commit = off stops waiting for the fsync and returns success anyway. Move wal_writer_delay and read what a crash takes with it:

At the 200 ms default the exposure is up to three delays — 600 ms — and at the 7,680 commits per second we just measured, that is 4,608 transactions the client was told had committed. Nothing is corrupted: the database comes back consistent, having simply forgotten them. That is the setting to reach for when losing the last half-second is genuinely fine, and never because a graph looked better.

The step worth memorising is the third rung to the fifth: a page read is microseconds, a disk rotation is milliseconds. Above that gap you tune with memory budgets; below it you are choosing hardware, and no configuration file will help.

Notice that the B+tree only wins on the top bar. In key order it moves 1.8 bytes per byte written and nothing else comes close; in random UUID order it moves 105, which is worse than a leveled LSM. The structure is not the decision — the key order is, and after that it is whether you can afford a permanent background compactor.

The last red flag is the one that looks like tuning. Postgres's pool reads through the kernel, so a page it caches is usually in the OS page cache too. Take more of the machine and watch the same bytes get cached twice:

At the 25% starting point the double-buffered overlap is 16 GB and there is still 42 GB of kernel cache. Past 90% there is nothing left for sorts or connections at all, and the machine starts swapping — which is why InnoDB's 70–80% rule does not transfer: it uses O_DIRECT, so there is no second copy to pay for.

• synchronous_commit = off for "performance." Group commit gets most of it with no durability loss.
• Random UUIDs as a primary key. 49× the WAL. UUIDv7 sorts by time.
• Alerting on LSM write throughput. Alert on the L0 file count instead.
• A drive whose cache lies about fsync. Verify with a power-cut test, not a benchmark.