03 — Database Internals

A relational database — a system that stores data as tables, grids of rows and columns — takes one kind of input and produces one kind of output. The input is a SQL query: a sentence that declares which rows you want without saying how to fetch them. The output is a set of rows.

Everything in between is the engine deciding which bytes to move off disk, in what order, and under which guarantees. This chapter opens that gap end to end:

• how a table is laid out on disk (Storage what a query actually reads off disk)
• how an index turns a search into a handful of reads (B trees why a lookup is four page reads–The write cost of indexes quantified)
• how the planner chooses one plan over another (How the planner picks a plan–Reading explain analyze line by line)
• what a transaction really guarantees when many run at once (Transactions acid precisely–Mvcc and deadlocks)
• what breaks once one machine is not enough (Scaling replication–Cap and the framing that is actually useful)

Finish it and you should be able to take a slow query, a number that goes wrong under concurrency, or a system that folds at ten times the traffic, and name both the mechanism responsible and the arithmetic that predicts it.

Writing correct SQL is a language skill. Knowing why a query is slow, why a number is wrong under concurrency, and why the system falls over at 10× traffic is a systems skill — and it is the one tested when the title says senior.

The three facts everything else rests on

Everything below follows from three physical facts:

1. The database reads and writes fixed-size pages.
2. A random page costs several times a sequential one.
3. Network > disk > RAM > cache in latency.

Every index, join algorithm, isolation level and replication topology in this chapter is an argument about those three numbers. The words in them have to be exact, so take them plainly:

• A page is a fixed-size block of bytes — 8 kilobytes (KB) in PostgreSQL — and it is the smallest unit the engine will read or write. There is no operation called “read 40 bytes.” Ask for a 40-byte row and you get an 8 KB read.
• Sequential access reads pages that sit next to each other on the device, so the hardware can stream them. Random access jumps to unrelated offsets and pays a seek per jump.
• Latency is the wait before the first byte comes back. The ordering in fact 3 says a network round trip costs more than a disk read, a disk read more than a fetch from main memory (RAM), and that more than a hit in the CPU’s own small cache. Each step is two to three orders of magnitude — not a little slower, 100× to 1,000× slower.

One more term, because it turns up before its own section: an isolation level is the setting that decides how much of other transactions’ in-flight work yours is allowed to see. It trades correctness guarantees against concurrency, and the full ladder is derived in Transactions acid precisely.

Which engine the numbers describe

The reference engine is PostgreSQL, “Postgres” below. Every default, cost constant and page size quoted without an engine name is a Postgres one.

MySQL/InnoDB is called out by name where it changes the answer. InnoDB is the storage engine MySQL uses by default — the component that actually puts bytes on disk — and it makes a different choice at almost every decision point in this chapter. That is why it is worth naming rather than glossing over: “the database does X” is usually a claim about one engine.

1. Storage: what a query actually reads off disk

The physical layout of a table — all of a row’s columns stored together, or all of a column’s values stored together — fixes the cost of a query before any index is considered, and that cost can be computed in bytes.

The page is the unit of everything

You cannot reason about read cost in rows, only in pages — and that one fact separates the two families of storage layout.

Postgres reads and writes 8 KB pages (BLCKSZ; InnoDB uses 16 KB). Not rows — pages. Asking for one 40-byte row costs one 8 KB read. (BLCKSZ is the compile-time constant that names the page size.)

Work out what that means for a real table. Take fct_orders: a fact table — the large, append-heavy table at the centre of an analytical schema — with 50 columns and 100 million rows. The block below adds up one row’s bytes, divides them into a page, and multiplies back out to a file size. Read it top to bottom; every term is defined immediately after.

tuple header 24 B + null bitmap 8 B + payload 50 x 8 B + line pointer 4 B  =  436 B/row
usable page = 8192 - 24 (page header)                                      = 8168 B
              (a heap page has no index "special" space; a B-tree page reserves
               16 B for it, which is where the 8152 of section 2 comes from)
rows/page   = floor(8168 / 436)                                            =   18
pages       = 100,000,000 / 18 = 5,555,556   ->   heap = 45.5 GB
                    (5,555,556 pages x 8,192 B = 45,511,114,752 B)

Every line of that is a physical structure rather than an accounting convention:

• A tuple is one stored version of a row. Its 24-byte header records which transactions created and deleted it — the fields that Mvcc and deadlocks turns into concurrency control.
• The null bitmap is one bit per column marking which values are absent, rounded up to 8 bytes here.
• The payload is the fifty column values themselves, 8 bytes each.
• The line pointer is a 4-byte slot near the top of the page pointing at where the row currently sits inside that page. A row can move within its page without anything outside the page noticing.
• The page header is 24 bytes of per-page bookkeeping, which is why the usable space is 8,168 and not 8,192.
• The heap is the plain, unordered file of pages that holds a table’s rows — “heap” as in pile, not the data structure.

Note what the rows/page line throws away. 18 rows at 436 B is 7,848 B, so 320 B of every page is dead space — real, but too small to hold a nineteenth row. The table is 45.5 GB before a single index exists.

Now ask the question an analyst asks, which touches almost none of that width:

SELECT date_trunc('month', order_ts) AS m, sum(amount_cents)
FROM fct_orders GROUP BY 1;                          -- two columns out of fifty

Two physical layouts can answer that query, and they are the two families of storage engine.

A row store keeps all fifty columns of row 1 adjacent, then all fifty of row 2. This is the layout every OLTP database uses — OLTP (online transaction processing) meaning a workload of many small reads and writes of individual rows.

A column store keeps all hundred million order_ts values together in one segment, all hundred million amount_cents values in another, and so on. A segment is simply the contiguous run of one column’s values. This is the layout analytical engines use — OLAP (online analytical processing) meaning a workload of few queries, each scanning huge numbers of rows.

The diagram below draws both: the row store is a chain of pages you must walk in full, while the column store is a set of independent piles of which the query opens only two. Two compression schemes are named in the boxes and both get one line here, because they come back in the table further down. Delta encoding stores each value as the difference from its neighbour, which is tiny when values climb slowly. Frame-of-reference encoding (FOR, as the later table abbreviates it) stores each value as an offset from the minimum of its block, so it needs only as many bits as the block’s range.

flowchart TB
    subgraph R["Row store — heap page, 8 KB, 18 rows"]
        R1["row 1 · all 50 columns"] --> R2["row 2 · all 50 columns"] --> R3["... then the next page"]
    end
    subgraph C["Column store — one segment per column"]
        C1["order_ts · 100M values<br/>delta encoded"]
        C2["amount_cents · 100M values<br/>frame-of-reference encoded"]
        C3["48 other segments<br/>never opened"]
    end
    style C1 fill:#2d6a4f,color:#fff
    style C2 fill:#2d6a4f,color:#fff
    style C3 fill:#40916c,color:#fff

The 48 segments the query never names are never opened at all. That is the whole of the difference.

Pricing the same query on both layouts

Put a device under it: one that streams 1 GB per second sequentially. Divide bytes by that rate to get time, rounded. The last column is the row-store time divided by each layout’s time.

The 28× is 45.5 / 1.6; the 104× is 45.5 / 0.438. The compressed row’s two figures come from the encoding table in the next subsection.

Why the row store reads so much more: two of fifty columns is 16 of 400 payload bytes, or 4% of the payload. Against the full stored row of 436 B — which also carries 36 B/row of header, bitmap and pointer — it is 16/436 = 3.7%. A row store cannot read a column without reading the row, and cannot read a row without reading its page, so a query touching 4% of the columns pays 100% of the bytes.

The second factor, inside the CPU

Disk is not the only place the layout is charged. A cache line is the 64-byte block the CPU moves between RAM and its own cache — the CPU cannot fetch less than that either.

In a row store, consecutive amount_cents values are 436 B apart, so each 64-byte line carries 8 useful bytes and 56 useless ones. That is 8/64 = 12.5% cache efficiency, against 100% in a column store where the next value you want is the next 8 bytes.

That 8× gap is also what makes vectorized execution possible: SIMD (single instruction, multiple data) instructions apply one operation to several values at once. You can sum eight lanes of a contiguous int64 array in one instruction. You cannot do that to a chain of tuples scattered across pages.

Now run the query the other way

Reverse the workload and the advantage reverses with it. Take the point read SELECT * FROM fct_orders WHERE order_id = 918273, which wants one whole row and nothing else.

• Row store: 4 index pages + 1 heap page = 5 pages = 40 KB, in 5 I/Os. (An I/O is one input/output request to the storage device; B trees why a lookup is four page reads derives where the 4 index pages come from.)
• Column store: 50 segments, each pulling a compressed block to decode one value — roughly 800 KB across 50 I/Os.

The asymmetry is ~28× one way and ~20× the other on identical data. That is why serious shops run both an OLTP row store and an analytical column store, and why “just query production” has an arithmetic answer rather than a political one.

The assumption, and what it costs when it is wrong. A row store is optimised for queries that touch few rows and most of each row’s columns, and for writing or updating a row at a time; that is the transactional workload, and there the layout is 20× ahead. A column store assumes the reverse — many rows, few columns, read far more often than written. Run the analytical query on the row store and you pay the 28×; run the point lookup on the column store and you pay the 20×. Neither number is a defect in the engine, and both are predictable from the layout alone, which is why the layout is chosen per workload rather than per taste.

Why compression works better in a column store

The same bytes compress an order of magnitude better once they are grouped by column — and the grouping also changes what you can do without decompressing.

Compression ratio is a function of how similar adjacent values are, and a column store is precisely the layout that makes adjacent values similar.

The table below prices three columns of fct_orders under three encodings. Read the last column as “how many times smaller than raw”, and notice that the three ratios span four orders of magnitude — the encoding that wins depends entirely on the column’s shape.

Each encoding is a one-line idea, and each row’s arithmetic is one multiplication:

• Dictionary encoding numbers the distinct values once and stores the number. Eight distinct statuses fit in 3 bits (2^3 = 8), so 100M rows × 3 bits = 300 Mbit = 37.5 MB, against 1.2 GB raw.
• Run-length encoding (RLE) stores a value and how many times it repeats. Three years is 1,095 distinct dates, and because the column is sorted each date appears as exactly one run: 1,095 pairs at 12 B is about 13 KB, against 800 MB raw.
• Frame-of-reference stores an offset from the block minimum. Amounts spanning 500,000 need 19 bits (2^19 = 524,288) rather than 64, so 100M × 19 bits = 1.9 Gbit = 238 MB.

Why the same compressor does worse in a row store

A row store’s page holds 18 rows × 50 heterogeneous columns. A general-purpose compressor (pglz/lz4, InnoDB page compression) therefore sees adjacent bytes from unrelated domains: a timestamp, then a price, then a status string. That is high entropy — little repeated structure to exploit — and the typical ratio is 2-3×.

The access pattern makes it worse. A row store must decompress a whole page to read one row, so compression taxes every access. A column store decompresses only the segments the query touched, and RLE, dictionary and FOR data can often be filtered and aggregated without decompressing at all — you can sum run lengths, or compare dictionary codes, directly in the encoded form.

The trade you accept

A single-row INSERT into a column store would touch all 50 segments. So real column stores refuse row-at-a-time writes and batch rows into immutable segments instead: Parquet row groups, Snowflake micro-partitions, ClickHouse parts — three names for the same thing, a block of rows written once and never edited.

“Insert one row” and “scan two columns of a hundred million” are the two ends of one design axis. No engine sits at both ends.

The assumption, and what it costs when it is wrong. Columnar compression assumes values arrive in bulk and in an order that groups similar values together — the order_date ratio of 60,000× exists only because the column is sorted. Feed the same engine unsorted data and the ratio falls toward the row store’s 2-3×; feed it one row at a time and it cannot build a segment at all, which is why column stores answer trickle inserts with either a rejection or a slow, ever-growing pile of tiny segments that a background merge must clean up.

2. B-trees: why a lookup is four page reads

Finding one row among a hundred million costs about four page reads, not a hundred million comparisons — and the number barely moves as the table grows. Both facts follow from what an index physically is.

What an index is, physically

