Unit 4.3 · about 4 h
259 / 324Pages, buffer pools and storage layouts
Assume Programming's layout-alignment-locality unit. Database layout adds page indirection, eviction and write ordering to CPU locality; those mechanisms explain work that SQL syntax cannot show.
- explain
You can now
- Trace a record through page identifiers, slots and buffer frames.
- Explain pinning, dirty-page eviction and the distinction between transaction locks and internal latches.
- Choose row, column or log-structured layout for point updates, projections and scans.
Covers
- Pages, records, buffer pools and storage managers
- Row, column and log-structured layout trade-offs
Study, in this order
4 steps
- Lecture 3: Database Storage ICMU 15-445/645 - database and storage core
Sections 4 and 6-11: disk-oriented overview, files, pages, heap, page layout, record IDs and tuple layout, pp. 2-5
Depth · Do not adopt section 7's unconditional hardware-page atomic-write guarantee. Atomicity under power loss depends on the device and I/O contract, not the page's size alone.
- Lecture 4: Memory & Disk ManagementCMU 15-445/645 - database and storage core
Sections 2-5: Buffer Pool, OS versus DBMS, replacement policies, and Disk I/O and OS Cache, pp. 2-5
- Lectures 5 and 6: layoutsCMU 15-445/645 - database and storage core
Lecture 5 notes, sections 2-4, pp. 1-3; Lecture 6 notes, sections 1-2, pp. 1-2: workloads and storage models
Depth · Stop before Lecture 6's compression algorithms.
- PostgreSQL 18: Database Page LayoutPostgreSQL - EXPLAIN and transaction isolation lab
Section 66.6, Tables 66.2-66.3 and the item-identifier paragraphs; stop before 66.6.1
Focus on
- A page ID identifies stored data; a frame identifies a current memory copy. A slot can remain stable while its tuple moves within a page.
- A pin prevents eviction, not concurrent mutation. A latch protects the buffer manager's data structures; transaction isolation is a different job.
- A dirty victim needs successful writeback before reuse. If all frames are pinned, the manager must wait or reject rather than evict a live pointer.
- Row stores favor whole-record access; column stores can avoid unrelated columns; log layouts defer consolidation. None makes all workloads cheaper.
Reproduce closed-book
pin_count=1 and dirty=false; B has pin_count=0 and dirty=true. Request C. B is the only possible victim; write B successfully, remove its page-to-frame mapping, then read C and install its mapping. Repeat with both frames pinned: no victim is legal. Draw a slotted page whose slot keeps its index while its tuple moves during compaction. In the section PostgreSQL container run SHOW block_size; the tested PostgreSQL 18.6 build returned 8192 bytes. Use the reported value, not an assumed OS page size, to label the database-page drawing.Traps
- Treating an unpinned dirty page as immediately reusable. A failed writeback must not destroy its only current copy.
- Equating the DBMS buffer pool with the kernel page cache, or equating pinning with locking.
- Assuming a page-sized write is atomic across a power cut. Torn writes remain part of the failure model.
Practice
The section mini-project covers this: a page/frame trace with pin exhaustion and failed-writeback cases, plus a layout choice for the append-only store and its read workload.
Self-test
-
Why can a slot reference survive movement of tuple bytes within a page?
The slot is an indirection entry. Updating its offset preserves the page-and-slot reference. -
Why cannot C replace A in the two-frame trace?
A is pinned. A caller may still hold a pointer to its contents. -
Does selecting two columns from a wide row store read only those two columns from storage?
Not generally. The engine fetches pages containing whole tuples, although indexes or other access paths can change the work.
Completion criterion
Stop when
You draw both eviction traces without violating a pin or losing dirty data, and justify a layout for one point-update and one projection-heavy workload.
Mark passed, then open 4.4 Only mark this when you can do it without notes.Leads to
- 4.4 Hash indexes, B-trees, selectivity and range scans Build a search structure from these pages.
Resources for this unit
- CMU 15-445/645 - database and storage core Use Fall 2025 Lectures 1-9, 11-18 and 20-22 with their notes: relational model, SQL, storage, buffer pools, layouts, indexes, execution, planning, concurrency, MVCC, logging and recovery. Complete the matching SQL, Storage, Indexes and Filters, Transactions and Recovery homeworks before considering a BusTub project.
- PostgreSQL - EXPLAIN and transaction isolation lab Create one normalized schema, joins, an aggregation and a window query. Compare EXPLAIN ANALYZE before and after one justified index. In two sessions, reproduce one documented isolation anomaly and prevent it with a stated database or application invariant.
Also in this section
- Designing Data-Intensive Applications, 2nd edition - storage and transactions Read only the sections on data models and query languages, storage and retrieval, encoding and evolution, and transactions that answer a live design question from the CMU route. Write one comparison table covering layout, index, isolation and recovery trade-offs.
- Operating Systems: Three Easy Pieces - persistence and integrity Use Chapters 36, 39-45 to trace devices, filesystem structures, journaling, log-structured storage, flash and integrity. Apply the crash sequence to your own append-only store rather than repeating the SYS-1 file experiment.
- CMU 15-445 - one reduced BusTub project slice If a C++ database implementation is the chosen depth lane, complete Project 1 Buffer Pool Manager or Project 2 Database Index, not both during the first pass. Follow the course publication rules and keep code private. The blank-file append-only store remains the core checkpoint.
- Point-in-time joins Read Point-in-time joins and Retrieving features as of the event time. Separate event-time eligibility from actual feature availability; implement the predicates in SQL, not a Feast installation.
- CMU Lecture 19: Timestamp Ordering Concurrency Control Section 1 only, p. 1: timestamp order as a chosen serialization order. The section pool omits Lecture 19; this fills the timestamp-ordering vocabulary gap without assigning all of OCC.
- SQLite Write-Ahead Logging Sections 1 and 3 only: rollback journaling remains the default and WAL is an opt-in mode. Correct the dated SQLite statement in CMU Lecture 21; inspect the bundled engine without running concurrent WAL writers.