Almost every performance and correctness fact below follows from three physical facts, and the reference engine is PostgreSQL (InnoDB called out where it differs).
Three facts everything rests on
The engine reads and writes fixed-size pages (8 KB Postgres, 16 KB InnoDB), never rows. A 40-byte row costs one 8 KB read.
A random page costs ~4× a sequential one (random_page_cost 4.0 vs seq_page_cost 1.0; ~1.1 on NVMe).
Latency ladder network > disk > RAM > cache, each step 100×–1,000× faster than the one below.
Storage layout and B-trees
Row store keeps all columns of a row together (OLTP): a query touching 2 of 50 columns still pays 100% of the bytes; cache-line efficiency 12.5%.
Column store keeps one column per segment (OLAP): reads only the columns named, compresses ~10× better (dictionary, run-length, frame-of-reference), and enables vectorized (SIMD) execution. Cost: no row-at-a-time writes.
B-tree index = sorted copy of key + pointer (heap TID). Fanout ≈ page bytes ÷ entry bytes (~300 for an 8-byte key); depth = ceil(log_fanout(N)).
A 100M-row lookup is ~4 page reads (root + level 2 stay cached, so ~2 physical I/O) + 1 heap fetch. Growth is nearly free (1M→100M adds one level); wide keys are the real cost (100-byte key → fanout 63 → 5 levels + 5× memory).
Leaves are linked in key order, so one B-tree serves ORDER BY, >=, BETWEEN, LIKE 'abc%'.
InnoDB clusters the table on the PK (rows are the leaves): secondary lookup = 2 descents; a random UUIDv4 PK splits leaves (~50–60% fill, 1.6× bloat) — use UUIDv7/ULID.
Why an index goes unused
Low selectivity: past ~1% of rows, a sequential scan beats random index fetches — the index correctly loses. Physical correlation (CLUSTER) can flip this; Bitmap Heap Scan sorts TIDs to make heap reads sequential.
Function/cast on the column (lower(email), created_at::date, implicit type cast) → no seekable range. Fix: rewrite to a half-open range on the bare column, else index the expression. MySQL silently casts and runs 1,000× slower.
Leading-wildcard LIKE '%abc' has no range → use pg_trgm GIN or index reverse(col). LIKE 'abc%' needs text_pattern_ops under non-C collations.
Composite index: usable only while every preceding key column is pinned to one value (leftmost prefix). Order columns: equality first, then one range column, then output-only.
Covering index (INCLUDE) → index-only scan, ~184× fewer page accesses, but degrades to a normal scan when the visibility map is stale (autovacuum lag).
Index write cost
An INSERT with k indexes dirties 1 + k random pages; throughput ≈ 1/(1 + 0.55k) (first index costs ~35%).
Write amplification is bimodal: 2.4× steady state vs 246× right after a checkpoint (first touch writes a full 8 KB page image to WAL). That sawtooth gets misdiagnosed as a bad query.
HOT update (no indexed column changed + fits on same page) touches zero indexes. fillfactor = 85 on hot update tables buys ~3.3× less write I/O.
LSM tree (RocksDB, Cassandra) appends only: memtable → SSTable → compaction. Write amp ~42× but sequential; point reads ~1.09 with bloom filters; range scans and deletes (tombstones) are the weakness. “Don’t use Cassandra as a queue.”
Planner and joins
Cost hinges on cardinality estimation. The independence assumption multiplies selectivities of correlated predicates → underestimate (e.g. city='SF' AND state='CA' off by 960×). Fix with CREATE STATISTICS (dependencies, ndistinct) + ANALYZE.
A bad estimate does not degrade gracefully — it changes the plan shape.
Join
Cost
Requires
Nested loop
N_outer × inner_lookup
anything (only option for <, LIKE)
Hash join
scan both sides once
equality; build side in work_mem
Merge join
one pass, O(1) mem
equality + both inputs sorted
Crossover ≈ inner_scan_cost / index_lookup_cost (~5,000 outer rows). A cardinality error straddling it = 300 ms vs 10 min.
Read EXPLAIN (ANALYZE, BUFFERS): rows=N loops=M is a per-loop average (multiply). Index Cond narrows the seek; Filter discards after reading (Rows Removed by Filter = wasted I/O). Always use BUFFERS; it prints physical bytes.
Transactions and isolation
ACID: Atomicity (WAL + clog), Consistency (only your declared constraints), Isolation (MVCC snapshots + locks), Durability (WAL fsync before commit ack). synchronous_commit=off trades ~600 ms of committed data for 2–5× writes.
Anomaly
READ COMMITTED (PG default)
REPEATABLE READ (PG snapshot iso)
SERIALIZABLE
Dirty read
no (PG never)
no
no
Non-repeatable read
yes
no
no
Phantom
yes
no (stricter than standard)
no
Lost update
yes
serialization error
no
Write skew
yes
yes
no
Lost update fix: move the read inside the write (SET n = n + 1) or FOR UPDATE.
Write skew is the one SI misses (same rows read, different rows written). Fix: CHECK constraint, materialize the conflict, or SERIALIZABLE (SSI) with a retry loop.
SERIALIZABLE turns conflicts into aborts that grow superlinearly with contention; use it only for invariants spanning unwritten rows.
MVCC, replication, scaling
MVCC: an update writes a new version (xmin/xmax); readers never block writers. Bill = bloat (needs VACUUM), long transactions pin the horizon and block cleanup DB-wide, and XID wraparound. InnoDB inverts it (undo log → no bloat, but old readers slow down).
Deadlock = cycle in the wait-for graph. Postgres detects only after deadlock_timeout (1 s), so deadlocks show as latency spikes. Prevent with consistent lock order + short transactions; retry on 40P01.
Replica lag is a correctness bug, not staleness: a read-after-write from a lagging replica feeds the next write → lost update. Fix with sticky-primary window or LSN tokens; alert on p99/max, never mean.
Synchronous replication adds RTT + remote fsync per commit (~4× write latency cross-AZ, ~13 writes/s cross-region — not viable on OLTP). One sync standby lowers availability; use ANY 1 (r1, r2).
Partition before you shard (sharding kills cross-piece transactions/joins, is irreversible). Shard key needs high cardinality, uniform access, and presence in the predicate (else scatter-gather = slowest shard). Use consistent hashing / fixed logical shards, not mod N (moves ~94% of rows).
Connection pooling: Postgres forks a process per connection; throughput peaks near 2 × cores active. pgbouncer transaction mode (breaks SET, temp tables, session state).
CAP = choose A or C only during a partition. PACELC: else (99.99% of the time) choose Latency or Consistency — the trade you pay every request.
Want the full picture? The lesson has the derivations, worked examples, and diagrams this card compresses into bullets. Read the full lesson →