The Engineer's Ledger

Three promises a file can't keep

Most programs start by saving data to a file, and for a while that works. Then three things happen. The machine loses power while the file is being written, and the next start finds half a file. Two requests arrive at the same moment, both read the file, both change it, and one change disappears. And the file grows until finding one record means reading all of them. Those are the three promises a database exists to keep: atomic, durable writes, safe concurrency, and finding without scanning.

import json, os, sqlite3, tempfile

d = tempfile.mkdtemp()
path = os.path.join(d, "accounts.json")

def save_in_place(data, crash_after=None):
    blob = json.dumps(data).encode()
    with open(path, "wb") as f:                    # opening for write truncates the old file
        f.write(blob if crash_after is None else blob[:crash_after])  # power cut mid-write

def save_atomically(data, crash_after=None):
    blob = json.dumps(data).encode()
    tmp = path + ".tmp"
    with open(tmp, "wb") as f:
        f.write(blob if crash_after is None else blob[:crash_after])
        if crash_after is not None:
            return                                 # crashed before the rename: old file untouched
        f.flush(); os.fsync(f.fileno())            # make the new bytes durable first
    os.replace(tmp, path)                          # atomic: readers see old or new, never half

def load():
    try:
        with open(path) as f:
            return json.load(f)
    except json.JSONDecodeError as e:
        return f"CORRUPT ({e.msg})"

# Promise 1: a write is all-or-nothing, even if the power fails halfway.
save_in_place({"alice": 100, "bob": 50})
save_in_place({"alice": 70, "bob": 80}, crash_after=12)
print("in-place write, crash halfway:", load())
save_atomically({"alice": 100, "bob": 50})
save_atomically({"alice": 70, "bob": 80}, crash_after=12)
print("atomic rename, crash halfway: ", load())

# Promise 2: two clients can't silently overwrite each other.
save_atomically({"visits": 0})
a = load()["visits"]; b = load()["visits"]         # both clients read 0
save_atomically({"visits": a + 1}); save_atomically({"visits": b + 1})
print("file, two increments:         ", load())

dbfile = os.path.join(d, "app.db")
setup = sqlite3.connect(dbfile)
setup.execute("CREATE TABLE counters(name TEXT PRIMARY KEY, n INTEGER)")
setup.execute("INSERT INTO counters VALUES ('visits', 0)"); setup.commit(); setup.close()
A = sqlite3.connect(dbfile, timeout=0, isolation_level=None)
B = sqlite3.connect(dbfile, timeout=0, isolation_level=None)
A.execute("BEGIN IMMEDIATE")                       # client A takes the write lock
A.execute("UPDATE counters SET n = n + 1 WHERE name = 'visits'")
try:
    B.execute("UPDATE counters SET n = n + 1 WHERE name = 'visits'")
except sqlite3.OperationalError as e:
    print("client B must wait:           ", e)
A.execute("COMMIT")
B.execute("UPDATE counters SET n = n + 1 WHERE name = 'visits'")   # B retries after A commits
print("database, two increments:     ", B.execute("SELECT n FROM counters").fetchone()[0])

in-place write, crash halfway: CORRUPT (Expecting ',' delimiter)
atomic rename, crash halfway:  {'alice': 100, 'bob': 50}
file, two increments:          {'visits': 1}
client B must wait:            database is locked
database, two increments:      2

The first accident is the torn write. Opening a file for writing truncates it, so a crash between the truncate and the last byte leaves a file that is neither the old version nor the new one. The usual fix, writing a temporary file, flushing it to disk with fsync and renaming it over the original, does keep the old version safe, because a rename is atomic on POSIX file systems. But it only works for one file, it rewrites the whole file for every change, and it does nothing for the second accident.

The second accident is the lost update. Both clients read 0, both write 1, and two visits are recorded as one. Nothing crashed and nothing reported an error: the data is simply wrong. The database turns the same two increments into 2 because it won't let the second writer act on stale data. Client B is told to wait while A holds the write lock, then its update runs against A's committed value. That waiting is concurrency control, and a whole part of this book (chapters 12 to 15) is about doing it without making everyone wait all the time.

The third promise isn't in the example because it's the subject of Parts II and III: a database keeps its data in fixed-size pages and builds indexes over them, so that finding one customer among ten million means reading three or four pages instead of all of them.

What's inside

Almost every relational database has the same parts, arranged the same way. Your SQL is parsed into a tree, the planner turns the tree into a plan, and the executor runs the plan as a pipeline of operators. The operators read through access methods, B-trees and their relatives, which ask the buffer pool for pages, which reads them from disk only when they aren't already in memory. Alongside, a transaction manager decides who may see and change what, and a log manager records every change before it is allowed to count.

The detail worth noticing now is the two arrows to disk. When you commit, the database does not rush your changed rows into the data files. It appends a description of the change to the log and flushes the log, a fast sequential write, and only then tells you the transaction is done. The data pages are written back later, in the background, in whatever order is efficient. If the machine crashes in between, the log holds everything needed to redo the work. The log is the ledger, and the data files are a convenient, searchable copy of what it says. Chapter 15 builds one.

Choosing an engine is choosing trade-offs

Databases differ in where they sit and what they optimise. Embedded databases such as SQLite run inside your process and store everything in one file. They are the most widely deployed database engine there is, in every phone and browser, and the right default for local and single-writer data. Client-server databases such as PostgreSQL and MySQL run as their own service, accept many concurrent writers over the network, and add replication, roles and online maintenance. Transactional (OLTP) systems are built for many small reads and writes; analytical (OLAP) systems are built for scans over billions of rows, and store data in columns instead of rows (chapter 20). Non-relational stores trade the query language for a particular access pattern or scale (chapter 18). None of these is better in general. The useful question is always which promises you need, and how much each one costs.

This volume uses SQLite for its real examples because it ships with Python, so every example runs anywhere without setup. Its mechanisms, pages, B-trees, a write-ahead log, locks, a cost-based planner, are the same ones the server databases use, at a smaller scale.

Constraints are rules nobody can skip

Every application has rules about its data: emails are unique, an order belongs to a customer who exists, a total is never negative. You can check them in application code, and you should, to give users friendly errors. But application checks only cover the code paths that remember to run them. They miss the admin script, the batch import, the second service written by another team next year, and, as exercise 2.2 shows, two requests racing each other. A constraint declared in the schema is checked by the database on every write, from every client, inside the same transaction as the write. It is the only check that can't be bypassed.

import sqlite3

db = sqlite3.connect(":memory:", isolation_level=None)   # autocommit: each statement stands alone
db.execute("PRAGMA foreign_keys = ON")             # SQLite leaves this OFF unless you ask
db.executescript("""
CREATE TABLE customers(
  id    INTEGER PRIMARY KEY,
  email TEXT NOT NULL UNIQUE CHECK (email LIKE '%_@_%'));
CREATE TABLE orders(
  id          INTEGER PRIMARY KEY,
  customer_id INTEGER NOT NULL REFERENCES customers(id) ON DELETE RESTRICT,
  total_cents INTEGER NOT NULL CHECK (total_cents >= 0));
INSERT INTO customers VALUES (1, 'ana@example.com');
INSERT INTO orders VALUES (10, 1, 2500);
""")
attempts = [
    ("duplicate email",               "INSERT INTO customers VALUES (2, 'ana@example.com')"),
    ("malformed email",               "INSERT INTO customers VALUES (3, 'not-an-email')"),
    ("order for a missing customer",  "INSERT INTO orders VALUES (11, 99, 100)"),
    ("negative total",                "INSERT INTO orders VALUES (12, 1, -5)"),
    ("delete a customer with orders", "DELETE FROM customers WHERE id = 1"),
]
for label, sql in attempts:
    try:
        db.execute(sql)
        print(f"ACCEPTED  {label}")
    except sqlite3.IntegrityError as e:
        print(f"rejected  {label:30} {e}")

db.execute("PRAGMA foreign_keys = OFF")
db.execute("INSERT INTO orders VALUES (13, 99, 100)")
print("with foreign_keys OFF, an order for customer 99 is quietly ACCEPTED")

rejected  duplicate email                UNIQUE constraint failed: customers.email
rejected  malformed email                CHECK constraint failed: email LIKE '%_@_%'
rejected  order for a missing customer   FOREIGN KEY constraint failed
rejected  negative total                 CHECK constraint failed: total_cents >= 0
rejected  delete a customer with orders  FOREIGN KEY constraint failed
with foreign_keys OFF, an order for customer 99 is quietly ACCEPTED

Each refusal names the rule that stopped it. UNIQUE blocks the duplicate email, CHECK rejects the malformed email and the negative total, and the foreign key blocks both the order for a customer who doesn't exist and the deletion of a customer who still has orders. ON DELETE RESTRICT is a choice: CASCADE would delete the orders too, and SET NULL would orphan them on purpose. Pick the one that matches what deleting a customer means in your business.

The last line is the trap. SQLite, for backward compatibility, enforces foreign keys only when the connection turns them on, and turning them on (or off) silently does nothing inside an open transaction. MySQL's old MyISAM engine accepted foreign key syntax and ignored it entirely. Never assume a constraint is enforced: write a test that tries to violate it.

Keys

A key is a set of columns whose values identify one row. A table can have several candidate keys (a customer might be identified by an internal id and also by an email); one is chosen as the primary key and the others should still be declared UNIQUE, or the database won't know they are keys. A surrogate key, an auto-incrementing integer or a UUID, carries no meaning and never needs to change; a natural key, like an ISBN, carries meaning and sometimes does change. SELECT Again's schema-design module covers that choice. The rule that matters here is simpler: every fact you believe is unique deserves a UNIQUE constraint, whichever key you pick.

One fact, one place

Normalisation sounds academic and is entirely practical. When the same fact is stored in many rows, an update that changes some copies and misses others leaves the database contradicting itself, and no query can tell you which copy is right. The tool for spotting this is the functional dependency: X → Y means that knowing X tells you Y. An order id tells you the customer; a customer id tells you the email. A table is in good shape, formally Boyce-Codd normal form, when the left side of every dependency is a key. When it isn't, that dependency's facts repeat.

from itertools import combinations

def closure(attrs, fds):
    """Everything the attributes determine, following dependencies until nothing changes."""
    result, changed = set(attrs), True
    while changed:
        changed = False
        for lhs, rhs in fds:
            if lhs <= result and not rhs <= result:
                result |= rhs; changed = True
    return result

def candidate_keys(attrs, fds):
    keys = []
    for size in range(1, len(attrs) + 1):
        for combo in combinations(sorted(attrs), size):
            c = set(combo)
            if closure(c, fds) == attrs and not any(k <= c for k in keys):
                keys.append(c)
    return keys

def bcnf_violations(attrs, fds):
    """A dependency whose left side is not a key means one fact is stored many times."""
    return [(lhs, rhs) for lhs, rhs in fds if closure(lhs, fds) != attrs]

# One wide table, as spreadsheets and first drafts love to do it.
A = set("order_id product_id qty customer_id customer_email product_name unit_price".split())
F = [({"order_id", "product_id"}, {"qty"}),
     ({"order_id"}, {"customer_id"}),
     ({"customer_id"}, {"customer_email"}),
     ({"product_id"}, {"product_name", "unit_price"})]

print("candidate keys:", [sorted(k) for k in candidate_keys(A, F)])
for lhs, rhs in bcnf_violations(A, F):
    print(f"  {', '.join(sorted(lhs)):11} -> {', '.join(sorted(rhs)):26} repeats on every row that shares {', '.join(sorted(lhs))}")
print("split each violation into its own table:")
for lhs, rhs in F:
    print(f"  table keyed by ({', '.join(sorted(lhs))}) holding {', '.join(sorted(rhs))}")

candidate keys: [['order_id', 'product_id']]
  order_id    -> customer_id                repeats on every row that shares order_id
  customer_id -> customer_email             repeats on every row that shares customer_id
  product_id  -> product_name, unit_price   repeats on every row that shares product_id
split each violation into its own table:
  table keyed by (order_id, product_id) holding qty
  table keyed by (order_id) holding customer_id
  table keyed by (customer_id) holding customer_email
  table keyed by (product_id) holding product_name, unit_price

The wide table's only key is (order_id, product_id), one row per line item. Every other dependency has a smaller left side, and each one means a fact repeated across rows. The customer's email is copied onto every line of every order they place, so changing it means updating hundreds of rows and getting all of them. The product name is copied onto every line that ever sold it. The classic names describe the two shapes: order_id → customer_id depends on part of the key (a second normal form violation), and customer_id → customer_email depends on a non-key column (a third normal form violation). The fix is the same for both: give each dependency a table of its own, keyed by its left side.

The output hides one deliberate trap. The tool treats unit_price as a fact about the product, and if it means the product's current price, it is. But on an order line, the price usually means the price this customer paid, which must not change when the catalogue price does. That's a different fact with a different key: it belongs on the order line. Normalisation can only be as right as the dependencies you write down, so the real work is asking what each column actually means.

Denormalising on purpose

A normalised schema is the right default for data you write. Sometimes you deliberately copy a fact anyway: an order count kept on the customer row so a list page doesn't count orders on every view, a materialised summary for a dashboard, a search document that flattens five tables. That's fine if you treat the copy as derived data, with one owner and a way to rebuild it. Update the copy in the same transaction as the source, or with a trigger, or rebuild it on a schedule and accept the lag, and keep a reconciliation query that finds copies that have drifted. The failure mode is the copy nobody owns, updated by some code paths and not others, quietly diverging for a year.

Trees

Categories, comment threads, org charts and folders are all trees, and a table is flat. The obvious design is the adjacency list: each row stores its parent's id. It's easy to write and to move a subtree (change one parent_id), but reading a whole subtree needs a recursive query that walks one level at a time. The closure table stores every ancestor-descendant pair, with its depth, in a second table. Reading a subtree, all ancestors, or the depth of any node becomes one indexed lookup, at the cost of more rows and more work when the tree changes. Two other designs are worth knowing by name: the materialised path stores '/1/2/3/' on each row and finds a subtree with a prefix search, and nested sets store left and right numbers that make subtree reads fast and every insert expensive.

import sqlite3

db = sqlite3.connect(":memory:")
db.executescript("""
CREATE TABLE category(id INTEGER PRIMARY KEY, parent_id INTEGER REFERENCES category(id), name TEXT);
INSERT INTO category VALUES
  (1, NULL, 'Electronics'), (2, 1, 'Computers'), (3, 2, 'Laptops'), (4, 2, 'Desktops'),
  (5, 1, 'Audio'), (6, 5, 'Headphones'), (7, 3, 'Gaming laptops');
""")

# Shape 1: adjacency list. Simple to write; reading a subtree needs a recursive query.
subtree_cte = db.execute("""
  WITH RECURSIVE sub(id, name, depth) AS (
    SELECT id, name, 0 FROM category WHERE id = 2
    UNION ALL
    SELECT c.id, c.name, sub.depth + 1 FROM category c JOIN sub ON c.parent_id = sub.id)
  SELECT name, depth FROM sub ORDER BY depth, name""").fetchall()

# Shape 2: closure table. Store every ancestor-descendant pair; a subtree is one indexed lookup.
db.executescript("""
CREATE TABLE category_path(ancestor INTEGER, descendant INTEGER, depth INTEGER,
                           PRIMARY KEY (ancestor, descendant));
WITH RECURSIVE p(a, d, depth) AS (
  SELECT id, id, 0 FROM category
  UNION ALL
  SELECT p.a, c.id, p.depth + 1 FROM p JOIN category c ON c.parent_id = p.d)
INSERT INTO category_path SELECT a, d, depth FROM p;
""")
subtree_closure = db.execute("""
  SELECT c.name, p.depth FROM category_path p JOIN category c ON c.id = p.descendant
  WHERE p.ancestor = 2 ORDER BY p.depth, c.name""").fetchall()

print("subtree of Computers:", subtree_cte)
print("same answer from the closure table:", subtree_cte == subtree_closure)
print("rows: category", db.execute("SELECT COUNT(*) FROM category").fetchone()[0],
      "| category_path", db.execute("SELECT COUNT(*) FROM category_path").fetchone()[0])

# Money: binary floats cannot represent most decimal fractions exactly.
total_float, total_cents = 0.0, 0
for _ in range(1000):                    # a running balance, the way application code adds
    total_float += 19.99
    total_cents += 1999
print("1000 x 19.99 as float:", total_float)
print("1000 x 1999 in cents: ", total_cents, "=", f"{total_cents // 100}.{total_cents % 100:02d}")
print("round(2.675, 2) ->", round(2.675, 2), " (2.675 is stored as 2.67499999...)")

subtree of Computers: [('Computers', 0), ('Desktops', 1), ('Laptops', 1), ('Gaming laptops', 2)]
same answer from the closure table: True
rows: category 7 | category_path 18
1000 x 19.99 as float: 19990.000000000135
1000 x 1999 in cents:  1999000 = 19990.00
round(2.675, 2) -> 2.67  (2.675 is stored as 2.67499999...)

Both tree designs return the same subtree. The closure table pays for it in storage, 18 path rows for 7 categories, because every node is also paired with itself and with each of its ancestors. In return, its subtree query has no recursion, and its (ancestor, descendant) primary key is an index the planner can use directly. Choose by the workload: an adjacency list for trees that change often and are read a level at a time, a closure table or materialised path for trees read whole far more often than they change.

