Heap Tuple Headers, Transaction Identifiers, and Visibility Rules

A row stored on a page is not the current row. It is one version of the row, tagged with the transaction that produced it and, once deleted, the transaction that removed it. Nothing is overwritten in place for a version that another snapshot may still need. The reader’s job is to look at the tag, compare it against its own snapshot, and decide whether this physical version is the logical row it is asking for.

This article works through the header layout and the comparison, using PostgreSQL’s heap format as the concrete case because it exposes the mechanism directly: the transaction identifiers are in the tuple, not in a separate undo area, so visibility is a pure function of the header bytes and the snapshot.

What the header carries

Every heap tuple begins with a fixed-size header before the user columns. The fields that matter for visibility are:

• xmin, the transaction identifier that inserted this version.
• xmax, the transaction identifier that deleted or superseded it, or zero if no deletion has been recorded.
• cid, the command identifier within the inserting transaction, which distinguishes rows written by earlier commands of the same transaction.
• ctid, a pointer to the next version of the same logical row, forming the update chain.
• an infomask word of bits that record, among other things, whether xmax is a lock rather than a deletion, whether the tuple has been frozen, and whether the tuple is known to be all-visible.

The header is 23 bytes before alignment and is padded to a multiple of the platform’s MAXALIGN, which is 8 bytes on 64-bit builds, so it occupies 24 bytes. The null bitmap follows when the tuple has nullable columns, and column data follows that. The header size is fixed per tuple; it is not compressed and not optional, which means a narrow row pays a substantial fraction of its storage in bookkeeping. A table of 8-byte integers spends three times the payload on the header.

The critical property is that xmin and xmax are transaction identifiers, not commit timestamps. A transaction identifier is assigned when the transaction starts, so identifiers are allocated in start order but do not become “visible” in that order; a transaction with a lower identifier can commit after one with a higher identifier. This is the single most important fact about the scheme, and it is why visibility cannot be decided by comparing a single number against a threshold.

The snapshot as a set, not a boundary

A snapshot is not a scalar. It is a structure containing:

• xmin, the lowest identifier among transactions that were still running when the snapshot was taken,
• xmax, one past the highest identifier assigned at that moment,
• xip, the list of identifiers of transactions that were in progress.

A transaction identifier x is visible to the snapshot if x < xmax and x is not in xip and x is not aborted. The xmin field is an optimization: any identifier below it is either committed or aborted and long resolved, so the in-progress list need not extend that far.

The reason a scalar boundary is insufficient is visible in a three-transaction example. T1 starts and gets identifier 100. T2 starts and gets 101. T1 commits. T3 starts, takes a snapshot with xmax = 102 and xip = {101}. Identifier 100 is committed and below xmax, so it is visible. Identifier 101 is below xmax but in xip, so it is not visible even though T2 might commit one microsecond later. If the snapshot were “everything committed before now”, T2’s commit would be visible; the snapshot semantics require it not to be, because the read view was fixed.

Deciding whether a version is in the snapshot

The visibility test for a version under a snapshot is a composition of two questions: was the inserting transaction visible, and was the deleting transaction visible.

/* Simplified: returns 1 if this version is visible to the snapshot.
 * in_snapshot(xid, snap) is the three-part check described above. */
static int
tuple_visible(TupleHeader tuple, Snapshot snap)
{
    TransactionId xmin = tuple_xmin(tuple);
    TransactionId xmax = tuple_xmax(tuple);

    if (!in_snapshot(xmin, snap))
        return 0;                       /* inserted by an invisible txn */

    if (xmax_is_valid(xmax) &&
        in_snapshot(xmax, snap) &&
        !xmax_is_lock_only(tuple))
        return 0;                       /* deleted by a visible txn */

    return 1;
}

in_snapshot performs the three-part check described above, with one addition that the header infomask makes possible: a tuple can be marked frozen, meaning its xmin has been replaced by a special identifier older than any real one, so the check succeeds without consulting the in-progress list. Freezing is the mechanism that keeps the identifier space from wrapping, and it interacts with version collection in the way described in vacuum horizons and dead version collection.

