Cover

CMU Database Group · 1:22:27 · Watch on YouTube

Summary

Third lecture of CMU 15-445/645 (Fall 2024), and the first one that goes inside the database engine. It builds the bottom of the storage stack from the hardware upward: why a disk-oriented DBMS exists, how the storage hierarchy and the sequential-vs-random access gap dictate design, how databases are laid out as files of fixed-size pages, how heap files, page directories, and free space maps locate a page, and how tuples are laid out inside a page with the slotted-page design. A live Postgres demo exposes the on-disk files, the free space map, and VACUUM, contrasted with SQL Server's per-page metadata. The lecture closes with a flash talk by Heikki, a Postgres committer and Neon co-founder, on Neon's serverless Postgres architecture that separates compute from a Rust storage system driven by the write-ahead log.

Classification: university lecture (educational) with an embedded conference-style flash talk.

flowchart TD
    A[01 Roadmap & system layers] --> B[02 Storage hierarchy]
    B --> C[03 Sequential vs random access]
    C --> D[04 Anatomy of a disk-oriented DBMS]
    D --> E[05 Files & storage manager]
    E --> F[06 Page contents & page IDs]
    F --> G[07 Page sizes & trade-offs]
    G --> H[08 Heap files, page directory, FSM]
    H --> I[09 Postgres & SQL Server demo]
    I --> J[10 Page layout & slotted pages]
    J --> K[11 Flash talk: Neon]

Topics

  1. Course Roadmap and System Layers — 0:05
  2. Storage Hierarchy and Disk-Oriented Design — 4:54
  3. Sequential vs Random Access and Design Goals — 14:19
  4. Anatomy of a Disk-Oriented DBMS — 19:49
  5. Database Files and the Storage Manager — 24:40
  6. Page Contents, Self-Containment, and Page IDs — 29:58
  7. The Three Notions of a Page and Page-Size Trade-offs — 36:39
  8. Heap Files, the Page Directory, and the Free Space Map — 42:42
  9. Demo: Postgres Free Space Map and SQL Server Page Metadata — 48:35
  10. Page Layout: Headers, Tuple Storage, and Slotted Pages — 59:44
  11. Flash Talk: Neon, Serverless Postgres — 1:08:55

Key takeaways

  • A database is nothing but ordinary files on an off-the-shelf file system (EXT4, XFS); the DBMS layers a storage manager, fixed-size pages, and a page directory on top of them, and only high-end systems such as Oracle ASM bypass the OS file system to do direct I/O on raw blocks (19:49, 25:59, 26:20).
  • Random access is orders of magnitude slower than sequential access on HDDs and still slower on SSDs, which is why MySQL writes dirty pages twice — sequentially to a side buffer to commit fast, then randomly to the real pages in the background (14:19, 15:55, 16:39, 16:57).
  • "Page" means three different things: the hardware page (4 KB, the largest atomic all-or-nothing write), the OS page (4 KB, or 2 MB/1 GB huge pages), and the database page — 4 KB in SQLite/RocksDB/WiredTiger, 8 KB in Postgres and SQL Server, 16 KB in MySQL, per-table in DB2 (36:39, 37:29, 39:07).
  • Page size is a no-free-lunch trade-off: big pages win on sequential read-heavy scans but force rewriting the whole page for a 1 KB update; small pages win on many small writes (41:11, 41:41, 42:16).
  • The Postgres demo showed the free space map is intentionally allowed to be stale — it reported all zeros for 7 pages until VACUUM corrected it — and that inserted tuples landed back in page 0 rather than at the end, a concrete demonstration that the relational model is unordered (50:32, 52:49, 53:43, 55:03, 55:21).
  • The slotted page — slot array growing forward, tuple data growing backward until they meet — is how essentially every row store works; in-page compaction after deletes is cheap in CPU terms but holds the page latch longer, so SQL Server and Oracle do it while Postgres does not (1:04:23, 1:05:03, 1:07:52, 1:08:22).
  • Neon separates Postgres compute from a Rust storage system fed by the intercepted WAL: safekeepers reach Paxos consensus (commit acknowledged after ≥3 receive the WAL) and page servers reconstruct any page at any LSN — which makes page eviction a no-op, eliminates checkpointing and startup WAL recovery, and enables branching and time-travel queries, at the cost of being single-writer (1:10:40, 1:11:02, 1:12:39, 1:12:57, 1:13:38, 1:14:46).
  • Auto-scaling memory remains an open problem for Neon: CPU shortage only slows things down and disk can be provisioned, but deciding when more memory is worth it requires predicting what plan the optimizer would choose (hash join vs merge join) with more memory available (1:15:39, 1:15:55, 1:17:28, 1:17:49).