An index is a second structure, stored alongside the table, that keeps a copy of one or more columns in sorted order together with a pointer back to the row. Because it is sorted, you can find a value by repeatedly halving the search space instead of scanning every row.

The structure that does the halving is a B-tree: a balanced tree whose nodes are pages. Each internal node holds many separator keys and many child pointers, and every leaf sits at the same depth, so every lookup costs the same number of reads. The number of children per node is the fanout, and the fanout is set by one thing — how many index entries fit in one 8 KB page.

So the whole cost model reduces to two divisions: bytes per entry into bytes per page gives the fanout, and the log of the row count in that base gives the depth.

entry = key 8 B + heap TID 6 B + item pointer 4 B + header/align 6 B  =  24 B
usable 8152 B at fillfactor 90 = 7337 B   ->   fanout floor(7337/24)  = 305
                                               rounded for discussion ~ 300
depth = ceil( log_300(1e8) ) = ceil( 18.42 / 5.70 ) = ceil(3.23)      =   4

Three terms in that block:

• The heap TID (tuple identifier) is the row’s physical address, a (page number, slot number) pair. That is the pointer back to the table.
• Fillfactor is the percentage of each page the engine is willing to fill before leaving the rest as free space for later insertions. A B-tree index defaults to 90, so 8152 × 0.90 = 7337 bytes of the 8152 usable.
• log_f(N) is the depth formula. If every node has f children, then d levels address f^d rows, so the depth needed for N rows is the logarithm of N in base f. The 18.42 / 5.70 is that logarithm done by hand: ln(10^8) = 18.42, ln(300) = 5.70.

Two fanout numbers appear in this chapter and both are exact — say which you are using where. The true fanout is floor(7337 / 24) = 305. Everything in this section — the depth, the levels table, the page counts in the tree diagram — uses 305 rounded to 300, because the point being made is about orders of magnitude and 300 is the number you can multiply in your head. Covering indexes and index only scans uses the exact 305, because there the index page count is compared against a heap-fetch count and rounding the fanout would change the comparison: ceil(200,000 / 305) = 656 index pages, where 300 would have said 667.

Why four reads, and why it stays four

At a fanout of 300, each level multiplies reach by 300. Read the table as “how many rows a tree of this height can address” — and notice how fast the numbers pass 100 million.

Four levels reach 8.1 billion rows, which is why a 100-million-row table needs exactly four.

A lookup walks that tree from the single root page down to a leaf, following one separator key per level, and then follows the heap TID into the table itself. The diagram traces one such walk. The page counts shrink by a factor of 300 at every step up, which is why the top two levels are small enough to stay in memory permanently.

flowchart TD
    ROOT["Root · 1 page<br/>~300 separator keys · always cached"]
    ROOT --> I1["Level 2 · 4 pages<br/>almost always cached"]
    ROOT --> I2["..."]
    I1 --> L1["Level 3 · 1,112 pages"]
    I1 --> L2["..."]
    L1 --> LF["Level 4 · leaves · 333,334 pages<br/>key + heap TID · doubly linked in key order"]
    LF --> H["Heap page · the actual row"]
    style ROOT fill:#2d6a4f,color:#fff
    style LF fill:#40916c,color:#fff
    style H fill:#bc6c25,color:#fff

Two terms from the diagram. A separator key is a boundary value in an internal node that tells the descent which child to follow. The leaves are the bottom level, holding one entry per row — key plus heap TID — and they are doubly linked in key order, meaning each leaf page points at both of its neighbours.

The page counts come from dividing by the fanout repeatedly, bottom up:

leaves   = ceil(100,000,000 / 300) = 333,334 pages
level 3  = ceil(    333,334 / 300) =   1,112 pages
level 2  = ceil(      1,112 / 300) =       4 pages
root     = ceil(          4 / 300) =       1 page

The root and Level 2 are five pages in total — 40 KB. Both therefore live permanently in shared_buffers, which is Postgres’s buffer pool: the slab of RAM the database uses to cache pages it has already read, so that a repeated read costs no I/O at all.

A point lookup is 4 page reads plus 1 heap fetch — and since the root and level 2 stay hot in shared_buffers, only ~2 of those are physical I/O.

Two corollaries fall out of log_f(N), and both are interview answers:

• Growth is nearly free. Going from 1M rows to 100M rows adds one level, because log_300(10^6) = 2.42 and log_300(10^8) = 3.23 — three levels becomes four. “The table got big so the index got slow” is almost never the diagnosis.
• Key width is the real lever. A 100-byte text key makes a 116-byte entry once you add the same 16 B of TID, pointer and header. Then f = floor(7337/116) = 63, and log_63(10^8) = 4.45, so you need 5 levels — one more read on every lookup — and an index nearly 5× larger competing for the same buffer pool.

One structural detail earns its keep across the whole chapter: leaves are linked in key order. That is why a single B-tree serves ORDER BY, >=, BETWEEN and LIKE 'abc%'. Every one of those is the same operation — seek once, then walk the leaf chain.

InnoDB does this differently, and it matters

Two words are needed to say how. A clustered index is one where the table’s rows are the leaves of the index, so the index and the table are the same object. A secondary index is any other index, whose leaves hold a pointer rather than the row.

Postgres has only secondary indexes, all pointing into a separate heap. In InnoDB the table is a B-tree clustered on the primary key, with full rows in the leaves.

Two consequences follow, and both are things you can be asked to price:

• A secondary lookup is two descents. An InnoDB secondary index stores (secondary key -> primary key), so you spend 4 pages finding the PK and 4 more finding the row. A wide PK is also copied into every secondary index, inflating all of them.
• A random PK is a write disaster. A monotonic PK — one that only ever increases, like an auto-increment counter — always appends to the rightmost leaf, which stays cached and fills to ~93%. A UUIDv4 PK (version 4 of the universally unique identifier, random by construction) lands on random leaves and splits them, settling near 50-60% fill. Same data, 1.6× larger index, and proportionally worse cache hit rate because the same RAM now holds fewer rows.

If you need a UUID, use UUIDv7 or ULID. Both put a timestamp in the high-order bits, which restores the monotonic append and the 93% fill.

The assumption, and what it costs when it is wrong. A B-tree is optimised for a read-heavy workload with small keys and roughly ordered insertions: it keeps everything sorted at all times, which makes reads flat and predictable and makes every write pay to maintain that order, in place, at a random offset. Break either premise and the arithmetic above turns against you — wide keys cost a level and 5× the memory, random keys cost 1.6× the space plus a page split per insert, and a write-dominated workload pays the full price of sortedness on every row while using almost none of the read benefit. That last case is exactly what Lsm trees vs b trees answers with a different structure.

3. When the index is not used, and why

A perfectly good index sits unused for one of four reasons — the planner declining it on cost, a function hiding the column, a pattern that maps to no contiguous range, or a type mismatch — and arithmetic separates the correct refusals from the fixable ones.

Low selectivity — the index correctly loses

The first reason is not a bug at all: past a certain fraction of the table, reading everything in order is genuinely cheaper than jumping around, and the planner computes exactly where that line is.

Two terms first. A predicate is a condition in a WHERE clause. Selectivity is the fraction of the table’s rows that predicate matches — 0.01 means 1% of rows come back.

The planner compares plans by adding up cost constants: arbitrary units calibrated so that one sequential page read is 1.0. In Postgres they are

Now set up a table to cost. events has 10M rows at 200 B each, so 40 rows fit in a page and the table is 10,000,000 / 40 = 250,000 pages. The predicate country = 'US' matches 40% of rows, which is 4M rows.

Cost both plans with those constants:

Seq scan   = 250,000 x 1.0  +  10,000,000 x 0.01                        =   350,000
             (pages x seq_page_cost)  (rows x cpu_tuple_cost)
             = 250,000 + 100,000

Index scan   heap pages, correlation ~ 0:  min(2TN/(2T+N), T)
             = min( 2·250,000·4e6 / 4.5e6 , 250,000 ) = 250,000 RANDOM reads
             = 250,000 x 4.0 + 4e6 x 0.005 + 4e6 x 0.01                 = 1,060,000
             = 1,000,000    + 20,000      + 40,000

Line by line: the sequential scan pays one unit per page plus a small CPU charge per row. The index scan pays four units per page, because its heap reads land at random offsets, plus a charge per index entry and a charge per row.

The min(2TN/(2T+N), T) term deserves its own sentence. It is the standard estimate of how many distinct pages N randomly-placed matches touch in a T-page table — two matches can land on the same page, so N matches touch fewer than N pages. Here T = 250,000 and N = 4,000,000, so the first term is 2 × 250,000 × 4,000,000 / 4,500,000 = 444,444, which exceeds T. The min clamps it to 250,000: with 4M matches spread over 250,000 pages, every page is touched anyway.

The index scan costs 1,060,000 / 350,000 = 3× the sequential scan. The index did not fail; it correctly lost.

Where the break-even actually sits

Now solve for the selectivity s at which the two costs are equal. Take the pessimistic case where each match sits on its own page, so pages touched ≈ s × N and each costs 4.0, plus 0.005 per index entry and 0.01 per row — 4.0 + 0.005 + 0.01 = 4.015 per matched row:

4.015 x s x 10,000,000 = 350,000   ->   s = 350,000 / 40,150,000 = 0.0087 = 0.87%

Below ~1% selectivity the index wins; above it the sequential scan does. That is the folklore number, derived rather than repeated.

The term everybody forgets: physical correlation

The second lever is not selectivity at all but physical correlation: how closely the order of rows on disk matches the order of the index key.

Rerun the same query on a table CLUSTERed on country. CLUSTER is the Postgres command that physically rewrites a table into an index’s order, so all the US rows end up next to each other on disk.

The 4M matches are now contiguous, so the heap reads are sequential rather than random:

pages touched = 0.40 x 250,000 = 100,000 pages, at seq_page_cost 1.0  =  100,000

100,000 against the sequential scan’s 350,000: the index now wins at 40% selectivity, on exactly the data where it lost by 3× a moment ago. Nothing changed but the physical ordering.

Selectivity is not the rule. The rule is how many distinct pages the matches touch and in what order — physical correlation is what decides that.

Postgres stores correlation in pg_stats.correlation (a number from -1 to 1) and interpolates between the two costings above.

Correlation is also what Bitmap Heap Scan exists for. It works in two passes: collect the matching TIDs from the index, sort them, then read the heap in physical page order. That converts random I/O into sequential, which is the engineered answer to poor correlation, and it owns the ~1-20% selectivity band that neither pure plan handles well.

The failure mode to know: when the bitmap outgrows work_mem — the per-operation memory budget a sort or hash gets before it spills to disk — it degrades to page granularity, remembering only “this page has a match somewhere” instead of which rows. Then Recheck Cond in the plan starts doing real work, re-testing every row on every such page.

The assumption, and what it costs when it is wrong. The whole cost model above assumes a random page costs four times a sequential one, which was calibrated for spinning disks. On NVMe flash — NVMe being the interface modern solid-state drives (SSDs) use — the true ratio is close to 1.1, so leaving random_page_cost at 4.0 makes the planner systematically avoid indexes it should use; correlation, meanwhile, decays on its own as a clustered table takes updates, so a plan that was right the week you ran CLUSTER degrades silently afterwards.

Function applied to the column

The third reason is syntactic and catches everyone: wrapping the indexed column in anything at all makes the index unusable, however obvious the equivalence looks to a human. Three examples, each with a perfectly good index that will not be used:

WHERE lower(email) = '[email protected]'              -- index on users(email)      unusable
WHERE created_at::date = DATE '2025-06-01'  -- index on orders(created_at) unusable
WHERE amount_cents / 100 > 500              -- index on amount_cents      unusable

Mechanism. An index is sorted by the stored expression, and the index on users(email) stores raw email values. To use it, the planner must translate your predicate into a contiguous range of that order.

The planner has no theorem prover. It matches the predicate’s left-hand side against an indexed expression syntactically. lower(email) is not the string email, so there is no match, so no range exists to seek to.

Two fixes, in order of preference.

Better: rewrite into a half-open range on the bare column. A half-open range includes its start and excludes its end, which is how you express “one day” without a function:

