Cellular Anatomy of PostgreSQL: MVCC & Tuple Visibility Algorithms¶

1. Introduction: The Quantum Horizon of Database Visibility¶

In quantum mechanics, an observation collapses a wave function into a specific state. In PostgreSQL Multi-Version Concurrency Control (MVCC), a Snapshot freezes the observable state of the entire universe of transactions at a single microsecond in time.

To understand MVCC like a medical pathologist, one must abandon the concept that rows exist in a binary state of "present or absent." A tuple exists in physical reality on an 8KB disk page with an insertion timestamp (xmin) and a deletion timestamp (xmax). Its visibility is a mathematical function computed by the C function HeapTupleSatisfiesMVCC() (src/backend/access/heap/heapam_visibility.c).

2. Anatomical Blueprint: `SnapshotData`¶

Located in src/include/utils/snapshot.h. When a transaction executes a query, the engine captures a SnapshotData struct:

typedef struct SnapshotData
{
    SnapshotType    snapshot_type;      /* SNAPSHOT_MVCC, SNAPSHOT_SELF, etc. */

    TransactionId   xmin;               /* All XIDs < xmin are KNOWN to be completed */
    TransactionId   xmax;               /* All XIDs >= xmax are in the future (INVISIBLE) */

    TransactionId  *xip;                /* Array of active uncommitted transactions */
    uint32          xcnt;               /* Number of active transactions in xip array */

    TransactionId  *subxip;             /* Array of active sub-transactions */
    int32           subxcnt;            /* Number of active sub-transactions */

    CommandId       curcid;             /* Current Command ID within our transaction */
    uint32          active_count;       /* Refcount on this snapshot */
    uint32          regd_count;         /* Registration count */
    bool            copied;             /* Is this a copy? */
} SnapshotData;

Visualizing the Snapshot Window:¶

           0 ------------ [ xmin: 100 ] ---------------------- [ xmax: 150 ] ------------> Infinity
Past Transactions:               |                                   |                    Future:
All XIDs < 100 are               |  Active Transactions in flight:   |                    All XIDs >= 150
GUARANTEED committed or aborted. |  xip array = [102, 108, 145]      |                    started AFTER this
Always visible (if committed).   |  If tuple has xmin in xip array,  |                    snapshot was created.
                                 |  it is INVISIBLE!                 |                    Always INVISIBLE.

3. The Commit Log: `pg_xact` (CLOG) Cellular Bit-Packing¶

Where does Postgres record whether transaction 105 committed or aborted? It does not write to the table! It writes to the Commit Log ($PGDATA/pg_xact/).

The 2-Bit Cellular Packing:¶

Every transaction ID in PostgreSQL requires exactly 2 bits of storage:

[Bit 1] [Bit 0] : Meaning
   0       0    : TRANSACTION_STATUS_IN_PROGRESS (Currently running)
   0       1    : TRANSACTION_STATUS_COMMITTED   (Committed successfully)
   1       0    : TRANSACTION_STATUS_ABORTED     (Rolled back / Crashed)
   1       1    : TRANSACTION_STATUS_SUB_COMMITTED

Storage Math:
1 byte holds 4 transactions.
1 standard 8KB CLOG page holds 32,768 transactions ($8,192 \times 4$).
A cluster executing 100 million transactions uses only ~24 MB of CLOG space on disk!

The CLOG Lookup Bottleneck:¶

If Postgres had to read the CLOG for every single row returned in a 1,000,000-row SELECT scan, performance would collapse under disk read contention. * The Cellular Solution (Hint Bits): The very first query that inspects a tuple performs the CLOG lookup, determines that xmin is committed, and atomically modifies the tuple header directly on the data page by flipping the bit HEAP_XMIN_COMMITTED in t_infomask. * Every subsequent query sees HEAP_XMIN_COMMITTED == 1 and bypasses the CLOG entirely!

4. The Exact Visibility Algorithm in C (`HeapTupleSatisfiesMVCC`)¶

When a query evaluates whether a tuple on an 8KB page is visible, it executes this exact logic branch tree (src/backend/access/heap/heapam_visibility.c):

