4.1 Paged Storage, Record Layout, and Buffer Pool

Returning one row does not mean reading only one row from disk. Storage engines usually move pages and reuse them through a buffer pool. Following one read through page layout, record lookup, and dirty-page writeback explains why an index lookup can lose to a sequential scan, and why a cache hit still needs a visibility check.

Learning Objectives

• Distinguish between row, tuple, page, extent/file, and block device;
• Explain how slotted pages accommodate variable-length records;
• Correctly compare sequential scan with random lookup;
• Understand the role of the buffer pool's page table, pinning, dirty flags, and eviction mechanisms;
• Identify the distinct responsibilities of the OS page cache, database cache, and durability.

How a Query Passes Through Layers

SQL executor
  -> access method (heap/index)
  -> buffer manager
  -> database page in memory
  -> database file
  -> filesystem / block layer
  -> storage device

The query executor typically does not perform a direct disk read for every row. Instead, it requests a page, and the buffer manager checks whether that page is already in memory. On a miss in the database cache, the buffer manager requests the page through the operating system, whose own cache may satisfy the request.

Sequential scan is not "random I/O × page count"

Suppose a table has 5,000,000 pages. A scan does indeed involve reading a large number of pages, but it typically accesses them in physical or logical page order. Operating systems and storage devices can perform readahead and request merging, and modern SSDs support parallel queuing.

Therefore, it's incorrect to estimate sequential scan time as "a single random I/O of 10 ms multiplied by 5 million pages." A more realistic lower-bound approximation starts with data volume and sustained throughput:

scan time >= bytes to read / effective read bandwidth

For example, assume 5 million pages of 8192 bytes must all be read from the device: that is 40.96 GB. At an assumed effective bandwidth of 1 GB/s, the ideal transfer-only lower bound is 40.96 seconds. This is a calculation under stated assumptions, not a measurement. Filtering, decompression, visibility checks, and result transfer may overlap or become separate bottlenecks; do not mechanically add their times.

When pages reside in the buffer pool or OS cache, physical reads may be few. If a query returns most of a table, sequential scanning can also cost less than repeated index lookups.

Page is a Fixed-Size Management Unit

Databases typically use a fixed page size, which is determined by engine, build, or table settings. The row count is not simply page_size / row_size; layout overhead includes:

• page header;
• line pointer or slot directory;
• tuple header, NULL bitmap, and alignment;
• variable-length value storage;
• MVCC metadata;
• free space, fragmentation, and engine-specific trailer.

Thus, the claim that "a 4 KiB page with 200-byte rows fits exactly 20 rows" is only a rough upper bound and does not reflect actual layout.

Slotted page

A common slotted-page structure:

+-------------------------------+
| page header                   |
+-------------------------------+
| slot 0 | slot 1 | ...         |  grows downward
+-------------------------------+
|          free space           |
+-------------------------------+
| record ... | record 1 | rec 0 |  grows upward
+-------------------------------+

Each slot stores the offset and length (or state) of a record. When records move within the page, only the slots are updated; external record identifiers remain valid and can continue to reference (page_id, slot_id). After a record is deleted, its corresponding slot is marked as free, allowing for later compaction of the page.

The exact implementation varies. In PostgreSQL heap pages, item identifiers and tuples grow from opposite ends of the page. The page header includes LSN (log sequence number), flags, and boundaries for free space. Checksum use depends on cluster configuration; do not assume every page is always checked.

Variable-length and Overflow

A row may contain text or blob data. The engine can employ several strategies:

• Inline storage for short values;
• Variable-length records within the same page;
• Overflow pages or chained storage;
• Data compression;
• Out-of-line storage similar to PostgreSQL's TOAST.

Large columns can alter row width, cache density, and the feasibility of indexing. SELECT * may force the engine to read overflow data as well as send more bytes across the network.

The Stability Boundary of Record Identifiers

In a heap-organized table, the index leaf nodes often store record locators, such as page/slot numbers. When a row is updated, several scenarios may occur:

• In-place modification;
• Creation of a new version within the same page;
• Movement to a different page, accompanied by forwarding or version links;
• Updates to all related indexes;
• Retention of the old version for concurrent snapshot reads.