WHERE created_at >= DATE '2025-06-01' AND created_at < DATE '2025-06-02'
WHERE amount_cents > 50000

Fallback: index the expression itself, when no rewrite exists (lower(email) is the usual case):

CREATE INDEX idx_users_email_lower ON users (lower(email));

Name the index explicitly. Postgres will invent a name if you omit it, but that spelling is a syntax error in every other engine.

The rewrite is strictly better than the expression index: no extra structure, no extra write cost, and The write cost of indexes quantified prices exactly what that saves.

Leading-wildcard LIKE

The fourth case is about which string patterns correspond to a contiguous range of sorted keys and which do not.

LIKE 'abc%' — a leading prefix — is rewritten by the planner to >= 'abc' AND < 'abd'. That is a contiguous range: one seek, then a leaf walk.

LIKE '%abc' — a leading wildcard — has no such rewrite. Strings ending in abc are scattered uniformly across the sorted key space (aabc, zabc, mabc sort nowhere near each other), so there is no range to seek to and the engine must test every row.

Two fixes for the suffix case:

• A pg_trgm GIN index, which chops every string into three-character fragments and indexes those. GIN is Postgres’s Generalized Inverted Index — the structure that maps one key to many rows, so one fragment points at every string containing it.
• Index reverse(col), which turns a suffix into a prefix and puts you back in the case that works.

The Postgres gotcha: LIKE 'abc%' only uses a plain B-tree under the C collation. A collation is the rule set that decides string ordering; C means plain byte order. Under en_US.UTF-8 the index order is not byte order — case and accents are folded into the comparison — so < 'abd' no longer bounds the same set of strings and the prefix rewrite is unsound. For that case you need an operator class that forces byte ordering:

CREATE INDEX idx_t_col_pattern ON t (col text_pattern_ops);

Type mismatch

The last case is the same function problem in disguise, inserted by the engine rather than by you.

Write WHERE user_id = 12345 against a varchar column and the engine has to make the types agree. It does so by casting the column, not the literal: user_id::bigint = 12345. That is a function on the column, so the previous case applies and the index is dead.

The two engines fail differently here, and the difference is the whole point:

• Postgres often raises a type error instead, which is the friendly outcome — you find out at development time.
• MySQL silently numeric-converts the varchar column. No error, no warning, the index is silently unused, and the query is merely 1,000× slower than it should be.

The same trap fires when joining INT to BIGINT, or joining VARCHAR columns that carry different collations.

Three smaller cases, same reasoning

Each of these is the “no contiguous range exists” argument applied to a different shape:

• a = 1 OR b = 2 — no single index covers both branches, because the matching rows for a and for b are two unrelated regions of two different sorted orders. Postgres can BitmapOr two indexes, combining the two matching-row sets before touching the heap. MySQL’s index-merge union covers the same shape but is chosen far less reliably.
• ORDER BY a, b DESC on an (a, b) index — the index is ascending in b within each a, so reading it gives you b in the wrong direction and the walk is not contiguous in the requested order. Index it (a, b DESC) instead.
• A table under ~8 pages — the whole table is one sequential I/O. Any index is genuinely slower, and the planner is right to ignore it.

4. Composite, covering, and hash indexes

Past the plain single-column B-tree sit three more index shapes — an index on several columns, an index that carries enough payload to answer a query without touching the table, and an index that gives up ordering entirely — plus one rule that decides column order in the first of them.

Leftmost prefix, derived from the sort order

A multi-column index is sorted by the whole tuple of columns, and every usable and unusable predicate follows from that one fact.

Take this index:

CREATE INDEX idx_events_tenant_created_status ON events (tenant_id, created_at, status);

It sorts entries by the tuple (tenant_id, created_at, status). That means: ordered by tenant_id first; only within one tenant_id value ordered by created_at; and only within one of those ordered by status.

Here are six entries in that stored order. Read them left to right, top row then bottom row — that is the order the leaves hold them in, and it is the only order the tree can walk.

(1, 2025-01-01, 'A')   (1, 2025-01-01, 'C')   (1, 2025-01-02, 'A')
(1, 2025-01-02, 'B')   (2, 2025-01-01, 'B')   (2, 2025-01-03, 'A')

Number those entries 1 to 6 in that reading order. Now take each predicate and ask one question: do its matches form one unbroken run of consecutive entries? An unbroken run is the only thing a tree can seek to, because a seek finds a starting point and then walks forward.

Look at the last row: created_at = '2025-01-01' matches entries 1, 2 and 5, with entries 3 and 4 in between. There is no single starting point that walks to all three, so the index cannot help at all.

The leftmost-prefix rule is not a convention — it is what “sorted by a tuple” means. A predicate can only seek while every preceding key column is pinned to a single value.

That gives you the rule for column order: equality columns first, then the single range column, then output-only columns. The reason is in row 3 of the table. Once you hit a range, the next key column restarts its ordering for every distinct value inside that range, so it can only filter rows you have already read — it can never narrow the scan.

(Postgres 18 added a skip scan, which loops over the distinct values of a low-cardinality leading column — cardinality being the count of distinct values in a column — and seeks once per value. That narrows the “useless” row above without repealing the rule.)

Covering indexes and index-only scans

A covering index is one that contains every column a query needs, so the engine can answer from the index alone and never follow a heap TID into the table. The resulting plan is called an index-only scan. The saving is large — and there is a production caveat that can take it all back.

Take a query that matches 200,000 rows and returns two columns:

SELECT customer_id, amount_cents FROM orders
WHERE tenant_id = 7 AND created_at >= DATE '2025-06-01';   -- 200,000 rows match

Count page accesses under two different indexes. The first can only find the rows; the second also contains them.

(tenant_id, created_at)                      :   656 index pages + 200,000 RANDOM heap fetches
                                                 = 200,656 page accesses
(tenant_id, created_at) INCLUDE (customer_id, amount_cents)
                                             : 1,093 index pages, sequential, 0 heap fetches
                                200,656 / 1,093  ->  ~184x fewer page accesses

Where the two page counts come from — both use the exact fanout arithmetic of B trees why a lookup is four page reads, with 7,337 usable bytes per page:

plain index, 24 B/entry:   floor(7337/24) = 305 entries/page
                           ceil(200,000/305)             =   656 pages
INCLUDE index, 40 B/entry: floor(7337/40) = 183 entries/page
                           ceil(200,000/183)             = 1,093 pages

Notice which term dominates: the index pages barely matter either way. The 184× comes almost entirely from deleting 200,000 random heap fetches.

The price is a 67% larger entry (24 → 40 B) and more work on every insert. One design detail is worth knowing: INCLUDE puts the payload columns in leaf pages only, leaving the internal nodes at the original 24 B/entry. Since fanout is what sets the depth, that is exactly why INCLUDE beats appending the columns to the key — the tree does not get taller.

The caveat that bites in production

An index does not store visibility — whether a given row version is visible to your transaction, which Mvcc and deadlocks explains. So an index-only scan cannot simply trust what it finds in the index.

Instead it consults the visibility map: a compact per-page bitmap recording which heap pages contain only rows visible to everyone. If the map says a page is all-visible, the index entry is trusted. If not, the scan fetches the heap page anyway — reported in EXPLAIN as Heap Fetches: N.

On a continuously-updated table with lazy autovacuum — autovacuum being the background process that reclaims superseded row versions and refreshes that map — the fraction of rows needing a heap fetch approaches 100%, and the index-only scan quietly becomes an ordinary index scan.

An index-only scan’s performance is a property of your vacuum schedule, not of your index.

The assumption, and what it costs when it is wrong. A covering index assumes the query set is stable and read-dominated: you are paying 67% more bytes per entry, on every insert and every update of the covered columns, to buy a 184× read saving. On a table whose queries change monthly the extra columns stop being used and the write cost stays; on a write-heavy table the trade is simply upside down.

Hash indexes

A hash index stores rows by a hash of the key — a fixed-size fingerprint computed from the value — which finds an exact value in one step but destroys any notion of order. Giving up that order is worth it more rarely than it sounds.

Start with what it buys. A B-tree lookup on 100M rows is ~2 physical reads (root and level 2 stay cached); a hash index is 1.

You save one page read and give up range scans, ORDER BY, prefix matching, multi-column keys, UNIQUE enforcement, and index-only scans. One read against six capabilities is why the default is always a B-tree.

The one case where it wins decisively

Very wide keys. Index a 2 KB URL and watch the B-tree arithmetic collapse:

B-tree entry = 2048 (key) + 16 (TID + pointer + header)  =  2,064 B
fanout       = floor(7337 / 2064)                        =      3
depth        = ceil(log_3(1e8)) = ceil(18.42 / 1.10)     =     17 levels

Seventeen page reads per lookup — and Postgres will not even let you get there, because it refuses B-tree entries over roughly 2,700 bytes outright.

A hash index stores a 4-byte hash instead of the key, so on the same accounting its entry is 4 + 16 = 20 B. Fanout stops mattering entirely, and the index is 2064 / 20 ≈ 100× smaller.

Price both sides with the same entry convention. Comparing 2 KB of key against 4 bytes of hash and quoting 500× counts the per-entry overhead on neither side — and that overhead is 16 of the hash entry’s 20 bytes, so dropping it inflates the ratio five-fold. 100× is the conservative figure. A real Postgres hash entry is leaner than 20 B, which only moves the number further in the hash index’s favour.

There is a portable version that needs no hash index at all: index a hash you compute yourself, then re-check the real value, because two different URLs can produce the same hash.

CREATE INDEX idx_pages_url_md5 ON pages (md5(url));
SELECT * FROM pages WHERE md5(url) = md5($1) AND url = $1;   -- hash seek, then verify

5. The write cost of indexes — quantified

Everything so far priced indexes on the read path. They also cost on the write path — a cost you can put a number on, and one that a single storage parameter recovers most of.

Write amplification is the ratio of bytes the storage device actually writes to the bytes of user data you asked it to store. Store 200 bytes, write 480 to the device, and your write amplification is 2.4×. It is the number that decides write throughput, and indexes are its main source in a B-tree engine.

Where the extra bytes come from

An INSERT on a table with k indexes dirties 1 + k pages — one heap page and one leaf page per index — in 1 + k different files, at 1 + k random offsets.

Then there is the WAL. The write-ahead log is a single sequential file to which every change is appended and flushed before the change is allowed to reach the data pages, so that a crash can be recovered by replaying it.

Two more terms make the arithmetic below readable:

• A checkpoint is the periodic moment at which all dirty pages are flushed to their data files. After a checkpoint, every page’s “has this been modified since the last checkpoint?” flag resets.
• With full_page_writes = on (the Postgres default, and required for crash safety on most filesystems, because a crash mid-write can leave a page half-updated and unrecoverable), the first modification of a page after a checkpoint writes the entire 8 KB page image into the WAL. That image is called an FPI, a full-page image.

So the same insert costs wildly different amounts depending on when in the checkpoint cycle it lands. Price a 200-byte row on a table with 5 indexes, at both extremes:

right after a checkpoint:  heap FPI 8,192 + 5 x 8,192  =  49,152 B/row  ->  246x
                                            (6 pages x 8,192 = 49,152; / 200 = 245.8)
steady state:              heap ~230    + 5 x ~50      =     480 B/row  ->  2.4x
                                            (480 / 200 = 2.4)

Write amplification is bimodal — 2.4× while pages are hot, 246× just after a checkpoint. That is a 100× swing in the cost of an identical statement, and it is why insert throughput has a sawtooth that gets misdiagnosed as a bad query or a noisy neighbour.

What each index costs in throughput

Plotted against index count, the penalty is close to linear in the number of extra page writes.

The absolute throughputs in the first row below are illustrative, not measured. There is no hardware, benchmark or source behind them, and there could not be a portable one, since inserts/s depends entirely on the device, the row width and the checkpoint schedule. Re-measure them on your own hardware before quoting them to anyone.

What is worth carrying is the shape: the Relative row (each throughput divided by the zero-index throughput) and the 1/(1 + 0.55k) model, which is a consequence of the 1 + k page writes derived above and holds regardless of what the top-left number is on your machine. Compare the bottom two rows — the model tracks the shape to within a percentage point.

