Database Internals - the deep-dive set

The whole engine on one board, one gear per lesson below. This lesson follows one UPDATE through all of them, then measures what COMMIT actually costs.

Boards

• The Map
• Pages & Heap Files
• The Buffer Pool
• WAL & Recovery
• B-Tree on Disk
• MVCC & Vacuum
• The Query Planner
• Locks, Latches & Transactions
• Everything

Before you start. The Right Book for the Job (databases, deeply) picked Postgres as the database under the app. Storage Engines showed the two ways an engine stores rows: overwrite each row where it sits (the B-tree family), or only ever append and merge files later (the LSM-tree family); Postgres overwrites in place. This note opens that engine to the bolt.

1973: two professors build the parts nobody had built yet

In the early 1970s IBM researchers were describing a database you could question in plain-ish language instead of fetching each row with code. Two Berkeley professors, Michael Stonebraker and Eugene Wong, read those papers and in 1973 started a rival of their own, on a grant meant for something else entirely: a geography tool called INGRES. They kept the name, spent the money on the database instead, and scraped together further funding after two military research funders turned them down.

Nobody had done this before, so there was no book to copy. Store a table as one long file, and finding row 42 means reading the whole file. Fix that, and two people editing the same row at once can corrupt each other’s work. Fix that, and a machine that loses power mid-write can leave the file half-changed forever. Each fix opens a new hole, and each hole below is one lesson in this set. Postgres, the database under your app, is Stonebraker’s second attempt at the same seven problems.

The hinge: a database tells the disk two lies

A disk is slow at reading and writing in random spots, and fast at one thing: writing one long stream, in order. So the engine lies to itself twice. It tells a reader “your row is right here,” when what is actually there is a cached copy sitting in RAM in front of the real file - the buffer pool. And it tells COMMIT “your change is saved,” when really one line describing the change was appended to a long, in-order file - the write-ahead log, WAL for short - while the real data file catches up a minute later.

The set, one gear per lesson

1. Pages & Heap Files - fixed 8 KB chunks; a row gets an address, not just a spot in one giant file.
2. The Buffer Pool - the RAM cache of busy chunks, so most reads skip the disk.
3. WAL & Recovery - the append-only log, so a crash mid-write never half-changes the file.
4. B-Tree on Disk - the index, a sorted lookup like the back of a book: row 42 in a handful of reads, not a full scan.
5. MVCC & Vacuum - old row versions kept, not erased, so readers and writers never block each other; vacuum later clears the ones nobody can see.
6. The Query Planner - decides how to run a query once more than one way exists.
7. Locks, Latches & Transactions - locks keep two transactions (batches of changes that land whole or not at all) off the same rows; latches guard the engine’s own memory briefly.
8. Capstone: Database Internals, Everything - the capstone: narrate one UPDATE across the whole board, unaided.

One UPDATE, six gears, in order

Send UPDATE users SET plan='pro' WHERE id=42 and watch it cross every gear:

flowchart TD
  C["your app sends the UPDATE to the database server"] --> B["a server process reads the SQL and picks a plan"]
  B --> X["it finds row 42 through the index, not by reading every row"]
  X --> P["the page holding it is already sitting in the buffer pool"]
  P --> W["the change is appended to the write-ahead log first"]
  W --> H["the new row version is written on the page; the old one is kept, not erased"]
  H --> K["COMMIT: wait until the log is forced onto disk, about 1 ms"]
  K --> R["reply OK to the client"]
  R -.->|minutes later| D["a background writer copies the changed page to the data file"]
  R -.->|later| V["a cleanup process, vacuum, removes the old version"]

Follow the solid arrows: the client hears “OK” the moment the WAL entry is on disk, before the data file has changed at all. That wait, about 1 ms (a thousandth of a second), is measured below. The dotted arrows are background work; the client never waits on either.

You now know

• A row lives inside a fixed-size page, usually 8 KB, not loose inside one giant file.
• The buffer pool is the RAM copy of the pages in use right now; the disk files are the fallback, not the first stop.
• COMMIT doesn’t wait for your row to reach its data file. It waits for one line appended to the write-ahead log, then answers OK.
• An update doesn’t erase the old row. It writes a new version and keeps the old one around for anyone still mid-read: that trick is MVCC.
• An index is a sorted lookup (Postgres’s is a B-tree, a shallow tree of pages) that turns “find row 42” into a handful of reads instead of a scan of the whole table.
• Two background processes run after the client has its answer: a checkpoint copies the changed page into its data file, and vacuum deletes old row versions no running query can still see.