As a result, the locator typically serves as an engine-internal identity rather than a business primary key. In PostgreSQL, ctid changes with each row version or location update and should not be persisted as an application-level identifier.

Buffer Pool's Core State

The buffer manager must at least answer the following questions:

• page_id -> frame Whether a page hit occurred;
• Whether a frame is pinned by a caller and therefore unavailable for eviction;
• Whether a page is dirty;
• The page’s recent access or frequency metadata;
• Whether the corresponding WAL entry satisfies the write-ahead rule before a dirty page is written back;
• How concurrent read and write operations are coordinated via latching or locking.

page table: page_id -> frame_id
free list / replacement candidates
frame metadata: pin_count, dirty, usage, io_state
frames: actual page bytes

A page hit only confirms that the page bytes are in memory; it does not guarantee that the rows are visible to the current transaction. MVCC visibility checks are still required.

Pin, Latch, and Transaction Lock Are Different

• Pin prevents a frame from being evicted while it is in use;
• Latch protects short critical sections of memory structures or pages;
• Transaction lock ensures logical data concurrency and may span across statements or transactions.

Mixing these three can lead to incorrect performance characteristics and deadlock scenarios. Reading a page might temporarily hold a latch, but it does not necessarily result in a row-level business lock.

Replacement Is Not Pure LRU

Exact LRU maintenance is expensive, and a single full scan can evict the hot working set. The engine employs strategies such as clock-sweep, LRU-K, 2Q, scan-resistant admission, and sequential-scan ring, either directly or in variant forms.

The goal of these strategies is not merely to maximize hit ratio: factors like dirty write cost, scan behavior, prefetching, concurrent contention, and page reuse distance all play a role.

"Setting the buffer pool to a fixed percentage of physical memory" is not a universal rule. Space must also be reserved for the OS, connection memory, sort and hash operations, background processes, filesystem cache, and other services. The caching paths in PostgreSQL and InnoDB differ, so configurations should be based on official documentation for the target version and actual workload measurements.

Dirty Page and Durability

When a modification occurs, the page may first become "dirty" in the buffer pool. The write-ahead rule stipulates that before a dirty data page is written to a durable data file, the corresponding WAL (Write-Ahead Log) entry that can redo the modification must itself be durable.

This does not mean that every memory byte modification must be immediately synchronized to the log. Group commit and checkpoint behavior depend on the distinction between memory modification, WAL insertion, WAL flush, data-page flush, and commit acknowledgment.

OS Page Cache and Direct I/O

Databases may use buffered I/O through the OS page cache, or they may employ direct I/O on certain paths. Whether double caching is wasteful depends on the database engine and the workload characteristics. The OS cache also serves to store filesystem metadata, executable files, and other file data.

Seeing data in memory and having it durably persisted to stable storage are two distinct operations. A successful write(), bytes in the kernel cache, bytes in a volatile device cache, and survival of power loss are different states.

Observing Problems

When troubleshooting I/O performance, collect the following metrics:

logical page reads versus physical reads
buffer hit/miss rates by relation or query
read/write latency distributions
dirty page counts and checkpoint write frequency
scan bytes, returned rows, and filtered rows
temporary spill bytes
device queue depth and utilization
working-set evolution over time

A high buffer hit ratio does not necessarily mean fast performance: even when every page is cached, CPU usage, latch contention, decompression overhead, or query plan complexity can still be bottlenecks. A low hit ratio is not always problematic: large, low-reuse analytical scans were never intended to pollute the hot cache.

Lesson Summary

Paged storage transforms row-level management into page-level management; the buffer pool determines which pages reside in memory and when they are flushed back to storage. Sequential scans, random lookups, and cache hits must all be understood in the context of data volume and access patterns. The next lesson introduces the B+ tree into this page model, analyzing point lookups, range scans, splits, and variations in leaf payload across different storage engines.

Official Resources Entry

• PostgreSQL Database Page Layout
• PostgreSQL Database Physical Storage
• MySQL InnoDB Buffer Pool