“Just add an index” costs about a third of your write throughput for the first one — 1/(1 + 0.55) = 0.65 — plus storage, plus buffer-pool share, plus autovacuum work.

The honest framing: an index is a denormalization — a redundant second copy of data kept purely to make reads faster — with an automatic consistency mechanism. Price it accordingly.

The assumption, and what it costs when it is wrong. Every index is a bet that the reads it accelerates are worth a fixed tax on every write to that table, forever. On a read-heavy table the bet is trivially good. On an ingest table it is not, and the tax is charged even for indexes nothing queries — which is why pg_stat_user_indexes.idx_scan = 0 is worth auditing, and why the same insert on an append-only workload is the case Lsm trees vs b trees redesigns from scratch.

HOT updates: the fillfactor result

There is one exception to “an update touches every index” — and a storage parameter that makes the exception the common case.

Postgres never updates a row in place. It writes a new version of it (Mvcc and deadlocks) at a new physical address. Since every index entry points at a physical row address, and the address just changed, every index normally gets a new entry — even indexes on columns that did not change.

The exception is a Heap-Only Tuple (HOT) update, which applies when both of these hold:

1. no indexed column changed, and
2. the new version fits on the same page as the old one.

Then the new version is chained within the page — the old version points at the new one — and no index is touched at all. The existing index entries still point at the right page, and the in-page chain does the rest.

Condition (2) is where fillfactor earns its keep. The heap default is 100, which leaves a freshly-loaded page with zero free space, so the first update to any row on it must go to a different page. That is a non-HOT update and it costs k index writes.

Price it. Take a table with 5 indexes taking 10,000 updates per second. A non-HOT update writes six pages — one heap page plus five index leaf pages — while a HOT update writes one. So the per-update page cost is a weighted average of 6 and 1:

5 indexes, 10,000 updates/s
fillfactor 100, HOT ~5%:   10,000 x (0.05 x 1 + 0.95 x 6)  =  57,500 page writes/s
                                     (0.05    + 5.70 = 5.75 pages per update)
fillfactor  85, HOT ~85%:  10,000 x (0.85 x 1 + 0.15 x 6)  =  17,500 page writes/s
                                     (0.85    + 0.90 = 1.75 pages per update)

57,500 / 17,500 = 3.3. 3.3× less write I/O from one storage parameter — and it works only because an update touching no indexed column can skip the indexes entirely.

ALTER TABLE t SET (fillfactor = 85);

On your hottest update table, that is among the highest-leverage single lines in Postgres tuning.

The assumption, and what it costs when it is wrong. Lowering fillfactor buys HOT updates by deliberately wasting 15% of every page, which is a good trade only if the table is actually updated. On an append-only or read-only table the same setting is pure loss: 15% more pages to store, 15% more pages to scan, and not one HOT update to show for it.

6. LSM trees vs B-trees

The B-tree is one of two major storage engine families. The other — behind RocksDB, Cassandra and most modern key-value stores — has read and write amplification you can derive, and a precise account of which workload it wins and which it loses.

The structure, in four moving parts

A B-tree updates in place: it finds the page holding the row and rewrites that page. An LSM — a log-structured merge tree — never does. It only appends. Four parts:

1. Writes land in a memtable, an in-memory sorted structure.
2. When the memtable fills, it is flushed whole to disk as an immutable sorted file called an SSTable (sorted string table).
3. Compaction, a background process, merges those files into larger sorted runs, so reads do not have to consult an unbounded number of them.
4. Nothing is ever modified after it is written. An “update” is a newer record that shadows the older one.

Costing compaction

The cost of compaction depends on how the levels are sized. In leveled compaction each level is T times bigger than the one above, and merging a file down into level i rewrites the overlapping files it lands among.

Set the parameters: size ratio T = 10, a 64 MB memtable, a 640 GB dataset. Multiply the level sizes out from the top:

L1 =  640 MB      L2 = 6.4 GB      L3 = 64 GB      L4 = 640 GB

L4 reaches the dataset size, so there are 4 levels below L0 — L0 being the landing zone for freshly flushed memtables, whose files may overlap each other and so cannot be treated as one sorted run.

Now count bytes written per user byte, and places read per lookup:

write amp  = 1 (WAL) + 1 (L0 flush) + T x L = 1 + 1 + 10 x 4 = 42 bytes per user byte
             the T x term is the merge: pushing one file into level i rewrites the
             ~T overlapping files it lands among

read amp   = memtable + up to 4 overlapping L0 files + 1 per level      = 9 lookups
             = 1      + 4                            + 4
with bloom filters at 10 bits/key (~1% FP)  =  1 + 9 x 0.01           ~= 1.09 lookups

Two terms from that block:

• Read amplification is the mirror of write amplification: how many places you must look to answer one read. Nine, here, because a key could be in any of nine sorted runs.
• A bloom filter is a small probabilistic structure that answers one question: “is this key definitely absent, or possibly present?” It can produce false positives (FP) — a “possibly” for a key that is not there — but never a false negative. So a “no” is a proof, and the file is skipped without being opened. At 10 bits per key the false-positive rate is about 1%, so of the 9 places you would have looked, you actually open 1 (where the key is) plus 9 × 0.01 = 0.09 false alarms.

Bloom filters are the entire reason LSM point reads are competitive. And a bloom filter cannot answer “what keys lie in [a, b]” — it only answers about a single key — so range scans get no help at all and must merge one iterator per level plus one per L0 file. The LSM’s weakness is exactly what the bloom filter cannot cover.

The three engine families side by side

Each column below is one storage engine family; each row is a cost you can be asked to price. The two LSM columns differ only in compaction strategy, and that one choice moves write amplification by an order of magnitude — compare their Write amplification cells.

Two rows need their terms named:

• Size-tiered compaction, the Cassandra default in the last column, merges files of similar size rather than maintaining strict levels. It writes far fewer bytes but leaves many overlapping files to read through — which is why its write amplification is 4-5× and its range scans merge 10-30 streams.
• Space amplification is the third member of the family: bytes stored on disk per byte of live data. 2× means half the device holds obsolete copies. Size-tiered pays 2× because a compaction must hold both the inputs and the output at once.

The headline is not “LSM writes less” — leveled LSM often writes more bytes. It is that LSM writes are sequential and batched while a B-tree’s are random and page-granular.

On flash that is the difference between saturating the device and being bounded by amplification inside the SSD’s own FTL — the flash translation layer, the controller firmware that must itself erase and rewrite whole blocks to service a small random write. A 42× sequential amplification can still beat a 2.4× random one.

This is the RUM conjecture in practice: Read, Update, Memory — optimize two, pay for the third. B-trees buy reads with update cost. LSMs buy updates with read cost. Both buy some back with memory (buffer pool, bloom filters) — which is why “add RAM” is the universal first answer, and also why it eventually stops working.

Tombstones, and why Cassandra is not a queue

A tombstone is a marker meaning “this key is deleted”, written as a new record — because in an append-only structure you cannot go back and remove anything.

The consequence is that a tombstone cannot be discarded early. An older SSTable may still hold the value it is shadowing, so the tombstone must be read on every subsequent lookup of that range until compaction has pushed it all the way to the bottom level.

Now shape a workload as a queue: insert, read, delete, repeat. A queue-shaped Cassandra table accumulates tombstones faster than compaction clears them. Reads slow monotonically as each lookup wades through more markers, and eventually tombstone_failure_threshold starts returning errors.

“Do not use Cassandra as a queue” is a direct consequence of append-only deletes, not a style rule.

The assumption, and what it costs when it is wrong. An LSM is optimised for a write-heavy workload whose reads are mostly point lookups against a working set the bloom filters and page cache can cover. Three mismatches each have a name above: a range-scan workload gets no help from the filters and pays the 9-stream merge; a delete-heavy or queue-shaped workload accumulates tombstones and degrades without bound; and a latency-sensitive workload meets compaction stalls, because the work an LSM defers has to happen eventually and it happens in bursts. A B-tree’s costs are worse on average here and far more predictable, which is the actual trade.

7. How the planner picks a plan

How does the engine choose between plans? The choice hinges almost entirely on one estimate — and a wrong estimate turns a 300 ms query into a 10-minute one.

Cardinality estimation is the whole game

The planner (or optimizer) is the component that turns a declarative query into an executable plan by enumerating candidates and costing each. Cardinality here means the number of rows a step is expected to produce, and it is the input every cost depends on.

The planner scores candidate plans with the cost model of When the index is not used and why. Those costs are fed by statistics kept in pg_statistic and refreshed by ANALYZE, the command that samples a table and stores what it found. Four of those statistics do the work:

Selectivity of country = 'US' is then the MCV frequency if 'US' is in that top-100 list, and otherwise (1 - sum(MCV freqs)) / (n_distinct - num_MCV) — “spread whatever probability the common values did not claim evenly over the remaining distinct values.”

The independence assumption, and the 960× error

Given selectivities for two predicates, Postgres combines ANDed predicates by multiplying them, as if the columns were statistically independent. That is the independence assumption, and it is where estimates go wrong. Watch it break on two columns that are anything but independent:

WHERE city = 'San Francisco' AND state = 'CA'      -- on 5,000,000 rows

With 5,000 distinct cities and 50 distinct states, each predicate looks selective on its own:

estimate = (1/5000) x (1/50) = 4e-6   ->      20 rows      (4e-6 x 5,000,000 = 20)
actual                                ->  19,204 rows   (city determines state)
                                              960x underestimate  (19,204 / 20)

Every San Francisco row is already a California row, so the state predicate removes essentially nothing — but the planner still divided by 50 for it.

Now feed 20 into the plan chooser. A nested loop is the join that scans one input and looks up the other once per row, so its cost is outer_rows × inner_lookup_cost. Twenty outer rows makes it look almost free:

planner believes:      20 x 5 page reads =    100 reads   -> "cheap, nested loop"
reality:           19,204 x 5 page reads = 96,020 random  ~= 9.6 seconds
hash join would have been: scan both sides once           ~= 0.3 seconds

Bad statistics do not degrade a plan gracefully. The estimate enters the cost model multiplicatively, and nested-loop cost is linear in the outer cardinality, so a 1,000× underestimate buys you a roughly 1,000× slower plan. The plan did not get 10% worse; it changed shape.

Fix the estimate, not the plan. Extended statistics tell the planner the two columns are dependent, and it stops multiplying:

CREATE STATISTICS stx_city_state (dependencies, ndistinct) ON city, state FROM customers;
ANALYZE customers;

Four other standard causes of a bad estimate, worth naming because the fix differs for each:

• stale statistics after a bulk load — nothing ran ANALYZE;
• default_statistics_target = 100 on a column with 200,000 distinct values, so the histogram is far too coarse;
• correlated predicates that extended statistics do not cover, such as expressions and inequalities;
• estimates through a join, where the error at each level of the plan tree multiplies into the level above it.

The assumption, and what it costs when it is wrong. The cost model assumes predicates are statistically independent and that the sampled statistics still describe the table. Both assumptions are cheap — they make planning a few hundred microseconds instead of a search over correlations — and both fail in the same direction, underestimating rows, which is the direction that picks nested loops. That is why the failure mode is not “slightly worse plan” but “different plan shape, three orders of magnitude slower.”

Join algorithms and their cost models

Three algorithms exist to join two inputs, and the choice between them is a function of one number — how many rows come out of the outer side.

The flowchart below is the decision the planner makes. Follow it top to bottom: the first question is whether hashing or sorting is even available, and only then does the row count matter.

flowchart TD
    J{"Join condition<br/>is an equality?"} -->|no| NL["Nested loop — the only general option,<br/>and the expensive one: cost grows<br/>linearly with the outer row count"]
    J -->|yes| O{"Outer row count<br/>after filters"}
    O -->|"small · under ~5,000"| NLI["Nested loop<br/>+ index on the inner key"]
    O -->|large| S{"Both inputs already<br/>sorted on the join key?"}
    S -->|yes| MJ["Merge join<br/>one pass · O(1) memory"]
    S -->|no| H{"Build side fits<br/>in work_mem?"}
    H -->|yes| HJ["Hash join"]
    H -->|no| HB["Hash join, batched<br/>spills · 2x extra I/O"]
    style NLI fill:#2d6a4f,color:#fff
    style HJ fill:#2d6a4f,color:#fff
    style HB fill:#bc6c25,color:#fff
    style NL fill:#9d0208,color:#fff

