Database Fundamentals for System Design

TL;DR: A relational database is a SQL engine on top of a storage engine that uses B-tree indexes, a write-ahead log for durability, and MVCC for isolation. Every index speeds one query and slows every write. Stronger isolation prevents more anomalies but aborts more transactions. Postgres defaults to Read Committed, uses 8 KB pages^[1], and caps at 100 connections^[2] without a pooler. If you understand these three tensions (reads vs writes, isolation vs throughput, connections vs memory), you can predict most production failures from first principles.

Learning Objectives#

After this module, you will be able to:

• Explain ACID with concrete mechanisms (WAL for durability, MVCC for isolation)
• Design composite indexes that serve your queries and recognize indexes that hurt
• Read an EXPLAIN ANALYZE plan and identify where time is actually spent
• Distinguish isolation levels by the anomalies they permit (dirty read, phantom, write skew)
• Decide when to normalize (OLTP) vs denormalize (high-read feeds)
• Explain why connection pooling is mandatory in production Postgres

Intuition#

Think of a database as a library with a very strict librarian. The librarian keeps a card catalog (indexes) so you can find any book in seconds instead of scanning every shelf. She keeps a logbook (the write-ahead log) where she writes down every change before making it, so if the building loses power, she can replay the logbook and nothing is lost. And she has a rule: two people can read the same book at the same time, but if someone is rewriting a page, other readers still see the old version until the rewrite is finished (MVCC).

Every superpower costs something. The card catalog takes up space and must be updated every time a book moves. The logbook must be flushed to permanent storage before she can say "done," which takes milliseconds. And keeping old page versions around means someone has to clean them up eventually (VACUUM). Your job as a system designer is to understand these costs so you spend them on the right things.

Theory#

ACID and the write-ahead log#

ACID is the guarantee contract a transaction provides^[3]:

• Atomicity: all or nothing. If any statement fails, the entire transaction rolls back.
• Consistency: constraints (foreign keys, CHECK, unique) hold after every commit.
• Isolation: concurrent transactions do not see each other's partial work.
• Durability: committed data survives crashes.

Atomicity and durability share one mechanism: the write-ahead log (WAL). Every change is appended to the WAL and fsynced to disk before the transaction is told "commit OK."^[4] The actual data pages are updated later at a checkpoint. If the database crashes, recovery replays the WAL from the last checkpoint. No ad-hoc repair needed.

Durability comes from fsync on the WAL at commit time; data files are updated lazily at checkpoints, so crash recovery only needs to replay the WAL.

Isolation levels and anomalies#

SQL defines four isolation levels by which anomalies they permit^[3:1]:

Postgres defaults to Read Committed. At this level, each statement sees a fresh snapshot. You can read a row, another transaction updates it and commits, and your next read sees the new value. This is fine for most web apps but dangerous for invariant checks.

Write skew is the subtle one. Two transactions each read a disjoint view, each writes based on what it read, both commit, and the combined result violates an invariant neither individually broke. Example: two on-call doctors each check "is someone else on call?", see yes, and both go off-call. Now nobody is on-call.^[5] Snapshot Isolation (Postgres Repeatable Read) permits this. Only Serializable prevents it.

Postgres Serializable uses Serializable Snapshot Isolation (SSI): it detects read-write dependency cycles at runtime and aborts one transaction with SQLSTATE 40001.^[3:2][6] Your application must retry on that error.

Indexes: B-tree, composite, covering#

An index is an auxiliary data structure that converts full-table scans into O(log n) lookups.^[7] Postgres defaults to B-tree (Lehman-Yao variant with right-links for concurrent search).^[8]

Data Structures for Systems covers B-tree internals. The key facts for database design:

• Postgres pages are 8 KB.^[1:1] Each internal page holds hundreds of (key, child-pointer) pairs, so tree height stays at 3 to 5 levels even for billions of rows.^[9]
• Leaf pages are doubly linked for ordered range scans in both directions.^[8:1]
• An index lookup touches one page per tree level: ~3 to 5 random reads, or ~10 us from memory, ~10 ms from cold disk.

A B-tree with fan-out in the hundreds keeps billions of rows within 3 to 5 levels; doubly-linked leaf pages support efficient range scans.

Composite index ordering. An index on (a, b) is sorted by a first, then b. Queries filtering on a alone or on a AND b use the index. Queries filtering on b alone cannot. Think phonebook: sorted by surname then first name. You can find all Smiths fast, but not all Johns.^[10]