Money

The last lines of the example are the reason money is never a binary float. A float stores most decimal fractions as the nearest binary fraction, so a running total of 1,000 prices of 19.99 drifts off by a few billionths. Rounding 2.675 to two places gives 2.67, because 2.675 is actually stored as 2.67499999.... Each error is tiny, and an accounting system that is off by a cent in a few thousand invoices fails its audit anyway. Store money either as an integer number of the currency's minor unit (cents, pence) or as an exact DECIMAL(19, 4). Always store the currency next to the amount, and decide explicitly where rounding happens, because tax and currency conversion force it somewhere.

Things that are several kinds of thing

A payment might be a card payment, a bank transfer or a voucher, each with its own fields. Single-table inheritance puts them all in one table with a type column and nullable columns for every kind: simple to query, but the database can't enforce that a card payment has a card number. Class-table inheritance keeps the shared columns in a payments table and each kind's columns in its own table, keyed by the payment id: the constraints work, at the cost of a join. The design to avoid is the polymorphic foreign key, a pair like (commentable_type, commentable_id) that might point at a post or a photo. It can't be a real foreign key, so the database can no longer guarantee that the thing it points at exists. Where you need that shape, use one nullable foreign key column per target, with a CHECK that exactly one is set.

Time and history

Store timestamps in UTC, as a timestamp type rather than text, and convert to local time only for display. Daylight-saving shifts make local times ambiguous for one hour every autumn. When you need history, don't overwrite and hope: give the row valid_from and valid_to columns so you can ask what was true on a given date, or append changes to an event or audit table so you can ask what happened. Soft deletes, a deleted_at column instead of a real delete, preserve history but cost more than they look. Every query must remember to filter them, and unique constraints break, because the deleted row still holds the email a new user wants (exercise 3.3).

Semi-structured data

Modern relational databases store JSON well, and a JSON column is the right home for data whose shape genuinely varies: a webhook payload you keep for debugging, product attributes that differ by category, user preferences. It's the wrong home for data you filter, join or constrain, because the schema can no longer enforce types, keys or references inside it, and indexing it takes expression indexes you must remember to create. A useful rule: any field you query by gets promoted to a real column.

Two models of the same data

Your code thinks in objects: an author has a list of books, you follow references from one object to the next, and identity means "the same object in memory". The database thinks in relations: sets of rows, related by matching values, combined by joins, where identity means "the same key". The gap between the two is called the object-relational mismatch, and an ORM such as Django's, SQLAlchemy, Hibernate or ActiveRecord bridges it. It does a lot well. It maps rows to objects and back, always parameterises queries (which prevents SQL injection), tracks which objects changed and writes them in one transaction, and generates migrations. The trouble is that following a reference in object code looks free, and in an ORM it can be a network round trip.

import sqlite3

class Connection:
    """Wraps a database connection: counts round trips and charges each one network latency."""
    def __init__(self, conn, rtt_ms=1.0):
        self.conn, self.rtt_ms, self.queries = conn, rtt_ms, 0
    def query(self, sql, params=()):
        self.queries += 1
        return self.conn.execute(sql, params).fetchall()
    def latency_ms(self):
        return self.queries * self.rtt_ms

raw = sqlite3.connect(":memory:")
raw.execute("CREATE TABLE author(id INTEGER PRIMARY KEY, name TEXT)")
raw.execute("CREATE TABLE book(id INTEGER PRIMARY KEY, author_id INTEGER, title TEXT)")
raw.execute("CREATE INDEX book_author ON book(author_id)")
for a in range(1, 101):
    raw.execute("INSERT INTO author VALUES (?, ?)", (a, f"Author {a}"))
    raw.executemany("INSERT INTO book(author_id, title) VALUES (?, ?)",
                    [(a, f"Book {a}.{i}") for i in range(3)])

class Author:
    """What a lazy-loading ORM gives you: an object whose books load on first access."""
    def __init__(self, conn, row):
        self._conn, (self.id, self.name), self._books = conn, row, None
    @property
    def books(self):
        if self._books is None:                   # looks like an attribute, is a query
            self._books = self._conn.query("SELECT title FROM book WHERE author_id = ?", (self.id,))
        return self._books

def page_lazy(c):        # the innocent-looking loop in a template
    authors = [Author(c, r) for r in c.query("SELECT id, name FROM author")]
    return {a.name: len(a.books) for a in authors}

def page_join(c):        # ask for exactly what the page shows, in one query
    return dict(c.query("""SELECT a.name, COUNT(b.id) FROM author a
                           LEFT JOIN book b ON b.author_id = a.id GROUP BY a.id"""))

def page_prefetch(c):    # the ORM's "eager loading": one query for parents, one for all children
    authors = c.query("SELECT id, name FROM author")
    ids = [a for a, _ in authors]
    books = c.query(f"SELECT author_id FROM book WHERE author_id IN ({','.join('?' * len(ids))})", ids)
    counts = {}
    for (author_id,) in books:
        counts[author_id] = counts.get(author_id, 0) + 1
    return {name: counts.get(i, 0) for i, name in authors}

results = []
for fn in (page_lazy, page_join, page_prefetch):
    c = Connection(raw, rtt_ms=1.0)
    results.append(fn(c))
    print(f"{fn.__name__:14} {c.queries:4} queries  ~{c.latency_ms():5.0f} ms of round trips at 1 ms each")
print("same page every time:", results[0] == results[1] == results[2])

page_lazy       101 queries  ~  101 ms of round trips at 1 ms each
page_join         1 queries  ~    1 ms of round trips at 1 ms each
page_prefetch     2 queries  ~    2 ms of round trips at 1 ms each
same page every time: True

All three functions produce the same page. The lazy version sends 101 queries: one for the authors, then one for each author's books the moment the loop touches a.books. This is the N+1 query problem, and it is invisible in the code, because a.books reads like an attribute. Each query is fast, so it doesn't show up in a profiler either. What shows up is the page: at one millisecond per round trip to a database on another machine, the round trips alone cost a tenth of a second, and on a page with a thousand rows, a full second.

The fixes

There are two good fixes, and the example shows both. A join fetches parents and children in one query. For a count, as here, it's exact and minimal. The ORM's eager loading (select_related in Django, joinedload in SQLAlchemy) does the same for related objects. Prefetching fetches all the parents, then all their children in one IN (...) query, and stitches them together in memory: two queries regardless of N (prefetch_related, selectinload). Prefetching is often the better default for one-to-many relations, because a join repeats each parent's columns on every child row, and joining two collections at once multiplies them (exercise 4.2). Services built on GraphQL get the same effect from a batching loader that collects every id requested in one tick and fetches them together.

Other things the ORM hides

N+1 is the famous one, but not the only one. Loading full objects to change one field reads every column and writes them all back. Iterating over a query that returns a million rows can load them all into memory before the first iteration. Transaction boundaries are set by the framework's defaults, often one per request or one per statement, rather than by what the business operation needs. And the ORM writes whatever SQL its query builder produces, which may wrap an indexed column in a function and quietly defeat the index (chapter 8). None of this means avoiding ORMs. It means looking at the SQL they generate, which every ORM can log, and treating the number of queries per request as a quantity to test.

Write SQL directly where the relational model is the natural one: reports and aggregates, bulk updates (UPDATE ... WHERE touching a million rows should be one statement, not a million objects), window functions, and anything performance-critical you want to read in an EXPLAIN. Most ORMs make raw SQL easy and still map the results.

Why pages

Storage hardware doesn't hand out single bytes. Disks and SSDs transfer blocks, the operating system caches pages, and a read of one byte costs the same as a read of the four or eight kilobytes around it. So databases organise everything in pages of a fixed size they choose: 4 KB by default in SQLite, 8 KB in PostgreSQL, 16 KB in MySQL's InnoDB. A table is a file of pages holding rows; an index is a file of pages holding keys. When a query needs a row, the database works out which page holds it, reads that page if it isn't already in memory, and looks inside.

Rows are placed in pages one of two ways. In a heap, PostgreSQL's default, rows go wherever there is room, in no particular order, and every index points at a row's physical location. In a clustered layout, InnoDB's primary key and SQLite's rowid tables, the rows themselves live in the leaves of the primary key's B-tree, sorted by key. Chapter 6 shows why that difference matters for lookups.

Inside a page

Rows vary in length, and the database needs to find any one of them quickly and move them around without breaking the indexes that point at them. The standard answer is the slotted page. A small header records how many slots exist and where free space ends. A slot directory grows forward from the front of the page, one fixed-size entry per row holding that row's offset and length. The rows themselves are packed backwards from the end. Free space is the gap in the middle, and the page is full when the two meet.

import struct

PAGE_SIZE = 4096
HEADER = struct.Struct("<HH")    # number of slots, offset where the record area begins
SLOT = struct.Struct("<HH")      # record offset, record length (length 0 means deleted)

class SlottedPage:
    """A fixed-size page. The slot directory grows from the front, records grow from the back,
    and free space is the gap between them."""
    def __init__(self):
        self.buf = bytearray(PAGE_SIZE)
        HEADER.pack_into(self.buf, 0, 0, PAGE_SIZE)
    def _slot_at(self, s):
        return HEADER.size + s * SLOT.size
    def free_space(self):
        n, start = HEADER.unpack_from(self.buf, 0)
        return start - self._slot_at(n)
    def insert(self, record):
        n, start = HEADER.unpack_from(self.buf, 0)
        if len(record) + SLOT.size > self.free_space():
            return None                                    # full: the caller tries another page
        start -= len(record)
        self.buf[start:start + len(record)] = record
        SLOT.pack_into(self.buf, self._slot_at(n), start, len(record))
        HEADER.pack_into(self.buf, 0, n + 1, start)
        return n                                           # the record id is (page, slot)
    def read(self, s):
        off, length = SLOT.unpack_from(self.buf, self._slot_at(s))
        return None if length == 0 else bytes(self.buf[off:off + length])
    def delete(self, s):
        off, _ = SLOT.unpack_from(self.buf, self._slot_at(s))
        SLOT.pack_into(self.buf, self._slot_at(s), off, 0)  # the bytes stay until compaction
    def compact(self):
        n, _ = HEADER.unpack_from(self.buf, 0)
        live = [(s, self.read(s)) for s in range(n)]
        start = PAGE_SIZE
        for s, rec in live:
            if rec is not None:
                start -= len(rec)
                self.buf[start:start + len(rec)] = rec
                SLOT.pack_into(self.buf, self._slot_at(s), start, len(rec))
        HEADER.pack_into(self.buf, 0, n, start)            # slots keep their numbers

page = SlottedPage()
slots = []
while (s := page.insert(f"order {len(slots):04d} ".encode().ljust(100, b"."))) is not None:
    slots.append(s)
print(f"a {PAGE_SIZE}-byte page holds {len(slots)} records of 100 bytes; {page.free_space()} bytes left over")
before = page.read(1)
for s in slots[::2]:
    page.delete(s)
print("deleted every other record; free space before compaction:", page.free_space())
page.compact()
print("free space after compaction:", page.free_space())
print("record in slot 1 unchanged after compaction:", page.read(1) == before, "->", page.read(1)[:10])

a 4096-byte page holds 39 records of 100 bytes; 36 bytes left over
deleted every other record; free space before compaction: 36
free space after compaction: 2036
record in slot 1 unchanged after compaction: True -> b'order 0001'

Thirty-nine records of 100 bytes fill the page, with 36 bytes too few for a fortieth. Deleting every other record frees nothing: a delete only zeroes the slot's length, leaving the bytes where they were, because moving data on every delete would be expensive. The space comes back when the page is compacted, all at once, and 2,036 bytes reappear. The slot numbers survive compaction, so a record's id, its page and slot, stays valid. PostgreSQL calls that id the ctid, and every index entry stores one. A value too large for a page goes to separate overflow pages, which PostgreSQL calls TOAST, and the page keeps a pointer.

The buffer pool

The buffer pool is the database's own page cache: a large region of memory divided into page-sized frames. Every page access goes through it. A hit costs a memory read; a miss costs a disk read, which is roughly a thousand times slower on an SSD and a hundred thousand times slower on a spinning disk. Changed pages are marked dirty and written back later (chapter 15 explains why that's safe). When the pool is full, a page has to be evicted, and which one is the whole game. The natural choice, least recently used, has a famous weakness.

import random
from collections import OrderedDict

class BufferPool:
    """Caches pages in memory. On a miss it 'reads from disk' and evicts the least recently used page.
    With a scan ring, large sequential scans reuse a few private buffers instead of the shared cache."""
    def __init__(self, capacity, scan_ring=0):
        self.capacity, self.cache, self.ring, self.ring_size = capacity, OrderedDict(), OrderedDict(), scan_ring
        self.disk_reads = 0
    def get(self, page_id, scan=False):
        if page_id in self.cache:
            self.cache.move_to_end(page_id)
            return
        self.disk_reads += 1
        if scan and self.ring_size:
            self.ring[page_id] = True
            if len(self.ring) > self.ring_size:
                self.ring.popitem(last=False)
            return
        self.cache[page_id] = True
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

random.seed(5)
hot = list(range(80))                       # an index and a few busy tables: the working set
for name, pool in (("plain LRU", BufferPool(100)), ("LRU + scan ring", BufferPool(100, scan_ring=8))):
    for _ in range(2000):
        pool.get(random.choice(hot))        # warm up: the hot pages settle into the cache
    for p in range(1000, 11000):
        pool.get(p, scan=True)              # someone runs a report that scans a 10,000-page table
    still = sum(p in pool.cache for p in hot)
    before = pool.disk_reads
    for _ in range(1000):
        pool.get(random.choice(hot))
    print(f"{name:16} hot pages still cached after the scan: {still:2}/80 | "
          f"disk reads for the next 1000 hot lookups: {pool.disk_reads - before}")

plain LRU        hot pages still cached after the scan:  0/80 | disk reads for the next 1000 hot lookups: 80
LRU + scan ring  hot pages still cached after the scan: 80/80 | disk reads for the next 1000 hot lookups: 0

Eighty hot pages, the indexes and busy tables the application touches constantly, sit comfortably in a 100-page pool. Then one report scans a 10,000-page table. Under plain LRU, each scanned page is the most recently used, so the scan pushes every hot page out. Afterwards, the next thousand ordinary lookups need 80 disk reads to warm the cache back up. That is sequential flooding, and it explains the classic complaint that "the app is slow every morning after the overnight report". With a scan ring, large sequential scans recycle a handful of private buffers and leave the shared cache alone. PostgreSQL does exactly this for big sequential scans; InnoDB instead inserts new pages at the midpoint of its LRU list, so a page must be touched twice before it can push out the hot ones.

What this means for your schema and queries

Because pages are the unit of cost, row width matters. A table of 200-byte rows fits about forty rows in an 8 KB page; at 2,000 bytes, four. The same million-row scan reads ten times as many pages. Keep large, rarely read columns in a separate table or let the database move them out of line, select only the columns you need, and size the buffer pool so the working set, the pages your hot queries touch, fits in memory. A database whose working set fits in RAM behaves like a different machine from one whose working set doesn't.

Wide and shallow

A binary search tree over a billion keys is about 30 levels deep, and if every level is a separate disk read, a lookup costs 30 reads. A B-tree puts as many keys in a node as fit in a page. With 8-byte keys and 8 KB pages, that's around 500 children per node, so each level multiplies the reach by 500: 500 rows at one level, 250,000 at two, 125 million at three, 60 billion at four. Better still, the root and the next level are touched by every lookup, so they stay in the buffer pool permanently. In practice a lookup in a huge table costs one or two real disk reads.

Search, insert and split

A search starts at the root, picks the child whose range contains the key, and repeats until it reaches a leaf. An insert finds the leaf the key belongs in and adds it. If the leaf overflows, it splits in two and a separator key goes up to the parent; if the parent overflows, it splits too. When the root splits, a new root is created above it, so the tree only ever grows at the top and every leaf stays at the same depth. That is what keeps a B-tree balanced without any rebalancing pass.

import bisect, math, random

class Node:
    def __init__(self, leaf):
        self.leaf, self.keys, self.children, self.values, self.next = leaf, [], [], [], None

