The idea: commit status is stored once, outside the rows

Every PostgreSQL tuple carries xmin, the id of the transaction (xid) that inserted it. The tuple does not say whether that transaction committed. That answer is kept in one place for all rows: pg_xact, also called the CLOG (commit log). A COMMIT therefore touches no table page at all; it flips two bits in pg_xact. A reader that meets a tuple with an unknown xmin looks the xid up there, then writes the answer into the tuple header as a hint bit so the next reader does not have to ask again.

A heap tuple with xmin 100 and no hint bits: the reader asks pg_xact, whose cell for xid 100 holds 01 = committed, and then sets HEAP_XMIN_COMMITTED in the tuple header. A second reader sees the hint bit and skips pg_xact.
The first reader pays for a pg_xact lookup and leaves a hint bit in the tuple; every later reader uses the hint.

pg_xact: 2 bits per transaction

pg_xact is an array indexed by xid with 2 bits per xid, so one 8 KB page covers 32,768 transactions:

bitsstatusset by
00in progressthe default: a new page is zero-filled when xids reach it
01committedCOMMIT, after its WAL record is flushed
10abortedROLLBACK, an error, or crash recovery for xids that never committed
11sub-committeda subtransaction (SAVEPOINT) during its parent's commit

The pages live in files pg_xact/0000, 0001, … and are cached in shared memory by the SLRU (simple least-recently-used) buffer manager, a small cache separate from shared_buffers. A dirty pg_xact page is written at the next checkpoint (CheckPointCLOG), like a dirty heap page. Old pages are deleted once every xid on them is older than the oldest unfrozen xid (see XID wraparound).

What COMMIT does, in order

The order matters, and the canvas highlights each step (Demo: commit, then read twice):

  1. Append a COMMIT record to the WAL and flush it (XLogFlush, an fsync). This is the moment the transaction becomes durable.
  2. Set the xid's bits in pg_xact to 01 (TransactionIdCommitTree). A crash between steps 1 and 2 is harmless: recovery replays the COMMIT record and sets the bits.
  3. Remove the xid from the ProcArray, the shared list of running transactions. Only now can a new snapshot treat it as finished.

Because step 3 comes last, a reader that sees an xid as "not running" can trust pg_xact to hold the final answer. The data pages are not touched: the new tuples still have no hint bits.

Time runs down. Session A: INSERT writes the tuple with xmin 100. COMMIT: 1, the COMMIT record is flushed to pg_wal; 2, pg_xact bits for 100 become 01; 3, xid 100 leaves the ProcArray. Session B: a SELECT before step 3 has 100 in its snapshot and does not see the row; a SELECT after step 3 looks up pg_xact and sees it.
WAL flush, then pg_xact, then the ProcArray: a snapshot never sees an xid as finished before its commit is durable and recorded.

The visibility check for xmin

For each tuple, the xmin half of HeapTupleSatisfiesMVCC asks, in order:

  1. Hint bit set? HEAP_XMIN_COMMITTED means committed, HEAP_XMIN_INVALID means aborted. No lookup.
  2. Is xmin in my snapshot's running list (xip) or ≥ its xmax? Then the tuple is invisible to me, whatever happens later. No lookup, and no hint bit: the answer is not final yet (Demo: read while the INSERT is still running).
  3. Otherwise ask pg_xact (TransactionIdDidCommit), and store the answer as a hint bit.

A committed hint does not make a tuple visible to an older snapshot: step 2's snapshot test still applies to hinted tuples. The hint only replaces the pg_xact lookup.

Hint bits and the first SELECT after a load

Hint bits are bits in the tuple header's t_infomask. Setting one changes the page, so the buffer is marked dirty, and some later write (a checkpoint, the background writer, or a backend evicting the page) must write it again. That is why the first SELECT after a bulk load can cause as much write I/O as the load itself: every tuple is hinted once, by whoever reads it first (Demo: first SELECT after a bulk load writes: two writes of the same page, one before and one after the SELECT). VACUUM right after a load sets the hints (and freezes, with VACUUM FREEZE) in one planned pass instead.

A hint-bit change is not WAL-logged on its own: if the page is lost, the hint can simply be set again. With data_checksums or wal_log_hints = on, the first hint-bit change after a checkpoint writes a full-page image to the WAL, so a torn page cannot fail its checksum. That makes the first read after a load also write WAL.

ROLLBACK: no undo

PostgreSQL has no undo log. A ROLLBACK writes an ABORT record (without waiting for its flush, since losing it means the same thing) and sets the xid's bits to 10. Its tuples stay in the heap exactly where they were written; they are dead only because pg_xact says the inserter aborted. The first reader sets HEAP_XMIN_INVALID on them, and VACUUM reclaims the space later (Demo: aborted INSERT). Compare InnoDB, which rolls rows back from its undo log (How MySQL Runs a Query).

See also How PostgreSQL Runs a Query, MVCC and isolation levels, the 8 KB heap page, WAL internals, checkpoints and the shared buffer pool.

For the InnoDB side (undo log, purge, history list), see InnoDB undo logs, read views and purge.

What the page leaves out

The page checks only xmin; deletes and updates set xmax, which has its own hints (HEAP_XMAX_COMMITTED, HEAP_XMAX_INVALID) and can be a lock-only xid or a MultiXact. Subtransactions use the 11 state and pg_subtrans to map a child xid to its parent. With synchronous_commit = off the commit record may not be flushed yet, so a reader may not set HEAP_XMIN_COMMITTED until the WAL is flushed past the commit LSN. Freezing replaces old xids with "frozen" so pg_xact can be truncated. Real SLRU caches hold many pages (transaction_buffers), and a backend checks its own xid (TransactionIdIsCurrentTransactionId) before the snapshot test. The visibility map, index-only scans and VACUUM are elsewhere.