PostgreSQL Internals: Heap, Tuples, Shared Buffers, WAL, VACUUM

Everything below is a specific implementation of a general mechanism taught elsewhere in the internals layer. Keep the two apart: "a slotted page" is a concept; "an 8 KB heap page with pd_lower/pd_upper and ItemIdData line pointers" is PostgreSQL. "Multi-version concurrency control" is a concept; "xmin/xmax stamped on the tuple itself, with VACUUM as the garbage collector" is PostgreSQL's choice, and InnoDB made a different one (InnoDB Internals: Clustered Index, Buffer Pool, Redo, Undo, Locks). The matrix is the map; each row is a section of this lesson and names the view or extension that lets you look at the real thing.

A table is a heap: one or more 1 GB files (base/<db>/<relfilenode>, .1, .2 …) of 8 KB pages — 8192 bytes, compiled in, and the unit of every read, write, lock and WAL full-page image. Pages have no order among themselves and rows have no order inside them; a row is identified by its TID (block, offset), which is what ctid shows and what every index leaf stores. Because there is no clustered order, INSERT is cheap — the free-space map names a page with room, and the tuple goes wherever pd_upper allows.

Inside the page: a 24-byte header, a growing array of 4-byte line pointers (ItemIdData) from the front, tuples from the back, and free space between pd_lower and pd_upper. Indexes address the line pointer, never the byte offset, so VACUUM can compact tuples within the page without touching a single index. pd_lsn holds the LSN of the last WAL record that modified the page — recovery compares it to the record it is replaying and skips the page if it is already newer.

Every tuple begins with a 23-byte HeapTupleHeaderData: `t_xmin` — the xid that inserted it; `t_xmax` — the xid that deleted or updated it, or 0; `t_cid` — the command number within that transaction (so a statement does not see its own earlier rows in the same transaction); `t_ctid` — the TID of the next version of this row, or its own TID if it is the latest; `t_infomask`/`t_infomask2` — flag bits; `t_hoff` — where the data starts. The visibility rule a snapshot applies to each tuple is short: xmin must be committed and not in the snapshot's in-progress set; xmax must be 0, aborted, or in progress / after the snapshot. UPDATE is literally DELETE + INSERT with a ctid link between them.

Hint bits save the commit-log lookup: the first transaction to examine a tuple after its xmin committed sets HEAP_XMIN_COMMITTED (or HEAP_XMIN_INVALID), and likewise for xmax. Setting a hint bit dirties the page — the reason a read-only SELECT after a bulk load generates writes. HOT: when an UPDATE changes no indexed column and the new version fits on the same page, the old tuple gets HEAP_HOT_UPDATED, the new one HEAP_ONLY_TUPLE, and no index is touched; the index still points at the chain head, whose line pointer becomes LP_REDIRECT when the head is pruned. Leave 10–20 % free per page (fillfactor = 90) on update-heavy tables and HOT applies far more often.

shared_buffers is a fixed array of 8 KB slots (default 128 MB; 25 % of RAM is the usual starting point) with a hash table from (relfilenode, fork, block) to slot, pin counts, a dirty flag, and clock-sweep replacement — each buffer has a usage count up to 5, decremented as the clock hand passes, evicted at zero (Buffer Replacement: LRU, Clock and Scan Resistance). A sequential scan of a table larger than a quarter of the pool uses a 256 KB ring buffer so it cannot flush the working set. Dirty pages are written by the background writer ahead of demand and by the checkpointer at checkpoints; a backend only writes a page itself when it must evict a dirty one. Underneath sits the kernel page cache, so a "miss" in pg_stat_database.blks_read is often still a memory read; pg_stat_io (16+) separates the two.

The default index is nbtree, a Lehman–Yao B-tree: every page carries a right-link to its sibling and a high key bounding what it may contain, so a reader that arrives at a page just split can step right instead of restarting, and only one page needs to be locked at a time. Leaves hold (key, TID) items; internal pages hold (separator, child block). Fanout for an 8-byte key is roughly 400 per page, so three levels cover ~64 million rows and the root and inner level are always in shared buffers. Since PostgreSQL 12 the heap TID is a trailing key column, which makes duplicate keys ordered and lets 13+ deduplicate equal keys into posting lists; 14+ bottom-up deletion removes index entries for dead tuples on the way to a split, blunting the non-HOT-update bloat problem.