class BPlusTree:
    """Keys live in leaves, chained left to right; inner nodes hold only separators."""
    def __init__(self, max_keys):
        self.root, self.max_keys, self.splits = Node(leaf=True), max_keys, 0
    def search(self, key):
        node, visited = self.root, 1
        while not node.leaf:
            node = node.children[bisect.bisect_right(node.keys, key)]
            visited += 1
        i = bisect.bisect_left(node.keys, key)
        hit = i < len(node.keys) and node.keys[i] == key
        return (node.values[i] if hit else None), visited
    def insert(self, key, value):
        split = self._insert(self.root, key, value)
        if split:                                    # the root split: the tree grows at the top
            sep, right = split
            root = Node(leaf=False)
            root.keys, root.children = [sep], [self.root, right]
            self.root = root
    def _insert(self, node, key, value):
        if node.leaf:
            i = bisect.bisect_left(node.keys, key)
            if i < len(node.keys) and node.keys[i] == key:
                node.values[i] = value
                return None
            node.keys.insert(i, key); node.values.insert(i, value)
        else:
            i = bisect.bisect_right(node.keys, key)
            split = self._insert(node.children[i], key, value)
            if not split:
                return None
            sep, right = split
            node.keys.insert(i, sep); node.children.insert(i + 1, right)
        return self._split(node) if len(node.keys) > self.max_keys else None
    def _split(self, node):
        self.splits += 1
        mid, right = len(node.keys) // 2, Node(node.leaf)
        if node.leaf:
            right.keys, right.values = node.keys[mid:], node.values[mid:]
            node.keys, node.values = node.keys[:mid], node.values[:mid]
            right.next, node.next = node.next, right        # keep the leaf chain intact
            return right.keys[0], right                       # copy the first right key up
        sep = node.keys[mid]
        right.keys, right.children = node.keys[mid + 1:], node.children[mid + 1:]
        node.keys, node.children = node.keys[:mid], node.children[:mid + 1]
        return sep, right                                     # move the middle key up
    def range(self, lo, hi):
        node = self.root
        while not node.leaf:
            node = node.children[bisect.bisect_right(node.keys, lo)]
        out = []
        while node:                                           # walk the chain, no going back up
            for k in node.keys:
                if k > hi:
                    return out
                if k >= lo:
                    out.append(k)
            node = node.next
        return out
    def height(self):
        h, node = 1, self.root
        while not node.leaf:
            node, h = node.children[0], h + 1
        return h

def levels(tree):
    rows, level = [], [tree.root]
    while level:
        rows.append("  ".join(str(n.keys) for n in level))
        level = [] if level[0].leaf else [c for n in level for c in n.children]
    return rows

small = BPlusTree(max_keys=4)
for k in range(1, 11):
    small.insert(k, f"row {k}")
print("keys 1..10, at most 4 keys per node:")
for row in levels(small):
    print("  ", row)

random.seed(1)
big = BPlusTree(max_keys=100)
keys = random.sample(range(10_000_000), 100_000)
for k in keys:
    big.insert(k, k)
value, visited = big.search(keys[12345])
print(f"\n100,000 random keys, up to 100 per node: height {big.height()}, {big.splits} splits, "
      f"a lookup visits {visited} nodes")
print("range 500..600000 via the leaf chain:", len(big.range(500, 600_000)), "keys, all in order:",
      big.range(500, 600_000) == sorted(k for k in keys if 500 <= k <= 600_000))

print("\nlevels needed with 8 KB pages about 70% full:")
for fanout, kind in ((500, "8-byte keys"), (100, "wide keys, ~80 bytes")):
    print(f"  {kind:22}(fanout ~{fanout}): " + ", ".join(
        f"{n:>13,} rows -> {math.ceil(math.log(n, fanout * 0.7))} levels" for n in (10**6, 10**9)))

keys 1..10, at most 4 keys per node:
   [3, 5, 7]
   [1, 2]  [3, 4]  [5, 6]  [7, 8, 9, 10]

100,000 random keys, up to 100 per node: height 3, 1458 splits, a lookup visits 3 nodes
range 500..600000 via the leaf chain: 6021 keys, all in order: True

levels needed with 8 KB pages about 70% full:
  8-byte keys           (fanout ~500):     1,000,000 rows -> 3 levels, 1,000,000,000 rows -> 4 levels
  wide keys, ~80 bytes  (fanout ~100):     1,000,000 rows -> 4 levels, 1,000,000,000 rows -> 5 levels

The small tree shows the shape after ten sequential inserts: a root of separators over four leaves. It also shows a real-world quirk. Because each new key was larger than everything before it, the splits always happened at the right edge, leaving half-full leaves behind and a full one at the end. Real engines detect ascending inserts and split unevenly so that pages stay full. Random keys are worse: they land in a random leaf, so they cause splits everywhere, leave pages around 70% full, and touch a different page on every insert. That's why random UUIDs make poor clustered primary keys, and why time-ordered ids such as UUIDv7 or ULIDs exist.

The large tree holds 100,000 random keys in just three levels, with 1,458 splits along the way, and every lookup visits exactly three nodes. The range scan finds its first leaf with one descent, then walks the leaf chain, returning 6,021 keys already in order. That chain is why ORDER BY on an indexed column can cost nothing: the index is already sorted. The capacity lines are the arithmetic that matters. With 8-byte keys, a billion rows need four levels; wider keys mean fewer per page and an extra level.

Clustered and secondary indexes

Databases use the B+tree variant shown here, where inner nodes hold only separators and the data lives in the leaves. What a leaf holds depends on the index. In a clustered index, the leaf holds the row itself: InnoDB stores every table this way, ordered by primary key, and SQLite does the same by rowid. A secondary index leaf holds the indexed value plus a way to find the row. In PostgreSQL that's the row's physical location, the ctid from chapter 5. In InnoDB it's the primary key, so a secondary lookup is two descents, one through the secondary index and one through the clustered one. That design keeps secondary indexes valid when rows move, at the cost of the second descent.

Every index costs writes. An insert adds an entry to every index on the table, and an update to an indexed column deletes the old entry and inserts a new one. Deleted entries leave space that is reused later rather than immediately, so heavily churned indexes grow larger than their contents. The right number of indexes is the smallest number that serves your queries, which chapter 8 makes precise.

Writes go to memory first

In an LSM tree, a write is appended to a log for durability (the same idea as chapter 15) and inserted into the memtable, a sorted structure in memory. Nothing on disk is touched. When the memtable fills, it is written out in one sequential pass as a sorted, immutable file, usually called an SSTable (sorted string table), and a fresh memtable takes its place. Updates and deletes are writes too: an update is just a newer value for the key, and a delete writes a marker called a tombstone. Old values aren't removed; they're shadowed by newer ones.

Reads look everywhere a key could be

A read checks the memtable, then each run from newest to oldest, and stops at the first version it finds, which is by construction the newest. A tombstone means the key was deleted. Each run is sorted, so finding a key within one is a binary search over a small index of its pages. The problem is the number of runs: a key that was never written, or was written long ago, means checking every run. Two tools keep this under control. Bloom filters, one per run, answer "definitely not here" for most runs a key isn't in, using about ten bits per key. Compaction merges runs so there are fewer of them to check.

import bisect, hashlib, random

TOMBSTONE = "<deleted>"