Stop here if you want. What follows is the same UPDATE, run for real on Postgres 16, with every number it printed kept exactly as measured.

Second read: the same UPDATE, measured on Postgres 16

The trace ran on a throwaway Docker container, with Postgres’s own inspection tools.

The row before. Table accounts, 50 rows, one page, 3,968 bytes free. pageinspect shows row 42’s slot: line pointer 42, created by transaction 750, no deleter yet (t_xmax = 0), t_ctid pointing at itself.

 lp | lp_flags | t_xmin | t_xmax | t_ctid
----+----------+--------+--------+--------
 42 |        1 |    750 |      0 | (0,42)

The first UPDATE after a checkpoint. pg_walinspect lists what was appended to the log, one row per record: record_length is its size in bytes, fpi_length how much is a copy of the whole page, block_ref the page it touched:

UPDATE accounts SET plan='pro' WHERE id=42;
 wal_bytes_first_update_after_checkpoint: 4416
 resource_manager | record_type | record_length | fpi_length | block_ref
 Heap             | HOT_UPDATE  |          4373 |       4308 | rel 16447 blk 0 (FPW); hole: offset 228, length 3884
 Transaction      | COMMIT      |            34 |          0 |

Two records. The update record is 4,373 bytes, of which 4,308 is a full-page image (FPW): the first change to a page since the last checkpoint logs the whole page (minus its 3,884-byte free-space hole) so a torn write can be repaired from the log. The commit record is 34 bytes. No index record: the column isn’t indexed and the new version fit on the same page, so this is a HOT update, and the primary-key index was never touched.

The second UPDATE on the same page, before the next checkpoint, same columns:

UPDATE accounts SET plan='team' WHERE id=42;
 Heap             | HOT_UPDATE  |            75 |          0 | rel 16447 blk 0
 Transaction      | COMMIT      |            34 |          0 |

Seventy-five bytes for the change plus 34 for the commit: the honest size of one row update in the log. The 4 KB image was a once-per-checkpoint tax.

The tax, by hand. The page is 8,192 bytes; 3,884 of that is the hole, so the image is 8,192 − 3,884 = 4,308, exactly the printed fpi_length. Against the 75-byte record for the same change, that is 4,308 ÷ 75 ≈ 57 ordinary updates’ worth of log, paid once per page per checkpoint. So a busy page’s WAL between two checkpoints is 4,308 + 75 × (updates − 1): at 1,000 updates the image is 5% of the total; at 10 it is 86% (4,308 ÷ 4,983). Halve the checkpoint interval and the 75s stay put while the 4,308s double.

The page after. Three versions of row 42 now share the page, chained by t_ctid:

 lp | lp_flags | t_xmin | t_xmax | t_ctid
----+----------+--------+--------+--------
 42 |        1 |    750 |    751 | (0,51)     the original, killed by txn 751, points at its successor
 51 |        1 |    751 |    752 | (0,52)     version 2, killed by txn 752
 52 |        1 |    752 |      0 | (0,52)     the live version
 ctid (0,52)  xmin 752  xmax 0  plan 'team'   <- what SELECT returns

The index still points at slot 42; a reader follows the chain to slot 52. A transaction started before 751 committed stops at slot 42 and sees plan='free' instead. Stats agree: n_tup_upd 2, n_tup_hot_upd 2, n_dead_tup 2.

After VACUUM:

 42 |        2 |        |        |        lp_flags 2 = REDIRECT: slot 42 now just points at 52
 51 |        0 |        |        |        lp_flags 0 = UNUSED: the space is free again
 52 |        1 |    752 |      0 | (0,52)
 n_dead_tup 0

Vacuum moved nothing and touched no index; it turned slot 42 into a redirect and freed slot 51. That is why HOT updates are cheap to clean up, and why updating an indexed column, which can’t use this chain, leaves index entries for vacuum too.

What COMMIT costs. The board says COMMIT = flush + fsync, about 1 ms. pgbench ran the same one-row update in a loop. synchronous_commit=on makes each commit wait for the disk flush; off answers first. Each line is one five-second run on the disk under that one Docker container, so another machine will print different latencies and only the ratios between the lines carry over. Each line reads time per commit, then commits per second:

synchronous_commit=on,  1 client:   latency 0.579 ms   1,727 commits/s
synchronous_commit=off, 1 client:   latency 0.046 ms  21,751 commits/s
synchronous_commit=on,  8 clients:  latency 1.170 ms   6,839 commits/s