Reading the diagram, branch by branch.

The first question eliminates two of the three algorithms. Only an equality join can be answered by hashing (you must hash something and look it up) or by a merge (you must be able to say “these two are equal, advance both”). So a join on <, LIKE, or a range condition is a nested loop by elimination. That box is flagged not because a nested loop is a bad choice, but because it is the absence of a choice: its cost is linear in the outer row count with no ceiling, and a non-equality join on a large outer side is the one shape in this section with no fast plan available at any price.

Given equality, the outer row count decides. A small outer side favours the nested loop with an index on the inner key — a few thousand cheap lookups. A large one favours a merge join if both sides already arrive sorted on the join key, and otherwise a hash join, which builds a hash table over the smaller “build” side and probes it with the larger side.

One failure mode to know: if the build side does not fit in work_mem, the hash join spills. It partitions both inputs into temporary files and processes them batch by batch, paying roughly double the I/O.

The same three algorithms as a cost table. The Memory column is the one people forget, and it is what decides behaviour under pressure:

The crossover, in numbers

Join orders (10M rows, 100,000 pages) to customers (1M rows, 20,000 pages) on an indexed customer_id. Run the same join at both extremes of outer row count.

Case A — WHERE o.order_id = 12345, one outer row
  nested loop:  5 + 4 + 1                              =         10 page reads
                (find the 1 order: 5)  (descend the customers index: 4)  (its heap page: 1)
  hash join:    build over customers                   =     20,000 page reads   -> NL wins 2,000x

Case B — no filter, 10M outer rows
  nested loop:  10,000,000 x ~5 random                 = 50,000,000 reads  ~= 5,000 s
  hash join:    100,000 + 20,000 sequential            =    120,000 reads  ~=     1 s   -> HJ wins ~5,000x
                (scan orders)  (scan customers)

crossover:  N_outer x C_index_lookup = inner scan cost  ->  N_outer x 4 = 20,000  ->  5,000 rows

The hash join costs the same 20,000 pages in both cases — it scans the inner side once no matter what. The nested loop costs 10 in one case and 50,000,000 in the other. Set the two equal and solve, and the crossover lands at 5,000 outer rows.

Nested-loop cost is linear in the outer row count; hash-join cost is constant in it. So the crossover sits at inner_scan_cost / index_lookup_cost, and a cardinality error that straddles that point is the difference between a 300 ms query and a 10-minute one.

That is the mechanical link to every “it was fast yesterday” incident. Nothing changed except a statistic.

8. Reading EXPLAIN ANALYZE line by line

EXPLAIN output is the engine’s own account of a query — what it expected, what actually happened, and where the two diverged. One plan, whose 19-second runtime traces back to a single bad estimate, carries the whole lesson.

Three commands, three levels of detail:

• EXPLAIN prints the plan the planner chose, along with its estimates. It does not run the query.
• EXPLAIN ANALYZE additionally runs the query and prints what really happened next to each estimate.
• BUFFERS adds the page counts, which is the only physical number in the output.

Here is the query. It is the same correlated city/state predicate from How the planner picks a plan, now joined to a second table.

EXPLAIN (ANALYZE, BUFFERS)
SELECT c.name, sum(o.amount_cents)
FROM customers c JOIN orders o ON o.customer_id = c.customer_id
WHERE c.city = 'San Francisco' AND c.state = 'CA'
  AND o.created_at >= DATE '2025-06-01'
GROUP BY c.name;

And here is its plan. Do not try to absorb it all at once. The two numbers that matter are on every node: rows=N inside the cost=... parentheses is what the planner expected, and rows=N inside the actual time=... parentheses is what it got. Scan down comparing those two, and the whole diagnosis falls out.

 GroupAggregate  (cost=41.20..2913.55 rows=4 width=42)
                 (actual time=8114.902..19244.371 rows=18732 loops=1)
   Group Key: c.name
   Buffers: shared hit=1204118 read=812446
   ->  Sort  (cost=41.20..41.21 rows=4 width=18)
             (actual time=8114.833..9902.114 rows=2841190 loops=1)
         Sort Key: c.name
         Sort Method: external merge  Disk: 91352kB
         ->  Nested Loop  (cost=0.86..41.16 rows=4 width=18)
                          (actual time=0.094..6402.775 rows=2841190 loops=1)
               ->  Index Scan using idx_customers_city on customers c
                     (cost=0.43..12.90 rows=4 width=14)
                     (actual time=0.041..44.208 rows=19204 loops=1)
                     Index Cond: (city = 'San Francisco'::text)
                     Filter: (state = 'CA'::text)
                     Rows Removed by Filter: 12
               ->  Index Scan using idx_orders_customer on orders o
                     (cost=0.43..7.05 rows=1 width=12)
                     (actual time=0.011..0.298 rows=148 loops=19204)
                     Index Cond: (customer_id = c.customer_id)
                     Filter: (created_at >= '2025-06-01'::date)
                     Rows Removed by Filter: 1103
 Planning Time: 0.612 ms
 Execution Time: 19270.884 ms

Two labels in that output decide everything below, and confusing them is the most expensive mistake you can make reading a plan:

• An Index Cond is a predicate the index itself used to narrow the seek. Rows that fail it are never read at all.
• A Filter is a predicate applied after the row was read, and the row is then discarded. The row cost you I/O regardless.

Now read the plan bottom-up and inside-out. Six observations, in the order they lead to each other.

1. rows=148 loops=19204 is a per-loop average, not a total.

Multiply to get the real row count: 148 × 19,204 = 2,842,192. That recovers the Nested Loop’s rows=2841190 to within the rounding in that 148.

The two are not equal and should not be presented as though they were. EXPLAIN rounds the per-loop figure to a whole number, so the true average is 2,841,190 / 19,204 = 147.948, and multiplying the printed 148 back out overshoots by 1,002 rows — 0.04%. Use the multiplication as an order-of-magnitude check, not as an identity.

Misreading it the other way is the most common EXPLAIN error: people see “148 rows”, conclude the inner side is cheap, and miss that it ran 19,204 times.

2. rows=4 estimated against rows=19204 actual on the customers scan — 4,800× low.

The cause is one line down in the output: Filter: (state = 'CA') with Rows Removed by Filter: 12. That predicate removed 12 rows out of 19,216, so it is almost perfectly redundant with city. The planner multiplied by 1/50 for it anyway — the independence assumption of How the planner picks a plan, caught in the act.

3. That estimate chose the Nested Loop.

With 4 outer rows a nested loop is the right plan. With 19,204 it is the wrong one, because the crossover is around 5,000 (Join algorithms and their cost models). The plan is not stupid; it correctly answered a different question than reality asked.

4. loops=19204 means 19,204 separate index descents into orders.

Each descent returns 148 + 1103 = 1,251 rows and throws away 1,103 of them. That is 1,103 × 19,204 = 21.2 million rows read and discarded — because created_at appears as a Filter and not an Index Cond, so those rows had to be fetched before they could be rejected.

5. Sort Method: external merge Disk: 91352kB — the sort spilled.

It expected 4 rows and got 2.8 million, blew through work_mem, and wrote 91 MB to temporary files. This is also caused by the estimate: with a correct one, the planner picks HashAggregate — grouping through a hash table, which needs no sort at all — and skips this node entirely.

6. Buffers: shared hit=1204118 read=812446 — the physical cost.

hit is pages found in the buffer pool; read is pages fetched from outside it. So 812,446 × 8,192 B = 6.6 GB of I/O.

Always run with BUFFERS. Cost units are arbitrary; buffer counts are physical bytes.

Note also the ratio of Execution Time to Planning Time: 19,270 ms against 0.6 ms. Planning is effectively free. If it is ever comparable to execution, you have a prepared-statement or partition-count problem, not a query problem.

The fix, in the order the diagnosis gives it

None of this touches the query text.

-- 1. fix the ESTIMATE, which fixes the plan shape for free
CREATE STATISTICS stx_cust_city_state (dependencies, ndistinct) ON city, state FROM customers;
ANALYZE customers;
-- 2. make created_at a seek boundary instead of a post-read filter
CREATE INDEX idx_orders_cust_created ON orders (customer_id, created_at);
-- 3. only now consider work_mem; with (1) the planner picks HashAggregate anyway

After (1) the estimate becomes ~19,000, the planner switches to a hash join, the sort becomes a HashAggregate, and (2) removes the 21.2M discarded rows. 19.3 s -> ~340 ms, and not one line of the SQL changed.

One safety note before you use any of this. EXPLAIN ANALYZE runs the statement, so on an INSERT, UPDATE or DELETE it really does modify the data — wrap it in a transaction you roll back. The cost gate in the SQL analytics agent case study uses plain EXPLAIN for exactly that reason: it needs the estimate before the query is allowed to run.

9. Transactions: ACID, precisely

What does a transaction actually promise, one letter at a time, and what does each isolation level give up in exchange for concurrency? The five anomalies below are worked as interleavings you could type into two psql sessions rather than as definitions — four of the five, anyway. The fifth, the dirty read, has no Postgres interleaving to show: Postgres cannot produce it at any isolation level, and that is the demonstration.

A transaction is a group of statements the database treats as one unit: either all of their effects apply or none do, and while they run, other transactions see a controlled view of them.

ACID is the four-letter acronym for what that unit guarantees — atomicity, consistency, isolation, durability. Each letter is a precise claim backed by a specific mechanism, and the table below pairs them. The row worth staring at is C, which is the odd one out and is the letter interviews probe.

Five terms from that table:

• An xid is a transaction id, the monotonically increasing number Postgres stamps on every transaction. clog is the commit log, a small array recording whether each xid committed or aborted.
• FK is a foreign key, a declared reference from one table’s column to another’s.
• MVCC is multi-version concurrency control, the subject of Mvcc and deadlocks: keeping several versions of a row so readers and writers do not block each other.
• SSI is serializable snapshot isolation, defined later in this section.
• fsync is the system call that forces buffered writes onto the physical device. The operating system reporting a successful write is not durability; the device acknowledging it is.

Durability is the letter to say out loud in an interview, because Postgres has a setting that breaks it deliberately. With synchronous_commit = off, commits are acknowledged before the WAL is flushed, so a crash loses up to about 600 ms of committed transactions. It buys a 2-5× write win, and it is a durability setting, not a performance setting. Fine for event ingest; not for payments.

The isolation ladder

Higher isolation levels forbid more anomalies and cost more concurrency, and the ladder is short — three rungs in practice.

The diagram below shows those three rungs and, on the dotted arrows, what each one still permits. It names four anomalies — non-repeatable read, phantom, lost update and write skew — before any has been defined. For now read them as nothing more than labels for four specific ways concurrent transactions produce a wrong answer. Each gets a definition and a worked, two-session interleaving below the table that follows.

flowchart TD
    RC["READ COMMITTED<br/>a new snapshot per statement"] --> RR["REPEATABLE READ<br/>one snapshot per transaction"]
    RR --> SER["SERIALIZABLE<br/>snapshot + read-set tracking"]
    RC -.->|"still allows"| A1["non-repeatable read · phantom<br/>lost update · write skew"]
    RR -.->|"still allows"| A2["write skew"]
    SER -.->|"allows"| A3["nothing — it aborts you instead"]
    style SER fill:#2d6a4f,color:#fff
    style A1 fill:#9d0208,color:#fff
    style A2 fill:#bc6c25,color:#fff

A snapshot is the frozen view of the database a statement or transaction reads from. That one word is the whole difference between the first two rungs: READ COMMITTED takes a new snapshot per statement, REPEATABLE READ takes one per transaction and holds it. The third rung needs something extra — tracking which rows a transaction read, not just which it wrote.

Three abbreviations used from here on: RC is READ COMMITTED, RR is REPEATABLE READ, and Postgres’s implementation of RR is what the literature calls snapshot isolation (SI).