class Bloom:
    """Answers 'definitely not here' or 'maybe here' using a few bits per key."""
    def __init__(self, keys, bits_per_key=10, k=7):
        self.m, self.k = max(64, len(keys) * bits_per_key), k
        self.bits = bytearray(self.m // 8 + 1)
        for key in keys:
            for h in self._hashes(key):
                self.bits[h // 8] |= 1 << (h % 8)
    def _hashes(self, key):
        d = hashlib.blake2b(str(key).encode(), digest_size=16).digest()
        a, b = int.from_bytes(d[:8], "little"), int.from_bytes(d[8:], "little")
        return [(a + i * b) % self.m for i in range(self.k)]
    def might_contain(self, key):
        return all(self.bits[h // 8] >> (h % 8) & 1 for h in self._hashes(key))

class SSTable:
    """A sorted run written once and never modified."""
    def __init__(self, items, bloom):
        self.keys, self.vals = [k for k, _ in items], [v for _, v in items]
        self.bloom = Bloom(self.keys) if bloom else None
    def find(self, key):
        i = bisect.bisect_left(self.keys, key)
        return (True, self.vals[i]) if i < len(self.keys) and self.keys[i] == key else (False, None)

class LSMTree:
    def __init__(self, memtable_size=100, compact_at=None, bloom=False):
        self.mem, self.runs = {}, []                       # runs: newest first
        self.memtable_size, self.compact_at, self.bloom = memtable_size, compact_at, bloom
        self.user_writes = self.disk_writes = self.probes = 0
    def put(self, key, value):
        self.user_writes += 1
        self.mem[key] = value                              # writes only ever touch memory...
        if len(self.mem) >= self.memtable_size:
            self._flush()
    def delete(self, key):
        self.put(key, TOMBSTONE)                           # ...even deletes, which are writes
    def _flush(self):
        items = sorted(self.mem.items())
        self.mem = {}
        self.runs.insert(0, SSTable(items, self.bloom))    # ...then go to disk as one sorted run
        self.disk_writes += len(items)
        if self.compact_at and len(self.runs) >= self.compact_at:
            self._compact()
    def _compact(self):
        merged = {}
        for run in reversed(self.runs):                    # oldest first, so newer values win
            merged.update(zip(run.keys, run.vals))
        items = [(k, v) for k, v in sorted(merged.items()) if v != TOMBSTONE]
        self.runs = [SSTable(items, self.bloom)]           # rewrite everything as one run
        self.disk_writes += len(items)
    def get(self, key):
        if key in self.mem:
            return None if self.mem[key] == TOMBSTONE else self.mem[key]
        for run in self.runs:
            if run.bloom and not run.bloom.might_contain(key):
                continue                                   # skipped without reading it
            self.probes += 1
            found, value = run.find(key)
            if found:
                return None if value == TOMBSTONE else value
        return None
    def stored(self):
        return sum(len(r.keys) for r in self.runs) + len(self.mem)

random.seed(7)
writes = [(random.randrange(5000), i) for i in range(20_000)]      # 5,000 keys, each updated ~4 times
present = random.sample(range(5000), 1000)
missing = [10**6 + i for i in range(1000)]
print(f"{'':28}{'runs':>5}{'write amp':>11}{'space amp':>11}{'reads/hit':>11}{'reads/miss':>12}")
for name, tree in (("no compaction, no Bloom", LSMTree()),
                   ("no compaction, Bloom", LSMTree(bloom=True)),
                   ("compact at 4 runs, Bloom", LSMTree(compact_at=4, bloom=True))):
    for k, v in writes:
        tree.put(k, v)
    live = len({k for k, _ in writes})
    tree.probes = 0
    for k in present:
        tree.get(k)
    per_hit = tree.probes / len(present)
    tree.probes = 0
    for k in missing:
        tree.get(k)
    per_miss = tree.probes / len(missing)
    print(f"{name:28}{len(tree.runs):5}{tree.disk_writes / tree.user_writes:10.1f}x"
          f"{tree.stored() / live:10.1f}x{per_hit:11.1f}{per_miss:12.1f}")

tree.delete(present[0])
print("\nafter delete:", tree.get(present[0]), "| the tombstone hides the old value until compaction removes both")

                             runs  write amp  space amp  reads/hit  reads/miss
no compaction, no Bloom       198       1.0x       4.0x       48.4       198.0
no compaction, Bloom          198       1.0x       4.0x        1.4         2.0
compact at 4 runs, Bloom        3      13.4x       1.0x        1.0         0.0

after delete: None | the tombstone hides the old value until compaction removes both

The table holds the whole trade-off in three rows. Without compaction, writes are as cheap as they can be: each entry is written to disk exactly once, a write amplification of 1.0. But all 20,000 versions of 5,000 keys stay on disk, a space amplification of 4.0, and reads are dreadful: finding a present key checks 48 runs on average, and proving a key absent checks all 198. Bloom filters rescue the reads without changing anything else, down to 1.4 and 2.0 runs. Compaction rescues the space too, down to 1.0, with about one run read per lookup, but it pays by rewriting live data again and again: every entry was written 13.4 times. This is the RUM conjecture in miniature: you can optimise for reads, updates or memory (space), and improving one costs at least one of the others.

Compaction strategies

Real systems compact more cleverly than "merge everything at four runs", but they choose between the same costs. Size-tiered compaction, Cassandra's long-time default, merges runs of similar size: it rewrites data fewer times, but may hold several versions of a key for a while, and needs free disk space as large as the runs being merged. Leveled compaction, used by LevelDB and RocksDB, keeps data in levels that each grow about ten times larger, with no overlapping keys within a level. Space and read costs stay tightly bounded, and data gets rewritten more often. Tombstones are their own hazard. A tombstone can only be dropped once compaction reaches the oldest run that might hold the key, so a workload that deletes heavily can leave reads wading through tombstones in the meantime.

B-tree or LSM tree?

B-trees suit read-heavy workloads that want predictable latency: every read is a fixed number of page reads, and no background process competes for the disk. LSM trees suit write-heavy workloads: event logs, metrics, messaging, anything that ingests far more than it updates. They also compress well, because runs are immutable and sorted, and they write sequentially. They power RocksDB (and through it MyRocks, CockroachDB's Pebble and TiKV), Cassandra, ScyllaDB and most time-series stores. Discord stores its message history this way: it moved it to Cassandra in 2017 and to ScyllaDB in 2023. B-trees have write amplification too, which is easy to forget: changing 100 bytes rewrites an 8 KB page, and if the change touches five indexes, five pages.

Reading the plan

Every database will tell you how it intends to run a query. SQLite's EXPLAIN QUERY PLAN prints one line per step; PostgreSQL and MySQL's EXPLAIN print a tree, and their EXPLAIN ANALYZE actually runs the query and adds real row counts and timings to each step. The words to look for are few. A scan reads a whole table or index (SCAN in SQLite, Seq Scan in PostgreSQL). A search descends an index to the matching entries (SEARCH ... USING INDEX, Index Scan). A covering or index-only scan answers from the index without touching the table at all. The example below runs four index lessons against SQLite's real planner, on a 200,000-row orders table, and measures the work as the number of instructions SQLite's engine executes, a count that comes out identical on every run.

import random, sqlite3
from datetime import date, timedelta

random.seed(8)
db = sqlite3.connect(":memory:")
db.execute("""CREATE TABLE orders(id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT,
                                  created_at TEXT, total_cents INTEGER)""")
start = date(2025, 1, 1)
db.executemany("INSERT INTO orders(customer_id, status, created_at, total_cents) VALUES (?, ?, ?, ?)",
    ((random.randint(1, 20_000),
      random.choices(["shipped", "pending", "cancelled"], [85, 10, 5])[0],
      (start + timedelta(days=random.randrange(638))).isoformat(),
      random.randint(500, 50_000)) for _ in range(200_000)))

def plan(sql):
    return " / ".join(row[-1] for row in db.execute("EXPLAIN QUERY PLAN " + sql))

def work(sql):
    """Virtual-machine steps SQLite executes for the query: a deterministic measure of effort."""
    steps = 0
    def tick():
        nonlocal steps
        steps += 1
        return 0
    db.set_progress_handler(tick, 10)                 # called every 10 instructions
    db.execute(sql).fetchall()
    db.set_progress_handler(None, 0)
    return steps * 10

def show(label, sql, count=True):
    effort = f"{work(sql):>10,} steps" if count else " " * 16
    print(f"  {label:34} {effort}  {plan(sql)}")

def reset(*indexes):
    for (name,) in db.execute("SELECT name FROM sqlite_master WHERE type = 'index'").fetchall():
        db.execute(f"DROP INDEX {name}")
    for ddl in indexes:
        db.execute(ddl)

q1 = "SELECT * FROM orders WHERE customer_id = 4242"
print("1. equality lookup")
reset(); show("no index", q1)
reset("CREATE INDEX by_customer ON orders(customer_id)"); show("index on customer_id", q1)

q2 = "SELECT id FROM orders WHERE status = 'pending' AND created_at >= '2026-09-01'"
print("2. composite index: column order")
reset("CREATE INDEX by_created_status ON orders(created_at, status)"); show("(created_at, status): range first", q2)
reset("CREATE INDEX by_status_created ON orders(status, created_at)"); show("(status, created_at): equality first", q2)

print("3. a function on the column hides it from the index")
reset("CREATE INDEX by_created ON orders(created_at)")
show("substr(created_at, 1, 7) = ...", "SELECT id FROM orders WHERE substr(created_at, 1, 7) = '2026-09'")
show("created_at range, same rows", "SELECT id FROM orders WHERE created_at >= '2026-09-01' AND created_at < '2026-10-01'")

q4 = "SELECT created_at, total_cents FROM orders WHERE customer_id = 4242"
print("4. covering index: answer from the index alone (each table lookup is one step here, so see chapter 11 for timings)")
reset("CREATE INDEX by_customer ON orders(customer_id)"); show("index on customer_id", q4, count=False)
reset("CREATE INDEX by_customer_cover ON orders(customer_id, created_at, total_cents)"); show("index includes every column used", q4, count=False)

1. equality lookup
  no index                              600,070 steps  SCAN orders
  index on customer_id                      120 steps  SEARCH orders USING INDEX by_customer (customer_id=?)
2. composite index: column order
  (created_at, status): range first      29,800 steps  SEARCH orders USING COVERING INDEX by_created_status (created_at>?)
  (status, created_at): equality first      3,730 steps  SEARCH orders USING COVERING INDEX by_status_created (status=? AND created_at>?)
3. a function on the column hides it from the index
  substr(created_at, 1, 7) = ...        818,630 steps  SCAN orders USING COVERING INDEX by_created
  created_at range, same rows            37,250 steps  SEARCH orders USING COVERING INDEX by_created (created_at>? AND created_at<?)
4. covering index: answer from the index alone (each table lookup is one step here, so see chapter 11 for timings)
  index on customer_id                                 SEARCH orders USING INDEX by_customer (customer_id=?)
  index includes every column used                     SEARCH orders USING COVERING INDEX by_customer_cover (customer_id=?)

Rule 1: an index turns a scan into a search

Without an index, finding one customer's orders means reading all 200,000 rows: 600,070 steps. With one, it's a descent and a few entries: 120 steps, five thousand times less work. That ratio grows with the table, because a scan is linear and a B-tree descent is logarithmic.

Rule 2: equality columns first, then range

A composite index is sorted by its first column, then by its second within equal first values, like a phone book sorted by surname, then first name. That ordering decides what the index can find. With (status, created_at), all the 'pending' entries sit together, sorted by date, so "pending since September" is one contiguous slice: 3,730 steps. With (created_at, status), the index can only use the date range, and must read every entry from September 1st onwards, of every status, checking each one: 29,800 steps for the same answer. The general rule: put columns compared with = first and the one range column last. An index on (a, b, c) serves queries on a, on a and b, and on all three, but not on b alone. This is the leftmost prefix rule.

Rule 3: keep the column bare

An index on created_at is sorted by created_at, not by substr(created_at, 1, 7). Wrap the column in a function and the planner has no ordering to search, so it falls back to reading every entry and computing the function for each: 818,630 steps. The same rows, asked for as a range on the bare column, cost 37,250. This catches out WHERE date(created_at) = ..., WHERE lower(email) = ..., WHERE total_cents / 100 > 50, and implicit conversions, such as comparing a text column to a number. Rewrite the condition so the bare column is compared to a value, or, when you genuinely query by the expression, index the expression itself: CREATE INDEX ON users(lower(email)).

Rule 4: a covering index never touches the table

An ordinary index finds the matching entries and then fetches each row from the table to get the other columns: one more lookup per row, often to a random page. If the index contains every column the query uses, the plan says COVERING INDEX (PostgreSQL: Index Only Scan) and the table is never read. The instruction count can't show the saving, because each table lookup is a single instruction however many pages it reads, so chapter 11 measures it with a stopwatch instead. On a million rows, making the index covering cut the report from 31.3 ms to 3.1. PostgreSQL lets you add columns to an index purely for covering, without sorting by them: CREATE INDEX ON orders(customer_id) INCLUDE (total_cents).

Selectivity, and what indexes cost

An index pays off when it narrows the rows to a small fraction. An index on status, where 85% of rows are 'shipped', narrows almost nothing, and following it to 170,000 scattered rows is slower than reading the table in order: chapter 11 shows exactly that. If a small subset is what you query, a partial index indexes just that subset: CREATE INDEX ON orders(created_at) WHERE status = 'pending'. And every index has a price: space, cache, and work on every insert and update. Find the unused ones (PostgreSQL's pg_stat_user_indexes counts scans per index) and the redundant ones, since (a) is already served by (a, b), and drop them.

The iterator model

Most databases execute a plan with the iterator or Volcano model, named after the research system that formalised it. Every operator has the same three methods: open, next and close. Calling next() on the top operator makes it call next() on its children until it has a row to return. A filter pulls rows from the scan below until one passes; a projection pulls one row and trims its columns. Rows stream upwards, one at a time, through the whole tree, without the intermediate results ever being stored. This is pipelining, and it's why LIMIT 10 can return after reading a few dozen rows of a huge table.

Some operators can't pipeline. A sort can't return its first row until it has seen every row, because the last one might sort first. A hash join must read its whole build side before it can probe it, and a grouping aggregate must see every row of a group. These blocking operators break the stream: everything below them runs to completion first. Spotting them in a plan explains most "why didn't LIMIT help?" mysteries.

Four ways to join

A join combines rows from two inputs where a condition holds, and there are four basic algorithms. A nested loop compares every row of one input with every row of the other: simple, and fine when one side has a handful of rows. An index nested loop looks each outer row's key up in an index on the inner side; it's the workhorse of transactional queries, where the outer side is small and the inner side is indexed. A hash join builds a hash table on the smaller input and streams the larger one past it; it suits large inputs with no useful index, works only for equality conditions, and needs memory for the table. A sort-merge join sorts both inputs on the key and walks them together once; it's cheapest when both inputs already arrive sorted, from an index for instance, and it also handles range conditions.

import bisect, functools, random

random.seed(3)
customers = [(cid, random.choice(["EU", "US", "APAC"])) for cid in range(1, 1001)]
orders = [(oid, random.randint(1, 1000), random.randint(100, 50_000)) for oid in range(1, 20_001)]

def nested_loop(outer, inner):
    """For every outer row, scan every inner row."""
    out, work = [], 0
    for o in outer:
        for c in inner:
            work += 1
            if o[1] == c[0]:
                out.append(o + c)
    return out, work

def index_nested_loop(outer, inner):
    """For every outer row, look the key up in a sorted index (a stand-in for a B-tree)."""
    keys = sorted(c[0] for c in inner)
    by_key = {c[0]: c for c in inner}
    out, work = [], 0
    for o in outer:
        lo, hi = 0, len(keys)
        while lo < hi:                                   # binary search, counting each step
            work += 1
            mid = (lo + hi) // 2
            if keys[mid] < o[1]: lo = mid + 1
            else: hi = mid
        if lo < len(keys) and keys[lo] == o[1]:
            out.append(o + by_key[o[1]])
    return out, work

def hash_join(probe, build):
    """Build a hash table on the smaller input, then stream the larger one past it."""
    table, work = {}, 0
    for c in build:
        work += 1
        table.setdefault(c[0], []).append(c)
    out = []
    for o in probe:
        work += 1
        for c in table.get(o[1], ()):
            out.append(o + c)
    return out, work

def merge_join(left, right):
    """Sort both inputs on the key, then walk them together once."""
    comparisons = 0
    def counted(key):
        def cmp(a, b):
            nonlocal comparisons
            comparisons += 1
            return (key(a) > key(b)) - (key(a) < key(b))
        return functools.cmp_to_key(cmp)
    L = sorted(left, key=counted(lambda o: o[1]))
    R = sorted(right, key=counted(lambda c: c[0]))
    out, i, j, steps = [], 0, 0, 0
    while i < len(L) and j < len(R):
        steps += 1
        if L[i][1] < R[j][0]: i += 1
        elif L[i][1] > R[j][0]: j += 1
        else:
            out.append(L[i] + R[j]); i += 1               # customer ids are unique on the right
    return out, comparisons + steps

results = {}
for name, fn in (("nested loop", nested_loop), ("index nested loop", index_nested_loop),
                 ("hash join", hash_join), ("sort-merge join", merge_join)):
    rows, work = fn(orders, customers)
    results[name] = sorted(rows)
    print(f"{name:18} {len(rows):6} rows  {work:>12,} units of work")
print("all four produce the same rows:", len({tuple(map(tuple, r)) for r in results.values()}) == 1)

# The iterator model: each operator pulls rows from the one below, one at a time.
def scan(rows, stats):
    for r in rows:
        stats["read"] += 1
        yield r
def where(rows, predicate):
    return (r for r in rows if predicate(r))
def limit(rows, n):
    for i, r in enumerate(rows):
        if i == n:
            return
        yield r

stats = {"read": 0}
top = list(limit(where(scan(orders, stats), lambda o: o[2] > 45_000), 10))
print(f"\nLIMIT 10 over a filter: {len(top)} rows returned after reading {stats['read']} of {len(orders)}")
stats = {"read": 0}
top = list(limit(sorted(where(scan(orders, stats), lambda o: o[2] > 45_000), key=lambda o: -o[2]), 10))
print(f"add ORDER BY (a blocking sort): {len(top)} rows returned after reading {stats['read']} of {len(orders)}")

nested loop         20000 rows    20,000,000 units of work
index nested loop   20000 rows       199,578 units of work
hash join           20000 rows        21,000 units of work
sort-merge join     20000 rows       277,244 units of work
all four produce the same rows: True

LIMIT 10 over a filter: 10 rows returned after reading 77 of 20000
add ORDER BY (a blocking sort): 10 rows returned after reading 20000 of 20000

All four produce the same 20,000 rows; the work differs by a factor of a thousand. The plain nested loop does 20 million comparisons, one for every pair. The index nested loop needs about ten binary-search steps per order, 199,578 in all. The sort-merge join spends most of its 277,244 units sorting, and would be nearly free if both inputs arrived sorted. The hash join wins at 21,000: one pass to build a table of 1,000 customers, one pass to stream 20,000 orders past it. The last two lines show the iterator model at work. LIMIT 10 over a filter read just 77 rows before it had its ten and stopped pulling. Add ORDER BY, and the sort, a blocking operator, read all 20,000 first.

Which join, and who decides

The planner chooses the algorithm for each join, along with the order in which tables are joined, from its estimates of how many rows each side will produce (chapter 10). Engines differ in what they offer. PostgreSQL and SQL Server implement all of them. MySQL relied on nested loops until it added hash joins in version 8.0.18. SQLite implements only nested loops, and when no index fits, it builds a temporary one just for the query, which its plans report as an automatic index. In PostgreSQL plans, look for Nested Loop, Hash Join with a Hash node beneath it, and Merge Join, usually above a Sort. A hash join whose build side exceeds its memory budget (work_mem) spills to disk in batches and slows sharply; EXPLAIN ANALYZE reports the batch count.

Cost-based optimisation

For any non-trivial query there are many correct plans: which index to use for each table, which order to join the tables in, which algorithm for each join. A cost-based optimiser, an idea that dates back to IBM's System R in the 1970s, enumerates candidate plans, estimates each one's cost with a model that charges for page reads and CPU work, and picks the cheapest. The search space grows explosively with the number of tables, so planners use dynamic programming for small joins and heuristics beyond that; PostgreSQL switches to a genetic search above twelve tables. All of this rests on one input that's easy to forget: the estimated number of rows flowing out of each step. Get that wrong and the cheapest-looking plan can be the slowest.

What the planner knows

Statistics are gathered by ANALYZE, run manually or by a background process (PostgreSQL's autovacuum, MySQL's persistent statistics). For each table they record the row count. For each column, typically: the fraction of NULLs, the number of distinct values, a list of the most common values with their frequencies, and a histogram of the rest. To estimate WHERE country = 'US', the planner checks the common-values list; to estimate a range, it reads the histogram. For combinations of conditions, it usually assumes they're independent and multiplies their selectivities. Each of those steps can go wrong.

import random, sqlite3
from collections import Counter

random.seed(10)
N = 100_000
countries = ["US"] * 70 + [f"C{i:02d}" for i in range(30)]                 # 70% US, then a long tail
rows = []
for _ in range(N):
    country = random.choice(countries)
    city = random.choice(["Paris", "Lyon", "Nice"]) if country == "C07" else f"city-{random.randrange(400)}"
    rows.append((country, city))

# What a planner keeps per column: row count, distinct values, and the most common values.
distinct = {"country": len({c for c, _ in rows}), "city": len({t for _, t in rows})}
mcv = dict(Counter(c for c, _ in rows).most_common(5))

def actual(pred):
    return sum(1 for r in rows if pred(r))

print("1. skew: WHERE country = 'US'")
print(f"   uniform guess N/distinct = {N // distinct['country']:>6,}   with most-common-values list = "
      f"{mcv['US']:>6,}   actual = {actual(lambda r: r[0] == 'US'):,}")

print("2. correlation: WHERE country = 'C07' AND city = 'Paris'")
sel_country = actual(lambda r: r[0] == "C07") / N
sel_city = actual(lambda r: r[1] == "Paris") / N
estimate = round(N * sel_country * sel_city)
true_rows = actual(lambda r: r[0] == "C07" and r[1] == "Paris")
print(f"   independence guess = {estimate:>7,}   actual = {true_rows:,}   (every Paris row is in C07)")

print("3. the plan follows the estimate: join those rows to a 600-page customers table")
def cost_nested_loop(outer_rows): return outer_rows * 4          # one index descent, ~4 pages, per row
def cost_hash_join(outer_rows): return 600 + outer_rows * 0.1    # read customers once, probe in memory
for label, rows_in in (("estimated", estimate), ("actual", true_rows)):
    nl, hj = cost_nested_loop(rows_in), cost_hash_join(rows_in)
    print(f"   {label:9} {rows_in:>5} outer rows: nested loop {nl:>7,.0f}  hash join {hj:>7,.0f}  -> "
          f"{'nested loop' if nl < hj else 'hash join'}")

print("4. a real planner, before and after it gathers statistics")
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE orders(id INTEGER PRIMARY KEY, status TEXT, created_at TEXT)")
db.executemany("INSERT INTO orders(status, created_at) VALUES (?, ?)",
               ((random.choices(["shipped", "pending", "cancelled"], [85, 10, 5])[0],
                 f"2026-{random.randint(1, 9):02d}-{random.randint(1, 28):02d}") for _ in range(N)))
db.execute("CREATE INDEX by_status ON orders(status)")
q = "SELECT count(*) FROM orders WHERE status = 'shipped' AND created_at >= '2026-09-01'"
print("   before ANALYZE:", [r[-1] for r in db.execute("EXPLAIN QUERY PLAN " + q)])
db.execute("ANALYZE")
print("   after ANALYZE: ", [r[-1] for r in db.execute("EXPLAIN QUERY PLAN " + q)])
print("   what it learned:", db.execute("SELECT stat FROM sqlite_stat1 WHERE idx = 'by_status'").fetchone()[0],
      "(rows, rows per distinct value)")

1. skew: WHERE country = 'US'
   uniform guess N/distinct =  3,225   with most-common-values list = 70,117   actual = 70,117
2. correlation: WHERE country = 'C07' AND city = 'Paris'
   independence guess =       3   actual = 308   (every Paris row is in C07)
3. the plan follows the estimate: join those rows to a 600-page customers table
   estimated     3 outer rows: nested loop      12  hash join     600  -> nested loop
   actual      308 outer rows: nested loop   1,232  hash join     631  -> hash join
4. a real planner, before and after it gathers statistics
   before ANALYZE: ['SEARCH orders USING INDEX by_status (status=?)']
   after ANALYZE:  ['SCAN orders']
   what it learned: 100000 33334 (rows, rows per distinct value)

The first case is skew. Seventy percent of customers are in one country, but a planner that only knows the number of distinct values assumes they're spread evenly and guesses 3,225 rows where there are 70,117, an error of more than twenty times. A most-common-values list fixes it exactly, which is why databases keep one.

The second case is correlation. Every Paris row is in country C07, so the second condition adds no filtering at all. The planner, multiplying the two selectivities as if they were independent, estimates 3 rows; there are 308. The third block shows why that matters. At 3 rows, an index nested loop costs 12 page reads and looks far cheaper than a hash join's 600, so the planner picks it. At the real 308 rows, the nested loop costs 1,232 and the hash join would have cost 631. The plan was the right choice for the wrong number, and errors like this compound: in a query with five joins, a tenfold error at the bottom can become a millionfold error at the top.

The last block is a real planner changing its mind. Without statistics, SQLite assumes an equality condition is selective and uses the index on status. After ANALYZE, it knows the index has about 33,000 rows per distinct value, so following it would mean tens of thousands of scattered row lookups, and it switches to a plain scan. Chapter 11 measures both plans and confirms the planner is right to switch.

Why estimates go wrong

Beyond skew and correlation, the usual causes are stale statistics after a bulk load or a big delete, conditions the statistics can't see into (functions, expressions, LIKE patterns, values from a subquery), and parameter sensitivity. A prepared statement may be planned once for a generic parameter and reused for a value that matches a million rows instead of ten. Joins make all of these worse, because the error in each input's estimate multiplies through every join above it.

Fixing a bad plan

Start with EXPLAIN ANALYZE and compare each step's estimated rows with its actual rows. The step where they first diverge badly is where the plan went wrong, and everything above it inherited the error. Then work through the fixes in order of how well they age. Run ANALYZE, and make it the last step of every bulk load. Raise the statistics detail for skewed columns (PostgreSQL's per-column STATISTICS target). Tell the planner about correlated columns: PostgreSQL's CREATE STATISTICS ... (dependencies) exists for exactly the Paris case. If none of that works, rewrite the query: split it, or materialise an intermediate result whose size is then known. Hints and forced indexes come last. They fix today's plan by freezing it, and they keep forcing it after the data has changed so much that it's wrong.

The method

Start with data that resembles production: the same row count, or close to it, and the same distributions. A query tuned on ten thousand evenly spread rows tells you nothing about ten million skewed ones. Measure each version several times and take the median, so one slow run doesn't mislead you, and note whether the cache was warm. Read the plan before changing anything, form a hypothesis about what it's doing badly, and change one thing. Then measure again, check the result is identical, and record the plan and the time. The record matters as much as the speed-up: it's how you explain the change in review, and how the next person learns why the index exists.

The query

The table holds a million orders spread over 21 months, 85% of them shipped. The report wants daily shipped revenue for September 2026, about 4.7% of the table. Here is the whole session, run against a real SQLite database. The output is one recorded run on a laptop; your timings will differ, but the ratios and the plans won't.

import random, sqlite3, statistics, time
from datetime import date, timedelta

random.seed(11)
db = sqlite3.connect(":memory:")
db.execute("""CREATE TABLE orders(id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT,
                                  created_at TEXT, total_cents INTEGER)""")
start = date(2025, 1, 1)
days = [(start + timedelta(days=d)).isoformat() for d in range(638)]
db.executemany("INSERT INTO orders(customer_id, status, created_at, total_cents) VALUES (?, ?, ?, ?)",
    ((random.randint(1, 50_000), random.choices(["shipped", "pending", "cancelled"], [85, 10, 5])[0],
      random.choice(days), random.randint(500, 50_000)) for _ in range(1_000_000)))

QUERY = """SELECT created_at AS day, COUNT(*) AS orders, SUM(total_cents) AS revenue
           FROM orders
           WHERE status = 'shipped' AND created_at >= '2026-09-01' AND created_at < '2026-10-01'
           GROUP BY created_at"""

def measure(label):
    plan = " / ".join(r[-1] for r in db.execute("EXPLAIN QUERY PLAN " + QUERY))
    times = []
    for _ in range(5):
        t = time.perf_counter()
        result = db.execute(QUERY).fetchall()
        times.append((time.perf_counter() - t) * 1000)
    ms = statistics.median(times)
    print(f"{label}\n   plan: {plan}\n   median of 5 runs: {ms:7.1f} ms   ({len(result)} days)")
    return ms, result

print(f"{db.execute('SELECT COUNT(*) FROM orders').fetchone()[0]:,} orders; report: daily shipped revenue for September 2026\n")
base_ms, expected = measure("step 0: no index")

db.execute("CREATE INDEX by_status ON orders(status)")
ms1, r1 = measure("step 1: index on status (85% of rows are 'shipped')")

db.execute("ANALYZE")
ms2, r2 = measure("step 2: ANALYZE, so the planner knows status barely filters")

db.execute("DROP INDEX by_status")
db.execute("CREATE INDEX by_created ON orders(created_at)")
db.execute("ANALYZE")
ms3, r3 = measure("step 3: index on created_at, the selective column")

db.execute("DROP INDEX by_created")
db.execute("CREATE INDEX by_status_created_total ON orders(status, created_at, total_cents)")
db.execute("ANALYZE")
ms4, r4 = measure("step 4: covering index: equality column, then range column, then the summed column")

assert r1 == r2 == r3 == r4 == expected                 # same answer at every step
print(f"\nsame result at every step: True | {base_ms:.0f} ms -> {ms4:.1f} ms, "
      f"{base_ms / ms4:.0f}x faster | under 50 ms: {ms4 < 50}")

1,000,000 orders; report: daily shipped revenue for September 2026

step 0: no index
   plan: SCAN orders / USE TEMP B-TREE FOR GROUP BY
   median of 5 runs:    68.2 ms   (30 days)
step 1: index on status (85% of rows are 'shipped')
   plan: SEARCH orders USING INDEX by_status (status=?) / USE TEMP B-TREE FOR GROUP BY
   median of 5 runs:    82.4 ms   (30 days)
step 2: ANALYZE, so the planner knows status barely filters
   plan: SCAN orders / USE TEMP B-TREE FOR GROUP BY
   median of 5 runs:    68.3 ms   (30 days)
step 3: index on created_at, the selective column
   plan: SEARCH orders USING INDEX by_created (created_at>? AND created_at<?)
   median of 5 runs:    31.3 ms   (30 days)
step 4: covering index: equality column, then range column, then the summed column
   plan: SEARCH orders USING COVERING INDEX by_status_created_total (status=? AND created_at>? AND created_at<?)
   median of 5 runs:     3.1 ms   (30 days)

same result at every step: True | 68 ms -> 3.1 ms, 22x faster | under 50 ms: True

Reading the session

Step 0, 68.2 ms. With no index, the plan is a scan of all million rows followed by a temporary B-tree to group the results by day. That's not terrible for a scan, but it reads every page to use one row in twenty.

Step 1, 82.4 ms: slower. An index on status looks like the obvious move, since the query filters on it, and with no statistics the planner assumes an equality condition is selective and uses it. But 85% of rows match. Following the index means about 850,000 row lookups in index order, each landing on a scattered page, instead of one sequential pass through the table. A low-selectivity index can be worse than none, and this is what it looks like.

Step 2, 68.3 ms. ANALYZE tells the planner what step 1 found out the hard way: status barely filters. With the statistics, it abandons the index and goes back to the scan, and the time returns to the baseline. The useless index is still costing every insert and update, so the next step drops it.

Step 3, 31.3 ms. An index on created_at, the selective column, narrows the read to September's 47,000 or so rows. Two things changed in the plan. The SEARCH ... (created_at>? AND created_at<?) line shows the index is used for the range, and the temporary B-tree for grouping has disappeared: the index delivers rows already in date order, so each day's group arrives together and no sort is needed. What's left is a table lookup per row, to check status and read total_cents.

Step 4, 3.1 ms. A covering index on (status, created_at, total_cents) follows all of chapter 8's rules at once. The equality column comes first, so the shipped orders are contiguous; the range column comes second, so September's shipped orders are one slice; and the summed column is included, so the plan says COVERING INDEX and never touches the table. The answer is identical at every step, the final time is 22 times faster than the scan, and it is comfortably under the fifty-millisecond target.

Writing it down

The deliverable asks for each plan change to be documented, and a table like this is enough. It's what a reviewer needs and what the next engineer will thank you for.

What it costs, and what else would work

The covering index isn't free. It is a second copy of three columns for every row, and every insert, and every update to those columns, now maintains another B-tree. For a report on a dashboard that refreshes every minute, that's a good trade. For a report run once a month, a slower query is fine and the index is waste. Indexes also aren't the only tool. A summary table of revenue per day, updated as orders ship, answers the report by reading thirty rows. A materialised view does the same with the refresh managed by the database. Partitioning the orders table by month lets the planner skip every partition but September's. And a cache in front of the database (chapter 19) can skip the query altogether. Pick by how fresh the answer must be and how often it's asked.

A transaction is the unit of every promise

A transaction is a group of statements between BEGIN and COMMIT that the database treats as one indivisible unit. Every ACID promise is made per transaction, which makes it important to know where your transactions actually begin and end. Many drivers default to autocommit, where every statement is its own transaction, so a two-statement operation is two separate promises, not one. Others open transactions implicitly and leave them open until you commit, as chapter 2's foreign-key trap showed. The example runs the classic test, a transfer that dies halfway, both ways.

import os, sqlite3, tempfile

path = os.path.join(tempfile.mkdtemp(), "bank.db")
db = sqlite3.connect(path, isolation_level=None)          # autocommit unless we say BEGIN
db.executescript("""
CREATE TABLE accounts(id TEXT PRIMARY KEY, balance INTEGER NOT NULL CHECK (balance >= 0));
INSERT INTO accounts VALUES ('alice', 100), ('bob', 50);
""")

def balances():
    rows = dict(db.execute("SELECT id, balance FROM accounts ORDER BY id"))
    return f"{rows}  total {sum(rows.values())}"

def reset():
    db.execute("UPDATE accounts SET balance = CASE id WHEN 'alice' THEN 100 ELSE 50 END")

class Crash(Exception):
    pass

def transfer(src, dst, amount, crash=False, atomic=True):
    if atomic:
        db.execute("BEGIN")
    try:
        db.execute("UPDATE accounts SET balance = balance - ? WHERE id = ?", (amount, src))
        if crash:
            raise Crash("the process died between the two updates")
        db.execute("UPDATE accounts SET balance = balance + ? WHERE id = ?", (amount, dst))
        if atomic:
            db.execute("COMMIT")
        return "ok"
    except (Crash, sqlite3.IntegrityError) as e:
        if atomic:
            db.execute("ROLLBACK")
        return f"failed ({e})"

print("start:                       ", balances())
print("A. no transaction, crash:    ", transfer("alice", "bob", 30, crash=True, atomic=False))
print("                             ", balances(), "<- 30 vanished")
reset()
print("B. transaction, crash:       ", transfer("alice", "bob", 30, crash=True))
print("                             ", balances())
print("C. transaction, overdraft:   ", transfer("bob", "alice", 500))
print("                             ", balances())

db.execute("BEGIN")
db.execute("UPDATE accounts SET balance = balance - 10 WHERE id = 'alice'")
db.execute("SAVEPOINT bonus")
db.execute("UPDATE accounts SET balance = balance + 999 WHERE id = 'bob'")
db.execute("ROLLBACK TO bonus")                           # undo only the work since the savepoint
db.execute("UPDATE accounts SET balance = balance + 10 WHERE id = 'bob'")
db.execute("COMMIT")
print("D. savepoint undid the bonus:", balances())

db.close()
reopened = sqlite3.connect(path)
print("E. after reopening the file: ", dict(reopened.execute("SELECT id, balance FROM accounts ORDER BY id")))

start:                        {'alice': 100, 'bob': 50}  total 150
A. no transaction, crash:     failed (the process died between the two updates)
                              {'alice': 70, 'bob': 50}  total 120 <- 30 vanished
B. transaction, crash:        failed (the process died between the two updates)
                              {'alice': 100, 'bob': 50}  total 150
C. transaction, overdraft:    failed (CHECK constraint failed: balance >= 0)
                              {'alice': 100, 'bob': 50}  total 150
D. savepoint undid the bonus: {'alice': 90, 'bob': 60}  total 150
E. after reopening the file:  {'alice': 90, 'bob': 60}

Atomicity: all or nothing

Case A is the bug every financial system fears. Without a transaction, the debit committed on its own and the credit never happened, so 30 left the system. Case B runs the same crash inside a transaction: the rollback undoes the debit and the books still balance. The database delivers this by recording how to undo each change until the commit. SQLite keeps a rollback journal or, in WAL mode, doesn't touch the main file until commit; PostgreSQL keeps old row versions; InnoDB writes undo records. However it's done, the promise is the same: a failed transaction leaves no trace.

Consistency: the rules the database knows

Case C is consistency as the database understands it: the transfer would have made Bob's balance negative, the CHECK constraint refused it, and the whole transaction rolled back. That's the limit of the database's version of consistency: it enforces the constraints you declared and nothing else. The rule that the total of all balances never changes in a transfer is consistency too, but no constraint expresses it. It holds only because the debit and credit are in one transaction. That's why the C in ACID is the application's responsibility, and why chapter 2 pushed so hard on declaring constraints.

Isolation, briefly

Isolation promises that concurrent transactions don't see each other's half-finished work. Fully honoured, it means they behave as if they ran one at a time, a level called serializable. Most databases default to weaker levels that are faster and allow specific anomalies, and chapter 13 shows exactly which. The savepoint in case D is a smaller tool: a named point inside a transaction you can roll back to without abandoning the whole thing, which is useful when one step of a larger operation may fail and be skipped.

Durability: committed means committed

Case E reopens the database file: the committed transfer and the savepoint result are there, because a commit isn't acknowledged until its log record is flushed to disk (chapter 15). Durability can be weakened deliberately for speed. PostgreSQL's synchronous_commit = off, MySQL's innodb_flush_log_at_trx_commit = 2 and SQLite's synchronous = NORMAL each acknowledge commits before the flush, risking the last fraction of a second of commits in a crash, without corrupting anything. Hardware can weaken it accidentally: a disk with a volatile write cache that reports a flush as done before it is. Servers use drives with power-loss protection for exactly this reason.

Drawing the boundaries

Draw a transaction around one business operation: everything that must happen together, and nothing else. Keep it short. A transaction holds locks and an old snapshot for its whole life, and a long one blocks other writers and holds back the cleanup chapter 14 describes. Above all, never make a network call to another service inside a transaction. The call may take seconds while every lock waits, and if the transaction rolls back afterwards, the other service's action can't be undone with it. Make the external call outside, with an idempotency key so a retry can't do it twice. Across services there is no ACID at all; Fleet's sagas and outbox pattern take over there.

Levels defined by what goes wrong

Serializable isolation means concurrent transactions produce the same result as running them one at a time in some order. It's the only level at which you can reason about each transaction alone. The weaker levels exist because serializability costs throughput, and the SQL standard defines them by the anomalies they forbid. Read uncommitted allows dirty reads of another transaction's uncommitted changes. Read committed forbids those, but allows a value to change between two reads in the same transaction. Repeatable read keeps such values stable, but in the standard's definition allows phantom rows to appear. A famous 1995 paper by Berenson and colleagues showed these definitions miss two anomalies that matter in practice: the lost update and write skew.

Defaults vary, and the names don't mean the same thing everywhere. PostgreSQL, Oracle and SQL Server default to read committed; MySQL's InnoDB defaults to repeatable read. PostgreSQL's repeatable read is really snapshot isolation: each transaction reads from a snapshot taken when it starts. Its serializable level adds conflict detection on top of snapshots (serializable snapshot isolation, since version 9.1). SQLite is serializable because it allows only one writer at a time. The example implements three levels in a small multi-version engine and runs the three classic scenarios against each.

class Database:
    """A tiny multi-version store: every committed write adds a version stamped with a commit time."""
    def __init__(self, data):
        self.versions = {k: [(0, v)] for k, v in data.items()}
        self.clock = 0
    def value(self, key, as_of):
        return [v for ts, v in self.versions[key] if ts <= as_of][-1]
    def begin(self, level):
        return Transaction(self, level)

class Transaction:
    def __init__(self, db, level):
        self.db, self.level, self.start = db, level, db.clock
        self.reads, self.writes, self.status = set(), {}, "active"
    def read(self, key):
        self.reads.add(key)
        if key in self.writes:
            return self.writes[key]
        # read committed sees the latest commit; the other two levels read from their start snapshot
        return self.db.value(key, self.db.clock if self.level == "read committed" else self.start)
    def write(self, key, value):
        self.writes[key] = value
    def commit(self):
        changed = {k for k, vs in self.db.versions.items() if vs[-1][0] > self.start}
        if self.level != "read committed" and changed & set(self.writes):
            self.status = "aborted: someone else wrote that row first"
            return
        if self.level == "serializable" and self.writes and changed & self.reads:
            self.status = "aborted: data it read has changed"
            return
        self.db.clock += 1
        for k, v in self.writes.items():
            self.db.versions[k].append((self.db.clock, v))
        self.status = "committed"

def lost_update(level):
    db = Database({"counter": 0})
    a, b = db.begin(level), db.begin(level)
    x, y = a.read("counter"), b.read("counter")            # both read 0
    a.write("counter", x + 1); b.write("counter", y + 1)
    a.commit(); b.commit()
    if b.status == "committed":
        note = " (both committed: one increment lost)"
    else:
        note = f" (B {b.status}; it can retry)"
    return f"counter = {db.value('counter', db.clock)}{note}"

def write_skew(level):
    db = Database({"alice": 1, "bob": 1})                  # rule: at least one doctor on call
    a, b = db.begin(level), db.begin(level)
    if a.read("alice") + a.read("bob") >= 2: a.write("alice", 0)
    if b.read("alice") + b.read("bob") >= 2: b.write("bob", 0)
    a.commit(); b.commit()
    on_call = db.value("alice", db.clock) + db.value("bob", db.clock)
    note = " (both committed: the rule is broken)" if b.status == "committed" else f" (B {b.status})"
    return f"{on_call} doctor(s) on call{note}"

def non_repeatable(level):
    db = Database({"price": 100})
    t1 = db.begin(level)
    first = t1.read("price")
    t2 = db.begin(level); t2.write("price", 70); t2.commit()
    second = t1.read("price"); t1.commit()
    return f"T1 read {first}, then {second}"

for name, scenario in (("lost update: two increments", lost_update),
                       ("write skew: both go off call", write_skew),
                       ("non-repeatable read", non_repeatable)):
    print(name)
    for level in ("read committed", "snapshot", "serializable"):
        print(f"   {level:15} {scenario(level)}")

lost update: two increments
   read committed  counter = 1 (both committed: one increment lost)
   snapshot        counter = 1 (B aborted: someone else wrote that row first; it can retry)
   serializable    counter = 1 (B aborted: someone else wrote that row first; it can retry)
write skew: both go off call
   read committed  0 doctor(s) on call (both committed: the rule is broken)
   snapshot        0 doctor(s) on call (both committed: the rule is broken)
   serializable    1 doctor(s) on call (B aborted: data it read has changed)
non-repeatable read
   read committed  T1 read 100, then 70
   snapshot        T1 read 100, then 100
   serializable    T1 read 100, then 100

The lost update

Two transactions each read a counter, add one in application code and write it back. At read committed, both read 0, both write 1, and both commit: one increment is gone and nothing reported an error. Snapshot isolation catches it, because the second transaction tries to write a row that someone else changed since its snapshot, and it aborts with an error the application can retry. Note the shape of the bug: a read, then a write computed from it. UPDATE counters SET n = n + 1 is a single atomic statement, and every common database executes it safely at read committed. The lost update lives in read-modify-write code, which is exactly what ORMs generate when you load an object, change a field and save it.

Write skew

The on-call rule says at least one doctor must stay on call. Alice and Bob both feel unwell at the same moment, and each transaction checks the rule: two doctors on call, so it's safe for me to go. Alice's transaction updates Alice's row; Bob's updates Bob's. Neither writes a row the other wrote, so snapshot isolation sees no conflict, both commit, and nobody is on call. Each transaction was correct on its own; together they broke the rule. Only serializable catches it here, by noticing that Bob's transaction read a row (Alice's) that changed before it committed.

The non-repeatable read is the mildest of the three: at read committed, a transaction that reads the price twice sees 100 and then 70, because another transaction committed in between. A report that sums one table and then another can be inconsistent this way. Snapshot isolation and serializable both read from the transaction's starting snapshot, so the price stays 100 until the transaction ends.

Defences short of serializable

You don't have to switch the whole database to serializable to be safe; you have to protect the operations that can't tolerate an anomaly. Replace read-modify-write with a single atomic statement where you can. Lock what you read with SELECT ... FOR UPDATE, so concurrent transactions queue: in the on-call case, locking both doctors' rows before checking makes the second transaction wait and then see the first one's change. Use optimistic version checks (chapter 14). Turn the rule into a constraint where it fits one, or materialise the conflict: give the rule a row of its own, such as one row per shift, that every transaction touching the rule must update, so they conflict on it. Or run serializable for those transactions and retry when they abort, as exercise 13.3 describes.

Isolation is subtle enough that database implementations get it wrong too. Kyle Kingsbury's Jepsen analyses test databases against their documented guarantees and have found real violations in many of them, including a serializable-isolation bug in PostgreSQL in 2020, fixed promptly after the report.

Locks and two-phase locking

A lock is permission to use a piece of data. A shared lock lets you read and lets others read too; an exclusive lock lets you write and keeps everyone else out. The classic protocol for serializability is two-phase locking: a transaction acquires locks as it goes and releases none until it is done with all of them. The strict form, holding every lock until commit, is the one databases use, because it also prevents others from reading uncommitted data. It works, and it's expensive: a long report holding shared locks blocks every writer, and every writer blocks the report. Locks can cover a row, a page or a whole table. Some engines escalate many row locks into one table lock to save memory, which can suddenly block unrelated work.

MVCC: readers don't wait

MVCC removes the reader-writer conflict by never overwriting a row in place. An update creates a new version and marks the old one as ended, and each transaction reads whichever version was committed as of its snapshot. PostgreSQL stores every version in the table, stamped with the id of the transaction that created it (xmin) and the one that ended it (xmax). InnoDB and Oracle keep only the newest version in the table and reconstruct older ones from their undo logs on demand. Either way, the result is the snapshot isolation of chapter 13: a reader sees a consistent picture and never waits for a writer.

class Version:
    def __init__(self, value, xmin):
        self.value, self.xmin, self.xmax = value, xmin, None   # created by xmin, ended by xmax

class Store:
    """Row versions with PostgreSQL-style visibility: no reader ever waits for a writer."""
    def __init__(self):
        self.next_xid, self.active, self.committed, self.chain = 1, set(), set(), []
    def begin(self):
        xid = self.next_xid; self.next_xid += 1; self.active.add(xid)
        return xid, (xid, frozenset(self.active - {xid}))     # snapshot: my id, who was in flight
    def commit(self, xid):
        self.active.discard(xid); self.committed.add(xid)
    def _done_before(self, xid, snap):
        me, in_flight = snap
        return xid == me or (xid in self.committed and xid < me and xid not in in_flight)
    def read(self, snap):
        for v in self.chain:
            if self._done_before(v.xmin, snap) and not (v.xmax and self._done_before(v.xmax, snap)):
                return v.value
    def write(self, xid, value):
        for v in self.chain:
            if v.xmax is None:
                v.xmax = xid                                   # the old version is ended, not erased
        self.chain.append(Version(value, xid))
    def vacuum(self):
        oldest = min(self.active, default=self.next_xid)
        before = len(self.chain)
        self.chain = [v for v in self.chain if not (v.xmax in self.committed and v.xmax < oldest)]
        return before - len(self.chain)

s = Store()
t1, snap1 = s.begin(); s.write(t1, "balance 100"); s.commit(t1)
reader, rsnap = s.begin()                                      # a long report starts
writer, wsnap = s.begin(); s.write(writer, "balance 70")       # an update, not yet committed
print("writer sees its own change:     ", s.read(wsnap))
print("reader sees the committed value:", s.read(rsnap), "(and did not wait)")
s.commit(writer)
print("after the writer commits:")
print("   reader, same snapshot:        ", s.read(rsnap))
late, lsnap = s.begin()
print("   a transaction that starts now:", s.read(lsnap))
print("versions:", [(v.value, f"xmin={v.xmin}", f"xmax={v.xmax}") for v in s.chain])
print("vacuum while the report still runs removes", s.vacuum(), "versions")
s.commit(reader); s.commit(late)
print("vacuum after it finishes removes", s.vacuum(), "->", [v.value for v in s.chain])

# Deadlocks: who waits for whom, and a cycle means nobody can ever proceed.
class LockManager:
    def __init__(self):
        self.owner, self.waits_for = {}, {}
    def lock(self, txn, row):
        holder = self.owner.get(row)
        if holder in (None, txn):
            self.owner[row] = txn
            return f"T{txn} locks {row}"
        self.waits_for[txn] = holder
        cycle = self._cycle(txn)
        if cycle:
            victim = max(cycle)                                # abort the youngest transaction
            self.abort(victim)
            return f"T{txn} waits for T{holder} -> deadlock {' -> '.join(f'T{t}' for t in cycle + [cycle[0]])}; abort T{victim}"
        return f"T{txn} waits for T{holder} (holds {row})"
    def _cycle(self, start):
        path, t = [start], self.waits_for.get(start)
        while t is not None and t not in path:
            path.append(t); t = self.waits_for.get(t)
        return path if t == start else None
    def abort(self, txn):
        self.waits_for.pop(txn, None)
        for row, holder in list(self.owner.items()):
            if holder == txn:
                del self.owner[row]
        for t, h in list(self.waits_for.items()):              # waiters on the victim may now proceed
            if h == txn:
                del self.waits_for[t]

print()
lm = LockManager()
for txn, row in ((1, "account A"), (2, "account B"), (1, "account B"), (2, "account A")):
    print(lm.lock(txn, row))
print(lm.lock(1, "account B"), "(T1 retries and proceeds)")

writer sees its own change:      balance 70
reader sees the committed value: balance 100 (and did not wait)
after the writer commits:
   reader, same snapshot:         balance 100
   a transaction that starts now: balance 70
versions: [('balance 100', 'xmin=1', 'xmax=3'), ('balance 70', 'xmin=3', 'xmax=None')]
vacuum while the report still runs removes 0 versions
vacuum after it finishes removes 1 -> ['balance 70']

T1 locks account A
T2 locks account B
T1 waits for T2 (holds account B)
T2 waits for T1 -> deadlock T2 -> T1 -> T2; abort T2
T1 locks account B (T1 retries and proceeds)

The first half is PostgreSQL's design in miniature. Transaction 3 updates the balance but hasn't committed: it sees its own 70, while the long report, transaction 2, sees the committed 100, without waiting. After the commit, the report still sees 100, because its snapshot predates transaction 3. A transaction that starts afterwards sees 70. The version list shows how: the old version wasn't erased, only ended (xmax=3), and the new one carries xmin=3.

The cost of keeping versions

Old versions must eventually be removed, by PostgreSQL's VACUUM or InnoDB's purge thread, and they can only be removed once no running transaction might still need them. The example's first vacuum, run while the report is open, removes nothing; after it finishes, the dead version goes. That's why a single long transaction is dangerous on a busy database. A report running for six hours, or a session left "idle in transaction", holds back cleanup for the whole database, and tables bloat with versions nobody can see. PostgreSQL has a sharper version of the same problem. Transaction ids are 32-bit counters, and if old rows aren't vacuumed in time, the counter approaches wraparound, at which point the database stops accepting writes rather than risk data appearing to come from the future. Sentry in 2015 and Mailchimp's Mandrill in 2019 both had outages for exactly this reason.

Version design also shapes write costs. Because PostgreSQL writes a new version for every update, the new version needs new entries in every index on the table, unless the update qualifies as a "heap-only tuple" update that stays on the same page and touches no indexed column. Uber cited that write amplification, among other reasons, when it moved from PostgreSQL to MySQL in 2016.

Deadlocks

MVCC handles readers; writers still lock. Transaction 1 locks account A and transaction 2 locks account B. Then 1 asks for B and waits for 2, and 2 asks for A and waits for 1. Neither can ever proceed. The second half of the example catches this the way databases do: it keeps a wait-for graph of who is waiting for whom, and a cycle in that graph is a deadlock. The database aborts one transaction, usually the youngest or the one that has done the least work, and the other proceeds. PostgreSQL checks for cycles after a transaction has waited for deadlock_timeout (one second by default); InnoDB checks as each lock wait begins. The aborted transaction gets an error, and the application should retry it. Prevention is cheaper than detection: acquire locks in a consistent order, such as always locking the lower account id first, and the cycle can't form.

Optimistic concurrency

When conflicts are rare, it's cheaper to check than to lock. Give the row a version column, read it with the data, and write with UPDATE ... SET ..., version = version + 1 WHERE id = ? AND version = ?. If another writer got there first, the version won't match, the update changes zero rows, and the application reloads and retries or asks the user. This is the right tool for edits that span human time, such as a form open for ten minutes, where holding a database lock is impossible.

The rule

Writing a changed page back to its place in a data file is a random write, and a transaction may change dozens of pages scattered across many files. Making all of them durable before acknowledging a commit would be slow, and a crash partway through would leave some pages old and some new. The write-ahead log solves both problems with one rule: before any change reaches the data files, a record describing it must be on disk in the log. A commit then needs only one sequential append and one flush. The changed pages stay in the buffer pool and are written back later, at leisure, as chapter 1's diagram showed. After a crash, recovery replays the log: committed changes whose pages never reached disk are redone, and changes from transactions that never committed, which may have reached disk early, are undone. Production databases implement this with the ARIES algorithm, published by IBM in 1992. The store below needs only the redo half, because it never writes uncommitted data anywhere but the log.

import json, os, struct, tempfile, zlib
from contextlib import contextmanager

class KVStore:
    """A key-value store made durable by a write-ahead log: every change is appended and
    flushed to the log before it is applied, so the log can rebuild the data after a crash."""
    HEADER = struct.Struct("<II")                           # payload length, CRC-32 of the payload

    def __init__(self, directory):
        self.log_path = os.path.join(directory, "wal.log")
        self.snap_path = os.path.join(directory, "snapshot.json")
        self.data, self.fsyncs, self._batching = {}, 0, False
        self.replayed, self.discarded = self._recover()
        self.log = open(self.log_path, "ab")

    def _append(self, op):
        payload = json.dumps(op).encode()
        self.log.write(self.HEADER.pack(len(payload), zlib.crc32(payload)) + payload)
        if not self._batching:
            self._sync()

    def _sync(self):
        self.log.flush(); os.fsync(self.log.fileno()); self.fsyncs += 1   # the commit point

    @contextmanager
    def batch(self):                                        # group commit: many records, one fsync
        self._batching = True
        try:
            yield
        finally:
            self._batching = False
            self._sync()

    def put(self, key, value):
        self._append(["put", key, value]); self.data[key] = value      # log first, then apply
    def delete(self, key):
        self._append(["del", key]); self.data.pop(key, None)
    def get(self, key):
        return self.data.get(key)

    def checkpoint(self):
        tmp = self.snap_path + ".tmp"
        with open(tmp, "w") as f:
            json.dump(self.data, f); f.flush(); os.fsync(f.fileno())
        os.replace(tmp, self.snap_path)                     # the snapshot appears atomically
        self.log.close()
        open(self.log_path, "wb").close()                   # everything before it is now redundant
        self.log = open(self.log_path, "ab")

    def _recover(self):
        if os.path.exists(self.snap_path):
            with open(self.snap_path) as f:
                self.data = json.load(f)
        if not os.path.exists(self.log_path):
            return 0, 0
        with open(self.log_path, "rb") as f:
            buf = f.read()
        pos = replayed = 0
        while pos + self.HEADER.size <= len(buf):
            length, crc = self.HEADER.unpack_from(buf, pos)
            payload = buf[pos + self.HEADER.size: pos + self.HEADER.size + length]
            if len(payload) < length or zlib.crc32(payload) != crc:
                break                                       # torn or corrupt: stop at the last good record
            op = json.loads(payload)
            if op[0] == "put": self.data[op[1]] = op[2]
            else: self.data.pop(op[1], None)
            pos += self.HEADER.size + length
            replayed += 1
        discarded = len(buf) - pos
        if discarded:
            with open(self.log_path, "r+b") as f:
                f.truncate(pos)                             # cut off the unusable tail
        return replayed, discarded

d = tempfile.mkdtemp()
kv = KVStore(d)
kv.put("alice", 100); kv.put("bob", 50); kv.put("carol", 75); kv.delete("carol")
before = dict(kv.data)
del kv                                                      # crash: no shutdown, no close
kv = KVStore(d)
print(f"1. crash and restart: replayed {kv.replayed} records, state recovered: {kv.data == before} -> {kv.data}")

kv.put("dave", 20)
with open(kv.log_path, "r+b") as f:                         # as if the power failed mid-write, before
    f.truncate(os.path.getsize(kv.log_path) - 5)            # fsync returned: the record is only partly there
kv = KVStore(d)
print(f"2. torn final write:  replayed {kv.replayed}, discarded {kv.discarded} bytes of the partial record -> {kv.data}")

with open(kv.log_path, "r+b") as f:                         # a bit flips inside the second record
    f.seek(KVStore.HEADER.size + 30); byte = f.read(1); f.seek(-1, 1); f.write(bytes([byte[0] ^ 0xFF]))
kv = KVStore(d)
print(f"3. corrupted record:  replayed {kv.replayed} before the checksum failed, discarded {kv.discarded} bytes -> {kv.data}")

kv = KVStore(tempfile.mkdtemp())
for i in range(1000):
    kv.put(f"key{i}", i)
size_before = os.path.getsize(kv.log_path)
kv.checkpoint()
kv.put("after", 1); kv.put("checkpoint", 2)
kv = KVStore(os.path.dirname(kv.log_path))
print(f"4. checkpoint: log shrank from {size_before:,} bytes to 0; restart loaded the snapshot "
      f"and replayed {kv.replayed} records -> {len(kv.data)} keys")

kv = KVStore(tempfile.mkdtemp())
for i in range(200):
    kv.put(f"a{i}", i)
one_each = kv.fsyncs
kv.fsyncs = 0
for chunk in range(4):
    with kv.batch():
        for i in range(50):
            kv.put(f"b{chunk}-{i}", i)
print(f"5. group commit: 200 writes, one fsync each = {one_each} fsyncs; in batches of 50 = {kv.fsyncs} fsyncs")

1. crash and restart: replayed 4 records, state recovered: True -> {'alice': 100, 'bob': 50}
2. torn final write:  replayed 4, discarded 22 bytes of the partial record -> {'alice': 100, 'bob': 50}
3. corrupted record:  replayed 1 before the checksum failed, discarded 78 bytes -> {'alice': 100}
4. checkpoint: log shrank from 29,780 bytes to 0; restart loaded the snapshot and replayed 2 records -> 1002 keys
5. group commit: 200 writes, one fsync each = 200 fsyncs; in batches of 50 = 4 fsyncs

Five ways to test a log

Crash and restart. The store is dropped without any shutdown, as if the process were killed. On restart it replays four records and reaches exactly the state it had acknowledged, with the delete of carol applied in order. Nothing in the dictionary itself was ever saved; the log was enough.

A torn final write. Power can fail while a record is being written, leaving only part of it on disk. Each record carries its length and a CRC-32 checksum of its contents, so recovery can tell a complete record from a fragment. It replays the four good records and discards the 22 bytes of the partial fifth. That's correct, not lossy: the fifth write never finished, so its put never returned, and no one was ever told it succeeded.

A corrupted record. A flipped bit in the second record fails its checksum, and recovery stops there, keeping only the first record and discarding everything after it. That looks harsh, since records three and four might be fine, but a log is only trustworthy as an unbroken prefix. Once one record is bad, recovery can't be sure where the next one starts, and replaying later changes without an earlier one could produce a state that never existed. PostgreSQL treats the first invalid record as the end of the log for the same reason. Real corruption in the middle of a log is a job for backups and replicas (chapter 16), not for recovery.

Checkpoints. A log that grows forever makes recovery slower every day. A checkpoint writes the current state durably (here, a snapshot file replaced atomically, the trick from chapter 1) and then discards the log before it. After a thousand writes, the log shrank from 29,780 bytes to nothing, and a restart loaded the snapshot and replayed just the two records written since. Real databases checkpoint by flushing dirty pages and noting the log position from which recovery must start, trading I/O spikes during checkpoints against shorter recovery.

Group commit. The flush is the expensive step: fsync takes anywhere from about a tenth of a millisecond on a good SSD to several milliseconds on a disk, and it caps how many commits per second one log can make. Batching commits that arrive together into one flush, called group commit, turned 200 flushes into 4 here. Databases do it automatically: when several transactions commit at once, one flush makes all of them durable.

When fsync lies, and when pages tear

The whole scheme rests on fsync meaning what it says. Disks with volatile write caches can acknowledge a flush before the data is safe, which is why servers use drives with power-loss protection. The operating system can fail too. In 2018, PostgreSQL's developers discovered that on Linux, a failed fsync could clear the error, so a retry would report success while the data was gone; PostgreSQL now stops with a panic on any fsync failure rather than retry. Data pages have their own torn-write problem. An 8 KB page written as two 4 KB halves can be half old and half new after a crash. PostgreSQL logs the full page image the first time a page changes after each checkpoint (full_page_writes), and InnoDB writes pages to a doublewrite buffer first.

The log is the database

The log turns out to be useful far beyond recovery. Ship it to another machine and replay it there, and you have a replica (chapter 16). Archive it next to a base backup, and you can restore the database to any moment, a minute before the bad DELETE: point-in-time recovery. Stream it to other systems, and every change becomes an event: change data capture, which is how tools like Debezium feed search indexes and warehouses. Seen this way, the log is the source of truth, and the tables are just a convenient, indexed copy of its latest state.

To finish the deliverable, swap the store's dictionary for chapter 6's B+tree, which adds ordered range scans, or put this log in front of chapter 7's memtable, which makes the LSM tree durable. Then test it the way this chapter did, but harder: kill the process at random moments thousands of times and check that every acknowledged write survives and no unacknowledged one appears.

Copying the log

Chapter 15 ended with the observation that the log is the database. Replication is that idea in practice: the primary streams its log to replicas, and each replica replays it to keep an identical copy. Physical replication ships the log's bytes and produces an exact copy of the primary's files, page for page. It's simple and complete, but the replica must run the same major version. Logical replication ships row changes, which can cross versions, replicate selected tables, and feed other systems, at the cost of more moving parts. PostgreSQL offers both; MySQL replicates its binary log, preferably in row format. The other choice is timing. With asynchronous replication, the primary acknowledges a commit without waiting for any replica. With synchronous replication it waits for at least one, which adds a network round trip to every commit. Semi-synchronous schemes wait for the replica to receive the record but not to apply it.

class Primary:
    """Every change is a numbered log record (its LSN); replicas replay the same log."""
    def __init__(self):
        self.log, self.data = [], {}
    def write(self, key, value):
        self.log.append((key, value))
        self._apply(self.data, key, value)
        return len(self.log)                               # the LSN of this change
    @staticmethod
    def _apply(data, key, value):
        if value is None: data.pop(key, None)
        else: data[key] = value

class Replica:
    def __init__(self, primary):
        self.primary, self.applied, self.data = primary, 0, {}
    def catch_up(self, records=None):
        end = len(self.primary.log) if records is None else min(len(self.primary.log), self.applied + records)
        for key, value in self.primary.log[self.applied:end]:
            Primary._apply(self.data, key, value)
        self.applied = end

p = Primary(); r1, r2 = Replica(p), Replica(p)
for i in range(100):
    p.write(f"user{i}", f"name {i}")
r1.catch_up(); r2.catch_up()

print("1. read your own writes")
lsn = p.write("user7", "Ana Lima")                         # the user saves a new display name...
print("   read from a lagging replica:   ", r1.data["user7"], "<- the save looks lost")
def read(key, replica, token):
    """Serve from the replica only if it has replayed the client's last write."""
    return (replica.data[key], "replica") if replica.applied >= token else (p.data[key], "primary")
print("   with the client's LSN token:   ", read("user7", r1, lsn))

print("2. monotonic reads")
r1.catch_up()                                              # r1 is now current, r2 still lags
print(f"   first read from r1: {r1.data['user7']!r}, next read from r2: {r2.data['user7']!r} <- time went backwards")

print("3. failover with asynchronous replication")
for i in range(5):
    p.write(f"order{i}", "paid")                           # acknowledged to customers
r1.catch_up(records=2)                                     # then the primary's disk dies
lost = len(p.log) - r1.applied
print(f"   promoted replica is {lost} records behind: {lost} acknowledged orders are gone (RPO > 0)")
print("   synchronous replication would have made each commit wait for the replica: no loss, slower commits")

print("4. a replica is not a backup")
r1.catch_up(); r2.catch_up()
backup_lsn, backup = len(p.log), dict(p.data)              # last night's base backup
p.write("user42", "renamed")
bad = p.write("user7", None)                               # someone runs DELETE with the wrong WHERE
r1.catch_up()
print("   replica after the DELETE:      ", r1.data.get("user7"), "<- replicated faithfully")
restored = dict(backup)
for key, value in p.log[backup_lsn:bad - 1]:              # replay the archived log up to just before it
    Primary._apply(restored, key, value)
print("   point-in-time restore:         ", restored.get("user7"), "| later change kept:", restored.get("user42"))

1. read your own writes
   read from a lagging replica:    name 7 <- the save looks lost
   with the client's LSN token:    ('Ana Lima', 'primary')
2. monotonic reads
   first read from r1: 'Ana Lima', next read from r2: 'name 7' <- time went backwards
3. failover with asynchronous replication
   promoted replica is 3 records behind: 3 acknowledged orders are gone (RPO > 0)
   synchronous replication would have made each commit wait for the replica: no loss, slower commits
4. a replica is not a backup
   replica after the DELETE:       None <- replicated faithfully
   point-in-time restore:          Ana Lima | later change kept: renamed

What lag does to users

An asynchronous replica is always a little behind, usually milliseconds and sometimes much more. Part 1 shows the classic consequence: a user saves a new display name, the next page reads from a replica that hasn't replayed the change yet, and the save looks lost. The fix is read-your-writes consistency. The primary returns the log position (LSN) of each write, the client keeps it, and a read is served by a replica only if that replica has replayed at least that far; otherwise it goes to the primary, or waits. PostgreSQL exposes a replica's position with pg_last_wal_replay_lsn(), and MySQL uses global transaction ids for the same purpose. A cruder fix sends a user's reads to the primary for a few seconds after any write. Part 2 is the subtler monotonic reads problem: two replicas with different lag, and a user whose reads alternate between them sees data go forward and then back in time. Pinning each user to one replica, or using the same position tokens, prevents it.

Failover, and what it can lose

When the primary dies, a replica is promoted to take its place. With asynchronous replication, whatever the replica hadn't received is gone: in part 3, three orders that customers were told had succeeded. Two numbers make this a decision instead of a surprise. The recovery point objective (RPO) is how much data you can afford to lose, and the recovery time objective (RTO) is how long you can afford to be down. An RPO of zero requires synchronous replication to at least one other machine, and pays a round trip on every commit; a few seconds of RPO allows asynchronous. Failover also has to make sure the old primary is truly dead, or fenced, before the new one accepts writes, or both accept writes at once. In October 2018, a 43-second network partition led GitHub's failover tooling to promote primaries in a different region while the original side kept writing too. Reconciling the two sets of writes took 24 hours of degraded service.

Backups are for mistakes

Part 4 is the case replication can't help with. Someone runs a DELETE with the wrong condition, and the replica, doing its job, deletes the row too. The defence is point-in-time recovery: a base backup, plus every log record archived since, replayed to the moment just before the mistake. The restore brings back the deleted row and keeps the legitimate change made just before it. Backups must also live somewhere a mistake or an attacker can't reach at the same time: another account, another region. And they must be tested, because a backup you've never restored is a hope, not a backup. In January 2017, an engineer at GitLab, fighting a replication problem late at night, deleted the primary's data directory instead of the replica's. The team then found that their regular backups had been failing silently. They restored from a snapshot taken six hours earlier for another purpose, and lost six hours of users' issues, merge requests and comments.

Why it's hard

On a laptop, renaming a column is one statement. In production, three things get in the way. The first is two versions of the code: a rolling deploy replaces servers one at a time, so for minutes or hours the old code and the new code run side by side against the same tables, and a rollback brings the old code back. Rename the column in one step and whichever version doesn't know the new name breaks. The second is locks. Many ALTER TABLE forms take an exclusive lock, and some rewrite the whole table while holding it. Even a change that needs the lock only for a moment must first wait for every running query on the table, and in PostgreSQL every query that arrives after it waits behind it, so a two-second change can stall the table for minutes behind one slow report. The third is the data: copying values into a new column across a hundred million rows takes time and can't be one transaction.

Expand and contract

The pattern breaks a change into steps, each compatible with both the code running before it and the code after it, and each reversible until the last.

import random, sqlite3

def fresh_db():
    db = sqlite3.connect(":memory:", isolation_level=None)
    db.execute("CREATE TABLE users(id INTEGER PRIMARY KEY, fullname TEXT NOT NULL)")
    db.executemany("INSERT INTO users(fullname) VALUES (?)", ((f"User {i}",) for i in range(10_000)))
    return db

# The application versions that will be running at various times.
def v1_rename(db, uid, name):            # the old code: knows only fullname
    db.execute("UPDATE users SET fullname = ? WHERE id = ?", (name, uid))
def v2_rename(db, uid, name):            # the transitional code: writes both columns
    db.execute("UPDATE users SET fullname = ?, display_name = ? WHERE id = ?", (name, name, uid))

def backfill(db, live_writer, batch=1000):
    """Copy old values into the new column in short batches, with live traffic between batches."""
    largest = 0
    for start in range(1, 10_001, batch):
        db.execute("BEGIN")
        n = db.execute("UPDATE users SET display_name = fullname WHERE id BETWEEN ? AND ? "
                       "AND display_name IS NULL", (start, start + batch - 1)).rowcount
        db.execute("COMMIT")
        largest = max(largest, n)
        for _ in range(50):                                # the application keeps working meanwhile
            live_writer(db, random.randint(1, 10_000), f"Renamed {random.randint(1, 10**6)}")
    return largest

def mismatches(db):
    return db.execute("SELECT COUNT(*) FROM users WHERE display_name IS NOT fullname").fetchone()[0]

random.seed(17)
print("wrong order: backfill while v1 is still deployed")
db = fresh_db()
db.execute("ALTER TABLE users ADD COLUMN display_name TEXT")    # expand: instant, nothing breaks
backfill(db, v1_rename)
print(f"   rows where the new column is stale or missing after backfill: {mismatches(db)}")

print("right order: expand, deploy v2 everywhere, then backfill")
db = fresh_db()
db.execute("ALTER TABLE users ADD COLUMN display_name TEXT")    # 1. expand
largest = backfill(db, v2_rename)                               # 2-3. dual-write deployed, then backfill
print(f"   mismatches after backfill: {mismatches(db)}   largest single transaction: {largest:,} rows")
print("   4. verify: 0 mismatches, so v3 can read display_name only")
db.execute("ALTER TABLE users DROP COLUMN fullname")            # 5. contract, once v1 and v2 are gone
print("   5. contract: columns now", [r[1] for r in db.execute("PRAGMA table_info(users)")])

wrong order: backfill while v1 is still deployed
   rows where the new column is stale or missing after backfill: 262
right order: expand, deploy v2 everywhere, then backfill
   mismatches after backfill: 0   largest single transaction: 1,000 rows
   4. verify: 0 mismatches, so v3 can read display_name only
   5. contract: columns now ['id', 'display_name']

The order is the whole trick

The first run backfills while the old code, v1, is still deployed. v1 knows nothing about display_name, so every rename it performs after a batch has passed that row updates fullname and leaves display_name holding the old value. The backfill finishes, everything looks done, and 262 rows are silently wrong, waiting to show users their old names the day v3 starts reading the new column. The second run deploys the dual-writing v2 everywhere first, so every rename keeps both columns in step, and only then backfills: zero mismatches. The batches matter too. Each one is its own short transaction of at most 1,000 rows, so no lock is held for long and replicas never fall far behind. A single UPDATE of the whole table would be one enormous transaction, holding locks and an old snapshot for its whole duration (chapter 14). Before switching reads, verify, as the example's mismatch count does, and only drop the old column once v1 and v2 are gone.

Engine features that help

Databases have steadily made more changes cheap. In PostgreSQL, adding a column with a constant default has been instant since version 11. CREATE INDEX CONCURRENTLY builds an index without blocking writes, and a constraint can be added NOT VALID, which checks new rows immediately, then validated against old rows later without a long lock. Setting lock_timeout before any DDL makes a change give up and retry rather than queue the whole table behind it. MySQL supports ALGORITHM=INSTANT for many column changes. For the rest, tools such as gh-ost and pt-online-schema-change build a shadow copy of the table, keep it in sync, and swap it in. SQLite supports adding, renaming and, since version 3.35, dropping columns. Whatever the engine, rehearse every migration on a copy of production-sized data before running it for real.

The families

Key-value stores (Redis, DynamoDB used by key) do one thing: get and put a value by its key, extremely fast. Document databases (MongoDB, Couchbase) store a nested JSON-like document per key and can index fields inside it. Wide-column stores (Cassandra, ScyllaDB, Bigtable, HBase) group rows into partitions by a partition key and keep the rows within a partition sorted by a clustering key, on LSM storage (chapter 7) that is built for writes. Graph databases (Neo4j, Amazon Neptune) store relationships as first-class links, so a query that follows them many hops deep doesn't become a pile of joins. Time-series databases (TimescaleDB, InfluxDB) are tuned for appending timestamped measurements and querying recent ranges. Search engines (Elasticsearch, OpenSearch) are the subject of the next chapter. What they share is a bargain: decide your queries up front, and the database makes those queries cheap at a scale where one relational server would struggle.

import random, sqlite3

random.seed(18)
customers = range(1, 2001)
orders = []                                                     # (order_id, customer_id, date)
items = []                                                      # (order_id, product_id, qty)
for oid in range(1, 20_001):
    orders.append((oid, random.choice(customers), f"2026-{random.randint(1, 9):02d}-{random.randint(1, 28):02d}"))
    for product in random.sample(range(1, 501), random.randint(1, 4)):
        items.append((oid, product, random.randint(1, 3)))

# Model 1: relational, with indexes for the queries we know about.
db = sqlite3.connect(":memory:")
db.executescript("""
CREATE TABLE orders(id INTEGER PRIMARY KEY, customer_id INTEGER, created_at TEXT);
CREATE TABLE items(order_id INTEGER, product_id INTEGER, qty INTEGER);
CREATE INDEX orders_by_customer ON orders(customer_id, created_at);
CREATE INDEX items_by_order ON items(order_id);
CREATE INDEX items_by_product ON items(product_id);
""")
db.executemany("INSERT INTO orders VALUES (?, ?, ?)", orders)
db.executemany("INSERT INTO items VALUES (?, ?, ?)", items)

# Model 2: documents. One document per customer, with orders and items embedded.
docs = {c: {"customer": c, "orders": []} for c in customers}
by_id = {}
for oid, cid, date in orders:
    by_id[oid] = {"id": oid, "date": date, "items": []}
    docs[cid]["orders"].append(by_id[oid])
for oid, pid, qty in items:
    by_id[oid]["items"].append({"product": pid, "qty": qty})

# Model 3: one wide-column/key-value table, keys designed around the access patterns
# (the single-table style used with DynamoDB): partition key -> sorted items.
kv = {}
for oid, cid, date in orders:
    kv.setdefault(f"CUST#{cid}", {})[f"ORDER#{date}#{oid}"] = {"order": oid}
    kv.setdefault(f"ORDER#{oid}", {})["META"] = {"customer": cid, "date": date}
for oid, pid, qty in items:
    kv[f"ORDER#{oid}"][f"ITEM#{pid}"] = {"qty": qty}

cid, oid, product = 77, 4242, 123

def relational(sql, params):
    """Run the query, and describe its cost from SQLite's own plan."""
    plan = [r[-1] for r in db.execute("EXPLAIN QUERY PLAN " + sql, params)]
    searches = sum(line.startswith("SEARCH") for line in plan)
    scans = sum(line.startswith("SCAN") for line in plan)
    label = f"{searches} index search" + ("es" if searches > 1 else "") if not scans else f"{scans} table scan"
    return db.execute(sql, params).fetchall(), label

print(f"{'access pattern':42}{'relational':>18}{'documents':>16}{'key-value':>18}")

rows, a_rel = relational("SELECT id FROM orders WHERE customer_id = ? ORDER BY created_at DESC LIMIT 5", (cid,))
recent = sorted(docs[cid]["orders"], key=lambda o: o["date"], reverse=True)[:5]          # read 1 document
part = sorted(kv[f"CUST#{cid}"].items(), reverse=True)[:5]                              # read 1 partition
print(f"{'A. a customer and their 5 latest orders':42}{a_rel:>18}{'1 document':>16}{'1 partition':>18}")

order, b_rel = relational("""SELECT o.id, i.product_id FROM orders o JOIN items i ON i.order_id = o.id
                             WHERE o.id = ?""", (oid,))
found = [d for d in docs.values() if any(o["id"] == oid for o in d["orders"])]          # no key leads to an order
print(f"{'B. one order with its items':42}{b_rel:>18}{f'scan {len(docs):,}':>16}{'1 partition':>18}")

(rel,), c_rel = relational("SELECT COUNT(DISTINCT order_id) FROM items WHERE product_id = ?", (product,))
rel = rel[0]
doc_hits = sum(1 for d in docs.values() for o in d["orders"] if any(i["product"] == product for i in o["items"]))
kv_hits = sum(1 for pk, part_ in kv.items() if pk.startswith("ORDER#") and f"ITEM#{product}" in part_)
print(f"{'C. every order containing product 123':42}{c_rel:>18}{f'scan {len(docs):,}':>16}{f'scan {len(kv):,}':>18}")
print(f"\nsame answers: A {[r[0] for r in rows] == [o['id'] for o in recent] == [v['order'] for _, v in part]}, "
      f"B {len(found) == 1 and len(order) == len(kv[f'ORDER#{oid}']) - 1}, C {rel == doc_hits == kv_hits} ({rel} orders)")

access pattern                                    relational       documents         key-value
A. a customer and their 5 latest orders       1 index search      1 document       1 partition
B. one order with its items                 2 index searches      scan 2,000       1 partition
C. every order containing product 123         1 index search      scan 2,000       scan 22,000

same answers: A True, B True, C True (86 orders)

Reading the table

The example models the same 20,000 orders three ways and asks three questions. The relational column comes from SQLite's own plans, and with the right indexes every answer is an index search. The document model, one document per customer with orders embedded, is perfect for question A: one read returns the customer and every order. The key-value model was designed for A and B: the customer's partition holds its orders sorted by date, and each order has a partition of its own.

Then the questions go off-script. Finding one order in the document model means scanning every customer document, because nothing leads from an order id to the customer who placed it; a real document database would need a secondary index on the embedded field, which is fine, as long as someone planned it. Question C, every order containing a product, is the one nobody planned. The relational database answers it with an index that can be added in a minute at any time. Both NoSQL models must scan everything, or have their data reorganised around the new question: a secondary index, or a copy of every order line keyed by product, kept in sync by every write. That is the trade in one table. NoSQL makes the anticipated access patterns cheap and the unanticipated ones expensive.

Designing for a NoSQL store

The method is the reverse of relational design. Start from the list of access patterns, not from the entities, and design keys so that each pattern is a lookup by key or a range within one partition. That is the single-table design style used with DynamoDB, where keys like CUST#77 and ORDER#2026-09-01#4242 encode the queries they serve. Denormalise on purpose and accept duplication. Watch the sizes: a partition or document that grows without bound, such as every comment on a viral post, becomes a hot spot or hits a hard limit (MongoDB documents are capped at 16 MB). And know what you're giving up. Joins move into application code, multi-record transactions are limited or missing (MongoDB and DynamoDB both added them later, with restrictions), and the schema is enforced, if at all, by your code reading the data.

When to choose one

NoSQL earns its place for enormous scale with simple, known patterns (Discord's message history, chapter 7), for records whose shape genuinely varies, for caching and sessions, for deep relationship traversals, and for high-rate time-series ingestion. Two developments have narrowed the gap. Relational databases absorbed the most useful NoSQL features: PostgreSQL's jsonb, with indexes inside documents, covers many document-store use cases. And distributed SQL databases such as Google Spanner and CockroachDB offer SQL and transactions across many machines. A sound default for a new product is a relational database, adding a specialised store when a specific access pattern demands it and you can name which one.

Cache-aside

The most common pattern is cache-aside, or lazy loading. To read, the application asks the cache first. On a hit it's done. On a miss it queries the database, stores the result in the cache with a time-to-live (TTL), and returns it. To write, it updates the database and deletes the cached entry, so the next read reloads it. Redis and Memcached are the usual caches. Alternatives exist: write-through updates the cache and the database together, and write-behind updates the cache and writes to the database later, which is fast and can lose data. Whatever the pattern, the TTL is the safety net: however the cache goes wrong, the error expires.

import sqlite3

# 1. A cache stampede: a popular key expires and 1,000 requests arrive in the same instant.
class Cache:
    def __init__(self): self.value, self.expired, self.refreshing = "v1", True, False

def serve(requests, strategy):
    cache, db_queries, waited = Cache(), 0, 0
    for _ in range(requests):
        if not cache.expired:
            continue                                      # a normal hit
        if strategy == "no protection":
            db_queries += 1                               # every miss queries the database
        elif strategy == "single flight":
            if cache.refreshing: waited += 1              # wait for the one query in flight
            else: cache.refreshing = True; db_queries += 1
        elif strategy == "serve stale, refresh once":
            if not cache.refreshing: cache.refreshing = True; db_queries += 1   # others get the old value now
    return db_queries, waited

print("1. stampede: 1,000 simultaneous requests for an expired key")
for strategy in ("no protection", "single flight", "serve stale, refresh once"):
    q, w = serve(1000, strategy)
    print(f"   {strategy:27} database queries: {q:5}   requests made to wait: {w}")

# 2. The invalidation race: read-through and write-invalidate interleaved badly.
db, cache = {"price": 100}, {}
log = []
stale_read = db["price"]; log.append("reader: cache miss, reads 100 from the database")
db["price"] = 120; log.append("writer: updates the database to 120")
cache.pop("price", None); log.append("writer: deletes the cache entry")
cache["price"] = stale_read; log.append("reader: writes the 100 it read into the cache")
print("\n2. invalidation race")
for line in log: print("   " + line)
print(f"   cache now says {cache['price']}, database says {db['price']}: stale until the entry expires")

# 3. Full-text search: an inverted index versus scanning every row.
docs = [
    "replica lag makes saves look lost", "the write ahead log makes commits durable",
    "a covering index avoids table lookups", "vacuum removes dead row versions",
    "the planner trusts its statistics", "a lagging replica can serve stale reads",
] * 2000
index = {}
for doc_id, text in enumerate(docs):
    for word in set(text.split()):
        index.setdefault(word, set()).add(doc_id)          # word -> the documents containing it
hits = index["replica"] & index["stale"]                   # intersect two posting lists
print(f"\n3. search 'replica stale' over {len(docs):,} documents")
print(f"   inverted index: read {len(index['replica']) + len(index['stale']):,} postings, {len(hits):,} matches")
scan = [i for i, t in enumerate(docs) if "replica" in t and "stale" in t]
print(f"   LIKE-style scan: read {len(docs):,} documents, {len(scan):,} matches, same: {set(scan) == hits}")

fts = sqlite3.connect(":memory:")
fts.execute("CREATE VIRTUAL TABLE notes USING fts5(body)")
fts.executemany("INSERT INTO notes(body) VALUES (?)", [(d,) for d in docs[:6]])
print("   SQLite FTS5, ranked by bm25:",
      fts.execute("SELECT body FROM notes WHERE notes MATCH 'replica' ORDER BY bm25(notes)").fetchall())

1. stampede: 1,000 simultaneous requests for an expired key
   no protection               database queries:  1000   requests made to wait: 0
   single flight               database queries:     1   requests made to wait: 999
   serve stale, refresh once   database queries:     1   requests made to wait: 0

2. invalidation race
   reader: cache miss, reads 100 from the database
   writer: updates the database to 120
   writer: deletes the cache entry
   reader: writes the 100 it read into the cache
   cache now says 100, database says 120: stale until the entry expires

3. search 'replica stale' over 12,000 documents
   inverted index: read 6,000 postings, 2,000 matches
   LIKE-style scan: read 12,000 documents, 2,000 matches, same: True
   SQLite FTS5, ranked by bm25: [('replica lag makes saves look lost',), ('a lagging replica can serve stale reads',)]

The stampede

A cache can hide a database's limits so well that nobody notices until it fails. When a popular entry expires, every request that arrives before it's refilled misses at once, and in part 1 a thousand of them query the database at the same moment for the same answer. That's a cache stampede, also called a thundering herd, and it can take down a database that handles the steady load easily. Three fixes appear in the example and in practice. Single flight lets the first request refresh the entry while the others wait for its result: one query, 999 short waits. Serve stale while revalidating returns the old value to everyone and refreshes it once in the background: one query, nobody waits. Early or jittered expiry refreshes a hot entry slightly before its TTL ends, at a random moment, so entries don't all expire together. A restart has the same effect at a larger scale: an empty cache sends every request to the database, so warm the cache, or let traffic back in gradually.

The invalidation race

Part 2 shows why "delete the cache entry after writing" isn't the end of the story. A reader misses and reads 100 from the database. Before it stores that value, a writer updates the database to 120 and deletes the cache entry. Then the reader stores the 100 it read. The cache now contradicts the database, and will until the TTL expires. Every step was correct in isolation; the order made it wrong. Facebook's memcache paper describes the fix it adopted: leases. A miss hands the reader a token, a delete invalidates outstanding tokens, and the cache refuses a set with an invalidated token. Simpler defences are a short TTL, which bounds how long the staleness lasts, and versioned keys that include the row's version or update time, so a stale value is stored under a key nobody reads any more.

Search indexes

A B-tree finds rows whose value starts with something; it can't find documents that contain a word somewhere in the middle, so LIKE '%stale%' scans every row. Search needs an inverted index: for every word, the list of documents that contain it, called its postings. A query for two words intersects two posting lists. In part 3, the search read 6,000 postings to find its 2,000 matches, where the scan read all 12,000 documents; the gap grows with the size of the collection and the rarity of the words. Real search engines add tokenisation, stemming (so lagging matches lag), and ranking, usually by BM25, which weighs rare words more heavily and rewards documents where the query's words are prominent. SQLite's FTS5, run at the end of the example, does exactly this inside the database.

Start with your database's built-in search, such as PostgreSQL's tsvector with a GIN index, SQLite's FTS5 or MySQL's FULLTEXT: it stays transactionally consistent with the data and needs nothing new to run. Move to a dedicated engine such as Elasticsearch or OpenSearch when you need typo tolerance, faceting, relevance tuning, or scale beyond one server. Feed it from the database's change stream (chapter 15) and accept that it lags slightly behind. Keep a way to rebuild it from scratch, because a derived index that drifts needs a reindex, and a reindex is only possible if the database is the source of truth.

Two workloads

An online shop's database spends its day on transactional (OLTP) work: show this order, add that item, update this stock count. Each query touches a handful of rows, by key, and needs an answer in milliseconds. The finance team's questions are analytical (OLAP): revenue by month and category for two years, the average basket size by region. Each query touches millions of rows but only a few columns, runs for seconds, and is asked by a few people. Run the second kind on a database built for the first and you get chapter 5's flooded cache and chapter 14's held-back vacuum, on the system your customers depend on. Analytical work belongs in a system built for it, fed from the transactional one.

Store columns, not rows

A row store keeps each row's values together in a page, which is ideal for fetching a whole row by key. A column store keeps each column's values together, so a query reads only the columns it mentions. Columns also compress far better than rows, because each holds one kind of value with lots of repetition.

import random, sqlite3, struct, zlib

random.seed(20)
N = 200_000
rows = [(i, random.randint(1, 50_000), random.choices(["shipped", "pending", "cancelled"], [85, 10, 5])[0],
         f"2026-{random.randint(1, 9):02d}-{random.randint(1, 28):02d}", random.randint(500, 50_000))
        for i in range(N)]

# 1. Row store versus column store for SELECT SUM(total) WHERE status = 'shipped'
row_bytes = sum(8 + 8 + len(s) + len(d) + 8 for _, _, s, d, _ in rows)      # every column of every row
col = {"status": [r[2] for r in rows], "total": [r[4] for r in rows]}
col_bytes = sum(len(s) for s in col["status"]) + 8 * N                     # only the two columns used
print("1. SUM(total) WHERE status = 'shipped'")
print(f"   row store reads    {row_bytes / 1e6:6.1f} MB (all five columns)")
print(f"   column store reads {col_bytes / 1e6:6.1f} MB (status and total only)")

# 2. Columns compress well because each holds one kind of value.
codes = {"shipped": 0, "pending": 1, "cancelled": 2}
status_dict = bytes(codes[s] for s in col["status"])                      # dictionary encoding
srt = sorted(col["status"])
runs = sum(1 for i in range(N) if i == 0 or srt[i] != srt[i - 1])          # run-length after sorting
dates = sorted(r[3] for r in rows)
day_numbers = [int(d[5:7]) * 31 + int(d[8:]) for d in dates]
deltas = bytes(min(255, day_numbers[i] - day_numbers[i - 1]) if i else 0 for i in range(N))  # delta encoding
raw_status = sum(len(s) for s in col["status"])
print("2. compression of single columns")
print(f"   status: {raw_status:,} bytes as text -> {len(status_dict):,} as 1-byte codes -> "
      f"{runs} runs once sorted ({runs * 5} bytes)")
print(f"   dates:  {sum(len(d) for d in dates):,} bytes as text -> {len(zlib.compress(deltas)):,} bytes "
      f"as sorted day-to-day deltas, compressed")

# 3. A star schema: one fact table of measurements, small dimension tables of context.
db = sqlite3.connect(":memory:")
db.executescript("""
CREATE TABLE dim_date(date_key INTEGER PRIMARY KEY, day TEXT, month TEXT);
CREATE TABLE dim_product(product_key INTEGER PRIMARY KEY, name TEXT, category TEXT);
CREATE TABLE fact_sales(date_key INTEGER, product_key INTEGER, qty INTEGER, revenue_cents INTEGER);
""")
days = [f"2026-{m:02d}-{d:02d}" for m in range(7, 10) for d in range(1, 29)]
db.executemany("INSERT INTO dim_date VALUES (?, ?, ?)", [(i, d, d[:7]) for i, d in enumerate(days)])
db.executemany("INSERT INTO dim_product VALUES (?, ?, ?)",
               [(p, f"product {p}", ["books", "games", "tools"][p % 3]) for p in range(30)])
db.executemany("INSERT INTO fact_sales VALUES (?, ?, ?, ?)",
               [(random.randrange(len(days)), random.randrange(30), q := random.randint(1, 5), q * random.randint(500, 3000))
                for _ in range(50_000)])
print("3. revenue by month and category, with subtotals (a ROLLUP, written out for SQLite)")
for month, category, revenue in db.execute("""
    SELECT d.month, p.category, SUM(f.revenue_cents) FROM fact_sales f
      JOIN dim_date d ON d.date_key = f.date_key JOIN dim_product p ON p.product_key = f.product_key
     GROUP BY d.month, p.category
    UNION ALL
    SELECT d.month, '(all)', SUM(f.revenue_cents) FROM fact_sales f
      JOIN dim_date d ON d.date_key = f.date_key GROUP BY d.month
    ORDER BY 1, 2"""):
    print(f"   {month}  {category:6} {revenue / 100:>12,.2f}")

1. SUM(total) WHERE status = 'shipped'
   row store reads       8.2 MB (all five columns)
   column store reads    3.0 MB (status and total only)
2. compression of single columns
   status: 1,419,838 bytes as text -> 200,000 as 1-byte codes -> 3 runs once sorted (15 bytes)
   dates:  2,000,000 bytes as text -> 790 bytes as sorted day-to-day deltas, compressed
3. revenue by month and category, with subtotals (a ROLLUP, written out for SQLite)
   2026-07  (all)    871,563.76
   2026-07  books    295,811.23
   2026-07  games    297,398.29
   2026-07  tools    278,354.24
   2026-08  (all)    871,569.62
   2026-08  books    291,120.00
   2026-08  games    290,521.41
   2026-08  tools    289,928.21
   2026-09  (all)    875,846.43
   2026-09  books    293,836.14
   2026-09  games    297,582.99
   2026-09  tools    284,427.30

Reading the numbers

For a sum of one column filtered by another, the row store reads all five columns of every row, 8.2 MB, while the column store reads two, 3.0 MB. That's before compression, which is where columns pull far ahead. The status column, 1.4 MB of repeated words, shrinks to 200,000 one-byte codes with dictionary encoding, and to three runs, 15 bytes, with run-length encoding once the table is sorted by status. Dates sorted in order become small day-to-day differences, which delta encoding plus a general compressor squeezes from 2 MB to under 800 bytes. A table can only be sorted one way, so column stores let you choose a sort key, and the leading columns of that key compress best. Engines then process compressed values in batches of thousands at a time (vectorised execution), which is how DuckDB on a laptop, or ClickHouse, BigQuery, Snowflake and Redshift at scale, scan billions of rows in seconds. Parquet files bring the same layout to data that lives in object storage.

Facts and dimensions

Analytical schemas are usually star schemas, the design Ralph Kimball popularised. A central fact table records events at a chosen grain, such as one row per order line, with numeric measures like quantity and revenue, plus keys to the dimension tables around it: date, product, customer, store. Dimensions are wide and denormalised on purpose, with month and quarter stored on the date row and category stored on the product row, because analytical data is loaded in bulk and read far more than it's changed, so chapter 2's arguments for normalisation weigh much less. History matters here: when a product changes category, a type 2 slowly changing dimension adds a new dimension row with validity dates rather than overwriting, so last year's sales stay in last year's category, the same idea as chapter 3's history tables.

The example's third part runs a typical star-schema query on SQLite: revenue by month and category, joined from the fact table to two dimensions, with a subtotal row per month. Databases that support it write the subtotals with GROUP BY ROLLUP (month, category), or more generally GROUPING SETS and CUBE, which compute several groupings in one pass; MySQL offers WITH ROLLUP. SQLite has none of these, so the example writes the rollup out as a UNION ALL of two groupings.

Pipelines

Data reaches the analytical store through a pipeline. Classic ETL extracts from the source, transforms in a separate system, and loads the result. Modern ELT loads raw data into the warehouse first and transforms it there with SQL, often managed with dbt, which keeps the raw data available for new questions and makes transformations versioned and testable. Batch loads run on a schedule; streaming loads follow the source's change log (chapter 15) for fresher data. Whichever you choose, treat the pipeline like production code: loads that are idempotent, so a rerun doesn't double-count; tests for row counts, nulls and uniqueness at each step; and a stated freshness target that someone is alerted about when it's missed.