Heap Files, Slotted Pages, and Tuple Layout

Introduction

Every database system must solve a fundamental problem: how to organize variable-length records on fixed-size disk pages, allow efficient insertion and deletion without excessive fragmentation, and maintain stable references to tuples even as data moves around on a page.
The heap file structure, slotted page format, and tuple layout conventions form the physical foundation on which higher-level abstractions (indexes, query execution, and concurrency control) are built.
Understanding these mechanisms is essential for reasoning about performance, storage overhead, and the design constraints of any relational storage engine.

Heap Files

A heap file is the simplest file organization: an unordered collection of pages, where each page contains a collection of tuples.
There is no sort order, no clustering by key, and no index structure governing placement.
A new tuple is inserted into any page that has sufficient free space.

Structure

A heap file is logically a sequence of pages, each identified by a page ID.
The database maintains a mechanism to locate pages with free space so that inserts do not require scanning every page.
Two common approaches exist:

Linked list of pages. The file header points to two linked lists: one for full pages and one for pages with free space.
On insert, the system traverses the free list to find a page with enough room.
This is simple but can be slow when many pages have small amounts of free space, since the system may traverse many pages before finding one with enough room.

Free space map (page directory). A separate set of directory pages records the amount of free space on each data page.
The directory is typically small enough to be cached in the buffer pool, allowing the system to jump directly to a page with sufficient space.
PostgreSQL, for example, uses a free space map (FSM) stored as an auxiliary fork file alongside the heap file.

Tuple Identifiers

Each tuple in a heap file is identified by a tuple identifier (TID), sometimes called a record identifier (RID).
A TID is typically the pair (page_id, slot_number).
This identifier is used by indexes to point to the physical location of a tuple.
The stability of TIDs under updates and page reorganization is a critical design concern, and the slotted page format exists in part to provide this stability.

Slotted Pages

The slotted page layout is the dominant page format in modern database systems.
It is a well-established technique that traces back to early relational systems such as IBM System R and INGRES and is described as a standard approach in textbooks including Ramakrishnan and Gehrke.
It is used in systems including PostgreSQL, SQLite, and many others.

Page Layout

A slotted page has three regions:

1. Header. Located at the beginning of the page. Contains metadata: page ID, number of slots, a pointer to the start of free space, flags (e.g., for WAL), checksum, and sometimes transaction metadata.
2. Slot array. Grows forward from the end of the header. Each slot is a small fixed-size entry (typically 4 bytes) containing an offset to the tuple's location within the page and sometimes the tuple's length.
3. Tuple data. Grows backward from the end of the page. Tuples are placed starting at the end of the page and growing toward the slot array.

Free space exists in the middle, between the end of the slot array and the start of the tuple data.
When the slot array and tuple region meet, the page is full.

+--------+-------------+---- free space ----+------------------+
| Header | Slot Array → |                    | ← Tuple Data     |
+--------+-------------+--------------------+------------------+
  low addresses                                   high addresses

Why Slotted Pages Work

The key property is indirection.
External references (index entries, other tuples) point to a slot number, not a byte offset.
When tuples are deleted or the page is compacted, tuples can be moved within the page.
The system only needs to update the slot array entries, not every external pointer.
This decoupling is what makes vacuum, compaction, and page reorganization practical.

When a tuple is deleted, its slot entry can be marked as "dead" or set to a special null offset.
The slot itself is not removed (since that would change the slot numbers of subsequent entries), but it can be reused by a future insert.
The actual bytes occupied by the deleted tuple become reclaimable during page compaction.

Page Compaction

Over time, deletions create holes in the tuple data region.
Compaction (sometimes called "defragmentation") slides all live tuples to the end of the page and adjusts slot array entries accordingly.
This recovers contiguous free space without changing any external TID, because the slot numbers remain the same.

Walkthrough

The following walkthrough illustrates insertion into a slotted page.

Inserting a Tuple into a Slotted Page

procedure INSERT_TUPLE(page, tuple):
    tuple_size = length(tuple)
    required = tuple_size + SLOT_ENTRY_SIZE

    free_space = page.free_space_end - page.free_space_start
    if free_space < required:
        COMPACT(page)
        free_space = page.free_space_end - page.free_space_start
        if free_space < required:
            return FAILURE  // page is genuinely full

    // Allocate a slot. Reuse a dead slot if available.
    // When reusing a dead slot, free_space_start does NOT change
    // (the slot entry already exists in the slot array).
    slot_index = find_dead_slot(page)
    if slot_index == NOT_FOUND:
        slot_index = page.num_slots
        page.num_slots += 1
        page.free_space_start += SLOT_ENTRY_SIZE

    // Place tuple data at the end of used tuple region.
    page.free_space_end -= tuple_size
    tuple_offset = page.free_space_end
    write(page, tuple_offset, tuple)

    // Update slot array.
    page.slots[slot_index].offset = tuple_offset
    page.slots[slot_index].length = tuple_size

    return (page.page_id, slot_index)  // the TID

Step-by-step Example

Consider a page of size 8192 bytes with a 24-byte header.
Initially, the slot array is empty, free_space_start = 24, and free_space_end = 8192.

1. Insert Tuple A (100 bytes). Allocate slot 0 (4 bytes). free_space_start becomes 28. Place tuple data at offset 8092 (8192 − 100). free_space_end becomes 8092. Slot 0 points to offset 8092. TID = (page_id, 0).

2. Insert Tuple B (60 bytes). Allocate slot 1 (4 bytes). free_space_start becomes 32. Place tuple data at offset 8032 (8092 − 60). free_space_end becomes 8032. Slot 1 points to offset 8032. TID = (page_id, 1).