Two special cases matter. If xmax is set but points to a transaction that has not committed and is not in progress — an aborted transaction — the deletion did not happen, and the version remains visible. If xmax is set to a transaction that is still in progress, the deletion is speculative from this snapshot’s point of view; under read committed the row is still visible, and the deleting transaction may yet abort.

The same transaction sees its own writes

A transaction must see its own uncommitted changes, which the snapshot rule alone would forbid, since the transaction’s own identifier is in progress from its own perspective. The cid field resolves this. A version written by the current transaction is visible if its command identifier is less than the current command’s, so a statement sees the effects of earlier statements in the same transaction but not of later ones.

This produces the odd but correct behaviour that a statement does not see rows it inserts itself through a re-scan in the same command. A single INSERT ... SELECT that reads the target table sees the pre-statement state, not the rows being added, because the inserted tuples carry a cid equal to the current command and are therefore not visible to it. The alternative — seeing your own in-flight inserts — would make the statement’s result depend on the order in which the executor happened to process rows.

Update chains and the ctid walk

An update does not modify the existing tuple. It writes a new tuple with xmin set to the updating transaction and sets the old tuple’s xmax to the same identifier, and the old tuple’s ctid is rewritten to point at the new one. The old version stays in place until no snapshot can see it.

A reader that lands on an old version because the index entry points there must follow the chain. The index stores a ctid for the row as it existed when the index entry was created; if that version has been superseded, the reader walks ctid forward until it finds a version visible to its snapshot. This is the “heap fetch and follow the chain” path, and it is the reason a long update chain costs more than one page access per index lookup.

-- Chain inspection through the pageinspect extension: t_xmin created the
-- version, t_xmax retired it, t_ctid points at the successor version.
SELECT t_ctid, t_xmin, t_xmax, t_infomask
FROM heap_page_items(get_raw_page('items', 0));

Chains are bounded in principle by the number of updates to a row between version collections, but not in practice by anything the engine enforces. A row updated many times between two vacuum passes produces a chain of that length, and every reader that arrives at the oldest link pays the walk.

Why the identifiers live in the tuple

The alternative design, used by engines with a separate undo area, keeps the current version in the heap and stores before-images in a rollback segment. A reader that needs an older version follows a pointer from the current row into the undo log, applies the inverse change, and reconstructs the version. The pointer is a small rollback segment number and slot, not a full transaction identifier pair.

The trade is storage against read cost, and it is the subject of undo records and version chains. Putting the identifiers in the tuple makes visibility a local decision: a reader examines the page it already has open and needs no other structure. It also means every update leaves a full copy of the row on the page, so a hot row’s history occupies heap space and index entries must be inserted for each new version. Keeping the current version in place and the history in undo makes updates cheap in heap space and index churn, at the cost of a read that must consult a second structure and may need to reconstruct several intermediate states.

Both designs use the same visibility logic. The difference is where the version is materialized, not how it is judged.

The boundary conditions that bite

Three degenerate cases are worth naming because they produce behaviour that looks like a bug.

An identifier comparison must be done with wraparound in mind. Identifiers are 32 bits, so the space holds about four billion values, and comparison is modular: x is older than y if y - x is less than half the space. A naive unsigned comparison fails when the counter wraps, treating very old identifiers as very new. Freezing exists to prevent any live tuple from carrying an identifier close to the wrap point.

The in-progress list grows with concurrency, and every visibility check against a snapshot scans it. A snapshot taken while a thousand transactions are running carries a thousand entries, and the check becomes a linear scan per tuple. Implementations mitigate this with a bitmap over identifier ranges, which is why the snapshot structure in a real engine is larger than the three fields described here.

And a snapshot’s xmax is not a commit horizon. It is the next identifier to be assigned, and identifiers above it belong to transactions that started after the snapshot. Those are invisible regardless of when they commit, which is why a reader never sees a transaction that began after it, even if that transaction commits first.