Pages, records and the buffer pool

Why it matters

Every query cost in a database comes down to how many pages it touches and whether they are already in memory. Knowing how rows are laid out on pages and how the buffer pool decides what stays cached explains why the first run of a query is slow and the second fast, why wide rows hurt, why SELECT * costs more than it looks, and why databases want so much RAM. It is also the foundation for indexes and recovery in the next lessons.

The idea

Disks and SSDs are read and written in blocks, so a database organises everything into fixed-size pages (8 KB in PostgreSQL, 16 KB in InnoDB). A table is a file of pages; each page holds many rows; the database reads and writes whole pages, never single rows.

Inside a page: the slotted layout

A record (row) holds a small header (null bitmap, transaction info for MVCC) followed by its column values; variable-length values store lengths or offsets. Values too large for a page (long text, big JSON) are moved to separate overflow storage with a pointer left in the row (PostgreSQL calls this TOAST). Deleted space is reclaimed by compacting the page; updates that no longer fit move the row elsewhere.

Files and organisation

A heap file stores rows in no particular order, appending where there is space; finding a row by value needs an index or a full scan. Some engines instead store the table itself as a B+ tree ordered by the primary key (a clustered or index-organised table, as InnoDB does), so primary-key lookups and range scans read rows directly in order.

The buffer pool

The buffer pool is a region of memory divided into frames, each holding one page. Every page access goes through the buffer manager: if the page is in the pool (a hit), use it; if not (a miss), choose a frame to evict, read the page from disk into it, then use it.

1. 1

   Page table

   A hash map from page id to frame tells the manager whether a page is cached.
2. 2

   Pin count

   A page in use by a query is pinned and cannot be evicted until unpinned.
3. 3

   Dirty flag

   A page modified in memory is dirty. Before it is evicted it must be written back, and, by the write-ahead rule in the recovery lesson, only after the log records describing its changes are on disk.
4. 4

   Replacement policy

   Choose an unpinned victim: LRU, the cheaper clock (second chance) approximation, or variants like LRU-K and 2Q that resist being flushed out by one large scan.
5. 5

   Background writer

   Writes dirty pages ahead of time so evictions rarely wait for a write.

A plain LRU policy is defeated by sequential flooding: one full table scan larger than the pool pushes out every frequently used page, each touched once. Databases counter it with scan-resistant policies, small ring buffers for large scans, and admission rules that do not promote a page until it is used twice.

Why not just use the operating system's cache?

The OS page cache does not know which pages a transaction depends on, when it is safe to write a dirty page (the write-ahead rule), or that a scan should not evict hot index pages. So most databases manage their own pool and either bypass the OS cache (O_DIRECT, as InnoDB typically does) or deliberately rely on it in part (PostgreSQL uses a moderate shared buffer plus the OS cache). Either way, sizing memory so the hot working set fits is the biggest single performance lever.

Trade-offs

Larger pages mean fewer I/Os for scans and less per-page overhead but more wasted reads for point lookups and more contention on hot pages. Row stores make transactional access cheap and analytical scans expensive; column stores do the reverse. A larger buffer pool raises the hit rate until the working set fits, after which more memory helps little; a pool too large for the machine causes swapping, which is far worse than misses.

In an interview

Tie query cost to pages: "The query reads 200,000 rows of 300 bytes, about 7,500 pages of 8 KB; from the buffer pool that is milliseconds, from SSD it is tens of thousands of random reads. So we size the buffer pool to hold the hot tables and indexes, avoid SELECT * on wide tables, and run large analytical scans on a replica so they do not flush the cache the OLTP workload depends on."