bool
HeapTupleSatisfiesMVCC(HeapTuple htup, Snapshot snapshot, Buffer buffer)
{
    HeapTupleHeader tuple = htup->t_data;

    /* -------------------------------------------------------------
     * STAGE 1: Check Insertion Transaction (t_xmin)
     * ------------------------------------------------------------- */
    if (!HeapTupleHeaderXminCommitted(tuple))
    {
        if (HeapTupleHeaderXminInvalid(tuple))
            return false; /* Inserting transaction aborted -> INVISIBLE */

        if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tuple)))
        {
            /* Inserted by OUR OWN transaction */
            if (HeapTupleHeaderGetCmin(tuple) >= snapshot->curcid)
                return false; /* Inserted by a later command in our transaction -> INVISIBLE */
        }
        else if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmin(tuple), snapshot))
        {
            /* Inserting transaction was STILL ACTIVE when snapshot was taken */
            return false; /* INVISIBLE */
        }
        else
        {
            /* Check CLOG if not already hinted */
            if (!TransactionIdDidCommit(HeapTupleHeaderGetRawXmin(tuple)))
                return false; /* Aborted in CLOG -> INVISIBLE */

            /* Set Hint Bit for future queries! */
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED, HeapTupleHeaderGetRawXmin(tuple));
        }
    }
    else
    {
        /* Hint bit HEAP_XMIN_COMMITTED is already set! */
        /* But wait: Is xmin >= snapshot->xmax? */
        if (HeapTupleHeaderGetRawXmin(tuple) >= snapshot->xmax)
            return false; /* Committed AFTER snapshot was taken -> INVISIBLE */

        /* Is xmin in our snapshot active list (xip)? */
        if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmin(tuple), snapshot))
            return false; /* Was still running when snapshot taken -> INVISIBLE */
    }

    /* -------------------------------------------------------------
     * STAGE 2: Check Deletion/Update Transaction (t_xmax)
     * ------------------------------------------------------------- */
    if (tuple->t_infomask & HEAP_XMAX_INVALID)
    {
        /* xmax is invalid -> Row was NEVER deleted or updated! */
        return true; /* VISIBLE! */
    }

    if (!HeapTupleHeaderXmaxCommitted(tuple))
    {
        if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
        {
            /* Deleted by OUR OWN transaction */
            if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
                return true; /* Deleted by a LATER command in our transaction -> Still VISIBLE */
            return false;    /* Deleted by an EARLIER command in our transaction -> INVISIBLE */
        }

        if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmax(tuple), snapshot))
        {
            /* Deleting transaction is STILL RUNNING -> Row is not yet officially deleted! */
            return true; /* VISIBLE! */
        }

        if (!TransactionIdDidCommit(HeapTupleHeaderGetRawXmax(tuple)))
        {
            /* Deleting transaction aborted/crashed! Delete did not succeed! */
            SetHintBits(tuple, buffer, HEAP_XMAX_INVALID, InvalidTransactionId);
            return true; /* VISIBLE! */
        }

        /* Deleting transaction committed! */
        SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED, HeapTupleHeaderGetRawXmax(tuple));
    }
    else
    {
        /* Hint bit HEAP_XMAX_COMMITTED is set! */
        if (HeapTupleHeaderGetRawXmax(tuple) >= snapshot->xmax)
            return true; /* Deleted AFTER snapshot was taken -> Still VISIBLE to us! */

        if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmax(tuple), snapshot))
            return true; /* Deleting TX was still active at snapshot time -> Still VISIBLE! */
    }

    /* Deleting transaction committed BEFORE our snapshot! */
    return false; /* INVISIBLE (Row is dead to this snapshot) */
}

5. The Cellular Pathology: Read Phenomena & Isolation Levels¶

PostgreSQL implements 3 ANSI SQL Isolation Levels on top of this visibility engine:

1. `READ COMMITTED` (Default)¶

Mechanics: Every single SQL statement in the transaction captures a brand new Snapshot!
Consequence: If Query 1 runs at $t_0$ and Query 2 runs at $t_1$, any transaction committed between $t_0$ and $t_1$ becomes visible in Query 2.
Vulnerable to: Non-repeatable reads and Phantom reads.

2. `REPEATABLE READ`¶

Mechanics: The transaction captures a single Snapshot at the start of the first query and preserves that exact same SnapshotData struct until COMMIT.
Consequence: All queries see the exact same view of historical data.
First-Committer-Wins Rule: If two transactions update the same row concurrently, the second transaction throws an error: ERROR: could not serialize access due to concurrent update.

3. `SERIALIZABLE` (SSI: Serializable Snapshot Isolation)¶

Mechanics: Uses SIREAD Predicate Locks in shared memory (src/backend/storage/lmgr/predicate.c).
Predicate locks do not block reads or writes. They track data dependency overlaps (rw-antidependencies).
If a cycle is detected in the dependency graph (indicating that serial execution ordering is impossible), the engine aborts one of the transactions with: ERROR: could not serialize access due to read/write dependencies among transactions.

Cellular Anatomy of PostgreSQL: MVCC & Tuple Visibility Algorithms¶

1. Introduction: The Quantum Horizon of Database Visibility¶

2. Anatomical Blueprint: SnapshotData¶

Visualizing the Snapshot Window:¶

3. The Commit Log: pg_xact (CLOG) Cellular Bit-Packing¶

The 2-Bit Cellular Packing:¶

The CLOG Lookup Bottleneck:¶

4. The Exact Visibility Algorithm in C (HeapTupleSatisfiesMVCC)¶