The table below is the same ladder as a grid: rows are anomalies, columns are levels, and each cell says whether that level permits that anomaly.

Read the READ COMMITTED column first. That is the Postgres default, so every “yes” in it is an anomaly your code is exposed to unless you asked for something else — all four of them. (MySQL/InnoDB defaults to REPEATABLE READ instead, one column to the right, which is a second reason to name the engine before quoting a guarantee.)

Then look at the two cells that say “standard: … · Postgres: …”. Those are where Postgres is stricter than the SQL standard requires, and they are what make “REPEATABLE READ” an ambiguous phrase across engines.

Each anomaly below gets a definition, then a two-column trace you could type into two psql sessions. In every trace, T1’s statements are on the left and T2’s are on the right, and vertical position is time: a line lower down happens later.

Dirty read

Reading a value another transaction wrote but never committed. T1 updates a balance from 100 to 500 and then rolls back; T2 reads 500 in between and acts on a value that never existed.

Postgres cannot do this at any level. READ UNCOMMITTED is accepted syntactically and behaves as READ COMMITTED, because a reader consults the xmin/xmax commit status of each row version and no code path returns an uncommitted one. There is no interleaving to show, and that absence is the demonstration.

Non-repeatable read

Reading the same row twice in one transaction and getting two different values. Allowed at READ COMMITTED:

 T1  (READ COMMITTED)                      T2
 BEGIN
 SELECT balance ... WHERE id=1;  -> 100
                                           BEGIN; UPDATE accounts SET balance=400
                                             WHERE id=1; COMMIT
 SELECT balance ... WHERE id=1;  -> 400    <- same row, same transaction, new value
 COMMIT

Mechanism exactly: at READ COMMITTED Postgres takes a fresh snapshot at the start of every statement. T1’s second SELECT gets a snapshot taken after T2 committed, so it sees 400. At REPEATABLE READ the snapshot is taken at the transaction’s first statement and held, so the second SELECT still returns 100.

The anomaly is not a bug in the level. It is the definition of the level.

Phantom

Re-running the same search and finding rows that were not there before. Same shape as the previous case, but what changes is the result set, not the value in a row you already read:

 T1  (READ COMMITTED)                      T2
 BEGIN
 SELECT count(*) FROM orders
   WHERE status='pending';  -> 42
                                           BEGIN; INSERT INTO orders (status)
                                             VALUES ('pending'); COMMIT
 SELECT count(*) FROM orders
   WHERE status='pending';  -> 43          <- same search, same transaction, a new row
 COMMIT

The same trace gives three different answers depending on where you run it:

• READ COMMITTED (any engine): 42 then 43. Each statement gets its own snapshot.
• The SQL standard’s REPEATABLE READ: 42 then 43. The standard explicitly permits phantoms at this level.
• Postgres’s REPEATABLE READ: 42 then 42. Postgres implements RR as a full transaction-wide snapshot, so it forbids phantoms the standard allows.

InnoDB is a fourth answer, and it is the one that catches people. Its RR gives snapshot reads too, so a plain SELECT returns 42 twice. But a locking read — SELECT ... FOR UPDATE, which takes a lock on every row it returns — or a write sees the latest committed row instead. That produces the notorious case where SELECT and SELECT ... FOR UPDATE in the same transaction disagree about what exists. InnoDB blocks phantoms in those locking reads using next-key (gap) locks, which lock the empty space between existing keys so no one can insert into it.

“REPEATABLE READ” is not one thing across engines. Say which engine you mean.

Lost update

Two transactions read the same value, both compute from it, and one of the two writes disappears. Allowed at READ COMMITTED:

 T1                                        T2
 SELECT count FROM counters WHERE id=1; -> 10
                                           SELECT count FROM counters WHERE id=1; -> 10
 UPDATE counters SET count=11 WHERE id=1; COMMIT
                                           UPDATE counters SET count=11 WHERE id=1; COMMIT
 -- two increments applied, count = 11

Both transactions read 10, both computed 11, both wrote 11. Two increments happened and the counter went up by one.

The fix is not a higher isolation level. Move the read inside the write:

UPDATE counters SET count = count + 1 WHERE id = 1;

That is atomic because the UPDATE re-reads the latest committed version under a row lock, rather than trusting a value your session read earlier. When the computation cannot be expressed in SQL, use SELECT ... FOR UPDATE to take the lock at read time instead.

At REPEATABLE READ Postgres does not silently lose the update — it detects the conflict and aborts T2 with could not serialize access due to concurrent update. Correct, but it means every RR transaction needs a retry loop.

Write skew

The one anomaly snapshot isolation does not prevent. Two transactions read an overlapping set of rows, each writes a different row, and together they break an invariant neither broke alone.

The invariant in the trace below: at least one doctor is on call for the night shift.

 T1  (Alice, REPEATABLE READ)              T2  (Bob, REPEATABLE READ)
 BEGIN
 SELECT count(*) FROM on_call
   WHERE shift='night' AND on_call;  -> 2
                                           BEGIN
                                           SELECT count(*) FROM on_call
                                             WHERE shift='night' AND on_call;  -> 2
 -- 2 >= 2, safe for me to leave
 UPDATE on_call SET on_call=false
   WHERE name='alice';
                                           -- 2 >= 2, safe for me to leave
                                           UPDATE on_call SET on_call=false
                                             WHERE name='bob';
 COMMIT                                    COMMIT
 -- both succeed · zero doctors on call

Snapshot isolation misses this because both transactions read the same rows and wrote different ones — there is no write-write conflict to detect. What was invalidated was each transaction’s premise, and snapshot isolation does not track premises. That sentence is the whole answer to “what does SERIALIZABLE buy me that REPEATABLE READ doesn’t.”

Postgres SERIALIZABLE — Serializable Snapshot Isolation, SSI — does track premises. Two pieces:

• SIREAD locks are predicate locks: records of what a transaction read, including the ranges it searched. They do not block anybody; they are bookkeeping.
• The engine aborts a transaction when those records reveal a dangerous structure: two consecutive read-write antidependency edges through a pivot transaction. An antidependency is “T2 wrote something T1 had read”, and that structure is the necessary condition for a cycle that no serial order could produce.

Three fixes that avoid needing SSI at all, best first:

1. Make the constraint checkable. A per-shift staffed_count row with CHECK (staffed_count >= 1) turns a premise into a constraint the database already enforces.
2. Materialize the conflict — force the two transactions to write the same row. SELECT ... FROM shifts WHERE id='night' FOR UPDATE converts write skew into a write-write conflict, which snapshot isolation does catch.
3. Lock every premise row. Correct, but it serializes readers, which is the cost you were trying to avoid.

Why SERIALIZABLE is not always the answer

Having established that SERIALIZABLE is the only level with no anomalies, this part explains why it is still not the default answer.

Four reasons.

It converts concurrency bugs into runtime errors. Every transaction now needs a retry loop, and every retried transaction must be safe to re-run: no emails, no charges, no non-transactional side effect inside it.

Its abort rate grows superlinearly with contention. SSI’s false positives worsen as read sets overlap, and past a point aborted work displaces useful work — so throughput decreases as load rises. That is a feedback loop, not a gentle degradation.

Predicate-lock granularity escalates. When SSI runs out of space to track individual rows, it escalates from tuple to page to relation, so one lock starts standing for a whole page or a whole table. That multiplies false positives exactly when you are busiest.

It is per-database. It says nothing about consistency across shards, across services, or between the database and a cache.

Use SERIALIZABLE when the invariant spans rows the transaction does not write and you cannot express it as a constraint. Use READ COMMITTED plus explicit locking or a constraint everywhere else — which on a well-designed schema is almost everywhere.

Here is the retry loop that makes SERIALIZABLE usable. Two details carry the weight: it catches only the serialization failure (not every exception), and it sleeps for an exponentially growing time with random jitter mixed in, so that two transactions that collided do not retry in lockstep and collide again.

import random, time

from psycopg.errors import SerializationFailure   # psycopg 3; psycopg2 has the
                                                  # same name under psycopg2.errors


def run_serializable(conn, work, max_retries=5):
    """SERIALIZABLE turns conflicts into errors, so a retry loop is mandatory.
    `work` must have no side effects outside the transaction."""
    for attempt in range(max_retries):
        try:
            with conn.transaction(isolation="serializable"):
                return work(conn)
        except SerializationFailure:          # SQLSTATE 40001, and 40P01 deadlock
            if attempt == max_retries - 1:
                raise
            time.sleep((2 ** attempt) * 0.01 * (0.5 + random.random()))
    raise AssertionError("unreachable")

The assumption, and what it costs when it is wrong. Every isolation level below SERIALIZABLE is a bet that the anomalies it permits do not matter for your data — a bet that is usually right and always silent when it is wrong, because a lost update produces a plausible number rather than an error. SERIALIZABLE inverts the bet: it never lets the anomaly through and instead charges you aborts, which are loud but grow superlinearly with contention. Choose per invariant, not per application.

10. MVCC and deadlocks

Behind the snapshots of Transactions acid precisely is the mechanism that lets Postgres run readers and writers concurrently without blocking each other. It sends three bills, and it leaves one failure mode that comes from locking rather than versioning.

MVCC, multi-version concurrency control, is one idea: an update does not overwrite a row, it writes a new version of it. An old reader can therefore keep reading the old version while the writer proceeds.

Three pieces make it work in Postgres:

• Every row version carries xmin, the xid of the transaction that created it, and xmax, the xid of the transaction that deleted or superseded it (unset if the version is still current).
• A snapshot is a triple: (oldest running xid, next xid, the list of in-progress xids). That is enough to say, of any xid, whether it had committed at the moment the snapshot was taken.
• A version is visible to a snapshot if its xmin committed before the snapshot was taken and its xmax is either unset or not yet committed as of that snapshot.

The diagram below traces one row through three updates: two different snapshots read the same row and get different versions, and both are correct.

flowchart LR
    V1["v1 · xmin=100 · xmax=140"] --> V2["v2 · xmin=140 · xmax=175"] --> V3["v3 · xmin=175 · xmax=null"]
    S1(["snapshot taken at xid 150"]) -.->|"sees v2"| V2
    S2(["snapshot taken at xid 200"]) -.->|"sees v3"| V3
    V1 -.->|"invisible to everyone<br/>reclaimable"| VAC["VACUUM"]
    style V3 fill:#2d6a4f,color:#fff
    style VAC fill:#bc6c25,color:#fff

Walking the diagram: version 1 lived from transaction 100 until 140, version 2 from 140 until 175, and version 3 from 175 onward with no end yet.

A snapshot taken at transaction 150 falls inside v2’s window (140 ≤ 150 < 175), so it sees v2. A snapshot taken at 200 falls inside v3’s window, so it sees v3. Same row, two answers, both correct.

Version 1 is visible to no living snapshot, which makes it garbage — and VACUUM, the background process that reclaims dead versions, is free to remove it.

A writer creates a new version instead of overwriting the old one, so the version a reader is looking at still exists. That is the entire mechanism, and it is why readers never block writers and writers never block readers.

Writers still block writers on the same row, via a lock in the tuple header. MVCC removes the reader-writer conflict, not the writer-writer one.

The bill for all this arrives in three places:

• Bloat. Dead versions occupy pages until VACUUM; bloat is the resulting gap between a table’s size on disk and the size of its live data. A row updated 10× is 11 versions until then.
• Long transactions pin the horizon. VACUUM may only remove versions invisible to every running snapshot, so one session idle in transaction since 09:00 blocks reclamation database-wide. This is exactly why the analytics agent’s connection string sets idle_in_transaction_session_timeout (case study 07).
• Transaction ID wraparound. Xids are 32-bit, so they eventually run out and restart, at which point an old transaction id would look like a future one. Autovacuum must freeze old tuples — mark them as visible to everyone, independent of xid — before the 2^31 window wraps, or Postgres refuses new writes to protect the data. A well-known outage class, always preceded by weeks of ignored warnings.

InnoDB does MVCC the other way round. It updates the row in place in the clustered index and pushes the old version into the undo log — a separate area holding the information needed to reconstruct earlier versions on demand.

The consequences invert cleanly:

