Database Internals — Learning Map

Overview

This directory is the internals track of the DBMS section: how engines actually store, execute, replicate, and recover data, at the level of pages, latches, log records, and version chains. Interviewers use internals questions to separate candidates who have used databases from candidates who can diagnose and tune them (“why is this table bloated?”, “what limits our write throughput?”). Use this page as a map: pick the layer you are weak in, follow the links in order, and use the engine deep dives (PostgreSQL MVCC, InnoDB) as worked case studies that tie all three layers together.

The Three Layers

Every client-server DBMS decomposes into three cooperating layers. Storage owns bytes on disk, execution owns the path from SQL to those bytes, and replication owns moving the durable record elsewhere before or after commit.

flowchart TD
    Q["Client sends SQL"] --> P["Execution layer"]
    subgraph EX["Execution layer"]
        P["Parser, planner, optimizer"]
        PE["Executor: iterators, joins, scans"]
        P --> PE
    end
    PE --> S["Storage layer"]
    subgraph ST["Storage layer"]
        BP["Buffer pool + page cache"]
        IX["B+tree / LSM structures"]
        WAL["WAL + checkpoints + GC"]
    end
    WAL --> R["Replication + recovery layer"]
    subgraph RP["Replication and recovery"]
        RS["Redo streaming / logical replication"]
        CO["Consensus, failover, backups"]
    end

The layers are coupled at two seams. The WAL seam: the execution layer’s commits are only durable when the storage layer’s log reaches disk, and the replication layer ships exactly that log. The snapshot seam: the storage layer’s MVCC visibility rules define what concurrent execution and replica readback are allowed to see.

One Commit, Three Layers

Trace a single UPDATE through all three layers and every internals page becomes relevant at once:

sequenceDiagram
    participant C as Client
    participant E as Executor
    participant S as Storage
    participant R as Replica
    C->>E: UPDATE accounts SET bal = bal - 100 WHERE id = 7
    E->>S: Visibility check, row lock, write new version
    S->>S: Undo/redo record appended to the log
    S->>S: Commit: fsync WAL or redo log
    S-->>E: Commit acknowledged
    E-->>C: UPDATE 1
    S->>R: Log record shipped to standby
    R->>R: Replay in commit order, snapshot-safe

The executor never touches disk directly; it asks the storage layer for pages and tuples. The storage layer never decides what is visible; it serves the snapshot the execution layer’s isolation level demands. The replica never invents data; it applies the same durable log the primary needed for its own commit. Interview answers that walk this full path (“where does fsync happen?”, “when is the row visible on the standby?”) immediately outperform single-layer answers.

Health Metrics by Layer

Layer 1 — Storage (pages in this directory)

Layer 2 — Execution (pages in this directory)

Layer 3 — Concurrency and Recovery (pages in this directory)

Link Map to the Wider Book

The internals track does not live alone. These existing directories supply the concept-level pages that the internals pages assume, and they are the right cross-reference targets when you need background instead of depth.

Note: there is no dbms/storage-engines/ directory; engine comparisons live in ./engines.md (here) and ../../storage/advanced/storage-engines.md.

Suggested Reading Order

flowchart LR
    A["engines.md<br/>pick your engines"] --> B["storage-engine.md<br/>pages + pools"]
    B --> C["wal.md<br/>durability"]
    C --> D{"Which engine?"}
    D -->|Postgres| E["postgresql-mvcc-deep.md"]
    D -->|MySQL| F["mysql-innodb-internals.md"]
    E --> G["transaction-internals.md"]
    F --> G
    G --> H["advanced: mvcc-internals,<br/>mvcc-garbage-collection"]
    B --> I["lsm-trees.md + compaction.md<br/>if RocksDB-family"]
    A --> J["query-execution.md,<br/>join-algorithms.md"]

Interview Questions

1. A DBMS commit returns to the client. What has physically happened, and what has not? The WAL/redo record for the transaction has reached stable storage (fsync, possibly via group commit shared with other commits). The dirty data pages carrying the actual row changes are usually still only in the buffer pool; they are written later by a background writer/page cleaner, protected against torn writes (doublewrite, full-page images). The commit is durable because recovery can redo the log; nothing else is guaranteed at that instant.

