Slotted Pages: Fitting Variable-Length Records into Fixed-Size Blocks

Storage engines move data between memory and disk in fixed-size units because the layers below them do. A disk exposes sectors, the file system and page cache work in pages, and a memory-mapped file maps whole pages. A database therefore picks a block size — 8 KiB is the PostgreSQL default, 4 KiB is the SQLite default, some engines use 16 KiB or larger — and every read and write touches one of those blocks. Records, however, are not fixed-size. A row may hold a short integer and an empty string, or several kilobytes of text. The page format has to reconcile the two, and it has to keep doing so while records are inserted, deleted, and updated in arbitrary order.

Two allocations growing toward each other

The layout that almost every row-oriented engine converged on divides the page into three regions. A fixed-size header sits at offset zero and records the page’s identity, its free-space boundary, its checksum, and a few flags. Immediately after the header is an array of small fixed-width entries, one per record on the page. Records themselves are stored from the end of the page backwards, so that the last record ends exactly at the block boundary.

The space between the end of the directory and the start of the newest record is the free region. An insert allocates a directory entry by advancing the directory end forward by the entry size, and allocates record bytes by pulling the record start backward by the record length. When the two cursors meet, the page is full. Nothing ever needs to be shifted to make room, which is the entire point: an insert is two pointer bumps and a memcpy of the record body.

The directory entry is a item identifier: a byte offset to the record plus its length, packed into four bytes in PostgreSQL’s ItemIdData and into a similar pair in other engines. Because offsets fit in a small integer, a page can address at most a few thousand records no matter how small they are. On an 8 KiB page with 4-byte identifiers, a ceiling of roughly 2000 records follows from arithmetic alone, and real engines reserve header space and impose their own limit somewhat below that.

/* Simplified page header and item identifier, after the usual row-store layout. */
struct page_header {
    uint16_t pd_checksum;
    uint16_t pd_flags;
    uint16_t pd_lower;   /* end of the item-id array */
    uint16_t pd_upper;   /* start of the newest record */
    uint16_t pd_special;
    uint16_t pd_pagesize_version;
};

struct item_id {
    uint16_t lp_off;     /* byte offset of the record */
    uint16_t lp_len;     /* record length, zero if the slot is dead */
};

static inline size_t free_space(const struct page_header *h) {
    return (size_t)h->pd_upper - (size_t)h->pd_lower;
}

Indirection is the load-bearing decision

The reason records are addressed through the directory rather than directly is not compactness. It is that the rest of the engine needs a stable name for a record.

An index entry in a heap-organized table stores a tuple identifier: a block number and a slot number, six bytes in PostgreSQL. That pair is the physical address of the row as far as every index is concerned. If the tuple identifier were a byte offset, then any operation that moved a record inside its page — compaction to reclaim holes, an update that grows the row and forces a rewrite elsewhere on the page — would invalidate every index entry pointing at it. With a slot number, the record can move freely; only the directory entry’s offset changes, and the slot number keeps its meaning. This is the same trick as a handle table or a page table: a level of indirection buys address stability at the cost of one extra memory access on every fetch.

The consequence is a rule that shows up in engine documentation as a hard constraint rather than an optimization: an update that does not change the key can keep the same slot, while an update that changes the key is a delete plus an insert. When the new version does not fit on the page, the engine writes it to a different page and leaves behind a forwarding pointer in the original slot, so index entries that still name the old slot can find their way to the new location. PostgreSQL calls this a tuple move; the index entry is not updated, and the chain is followed at read time.

Deletion, holes, and the cost of not compacting

Deleting a record marks its slot dead by zeroing the length, and optionally records the offset for later reuse. The record bytes are not moved. The space between live records is now a hole, and the free-space accounting has to distinguish “space between the cursors” from “space inside the used region that could be reclaimed.”

Two policies exist. The first compacts immediately: after a delete, records above the hole slide down and the directory offsets are rewritten. This makes the free region accurate and contiguous, at the cost of touching every record above the hole and updating every corresponding offset. On a page holding a few hundred small records the copy is cheap; on a page holding a few large ones it is not, and the page must be exclusively latched for the duration.

The second policy defers. The engine leaves the hole in place and records it for a later pass that runs when the page is otherwise being rewritten anyway — during checkpoint-driven cleaning, during vacuum, or when a new record does not fit in the nominal free region but would fit after compaction. PostgreSQL’s heap pages take this route, which is why an update-heavy table can show a page with plenty of total free bytes that nonetheless cannot accept a new tuple until pruning runs. The free-space map that the engine keeps for choosing a target page for an insert must therefore treat “free after pruning” separately from “free right now,” or inserts will keep choosing pages that then fail.

Fragmentation has a second-order effect on scans. A sequential scan that reads records in slot order jumps between offsets that no longer increase monotonically once holes exist, so the read pattern within a page degrades from a linear walk to a scattered one. The cost is small relative to the I/O of fetching the page, but it matters for in-memory workloads and for prefetching heuristics that assume forward progress.

Records that cannot fit

A record larger than the usable page area cannot be stored contiguously, and every engine has an escape hatch. PostgreSQL compresses and, if still too large, splits the value into a chain of overflow chunks stored in a separate TOAST table, keeping only a small pointer in the main tuple. SQLite uses overflow pages linked from the page that holds the record prefix. The design constraint is that the main page must remain a fixed-size unit that the buffer pool can pin, so the oversized value is pushed out of the page’s address space entirely.

The threshold is not the page size but the page size minus the header, the directory entry, and whatever alignment the engine requires. A tuple must also leave room for at least one more directory entry if the engine wants to guarantee that a page can always accept a null tuple; some engines reserve exactly that.

Concurrency at the page boundary

A page is the unit of physical consistency, and also a convenient unit of locking. An insert has to allocate a slot and record bytes without two writers choosing the same space. Engines either take an exclusive page latch for the allocation and then downgrade, or use an atomic compare-and-swap on the free-space pointer. The second is faster but leaves a window in which a crash produces a page whose header claims space that no record occupies; the write-ahead log record for the insert must describe the slot and the bytes, not merely the final pointer value, so that recovery can reconstruct the page from the log rather than trusting the header.

That requirement is why page formats and log formats are designed together. A slotted page whose header is updated in place is only crash-safe if the log contains enough information to redo the header change and the record write as separate, idempotent actions. The mechanics of that log are the subject of write-ahead logging and record ordering, and the reason pages are cached and pinned rather than read on demand is covered in buffer pool frames and pinning.

Where the format shows through

The slotted layout is old enough that its costs are well understood. It wastes four bytes per record on the directory entry and a few bytes of alignment per record, which is a few percent on narrow rows and negligible on wide ones. It cannot support records that grow in place without a move. It makes the page a mutable structure, so every modification dirties the whole block and forces the full block to be written back even if one byte changed — a property that dominates write amplification in row stores and motivates the log-structured alternatives compared in write amplification across the storage stack.

Against that, it gives O(1) insert and delete given free space, stable record addresses, and a page that can be validated with a checksum over a single contiguous region. For a workload of many small random updates, the fixed-block mutable page is still the simplest structure that satisfies the crash-consistency contract, which is why the alternatives have replaced it at the margins rather than at the center.