• No table bloat from updates, because the live row never moves and old versions live elsewhere.
• But a long-running reader grows the undo history and must walk undo records to rebuild the version it is entitled to see, and that walk gets longer over time.

So old readers get progressively slower in InnoDB, while in Postgres they stay fast and everyone else pays in bloat. Same problem, opposite victim.

The assumption, and what it costs when it is wrong. MVCC assumes transactions are short, so the set of versions any snapshot pins stays small and cleanup keeps up. Break that assumption — one analytics query running for an hour, one connection left open in a transaction — and the cost is not paid by the offender but by the whole database, as bloat in Postgres or as an ever-longer undo chain in InnoDB. That asymmetry is why the fix is always a timeout rather than a faster vacuum.

Deadlocks

Versioning removes the reader-writer conflict but not the writer-writer one, and two writers that need each other’s rows produce the one failure mode that no amount of MVCC can avoid.

A deadlock is a cycle of transactions each waiting for a lock another holds, so none can ever proceed. Trace the smallest possible one — two transactions, two rows, opposite order:

 T1                                        T2
 BEGIN                                     BEGIN
 UPDATE accounts .. WHERE id=1;            -- holds row lock on 1
                                           UPDATE accounts .. WHERE id=2;   -- holds 2
 UPDATE accounts .. WHERE id=2;            -- waits for T2
                                           UPDATE accounts .. WHERE id=1;   -- waits for T1 -> cycle

Detection uses a wait-for graph: a graph with an edge from each waiting transaction to the one it is waiting on. A cycle in that graph is a deadlock.

The two engines detect it on very different schedules, and this is the part people get wrong:

• Postgres does not check on every wait. It checks only after a wait exceeds deadlock_timeout (default 1 second), then aborts the transaction that ran the check. So a deadlock costs a full second of latency before anyone notices — which is why deadlocks show up in latency dashboards before they show up in error logs.
• InnoDB checks immediately and rolls back the transaction that modified the fewest rows, because that is the cheapest one to undo.

Prevention, in order of effectiveness:

1. Acquire locks in a consistent global order. Note that a multi-row UPDATE locks rows in plan order, which is not stable across plan changes. Lock explicitly: SELECT ... FOR UPDATE ORDER BY id.
2. Keep transactions short, and never make a network call inside one. A held lock plus an HTTP timeout is a deadlock waiting for a partner.
3. Shrink the lock footprint. Prefer FOR NO KEY UPDATE over FOR UPDATE when the key is unchanged, since the weaker lock does not conflict with foreign-key checks.
4. Retry. A deadlock is transient — SQLSTATE 40P01 — and a design that is provably deadlock-free is not achievable in general.

The deadlock that looks like nothing you wrote: foreign keys take a FOR KEY SHARE lock on the parent row. So two transactions inserting children of the same two parents, in opposite orders, deadlock on rows that neither INSERT statement mentions.

11. Scaling: replication

Keeping a second copy of the database costs something either way: commit latency when the copy is synchronous, and correctness when it is not.

Replication means maintaining copies of the database on other machines. One primary accepts writes; one or more replicas apply the same changes. The primary streams its WAL (The write cost of indexes quantified) and the replicas replay it.

Everything else is a single choice: when may the primary acknowledge the commit?

The table below is that choice, as the five settings Postgres offers. Read down the middle column — each row waits for one more step in the write’s journey than the row above, and the last two columns are what that step buys and costs.

Two terms from that table. RTT is the round-trip time to the replica. Failover is the act of promoting a replica to primary when the primary dies — which is the moment “everything not yet shipped” turns from a theoretical loss into a real one.

Now put real network numbers on the latency column. An AZ (availability zone) is one datacentre within a cloud region; a region is a geography.

same-AZ local commit                                    ~0.5 ms
                       = local WAL fsync only
cross-AZ synchronous  = 0.5 + 1.0 (RTT) + 0.5           ~2.0 ms   ->  4x write latency
                        local  network    remote fsync              (2.0 / 0.5)
cross-region us-east-1 -> eu-west-1, 75 ms RTT          ~76  ms   ->  13 serial writes/s
                                                                     (1 / 0.076)

Read the last line again: 76 ms per commit means one connection doing writes back to back manages 13 per second. Nobody runs synchronous cross-region replication on an OLTP write path, and now you can say why in one line rather than as a preference.

The availability trap. With exactly one synchronous standby, a standby outage blocks every commit on the primary — the primary is waiting for an acknowledgement that will never come. One sync replica is an availability downgrade, not an upgrade.

You need at least two candidates before synchronous replication improves availability at all:

synchronous_standby_names = 'ANY 1 (r1, r2)'

That says “wait for any one of these two”, so either replica can be down without stopping writes.

Replica lag is a correctness problem

Replication lag is how far behind the primary a replica’s applied state is, measured in time or in WAL bytes. Treating it as a staleness annoyance understates it by a category.

The diagram sets up the smallest case that breaks: the read happens 9 ms after the write, but the replica is 40 ms behind, so the read cannot see the write no matter how correct everything else is.

flowchart LR
    W["POST /profile<br/>t = 0 ms"] --> P[("Primary")]
    P -->|"WAL stream · lag 40 ms"| R[("Replica")]
    RD["GET /profile<br/>t = 9 ms"] --> R
    R --> OLD["returns the pre-write value<br/>user re-submits stale form data"]
    style OLD fill:#9d0208,color:#fff
    style P fill:#2d6a4f,color:#fff

Traced statement by statement, with the clock on the left:

t =  0 ms  POST /profile  ->  UPDATE users SET bio='...' WHERE id=42     [primary]
t =  6 ms  302 redirect to /profile
t =  9 ms  GET  /profile  ->  SELECT bio FROM users WHERE id=42          [replica, 40 ms behind]
                              returns the OLD bio
t = 12 ms  user sees the old bio, concludes the save failed
t = 15 ms  user edits the re-rendered (stale) form and saves again
t = 21 ms  the stale value is written back over the good one

Look at the last line. The stale value did not just get displayed — it got written back, over the good one.

Replica lag is not a staleness problem, it is a lost-update problem, because the user’s next write is computed from the stale read. This is the same anomaly as Transactions acid precisely’s lost update, arriving through routing instead of through isolation.

The nastier variant: POST /orders succeeds, the client immediately GETs the new id from a replica, gets a 404, and retries the POST. That is one duplicate order per lag window.

Fixes, ranked:

1. Sticky-primary window. Record last_write_at in the session and route that session’s reads to the primary for max_expected_lag afterwards. Simple, and it covers the common case.
2. LSN tokens. An LSN (log sequence number) is the WAL’s byte position, so it names an exact point in the change stream. Capture pg_current_wal_lsn() after each write, hand it to the client, and serve that client’s reads only from a replica whose pg_last_wal_replay_lsn() has caught up to it. Exact rather than heuristic, which is why it beats (1) when you can afford the plumbing.
3. Eject lagging replicas from the pool. Shrinks the bug without removing it.
4. Classify by path. Write paths read the primary; reporting reads go to replicas.

Lag is bimodal, not smooth. It sits near zero for hours, then jumps to minutes. Three things cause the jump: a bulk load, an index build, or a max_standby_streaming_delay conflict — where a long-running query on the replica pauses WAL replay so that the query’s snapshot stays valid.

That last one is perverse: the replica lags most exactly when analytics is running on it, which is the workload you moved there in the first place.

A mean-lag dashboard shows none of this, because hours of zero drown a two-minute spike. Alert on p99 and max — p99 being the 99th percentile, the value 99% of samples fall below.

The assumption, and what it costs when it is wrong. Asynchronous replication assumes reads tolerate being a lag-window stale, and it is what makes read scaling nearly free. The workloads where that assumption fails are not exotic: any read-after-write in a user’s own session, any read that feeds the next write, any client polling for something it just created. The cost is not slowness but wrong data, which is why the fixes above are routing rules rather than tuning knobs.

12. Scaling: partitioning, sharding, pooling, caching

When one database stops being enough, four moves are available, and they should be tried in this order: split a table inside one machine, split the data across machines, stop wasting the machine you have on connections, and put a cache in front.

Partitioning splits one table into several physical pieces inside a single database. Sharding splits the data across independent database instances.

They sound alike and they are not remotely the same purchase. The table below is the difference; the row that decides everything is the last one.

2PC there is two-phase commit, the protocol that makes one transaction span several databases. It is priced in full later in this section.

Partition for manageability first; shard only when a single primary cannot hold the write throughput or the working set. Partitioning solves most of what people reach for sharding to solve, at a fraction of the cost.

What partitioning actually buys

Dropping last year’s data, two ways:

• DETACH PARTITION — instant, and it takes no lock on the rest of the table.
• DELETE ... WHERE ts < ... — hours of work, plus bloat, plus a vacuum backlog behind it.

That one comparison justifies range partitioning on time for any append-heavy table.

The catch is pruning. Pruning is the planner’s ability to skip partitions that cannot contain a match, and it only happens if the partition key appears in the predicate. A query without it touches every partition.

There is a second cost that grows with the partition count: planning time. Instead of staying flat, it rises with the number of partitions the planner must consider — illustratively, sub-millisecond at a handful of partitions, rising to the order of a hundred milliseconds at 500.

Those two planning-time figures are order-of-magnitude illustrations, not measurements. The real numbers depend on the Postgres version and the plan shape, so measure them on your own schema before quoting them. The practical rule stands regardless: keep partition counts in the low hundreds.

Choosing a shard key

The shard key is the column whose value decides which machine a row lives on, and it is the single least reversible decision in this chapter. It must have three properties, and each failure has a price. The third property is the one people miss:

1. High cardinality. The number of distinct values is a hard ceiling on how many shards you can ever have. A boolean shard key gives you two shards, forever.
2. Uniform access, not just uniform storage. customer_id is perfectly uniform in rows and wildly non-uniform in traffic — every customer has a row, and a handful of them generate most of the requests.
3. Present in the query predicate. If a query does not name the shard key, it becomes a scatter-gather: sent to every shard and merged. Your p99 latency is then the maximum over N shards rather than the mean, which is a much worse number.

Pricing a hot shard

Property 2 has arithmetic behind it. Take 16 shards hashed on tenant_id, with realistic power-law traffic — a handful of tenants generate most of the requests while the long tail generates almost none. Say the largest tenant alone is 25% of requests.

That whale’s traffic all lands on one shard. That shard also gets its even 1-in-16 share of the other 75%:

hot shard    =  25%  +  (1/16) x 75%  =  25% + 4.69%  =  29.7%
average      =  100% / 16                             =   6.25%
ratio        =  29.7 / 6.25                           ->  hot shard is 4.75x average

You must provision every shard for the maximum, because you cannot buy 15 small machines and one large one and keep them balanced as traffic shifts. So you pay for 16 shards at 4.75× the size uniform load would need.

Two fixes:

• A composite (tenant_id, bucket) key that fans a whale across b shards. This forces scatter-gather, but only for those tenants.
• A routing table that pins whales to dedicated shards.

Hash vs range, and why resharding hurts

Two ways exist to map a key to a shard, and the choice determines both which queries stay cheap and what it costs to add a machine later.

Hash gives uniformity by construction, but it scatter-gathers every range query, because adjacent keys hash to unrelated shards.

Range preserves range scans and lets you split a hot range in half. But a timestamp key puts 100% of writes on the last shard, since “now” is always in the last range.

Then there is what happens when you add a machine. The naive-modulo number is brutal:

mod-N resharding, 16 -> 17 nodes:   hash(k) mod 16 and mod 17 agree for ~1/17 of keys
                                    ->  ~94% of all rows must move   (1 - 1/17 = 0.941)
consistent hashing, 16 -> 17:       ->    5.9% move                  (1/17 = 0.059)

Why mod N moves nearly everything: changing the divisor changes the remainder for almost every key. Only the keys whose remainder happens to be unchanged stay put, and that is about 1 in 17 of them.

Two terms:

• Consistent hashing places both keys and nodes on a ring and assigns each key to the next node clockwise. Adding a node only steals the arc immediately before it, so only the keys in that arc move.
• Virtual nodes give each physical machine many small arcs instead of one big one, so the arcs come out evenly sized.