Transaction ids are 32-bit and allocated from a global counter (pg_current_xact_id()); a read-only transaction takes none. Comparison is circular: xid A is "older" than B if it lies in the 2³¹ ids before B. That works only while no visible tuple is more than ~2 billion transactions old — beyond that its xmin would appear to be in the future and the row would vanish. VACUUM prevents it by freezing: any tuple whose xmin is older than vacuum_freeze_min_age (50 M by default) gets HEAP_XMIN_FROZEN and is thereafter visible to every snapshot. Once a table's oldest unfrozen xid reaches autovacuum_freeze_max_age (200 M), an anti-wraparound autovacuum runs whether or not the table is otherwise busy.

If freezing cannot keep up — VACUUM disabled, a table too large to finish, a prepared transaction or replication slot pinning the horizon — the server first warns at 40 M xids of headroom, then at ~3 M refuses new xids entirely and must be vacuumed in single-user mode. The metric to graph is age(datfrozenxid) per database and age(relfrozenxid) per table; 64-bit xids exist only in the per-page epoch and in xid8, not in tuple headers. Multixact ids (used when several transactions lock one row) have their own 32-bit space and their own wraparound.

Every change to a page is first described by a WAL record appended to pg_wal/ in 16 MB segments; the record's address is its LSN — a 64-bit byte position, printed as 0/1A2B3C4. The rule is the general one (Write-Ahead Logging): the record must be on disk before the page it describes, and COMMIT returns only after the commit record is flushed (synchronous_commit = on; off trades a few hundred milliseconds of durability for a large throughput gain on small transactions). Each page stores the LSN of its last change in pd_lsn, which is how a buffer knows it may not be written before the WAL up to that LSN is.

A checkpoint (every checkpoint_timeout, default 5 min, or when max_wal_size fills) writes all dirty buffers, then records the redo point in pg_control; recovery starts there and replays forward. The first modification of a page after a checkpoint writes a full-page image into WAL (full_page_writes) so a torn 8 KB page can be reconstructed — the reason WAL volume spikes right after each checkpoint and the reason InnoDB needed a doublewrite buffer instead. LSNs are the coordinate system for everything else: replication lag is a difference of two LSNs (Replication Internals: WAL Shipping, LSNs, Lag and Failover), pg_rewind finds the divergence point by LSN, and backups are consistent up to an LSN.

VACUUM walks a table's pages (skipping all-visible ones via the visibility map), prunes HOT chains, marks dead tuples' line pointers LP_DEAD after removing their index entries, compacts each page, updates the free-space map so INSERT can find room, freezes old xids, and records the results in pg_stat_user_tables. It does not shrink the file except for empty pages at the very end; VACUUM FULL rewrites the table under an exclusive lock and is the answer to bloat, not to routine maintenance. The single limit on what VACUUM may remove is the oldest snapshot still running anywhere — pg_stat_activity.backend_xmin — which is why one forgotten idle in transaction session bloats every table in the database.

Autovacuum launches a worker for a table when n_dead_tup > threshold + scale_factor × n_live_tup (defaults 50 + 20 %), or when freeze age demands it; it is throttled by autovacuum_vacuum_cost_delay, which is why it can fall behind a write-heavy table and why the fix is per-table settings (PostgreSQL in Production: Connections, VACUUM, Partitioning, Replication). The same worker runs ANALYZE on a 10 % threshold: it samples 300 × default_statistics_target rows (30,000 at the default 100) and writes per-column null_frac, n_distinct, most-common values with frequencies, a histogram of the rest, and correlation between column order and physical order — the number that decides whether an index range scan is treated as sequential or random I/O. Every estimate in EXPLAIN comes from this table; when rows= in the plan and actual rows= disagree by 100×, pg_stats is where to look first (Cost-Based Optimization).