Buffer pools, page layouts, row and column stores

Why it matters

Every query eventually reads pages. Whether a scan reads 40 GB or 2 GB, and whether those bytes come from memory or storage, is decided here. Buffer-pool behavior also explains everyday puzzles: why the first run of a query is slow, and why one large report can evict everyone else's working set.

Core ideas

Pages and slotted layout. Tables live in files divided into fixed-size pages (8 KB by default in PostgreSQL, 4 KB by default in SQLite). A slotted page has a header, an array of slots pointing to tuples, and tuples packed from the end of the page, with free space between. A record ID is (page, slot), so a tuple can move within its page without changing its ID. Large values go to overflow pages or side tables (TOAST in PostgreSQL).

Buffer pool. A fixed array of frames plus a page table from page ID to frame. Callers pin a page while using it; only unpinned pages can be evicted, and a dirty page may be written back only after the log records covering it are durable. Plain LRU suffers from sequential flooding, where one large scan evicts the hot pages; clock, LRU-K, ARC and small ring buffers for bulk scans are common answers. A DBMS prefers its own pool to mmap because it must control eviction and write-back order, prefetch using knowledge of the plan, and handle I/O errors explicitly; with mmap the kernel decides when dirty pages reach storage and reports I/O errors as signals.

Row versus column. A row store keeps a tuple's attributes together, so one page read fetches a whole record: good for OLTP point reads and updates. A column store keeps each attribute contiguous: a query touching 2 of 50 columns reads about 2/50 of the data, values of one type compress well, and execution can loop over arrays of one column. PAX keeps a page's rows together but groups each column inside the page; Parquet's row groups and column chunks apply the same idea at file scale, with per-chunk statistics that let readers skip data.

A back-of-envelope check: 100 million rows with 50 eight-byte columns is about 40 GB stored by row. Summing one column filtered on another reads about 1.6 GB stored by column, before compression.

Compression. Dictionary encoding replaces values with small integer codes; run-length encoding stores (value, count) pairs and shines on sorted columns; bit-packing stores small integers in few bits; delta encoding stores differences between neighboring values. Column engines often evaluate predicates directly on encoded data and build full tuples as late as possible.

Common misconceptions

• "The OS page cache makes a buffer pool unnecessary." The DBMS needs control over eviction and flush order for correctness and predictable performance.
• "LRU is the best policy." Sequential scans defeat it; real systems add scan resistance.
• "Column stores are always faster." Single-row inserts and updates are expensive, and rebuilding wide rows costs work; they win on scans of few columns.
• "Compression always costs speed." For scans it often saves time by cutting I/O and memory traffic, especially when encoded data can be filtered directly.

How to approach it

Draw a slotted page and walk through insert, delete and compaction. Then build or read a buffer pool; BusTub's buffer pool project exercises pinning, replacement and concurrency. Finally, estimate bytes scanned for the same query in row and column layouts and connect the result to query execution.