Covering indexes. If every column the query needs is in the index, Postgres satisfies the query without visiting the heap (Index Only Scan).^[7:1] Use CREATE INDEX ... INCLUDE (col) to add payload columns without changing sort order.

Partial indexes. CREATE INDEX ... WHERE status = 'pending' indexes only matching rows. If 1% of orders are pending, this index is 100x smaller than a full index and still serves the hot query.^[7:2]

The cost of indexes. Every index must be updated on every insert and on updates that touch indexed columns. Uber documented that updating one field on a table with 12 indexes required 13 physical updates (new tuple + 12 index pointer updates), each WAL-logged.^[11] This write amplification drove their 2016 migration from Postgres to MySQL.

Query execution and EXPLAIN#

A SQL string passes through three stages: parser (builds an AST), planner (picks the cheapest plan using table statistics from pg_statistic), and executor (runs the plan).^[13]

The planner picks Seq Scan for low-selectivity predicates and Index Scan for high-selectivity ones; Bitmap Heap Scan handles the middle ground by sorting random index hits into sequential heap order.

Reading EXPLAIN ANALYZE output:

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE user_id = 42 ORDER BY created_at DESC LIMIT 20;

Each node prints (cost=startup..total rows=N width=B) and, under ANALYZE, (actual time=start..total rows=N loops=M). A big divergence between estimated and actual rows means stale statistics. Run ANALYZE on the table.^[13:1]

The BUFFERS option shows shared hit (page cache) vs shared read (disk). If shared read dominates, your working set exceeds RAM. See OS Essentials for how the page cache works.

MVCC: readers never block writers#

Multi-Version Concurrency Control keeps multiple versions of each row so readers see a consistent snapshot without locking writers.^[14]

Postgres implementation: Every row has xmin (inserting transaction ID) and xmax (deleting/updating transaction ID). On UPDATE, Postgres writes a new tuple and marks the old one's xmax. The old version stays until VACUUM reclaims it.^[14:1][11:1] Each transaction gets a snapshot: a tuple is visible if its xmin committed before the snapshot and its xmax either did not commit or committed after.

Postgres MVCC writes a new tuple for every UPDATE; readers see the version whose xmin committed before their snapshot, never blocking writers.

The VACUUM cost. Dead tuples accumulate until VACUUM reclaims them. If VACUUM falls behind (long-running transactions hold back the oldest snapshot), tables and indexes bloat indefinitely. Notion's 2021 sharding was triggered precisely by VACUUM stalls threatening transaction-ID wraparound at the 2-billion XID boundary.^[15]

InnoDB's approach: Old versions live in the undo log (rollback segment) rather than the main table. The heap holds only the latest version, which is cheaper to vacuum but slower to reconstruct old snapshots.^[11:2]

Normalization vs denormalization#

Normalization stores every fact once, in the table where the key for that fact lives. A 3NF schema minimizes write anomalies and storage.

Denormalization duplicates facts so reads skip joins. A social feed is the classic example: on post creation, the post ID fans out into each follower's precomputed timeline in Redis, replacing a JOIN posts ON followers at read time with an O(1) list lookup.

Rule of thumb: Normalize for your source of truth. Denormalize for your read path. Connect them with a replication pipe (CDC, event stream). Storage Engines picks this up and shows how production databases implement both shapes.

Connection pooling#

Postgres uses a process-per-connection model. Each backend costs 5 to 10 MB of resident memory.^[2:1] The default max_connections is 100.^[2:2] A web app with 20 instances opening 50 connections each needs 1,000 connections, which is 10x the default and would consume 5 to 10 GB of RAM just for backend processes.

PgBouncer multiplexes thousands of application connections onto a small pool of real Postgres backends.^[16] In transaction pooling mode, a backend is assigned for the duration of one transaction and returned to the pool immediately after. This is the production default for high-concurrency web apps.

• default_pool_size: 20 server connections per user/database pair^[16:1]
• max_client_conn: raise to 10,000+ for production^[16:2]
• Figma added PgBouncer specifically to cap the thousands of connections their application was opening.^[17]

Real-World Example#

Figma: from one Postgres instance to horizontal sharding.

In 2020, Figma ran on a single r5.12xlarge Postgres RDS instance hitting 65% CPU at peak.^[17:1] Their database fleet grew ~100x between 2020 and 2024.^[18]