2. Why do PostgreSQL and InnoDB garbage-collect differently, and what breaks in each? PostgreSQL writes old row versions into the heap itself, so reclaiming them requires scanning the heap — VACUUM. InnoDB keeps the latest version in the clustered index and old versions in undo logs, so a purge thread can reclaim them in commit order without a heap scan. Postgres’s failure mode is table/index bloat and wraparound pressure; InnoDB’s is an unbounded history list and purge lag when a long-running ReadView pins undo. Details: postgresql-mvcc-deep.md and mysql-innodb-internals.md.

3. What is the difference between a lock and a latch, and where does each live? Locks protect logical transactional objects (rows, tables) for the transaction’s duration and participate in deadlock detection. Latches protect in-memory physical structures (B+tree pages, buffer pool lists) for nanoseconds-to-microseconds under an operating discipline (crabbing, right-link rescue). Locks are the database’s semantics; latches are its implementation. See btree-latching.md.

4. Why can a sequential scan ruin OLTP latency on a naive-LRU buffer pool, and how do production engines fix it? A scan streams tens of thousands of one-touch pages through the pool, evicting the entire hot working set. InnoDB inserts new pages at the head of an old sublist (~3/8 of the pool) and promotes them to the young sublist (~5/8) only after a second access at least innodb_old_blocks_time (1000 ms) later; one-touch scan pages recycle out the old tail. PostgreSQL uses a clock-sweep with usage counts plus ring buffers for bulk scans.

5. You must make one database subsystem 10× faster. Which do you pick and why? Typically the buffer pool / page access path, because every logical read funnels through it and its costs (latch contention, eviction stalls, flush bandwidth) multiply into both reads and writes. But the correct engineering answer profiles first: if checkpoint age caps write throughput or purge lag caps read latency, the log/GC path dominates. The internals pages give you the numbers to argue either case.

Key Takeaways

• Internals questions are diagnosis questions: bloat, lag, stalls, and wraparound all have page-level explanations.
• The three layers (execution, storage, replication) meet at two seams: the WAL (durability) and the snapshot (visibility). Trace every incident through one of them.
• Every engine is a bet: PostgreSQL bets heap + VACUUM is simpler; InnoDB bets clustered pages + undo is cheaper at runtime; LSM engines bet sequential writes beat in-place updates. Know the bet, know the failure mode.
• Durability is a log property, not a page property: commit latency is bounded by log fsync, data pages are written lazily.
• Memory sizing questions (buffer pool, redo capacity, work_mem) are always worked-math questions — practice computing fill rates, ages, and amplification factors.
• Cross-link freely: the concept pages in ../advanced/, ../transactions/, and ../postgresql/ are the background; this directory is the depth.

References

• PostgreSQL Documentation — storage layout, MVCC, VACUUM and WAL chapters.
• MySQL Reference Manual — specifically the InnoDB chapters.
• CMU 15-445 Database Systems — buffer pools, B+trees, concurrency control, recovery, with buildable projects.
• CMU 15-721 Advanced Database Systems — modern execution engine and MVCC research, all lectures online.
• mysql-server source on GitHub — buf0lru.cc, log0log.cc, btr0btr.cc for the structures described here.
• P. O’Neil et al., “The Log-Structured Merge-Tree (LSM-Tree)”, Acta Informatica, 1996.
• C. Mohan et al., “ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking”, ACM TODS, 1992.

Cross-References

• Write-Ahead Logging (WAL) — the durability protocol every page here assumes.
• Storage Engine Internals — page and tuple layout for both engines.
• Transaction Internals — XIDs, ARIES, and the visibility rules behind MVCC.
• MVCC Internals (cross-engine) — version-chain structures beyond Postgres and InnoDB.
• MVCC Garbage Collection — VACUUM, purge, and undo retention compared across four engines.
• PostgreSQL Overview — feature-level Postgres architecture and VACUUM concepts.
• Database Engines — the engine selection matrix this map expands.