Turning off the fsync wait made the transaction 12.6× faster (0.579 ÷ 0.046), and the gap, 0.533 ms, is the price of durability: the time for the WAL bytes to reach stable storage before the client hears OK. With the wait off, a crash can lose the last few hundred milliseconds of acknowledged commits, though the data files stay consistent, just behind the log. The third line is group commit: eight clients each waited about twice as long, but the engine fsynced once for several of them, so throughput went up almost 4×. Proof: if every one of those 6,839 commits/s paid its own 0.53 ms fsync, the disk would need 3.6 s of fsync time inside one second of wall clock, impossible, so at least four commits are sharing each flush. The log is one sequential stream; that sharing is the whole reason the WAL exists.

Try it (on any Postgres)

Break something: leave BEGIN; SELECT ... idle in one psql, loop UPDATEs in another, and watch n_dead_tup climb while autovacuum does nothing.

The trace, reproducible in ten minutes (docker rm -f chalk-pg removes the container after):

docker run -d --name chalk-pg -e POSTGRES_PASSWORD=pg postgres:16
docker exec -i chalk-pg psql -U postgres -X

CREATE EXTENSION pageinspect;  CREATE EXTENSION pg_walinspect;
CREATE TABLE accounts(id int PRIMARY KEY, plan text NOT NULL, note text);
INSERT INTO accounts SELECT g, 'free', repeat('x', 40) FROM generate_series(1, 50) g;
CHECKPOINT;
SELECT lp, lp_flags, t_xmin, t_xmax, t_ctid FROM heap_page_items(get_raw_page('accounts', 0)) WHERE lp = 42;

SELECT pg_current_wal_lsn() AS l0 \gset
UPDATE accounts SET plan='pro' WHERE id=42;
SELECT pg_current_wal_lsn() AS l1 \gset
SELECT pg_wal_lsn_diff(:'l1', :'l0') AS wal_bytes;
SELECT resource_manager, record_type, record_length, fpi_length, block_ref
  FROM pg_get_wal_records_info(:'l0', :'l1') ORDER BY start_lsn;

UPDATE accounts SET plan='team' WHERE id=42;          -- then repeat the two SELECTs above from l1
SELECT lp, lp_flags, t_xmin, t_xmax, t_ctid FROM heap_page_items(get_raw_page('accounts', 0)) WHERE lp IN (42,51,52);
SELECT pg_stat_force_next_flush(); SELECT 1;
SELECT n_tup_upd, n_tup_hot_upd, n_dead_tup FROM pg_stat_user_tables WHERE relname='accounts';
VACUUM accounts;                                      -- then the heap_page_items query again

Then the commit cost, from a shell inside the container:

printf '\\set id random(1, 50)\nUPDATE accounts SET plan = plan WHERE id = :id;\n' > /tmp/u.sql
pgbench -n -c 1 -T 5 -f /tmp/u.sql -U postgres postgres
PGOPTIONS="-c synchronous_commit=off" pgbench -n -c 1 -T 5 -f /tmp/u.sql -U postgres postgres
pgbench -n -c 8 -j 4 -T 5 -f /tmp/u.sql -U postgres postgres

Two variations. Add CREATE INDEX ON accounts(plan) and repeat the update: the WAL now carries B-tree records too, and n_tup_hot_upd stops climbing, because an indexed column can’t be HOT. Or fill the page first (INSERT 100 rows instead of 50, overflowing to a second page), then update a row there: the new version lands on page 1, the index gets updated, and the first-after-checkpoint WAL was 24,792 bytes, three full-page images instead of one.

Go deeper

• Database Internals (Alex Petrov) - Part I is this set in book form.
• The Internals of PostgreSQL (Hironobu Suzuki, interdb.jp) - free, the exact machinery per chapter.
• Andy Pavlo’s CMU 15-445 lectures - the mmap rant is “Are You Sure You Want to Use MMAP in Your DBMS?” (CIDR 2022).
• Cross-links: Storage Engines (LSM fork) · Transactions (isolation) · The copy clerks (database replication)/Replication (the WAL leaves the building) · The Ledger Everyone Reads (event-driven & the log) (CDC = logical decoding).

Related

• The eight per-gear lessons, Pages & Heap Files through Capstone: Database Internals, Everything, each taking one box of the flowchart above.
• Storage Engines names the B-tree family this engine belongs to and the LSM family it skipped.
• The Right Book for the Job (databases, deeply) put this engine under the application in the first place.
• The full Database Internals list is in CURRICULUM.

Retrieval (cold, no peeking)

20 questions. Answer each one before you open it.