Phase 1: Vertical partitioning (2022). Groups of related tables ("Figma files," "Organizations") moved onto dedicated physical databases, each fronted by PgBouncer. They used Postgres logical replication for the migration, dropping indexes before the initial copy and rebuilding after to avoid slow one-row-at-a-time index updates.^[17:2] By October 2022, they had moved 50 tables with ~30 seconds of partial availability impact per migration.

Phase 2: Horizontal sharding (2023). A Go service called DBProxy sits between the application and PgBouncer, parses SQL into an AST, extracts the shard key (UserID, FileID, OrgID), and routes to the correct physical shard.^[18:1] They chose hash-based routing to avoid hotspots from auto-incrementing IDs. The first horizontally sharded table went live in September 2023 with 10 seconds of partial primary-availability impact and no replica impact.^[18:2]

Why this matters for fundamentals: Every decision in Figma's migration traces back to concepts in this chapter. They needed PgBouncer because of connection limits. They needed to understand index rebuild cost. They needed to reason about which tables are co-queried (normalization boundaries). They rejected CockroachDB and Vitess due to migration risk, choosing to stay on Postgres and shard at the application layer.^[18:3]

Design decisions#

The only decision in this chapter that presents two substitutable shapes for the same job is normalize versus denormalize. Full treatment in Normalization vs denormalization.

The other four decisions in this chapter are not alternatives you pick between. They are independent choices you make per-table, per-transaction, or per-query, and each is covered in full in its native section:

• Whether to add an index. See Indexes: B-tree, composite, covering. Always measure with EXPLAIN ANALYZE before and after.
• Which isolation level. See Isolation levels and anomalies. Use Serializable for money or inventory-critical invariants; Read Committed is Postgres's default for everything else.
• Whether an index should be covering (INCLUDE). See Indexes: B-tree, composite, covering. This is a refinement on "add an index," not a separate choice: add the INCLUDE columns only when EXPLAIN shows heap fetches on a known hot query.

Common Pitfalls#

Exercise#

Design Challenge: You run EXPLAIN ANALYZE on a query against a 10-million-row events table and see a Seq Scan taking 4.2 seconds. The query is SELECT * FROM events WHERE user_id = 123 AND created_at > '2026-01-01' ORDER BY created_at DESC LIMIT 50. What index would you add, and how do you verify it works?

CREATE INDEX idx_events_user_created ON events (user_id, created_at DESC);

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM events WHERE user_id = 123 AND created_at > '2026-01-01'
ORDER BY created_at DESC LIMIT 50;

CREATE INDEX idx_events_cover ON events (user_id, created_at DESC)
INCLUDE (event_type, payload);

Key Takeaways#

• ACID is four guarantees with concrete mechanisms: WAL for atomicity and durability, MVCC or locks for isolation, constraints for consistency.
• Every index speeds one query shape and slows every write. Measure with EXPLAIN ANALYZE before adding one.
• Postgres defaults to Read Committed. Understand write skew before choosing weaker or stronger isolation.
• MVCC gives non-blocking reads but requires VACUUM to reclaim dead tuples. Long transactions are the enemy.
• Normalize for your source of truth, denormalize for your read path. Connect them with replication.
• Connection pooling (PgBouncer in transaction mode) is mandatory for production Postgres. The default 100 connections is not enough for modern web apps.
• Use UUIDv7 over UUIDv4 for primary keys on write-heavy tables to preserve B-tree locality.

Further Reading#

• PostgreSQL Concurrency Control (Chapter 13) - the canonical reference on Postgres MVCC and isolation levels, including concrete SQL examples of write skew and SSI behavior.
• PostgreSQL Using EXPLAIN (14.1) - the authoritative guide to reading plan nodes, ANALYZE, and BUFFERS; essential before any index tuning.
• Use the Index, Luke (Markus Winand) - free book on SQL indexing; the "Concatenated Indexes" chapter explains composite index column order with the phonebook analogy.
• Designing Data-Intensive Applications, Ch. 3 and 7 - Kleppmann's treatment of storage engines and transactions; the reference text for this chapter's depth.
• Why Uber Switched from Postgres to MySQL - the clearest public explanation of write amplification from secondary index pointers; motivates careful index design.
• Notion: Sharding Postgres at Notion - 480 logical shards on 32 physical DBs, triggered by VACUUM stalls threatening transaction-ID wraparound.
• How Figma's Databases Team Lived to Tell the Scale - DBProxy, logical vs physical sharding, and hash-based routing on Postgres.
• Jepsen: PostgreSQL 12.3 - Kyle Kingsbury's isolation test that found a 9-year-old Serializable bug; a reminder to test, not trust.

Flashcards#

References#