Rows, Pages, and Heap Storage

When tuples become bytes

The executor thinks in tuples, but disks and memory move in pages. Heap storage is the layer that turns table rows into bytes arranged inside fixed-size blocks. This is where a database becomes physical. A relational result eventually depends on page headers, line pointers, tuple headers, and free space, along with rules about where new versions can fit.

A heap is called a heap because rows are not kept in logical order by key. New tuple versions are placed where there is suitable free space. A table is a sequence of pages, and each page contains multiple tuple versions. The system identifies a tuple by a physical location such as page number plus item offset. That location can be stored in indexes as a tuple identifier, letting an index entry point back to the heap.

Anatomy of a page

Inside a page, line pointers create a layer of indirection. A line pointer sits in a small array near the page header and points to the actual tuple bytes elsewhere on the page. This lets the database move tuple bytes within the page to compact space while keeping the item offset stable. Stability matters because indexes may refer to that offset. The page can reorganize itself locally without forcing every external reference to change.

Tuple headers carry time

Tuple headers carry database meaning that ordinary records do not need. A tuple version must know which transaction created it and which transaction, if any, deleted or superseded it. It may carry flags for nulls, variable-width data, and visibility hints. This overhead is the price of MVCC and crash-safe storage. The row is more than user data. It is a versioned fact inside a transactional timeline.

Heap storage sits between two simpler designs. Append-only storage makes writes easy and crash recovery conceptually simple, but finding the current version of a row can become expensive unless additional indexes or compaction layers exist. In-place updates are space-efficient and intuitive, but they clash with readers that need an older snapshot and with rollback after partial failure. Heap tuple versioning chooses to spend space so time and isolation can be represented.

Free space and how it is tracked

Free space management keeps inserts from scanning the entire table looking for room. The database tracks pages with available space in auxiliary structures. When a new tuple arrives, storage can ask for a page likely to fit it. If none exists, the table grows. This matters most under update-heavy workloads, which create uneven holes across many pages. Good free space tracking keeps the heap from expanding unnecessarily while avoiding expensive searches.

Variable-width columns complicate layout. Text, byte arrays, and large values may not fit comfortably inside a page. A Postgre-like design can store small values inline, compress some values, and move very large values to separate overflow storage while leaving a reference behind. The heap tuple remains the logical row version, but not every byte of user data must live directly inside it.

Nulls also shape physical representation. A row with nullable columns needs a way to record which values are absent without storing full placeholders. A null bitmap can compactly mark missing values. Attribute alignment matters too. CPUs prefer some values at aligned addresses, so tuple layout may include padding. Physical storage involves many small compromises between compactness and speed.

Updates expose how the heap design works. If a row changes, the database may write a new tuple version and mark the old version as superseded. If the update does not affect indexed columns and there is room on the same page, a heap-only update can keep index entries pointing to a chain that leads to the newest visible version. This avoids unnecessary index churn, but it depends on page-local space and careful visibility rules.

Deletes do not erase immediately. A delete marks a tuple version as no longer visible to future transactions, but old snapshots may still need it. Physical cleanup waits until the system can prove no active transaction can see the dead version. This delayed cleanup is one reason vacuum exists and one reason storage cannot be understood apart from transaction state.