Consistent hashing with virtual nodes exists entirely to turn (N-1)/N into 1/N.

The alternative needs no cleverness at all: fix a large number of logical shards up front — say 1,024 — map them to physical nodes with a lookup table, and rebalance by moving whole logical shards. Nothing is ever rehashed.

The migration is where the weeks go

Whatever scheme you pick, changing it later is a five-step process, and every step has a correctness window:

1. Dual-write to both the old and new topologies.
2. Backfill history, throttled, over days.
3. Verify by range checksums.
4. Flip reads a slice at a time.
5. Stop dual-writes.

Choose the shard count so it splits by powers of two, and choose it before launch. It has the worst retrofit cost in this chapter.

The five things sharding takes away

Once data is split across machines, five operations that were free inside one database stop being free. Read the second row carefully — it is the one that turns an outage into a data-loss incident.

Six terms from that table, plainly:

• A dimension table is a small lookup table — customers, products, currencies — as against the large fact table of Storage what a query actually reads off disk. Small enough to copy to every shard, which is what makes the first row’s fix work.
• Two-phase commit (2PC) is the protocol where a coordinator first asks every participant to prepare — promise it can commit — and then tells them all to commit. The promise is what makes it atomic, and the promise is also what strands locks when the coordinator dies between the two phases.
• A saga is the alternative to 2PC: a sequence of local transactions, each with a compensating transaction that undoes it. Failure is handled by rolling forward with an apology rather than rolling back atomically.
• Idempotent means running a step twice has the same effect as running it once. That is what makes retrying a saga step safe.
• HyperLogLog is a sketch that estimates distinct counts in a few kilobytes and can be merged across shards. An exact COUNT(DISTINCT) cannot be merged, because merging would mean shipping every value to one place.
• Snowflake is the third id scheme in that table, alongside UUIDv7 and ULID (universally unique lexicographically sortable identifier). It is a 64-bit id built from a timestamp, a machine number and a per-millisecond counter, so ids are unique across machines without coordination and still sort by creation time.

The assumption, and what it costs when it is wrong. Sharding assumes the workload decomposes: that almost every query names the shard key, and that almost every transaction touches one shard. That is what buys linear capacity, and the whole table above is the invoice for queries that break it. When the assumption holds you get a machine’s worth of throughput per machine; when it does not, every query is a scatter-gather whose latency is the slowest shard, every transaction needs 2PC or a saga, and operations that were one line of SQL become distributed systems you now maintain. Check the assumption against your access patterns before the shard key is chosen, because it is the one decision in this chapter you cannot revise cheaply.

Connection pooling matters more than people expect

Connection pooling means keeping a small set of database connections and lending them to application requests rather than opening one per request. Postgres in particular punishes the alternative, and the punishment gets worse exactly as you scale the app tier.

Postgres forks an OS process per connection. That is the root of everything below, and it is a Postgres-specific fact — MySQL uses a thread per connection, which is cheaper but does not remove the problem.

Each Postgres backend costs two things:

• Memory: ~5-10 MB of private memory, plus up to work_mem per sort or hash node in its plan — not per connection, per node.
• Shared-structure work: snapshot construction and lock-table scans walk ProcArray, the shared array of every live backend. So per-transaction overhead grows with the total connection count, idle connections included.

Throughput therefore peaks near 2-3× the core count in active connections, and then declines. Work it out on a real machine:

16-core NVMe box
  optimal active connections   ~= (16 x 2) + 2  =  34        (the classic pool-size rule)
  20 app pods x 20-conn pools  =  400 connections
    400 backends x 8 MB        =  3.2 GB before a single query runs
    throughput                 =  well below the same workload through a 34-conn pool
                                  (the direction is the mechanism above; the size of
                                   the drop is workload-specific -- measure it)

400 against an optimum of 34, and nobody configured anything wrong — each pod’s 20-connection pool is perfectly reasonable in isolation.

Adding application replicas multiplies connections while the database’s optimal connection count stays fixed. So scaling the app tier degrades the database.

Which pgbouncer mode, and what it breaks

A pooler fixes the arithmetic above for free. pgbouncer offers three modes and only one is worth having:

What transaction mode breaks is exactly the set of things ORMs do silently — an ORM being an object-relational mapper, the library that turns objects into SQL. Namely: SET, advisory locks, LISTEN/NOTIFY, temp tables, and cursors held outside a transaction. Every one of those assumes your next statement lands on the same server connection, and in transaction mode it does not.

The classic incident: a multi-tenant app runs SET search_path = tenant_a at connection time. The transaction ends, the pooler hands that server connection to the next request, and tenant B reads tenant A’s schema.

The fix is to pass the tenant per query, and then to enforce it with row-level security — the Postgres feature that attaches a mandatory filter to every query against a table — so the tenant boundary is not made of application code.

The assumption, and what it costs when it is wrong. A transaction-mode pooler assumes a connection means nothing beyond the transaction currently running on it — no session state, no SET, no temp table, no open cursor. Applications that respect that assumption get the database’s peak throughput from a 34-connection pool; applications that quietly violate it get correctness bugs like the tenant leak above rather than error messages, because the pooler cannot tell a stateful session apart from a stateless one.

Caching layers and invalidation

A cache trades staleness for latency, and every strategy below differs only in how it handles the moment the underlying data changes.

The cheapest cache is the one you already have. A page in shared_buffers costs ~0.1 microseconds; the same page from NVMe costs ~100 microseconds. That is a 1,000× gap, and no application cache can beat it — so size the buffer pool right before adding anything in front of it.

The two engines want opposite answers here, and swapping them is a common and expensive mistake:

• Postgres shared_buffers at ~25% of RAM. Postgres reads through the OS page cache, so a larger setting mostly double-buffers — the same page held twice, once by Postgres and once by the kernel.
• InnoDB innodb_buffer_pool_size at 70-80% of RAM. InnoDB uses O_DIRECT, the flag that bypasses the OS page cache, so there is no double-buffering to avoid.

Past that, the four caching strategies. They differ only in what happens at the moment the underlying data changes, which is the Failure mode column:

Three of those names need one line each. TTL is time-to-live, the expiry stamped on a cache entry. Write-through writes the database and the cache together. Write-invalidate writes the database and deletes the cache entry, letting the next reader repopulate it.

Write-invalidate is where the race lives. Trace it with a reader on the left and a writer on the right, time running downward:

 Reader                                    Writer
 GET key -> miss
 SELECT ... FROM db -> v1
                                           UPDATE ... -> v2
                                           DELETE cache key      (nothing there yet)
 SET key = v1
 -- the cache now holds v1 forever, and nothing will invalidate it again

The reader’s SET lands after the writer’s DELETE. The invalidation therefore deleted nothing — the key was not there yet — and then the stale value arrived and stayed. Nothing will ever invalidate it again.

Three mitigations:

• A delayed second delete, issued a short time after the first.
• Compare-and-set on a version stamp: write the cache only if the stamp is still what you read.
• Versioned keys, which make the race unrepresentable rather than unlikely.

Cache stampede is the other race, and it is the one that takes the database down. A hot key expires; 5,000 concurrent requests all miss; all 5,000 hit the 34-connection pool from the previous subsection at once; everything queues; and the database’s throughput falls while load rises.

Three fixes:

• Single-flight per key — one request recomputes while the rest wait on its result.
• Probabilistic early expiry — each reader independently decides, with rising probability as expiry approaches, to refresh early, so the refreshes spread out.
• Never expire hot keys; refresh them in the background instead.

The assumption, and what it costs when it is wrong. A cache is a bet that the same data is read many times between writes; the hit rate is the bet’s payoff and the TTL is the staleness you agreed to pay for it. Two workloads break it. Write-heavy data invalidates faster than it is read, so the cache costs an extra round trip and returns nothing. And uniformly random access has no hot set, so the hit rate collapses toward the fraction of the data you can afford to keep resident — which is why “add a cache” fails silently in exactly the cases where the database was already doing random I/O.

13. CAP, and the framing that is actually useful

The CAP theorem is short, widely quoted, and reliably gotten wrong in four specific ways — and there is a reframing (PACELC) that applies to the 99.99% of the time when nothing is broken.

CAP, precisely

In an asynchronous network a distributed system cannot simultaneously provide all three of:

• C — linearizability: every read returns the most recent completed write, as if there were only one copy of the data.
• A — total availability: every request to a non-failing node returns a non-error response.
• P — partition tolerance: the system keeps working when arbitrary messages between nodes are lost.

An asynchronous network is one with no bound on message delay, so a node can never distinguish a slow peer from a dead one. That impossibility is what the whole theorem rests on.

Four things people get wrong

Any one of these costs you the question.

1. You do not “pick 2 of 3.” Partitions are imposed by the physical world; you do not choose whether to have them. What you actually pick is what happens during one: refuse service on the minority side (CP), or answer with possibly-stale data and reconcile later (AP).

The minority side is the group holding fewer than half the nodes, which therefore cannot form a quorum. A quorum is a majority, and the reason a majority is the magic number is this: any two majorities of the same set must share at least one member, so a value agreed by one majority is visible to the next.

2. The C in CAP is linearizability; the C in ACID is constraint satisfaction. Same letter, unrelated concepts.

3. The A in CAP is total availability — an all-or-nothing theoretical property, not “99.95% uptime.”

4. A single-node Postgres is not “CA.” It is not a distributed system at all, so the theorem says nothing about it.

PACELC: the reframing that covers the other 99.99%

PACELC: if there is a Partition, choose A or C; Else — in normal operation — choose Latency or Consistency.

The diagram is that sentence as a decision: the left branch fires rarely; the right branch fires on every single request.

flowchart TD
    Q{"Network partitioned?"} -->|"yes · rare"| PA{"A or C?"}
    Q -->|"no · 99.99% of the time"| EL{"L or C?"}
    PA -->|A| A1["Answer from the reachable side<br/>reconcile later"]
    PA -->|C| C1["Refuse on the minority side"]
    EL -->|L| L1["Local or replica read<br/>stale by the replication lag"]
    EL -->|C| C2["Quorum or leader read<br/>pay the round trip every request"]
    style EL fill:#2d6a4f,color:#fff
    style Q fill:#40916c,color:#fff

The diagram’s left branch is the CAP conversation and the right branch is the one you actually live in: read locally and be stale by the replication lag of Scaling replication, or read from a quorum or the leader and pay a round trip on every single request.

Partitions are rare; the latency/consistency trade is paid on every single request. You spend 99.99% of your time in the E branch and 100% of the average CAP conversation in the P branch — which is exactly backwards.

The table below classifies six real systems on both branches. Read the E column first, since that is the one you feel every day, and note that the last column is the observable consequence rather than the label.

The Cassandra rows use three letters: R is how many replicas a read waits for, W is how many a write waits for, and RF (replication factor) is how many copies exist in total.

R + W > RF forces the set of replicas a read touches and the set a write touched to overlap by at least one — so the read is guaranteed to see the write. That is the quorum argument from above, applied per query instead of per cluster. With R = W = 1 and RF = 3, 1 + 1 = 2 is not greater than 3, so the two sets can miss each other entirely, and the read may be stale.

The assumption, and what it costs when it is wrong. Every row in that table is a system that assumed a workload. The EL rows assume readers tolerate the replication lag, and they buy a local read at memory speed; the EC rows assume the data is worth a round trip on every request, and they buy a read that cannot be stale. Run a balance check on an EL system and you ship a wrong number; run a view counter on an EC system and you pay a consensus round trip a hundred thousand times a second for a number nobody verifies. The mismatch is not a bug you can tune away, because it is the property the system was built to provide.

Two questions, in this order: “which side of the E branch is this?” — you pay it every request, so it usually decides the architecture — and “during a partition, is a stale answer worse than no answer?”, which is a product question, not an engineering one. Bank balance: no answer. View counter: stale answer, obviously.

Cheat sheet

Every row below is a symptom you can observe, the mechanism this chapter derived for it, and the fix that follows from the mechanism. Use it in the middle column direction: if you cannot state the mechanism from memory, go back to the section that derives it.

Next: the system design track, which starts at 03 — Interview Framework and spends these results rather than re-deriving them.