03. MVCC & Concurrency Control¶

PostgreSQL achieves multi-version concurrency control (MVCC) without an undo log (unlike InnoDB or Oracle). Instead, updates create a new version of the tuple on the heap, and deletes mark the existing version as expired. Readers never block writers, and writers never block readers.

1. Transaction Identifiers (XIDs) & The Commit Log (`pg_xact`)¶

32-bit Circular Space: Transaction IDs are 32-bit unsigned integers. To prevent exhaustion, PostgreSQL treats numbers as circular modulo $2^{31}$:
For any current XID $X$, half of the space ($2^{31} \approx 2.14$ billion transactions) is in the past, and half is in the future.
Virtual XIDs (vxid): Read-only transactions do not consume a real 32-bit XID; they are assigned a lightweight pair backendId/localTransactionId, conserving global XID numbers.
The Commit Log (pg_xact): Stores the final state of every transaction using 2 bits per XID:
00: IN_PROGRESS
01: COMMITTED
10: ABORTED
11: SUB_COMMITTED Managed in shared memory via a Simple Least-Recently-Used (SLRU) buffer cache.

2. Hint Bits: Eliminating `pg_xact` Bottlenecks¶

Checking pg_xact for every tuple read would create massive shared memory lock contention on the SLRU cache. PostgreSQL solves this via Hint Bits in the tuple's t_infomask:

t_infomask Flags:
├── HEAP_XMIN_COMMITTED  : Inserting transaction has committed
├── HEAP_XMIN_INVALID    : Inserting transaction aborted
├── HEAP_XMAX_COMMITTED  : Deleting transaction has committed
└── HEAP_XMAX_INVALID    : Deleting transaction aborted / not deleted

When a reader accesses a tuple whose hint bits are not yet set: 1. It queries pg_xact to determine the status of t_xmin. 2. It immediately writes the answer (HEAP_XMIN_COMMITTED or HEAP_XMIN_INVALID) directly into the page's t_infomask. 3. Future queries read the hint bits directly from the page without touching pg_xact!

Operational Insight: This is why a simple SELECT * FROM table; can generate dirty buffers and write WAL records immediately after a bulk import!

3. Snapshot Math & Visibility Determination¶

When a transaction executes a query in READ COMMITTED or starts in REPEATABLE READ, it takes a snapshot (SnapshotData):

\[\text{Snapshot} = (\text{xmin} : \text{xmax} : \text{xip\_list})\]

xmin: The lowest XID that was still active when the snapshot was taken. All transactions with $X < \text{xmin}$ have already committed or aborted.
xmax: The highest committed XID $+ 1$. Any transaction with $X \ge \text{xmax}$ was not yet started when the snapshot was taken, and is completely invisible.
xip_list: Array of active transaction IDs between xmin and xmax.

graph LR
    subgraph Past Visible
        T1["T < xmin<br/>(Always Visible if Committed)"]
    end
    subgraph In-Flight Window
        XMIN["xmin"] --- T2["xip_list<br/>(Active: Invisible)"] --- XMAX["xmax"]
    end
    subgraph Future Invisible
        T3["T >= xmax<br/>(Always Invisible)"]
    end

Tuple Visibility Rules¶

For a tuple to be visible to snapshot $S$: 1. t_xmin must be committed, AND: * t_xmin < S.xmin OR (t_xmin < S.xmax AND t_xmin is NOT in S.xip_list). 2. AND t_xmax must be blank, aborted, OR: * t_xmax >= S.xmax OR t_xmax is in S.xip_list (the deleting transaction is still in-flight or in the future).

4. Heap-Only Tuples (HOT): The Write Optimization¶

Normally, updating a tuple requires inserting a new tuple into the heap AND updating every index on the table to point to the new tuple's ctid. This causes massive index bloat.

Heap-Only Tuples (HOT) bypasses index updates when two conditions are met: 1. The UPDATE statement does not modify any indexed column. 2. The page containing the old tuple has sufficient free space to hold the new tuple version.

BEFORE HOT UPDATE:
Index Leaf Page --------> Line Pointer 1 (lp_offset -> Tuple V1)

AFTER HOT UPDATE:
Index Leaf Page --------> Line Pointer 1 (LP_REDIRECT -> Line Pointer 2)
                                                │
                                                ▼
                                         Line Pointer 2 (Tuple V2)

Line Pointer Redirection: Line Pointer 1 is updated to LP_REDIRECT pointing to Line Pointer 2. The index continues pointing to Line Pointer 1.
Pruning: When a reader scans the page, it can collapse dead tuples in the chain and reclaim space without running a full VACUUM!

5. Serializable Snapshot Isolation (SSI)¶

PostgreSQL's SERIALIZABLE isolation level is lock-free. It uses Anti-Dependency Tracking (SIREAD locks) based on the Cahill-Rohr-Fekete theory:

An anti-dependency ($T_1 \xrightarrow{rw} T_2$) occurs when $T_1$ reads a version of data that $T_2$ overwrites.
A serialization anomaly can only occur if there is a cycle containing a pivot transaction with both an incoming and outgoing $rw$-antidependency: $$T_{\text{in}} \xrightarrow{rw} T_{\text{pivot}} \xrightarrow{rw} T_{\text{out}}$$
If PostgreSQL detects this condition, it aborts the pivot transaction with SQLSTATE 40001 (serialization_failure).