3. Delete Tuple A. Mark slot 0 as dead. The 100 bytes at offset 8092 are now reclaimable but are not contiguous with the central free region. The contiguous free space (between free_space_start = 32 and free_space_end = 8032) is 8000 bytes. The 100 bytes from Tuple A form a non-contiguous hole in the tuple data region.

   Hypothetical compaction at this point: If the system were to compact the page now, Tuple B (the only live tuple) would be slid from offset 8032 to offset 8132 (8192 − 60).
   Slot 1 would be updated to point to 8132, and free_space_end would be reset to 8132.
   The 100-byte hole from Tuple A is absorbed into the central free region, which now spans offsets 32 through 8132 — a contiguous 8100 bytes.
   Slot 0 remains marked dead; its slot entry still occupies space in the slot array but no longer references live data.

4. Insert Tuple C (80 bytes) — without compaction. The contiguous free space is 8032 − 32 = 8000 bytes, which is sufficient for Tuple C (80 bytes of data + 0 bytes of new slot overhead, since slot 0 is reused). Slot 0 is reused (its dead entry is overwritten). free_space_end becomes 7952 (8032 − 80). Slot 0 now points to offset 7952, with length 80. TID = (page_id, 0).

   At the physical storage level, the TID (page_id, 0) now designates Tuple C.
   In practice, MVCC systems prevent this from causing correctness problems: a slot is not made available for reuse until the storage engine has confirmed that no active or future transaction could legitimately resolve the old TID to the deleted tuple.
   PostgreSQL, for instance, defers slot reuse until vacuum has processed the page and confirmed that the old tuple (Tuple A) is dead to all active transactions; MVCC visibility checks using xmin/xmax provide an additional safety layer for any transaction that might hold a stale reference.

Tuple Layout

Within each tuple, the system must encode the values of all columns along with metadata needed for concurrency control and schema interpretation.

Common Tuple Structure

A typical tuple contains, from low to high offset:

1. Tuple header. Fixed-size metadata. In PostgreSQL (as of recent stable versions), this is 23 bytes (the HeapTupleHeaderData struct) and includes the transaction ID that inserted the tuple (xmin), the transaction ID that deleted it (xmax), the command ID (cid), and an infomask with flags indicating null presence, TOAST status, and visibility hints. The exact size may vary across PostgreSQL versions; consult the documentation for the version in use.

2. Null bitmap. A bit array with one bit per column. This bitmap is present in a specific tuple only when at least one column in that tuple actually contains a null value, as indicated by the HEAP_HASNULL flag in the tuple's infomask. If no column is null in a given tuple, the bitmap is omitted entirely, and no space is consumed for it. When the bitmap is present, a column whose bit is set has no storage in the data portion of the tuple.

3. Column data. Attribute values are stored in schema order. Fixed-length columns (e.g., int4, float8) are stored inline at their natural width. Variable-length columns are preceded by a 1-byte or 4-byte length prefix. Alignment padding may be inserted between columns to satisfy architecture alignment requirements (e.g., an int8 column aligned to an 8-byte boundary).

Alignment and Padding

Column alignment follows platform conventions.
PostgreSQL aligns columns based on their typalign catalog attribute: char (1-byte), short (2-byte), int (4-byte), or double (8-byte).
This means that column ordering in the CREATE TABLE statement can affect physical storage size.
Grouping columns by alignment class can reduce wasted padding bytes.

For example, a table with columns (bool, int8, bool, int8) would require padding between each bool and the following int8, wasting 7 bytes per pair.
Reordering to (int8, int8, bool, bool) eliminates most padding.

Large Values and TOAST

When a tuple's total size exceeds a system threshold — in PostgreSQL, approximately 2 KB (one quarter of the default 8 KB page size, or 2048 bytes) — the system uses a technique called TOAST (The Oversized-Attribute Storage Technique).
Large column values are compressed and/or moved to a separate TOAST table, with the original tuple containing only a small pointer.
This ensures that the base tuple always fits on a single page.
The threshold applies to the tuple as a whole: PostgreSQL attempts to keep the heap tuple under this limit by TOASTing the largest variable-length attributes first.

Key Points

• Heap files store tuples in unordered pages, relying on free space maps or linked lists to efficiently locate pages for insertion.
• Slotted pages use a slot array for indirection, allowing tuples to be moved within a page without invalidating external references (TIDs).
• Free space on a slotted page exists between the forward-growing slot array and the backward-growing tuple data region.
• Page compaction reclaims fragmented space by sliding live tuples and updating slot offsets, with no effect on external TIDs.
• Tuple headers carry MVCC metadata (transaction IDs, visibility flags) that are essential for concurrency control.
• The null bitmap is present in a tuple only when at least one column in that specific tuple is null; it is omitted entirely otherwise.
• Column alignment padding can be minimized through thoughtful column ordering in the schema definition.
• Oversized attributes are handled by mechanisms like TOAST, ensuring tuples always fit within a single page.

References

Ramakrishnan, R. and Gehrke, J. Database Management Systems, 3rd Edition. McGraw-Hill, 2003. Chapters 9 and 10.

Garcia-Molina, H., Ullman, J.D., and Widom, J. Database Systems: The Complete Book, 2nd Edition. Pearson, 2008. Chapters 12 and 13.

PostgreSQL Global Development Group. "Database Page Layout." PostgreSQL Documentation, Chapter 73. https://www.postgresql.org/docs/current/storage-page-layout.html

Stonebraker, M. "The Design of the POSTGRES Storage System." Proceedings of the 13th International Conference on Very Large Data Bases (VLDB), 1987.

Astrahan, M.M. et al. "System R: Relational Approach to Database Management." ACM Transactions on Database Systems, 1(2):97–137, 1976. (Primary reference for IBM System R's storage architecture, including its use of slotted-page heap storage.)