How PostgreSQL Stores a Row

Every database gives you a row and every database lies a little about what that row is. MySQL gives you a record copied into a row buffer. SQLite gives you a record in a b-tree leaf. PostgreSQL gives you something stranger and more interesting: a 23-byte header followed by a payload, living at some byte offset on an 8 kB page, reached through a 4-byte indirection that lives in a completely different part of that same page.

That indirection is the reason PostgreSQL can move tuples around during VACUUM without invalidating a single index entry. The header is the reason an UPDATE can leave a trail of old versions behind. The slotted page is the reason a table’s rows are not laid out contiguously — and why reclaiming the space left behind by dead rows is a whole subsystem.

This is a walk through how it all works, based on reading the PostgreSQL source (version 20devel, commit e75fcc9867f).

A row is not a record

Let’s start with the container. PostgreSQL stores a table as an array of fixed-size pages — 8 kB by default, configurable at initdb time. The heap access method never stores anything that isn’t on a page, and it never stores a row that spans two pages. A row that doesn’t fit in 8 kB gets pushed out of line entirely (more on that later).

Each page is a slotted page. From src/include/storage/bufpage.h:

/*
 * a postgres disk page is always a slotted page of the form:
 *
 * +----------------+---------------------------------+
 * | PageHeaderData | linp1 linp2 linp3 ...           |
 * +-----------+----+---------------------------------+
 * | ... linpN |									  |
 * +-----------+--------------------------------------+
 * |		   ^ pd_lower							  |
 * |												  |
 * |			 v pd_upper							  |
 * +-------------+------------------------------------+
 * |			 | tupleN ...                         |
 * +-------------+------------------+-----------------+
 * |	   ... tuple3 tuple2 tuple1 | "special space" |
 * +--------------------------------+-----------------+
 *									^ pd_special
 */

Five parts, and they grow in opposite directions:

The header is small enough to write out in full:

typedef struct PageHeaderData
{
	PageXLogRecPtr pd_lsn;		/* LSN: next byte after last byte of xlog
								 * record for last change to this page */
	uint16		pd_checksum;	/* checksum */
	uint16		pd_flags;		/* flag bits, see below */
	LocationIndex pd_lower;		/* offset to start of free space */
	LocationIndex pd_upper;		/* offset to end of free space */
	LocationIndex pd_special;	/* offset to start of special space */
	uint16		pd_pagesize_version;
	TransactionId pd_prune_xid; /* oldest prunable XID, or zero if none */
	ItemIdData	pd_linp[FLEXIBLE_ARRAY_MEMBER]; /* line pointer array */
} PageHeaderData;

pd_lower and pd_upper are the entire free-space bookkeeping. pd_lower marks the end of the line pointer array, pd_upper marks the start of the tuple area; the gap between them is what’s available. There is no free-list, no extent map, no per-page allocation structure. Free space is just an interval, and it is used from both ends.

A heap page has pd_special == BLCKSZ, because the “special space” is where an index access method stashes its own per-page state. A btree leaf page, for instance, ends with a BTPageOpaqueData holding the sibling links and the tree level. Heap pages have nothing to say for themselves.

Line pointers: the indirection that makes everything possible

The line pointer array is where the “row” abstraction starts to leak. Each entry is four bytes (src/include/storage/itemid.h):

typedef struct ItemIdData
{
	unsigned	lp_off:15,		/* offset to tuple (from start of page) */
				lp_flags:2,		/* state of line pointer, see below */
				lp_len:15;		/* byte length of tuple */
} ItemIdData;

Fifteen bits of byte offset, fifteen bits of length, two bits of state. lp_flags has four values:

#define LP_UNUSED		0		/* unused (should always have lp_len=0) */
#define LP_NORMAL		1		/* used (should always have lp_len>0) */
#define LP_REDIRECT		2		/* HOT redirect (should have lp_len=0) */
#define LP_DEAD			3		/* dead, may or may not have storage */

Note the convention, stated in the header comment: by convention lp_len == 0 in every line pointer that does not have storage, independently of its lp_flags state. A line pointer can be “in use” and still point at nothing. That is the whole trick.

So a row is addressed by a TID — a tuple identifier — which is a (block number, offset number) pair. The block number says which page; the offset number says which line pointer. The line pointer then says which byte range the tuple occupies. Three levels of addressing, and only the last one is a physical location.

This indirection is not incidental. It’s what lets VACUUM slide tuples around within a page, or move them between pages, and leave every index entry untouched — the index stores a TID, and the TID still resolves to the right line pointer, and the line pointer has been updated to point at the tuple’s new home.

Two details worth knowing:

• The number of line pointers is derived, not stored. It is (pd_lower - SizeOfPageHeaderData) / sizeof(ItemIdData). There’s no counter; the array simply grows.
• A line pointer’s lp_off is overloaded. For LP_NORMAL it’s a byte offset. For LP_REDIRECT it’s the offset number of another line pointer on the same page. Same field, completely different meaning.

The tuple header: 23 bytes

Now the header at the front of every heap tuple (src/include/access/htup_details.h):

struct HeapTupleHeaderData
{
	union
	{
		HeapTupleFields t_heap;
		DatumTupleFields t_datum;
	}			t_choice;

	ItemPointerData t_ctid;		/* current TID of this or newer tuple (or a
								 * speculative insertion token) */

	/* Fields below here must match MinimalTupleData! */

#define FIELDNO_HEAPTUPLEHEADERDATA_INFOMASK2 2
	uint16		t_infomask2;	/* number of attributes + various flags */

#define FIELDNO_HEAPTUPLEHEADERDATA_INFOMASK 3
	uint16		t_infomask;		/* various flag bits, see below */

#define FIELDNO_HEAPTUPLEHEADERDATA_HOFF 4
	uint8		t_hoff;			/* sizeof header incl. bitmap, padding */

	/* ^ - 23 bytes - ^ */

#define FIELDNO_HEAPTUPLEHEADERDATA_BITS 5
	uint8		t_bits[FLEXIBLE_ARRAY_MEMBER];	/* bitmap of NULLs */

	/* MORE DATA FOLLOWS AT END OF STRUCT */
};

Twenty-three bytes. Here is what each byte is doing, on a 64-bit machine with MAXIMUM_ALIGNOF == 8:

ItemPointerData is six bytes, not eight, and it gets there by fiat:

/* If compiler understands packed and aligned pragmas, use those */
#if defined(pg_attribute_packed) && defined(pg_attribute_aligned)
			pg_attribute_packed()
			pg_attribute_aligned(2)
#endif
ItemPointerData;

The comment above it explains why: “because there is an item pointer in each tuple header and index tuple header on disk, it’s very important not to waste space with structure padding bytes.” Two bytes saved here, on every row, forever.

Five virtual fields in three physical ones

The header stores five logical fields — Xmin, Cmin, Xmax, Cmax, Xvac — in three physical slots. From the header comment:

We store five “virtual” fields Xmin, Cmin, Xmax, Cmax, and Xvac in three physical fields. Xmin and Xmax are always really stored, but Cmin, Cmax and Xvac share a field. This works because we know that Cmin and Cmax are only interesting for the lifetime of the inserting and deleting transaction respectively.

Cmin and Cmax are command IDs — counters that order the statements within a single transaction. If the same transaction inserts and then deletes a row, both values have to survive. PostgreSQL solves this with a “combo CID”: a synthetic value that maps back to both, using local state in the originating backend. The HEAP_COMBOCID bit in t_infomask says “this field is a combo”.

Before 8.3, HeapTupleHeaderData had separate cmin and cmax fields. Removing one 4-byte field from every row in every table was worth the combo-CID machinery.

t_infomask

Sixteen bits, split into two groups. The low four describe the physical contents of the tuple:

#define HEAP_HASNULL			0x0001	/* has null attribute(s) */
#define HEAP_HASVARWIDTH		0x0002	/* has variable-width attribute(s) */
#define HEAP_HASEXTERNAL		0x0004	/* has external stored attribute(s) */
#define HEAP_HASOID_OLD			0x0008	/* has an object-id field */

The upper twelve are about visibility — who can see this row, and what happened to it:

#define HEAP_XMAX_KEYSHR_LOCK	0x0010	/* xmax is a key-shared locker */
#define HEAP_COMBOCID			0x0020	/* t_cid is a combo CID */
#define HEAP_XMAX_EXCL_LOCK		0x0040	/* xmax is exclusive locker */
#define HEAP_XMAX_LOCK_ONLY		0x0080	/* xmax, if valid, is only a locker */

#define HEAP_XMIN_COMMITTED		0x0100	/* t_xmin committed */
#define HEAP_XMIN_INVALID		0x0200	/* t_xmin invalid/aborted */
#define HEAP_XMIN_FROZEN		(HEAP_XMIN_COMMITTED|HEAP_XMIN_INVALID)
#define HEAP_XMAX_COMMITTED		0x0400	/* t_xmax committed */
#define HEAP_XMAX_INVALID		0x0800	/* t_xmax invalid/aborted */
#define HEAP_XMAX_IS_MULTI		0x1000	/* t_xmax is a MultiXactId */
#define HEAP_UPDATED			0x2000	/* this is UPDATEd version of row */
#define HEAP_MOVED_OFF			0x4000	/* moved to another place by pre-9.0
										 * VACUUM FULL; kept for binary
										 * upgrade support */
#define HEAP_MOVED_IN			0x8000	/* moved from another place by pre-9.0
										 * VACUUM FULL; kept for binary
										 * upgrade support */

HEAP_XMIN_COMMITTED and friends are hint bits. They cache a fact that could otherwise require looking up the transaction’s commit record in CLOG. Once a reader has established that the inserting transaction committed, it stamps the tuple and everyone afterwards gets the answer for free. The rules are conservative — a hint is only set when the answer is known-good — and the code is careful never to set a hint that would be wrong if the buffer is later written to disk:

	if (TransactionIdIsValid(xid))
	{
		if (BufferIsPermanent(buffer))
		{
			/* NB: xid must be known committed here! */
			XLogRecPtr	commitLSN = TransactionIdGetCommitLSN(xid);

			if (XLogNeedsFlush(commitLSN) &&
				BufferGetLSNAtomic(buffer) < commitLSN)
			{
				/* not flushed and no LSN interlock, so don't set hint */
				return;
			}
		}
	}

Notice the subtlety: if the commit record isn’t on disk yet, the hint isn’t set, because the page might reach disk before the commit record does, and then a crash would leave a tuple claiming to be committed when it isn’t.

t_infomask2

#define HEAP_NATTS_MASK			0x07FF	/* 11 bits for number of attributes */
/* bits 0x1800 are available */
#define HEAP_KEYS_UPDATED		0x2000	/* tuple was updated and key cols
										 * modified, or tuple deleted */
#define HEAP_HOT_UPDATED		0x4000	/* tuple was HOT-updated */
#define HEAP_ONLY_TUPLE			0x8000	/* this is heap-only tuple */

The low eleven bits hold the attribute count, which is why t_infomask2 is a uint16 and the number of columns is limited. The other three bits carry the HOT state machine, which we will come back to.

The null bitmap and the 23/24 trick

HEAP_HASNULL in t_infomask means a null bitmap is present, immediately after the fixed header, one bit per column:

static inline int
BITMAPLEN(int NATTS)
{
	return (NATTS + 7) / 8;
}

The bitmap is inverted — a 1 bit means not null:

/*
 * Check a tuple's null bitmap to determine whether the attribute is null.
 * Note that a 0 in the null bitmap indicates a null, while 1 indicates
 * non-null.
 */
static inline bool
att_isnull(int ATT, const uint8 *BITS)
{
	return !(BITS[ATT >> 3] & (1 << (ATT & 0x07)));
}

Attribute 0 is the low bit of byte 0. (This is the sort of detail that makes hand-parsing a heap page a mildly masochistic exercise. The pageinspect extension exists for a reason.)

Now, t_hoff is the offset from the start of the tuple to the first byte of user data, and it must be a multiple of MAXALIGN — 8 bytes on a 64-bit machine. The reason is that the data area must be 8-byte aligned so that fetchatt() can do a direct aligned load of an int8 or double column.

The calculation, in heap_form_tuple() (src/backend/access/common/heaptuple.c):

	len = offsetof(HeapTupleHeaderData, t_bits);

	if (hasnull)
		len += BITMAPLEN(numberOfAttributes);

	hoff = len = MAXALIGN(len); /* align user data safely */

offsetof(HeapTupleHeaderData, t_bits) is 23. So:

• No NULLs: len = 23 → MAXALIGN(23) = 24 → t_hoff = 24. Byte 23 is pure padding.
• 1–8 columns, some NULL: len = 23 + 1 = 24 → MAXALIGN(24) = 24 → t_hoff = 24. The bitmap lands exactly in the padding byte.
• 9–16 columns, some NULL: len = 23 + 2 = 25 → MAXALIGN(25) = 32 → t_hoff = 32. Seven bytes of padding.

So the header is a 23-byte struct that behaves like a 24-byte header. The one-byte discrepancy is deliberate: a 24-byte header is 8-byte aligned, so the data area inherits that alignment for free, and any 4-byte-aligned field inside it is also correctly aligned. Had the header been 24 bytes and the bitmap 1 byte, the data would start at 25 — unaligned.

There is a hard limit hiding here. t_hoff is a uint8, so it can hold at most 255. The comment in htup_details.h spells out the constraint:

The key limit on this value is that the size of the fixed overhead for a tuple, plus the size of the null-values bitmap (at 1 bit per column), plus MAXALIGN alignment, must fit into t_hoff which is uint8. On most machines the upper limit without making t_hoff wider would be a little over 1700.

Which is why MaxTupleAttributeNumber is 1664 and MaxHeapAttributeNumber is 1600. PostgreSQL’s real column limit is a storage-layout limit, not an arbitrary one.

The data area

After t_hoff come the column values, packed in attribute order. The rules come out of fill_val() in heaptuple.c:

1. NULL columns cost zero bytes. fill_val sets the bitmap bit and returns before writing any data. The space is genuinely not reserved.
2. By-value columns (int4, bool, oid, …) are aligned to their attalign and stored inline.
3. Fixed-length by-reference columns (numeric, uuid, …) are aligned and copied inline.
4. Short varlena (a text of 126 bytes or less) gets no alignment padding at all — it can sit at any byte offset.
5. Full 4-byte-header varlena is aligned, because the 4-byte length word must be naturally aligned.
6. cstring (attlen == -2) never needs alignment.

The interesting one is #4. Here is the code:

		else if (VARATT_IS_SHORT(val))
		{
			/* no alignment for short varlenas */
			data_length = VARSIZE_SHORT(val);
			memcpy(data, val, data_length);
		}
		else if (att->attispackable && VARATT_CAN_MAKE_SHORT(val))
		{
			/* convert to short varlena -- no alignment */
			data_length = VARATT_CONVERTED_SHORT_SIZE(val);
			SET_VARSIZE_SHORT(data, data_length);
			memcpy(data + 1, VARDATA(val), data_length - 1);
		}
		else
		{
			/* full 4-byte header varlena */
			data = (char *) att_nominal_alignby(data, att->attalignby);
			data_length = VARSIZE(val);
			memcpy(data, val, data_length);
		}

A text value whose payload is 126 bytes or less is stored with a one-byte header and needs no padding. A payload of 127 bytes cannot be short — the limit is VARATT_SHORT_MAX (0x7F) — so it falls back to the 4-byte-header format, which is aligned, and the value suddenly costs several bytes more than the one below it. It is a real, if obscure, discontinuity in the space cost of text columns.

Variable-length values: the four header formats

Every variable-length value shares the varlena concept, but there are four on-disk encodings, distinguished by the low bits of the first header byte (src/include/varatt.h):

typedef struct
{
	struct						/* Normal varlena (4-byte length) */
	{
		uint32		va_header;
		char		va_data[FLEXIBLE_ARRAY_MEMBER];
	}			va_4byte;
	struct						/* Compressed-in-line format */
	{
		uint32		va_header;
		uint32		va_tcinfo;	/* Original data size (excludes header) and
								 * compression method; see va_extinfo */
		char		va_data[FLEXIBLE_ARRAY_MEMBER]; /* Compressed data */
	}			va_compressed;
} varattrib_4b;

typedef struct
{
	uint8		va_header;
	char		va_data[FLEXIBLE_ARRAY_MEMBER]; /* Data begins here */
} varattrib_1b;

typedef struct
{
	uint8		va_header;		/* Always 0x80 or 0x01 */
	uint8		va_tag;			/* Type of datum */
	char		va_data[FLEXIBLE_ARRAY_MEMBER]; /* Type-specific data */
} varattrib_1b_e;

• 4-byte header — the general case. The header stores the length in its upper 30 bits and flags in the low bits (compressed / external).
• 1-byte header — the “short” format, for payloads up to VARATT_SHORT_MAX (0x7F = 127) bytes. One bit of the header is reserved as a flag; the other seven hold the length.
• 1-byte header + tag — the external (TOAST pointer) format. Also a one-byte header, so TOAST pointers cost no alignment.

TOAST: when a row doesn’t fit

A tuple can be at most MaxHeapTupleSize:

#define MaxHeapTupleSize  (BLCKSZ - MAXALIGN(SizeOfPageHeaderData + sizeof(ItemIdData)))

With BLCKSZ 8192, a 24-byte page header and a 4-byte line pointer, that’s 8192 − 32 = 8160 bytes.

But TOAST kicks in much earlier. From src/include/access/heaptoast.h:

/*
 * Find the maximum size of a tuple if there are to be N tuples per page.
 */
#define MaximumBytesPerTuple(tuplesPerPage) \
	MAXALIGN_DOWN((BLCKSZ - \
				   MAXALIGN(SizeOfPageHeaderData + (tuplesPerPage) * sizeof(ItemIdData))) \
				  / (tuplesPerPage))

#define TOAST_TUPLES_PER_PAGE	4

#define TOAST_TUPLE_THRESHOLD	MaximumBytesPerTuple(TOAST_TUPLES_PER_PAGE)

#define TOAST_TUPLE_TARGET		TOAST_TUPLE_THRESHOLD

TOAST_TUPLE_THRESHOLD works out to 2032 bytes: the largest tuple such that four of them fit on a page. If a tuple exceeds that, the toaster takes over.

The toaster’s strategy, in order:

1. Compress every compressible column, in place. Compression is tried per-column, and a column is only kept compressed if it actually got smaller. A text column that compresses to 40% of its size stays compressed inline, with a 4-byte header that records both the compressed length and the original length.
2. Move EXTENDED and EXTERNAL columns out of line into the table’s TOAST table, replacing them in the row with an 18-byte pointer.
3. As a last resort, move PLAIN and MAIN columns out of line too, up to TOAST_TUPLE_TARGET_MAIN (8160 bytes — the largest tuple that fits on a page at all). The user said “keep this inline if at all possible”, so this only happens when nothing else works.

The TOAST pointer itself is the varattrib_1b_e format: a one-byte header, a tag byte, and a payload:

typedef struct varatt_external_oid
{
	int32		va_rawsize;		/* Original data size (includes header) */
	uint32		va_extinfo;		/* External saved size (without header) and
								 * additional flag bits */
	Oid			va_valueid;		/* Unique ID of value within TOAST table */
	Oid			va_toastrelid;	/* RelID of TOAST table containing it */
} varatt_external_oid;

The key design decision: the pointer identifies the value by (toast table, value id), not by the physical location of the row that contains it. That is what makes TOAST pointers relocatable — a row can be moved by VACUUM FULL, CLUSTER, or ALTER TABLE ... SET TABLESPACE without rewriting its out-of-line data.

The TOAST table

Every table with toastable columns gets a companion table named pg_toast_<oid>, created in src/backend/catalog/toasting.c:

	tupdesc = CreateTemplateTupleDesc(3);
	TupleDescInitEntry(tupdesc, (AttrNumber) 1,
					   "chunk_id",
					   toast_chunkid_typid,
					   -1, 0);
	TupleDescInitEntry(tupdesc, (AttrNumber) 2,
					   "chunk_seq",
					   INT4OID,
					   -1, 0);
	TupleDescInitEntry(tupdesc, (AttrNumber) 3,
					   "chunk_data",
					   BYTEAOID,
					   -1, 0);

Three columns: an identifier for the value, a chunk sequence number, and the chunk payload. Large values are split across multiple rows.

The chunk size is bounded by what has to fit on a page:

#define TOAST_OID_MAX_CHUNK_SIZE	\
	(EXTERN_TUPLE_MAX_SIZE -							\
	 MAXALIGN(SizeofHeapTupleHeader) -					\
	 sizeof(Oid) -										\
	 sizeof(int32) -									\
	 VARHDRSZ)

EXTERN_TUPLE_MAX_SIZE is MaximumBytesPerTuple(4) = 2032, so the chunk payload is 2032 − 24 − 4 − 4 − 4 = 1996 bytes for an oid value id (and 1992 for the oid8 variant).

One last detail that is easy to miss:

	/*
	 * Ensure that the toast table doesn't itself get toasted, or we'll be
	 * toast :-(.  This is essential for chunk_data because type bytea is
	 * toastable; hit the other two just to be sure.
	 */
	TupleDescAttr(tupdesc, 0)->attstorage = TYPSTORAGE_PLAIN;
	TupleDescAttr(tupdesc, 1)->attstorage = TYPSTORAGE_PLAIN;
	TupleDescAttr(tupdesc, 2)->attstorage = TYPSTORAGE_PLAIN;

The TOAST table is explicitly not toastable. A row cannot contain a pointer to a value that lives in a table that itself contains pointers to values.

UPDATE: the version chain

Now that we know what a tuple looks like, we can see what an UPDATE does. PostgreSQL never modifies a row in place (with one narrow exception for system catalogs). It writes a new version and links the old one to it.

The link is t_ctid. From the header comment:

A word about t_ctid: whenever a new tuple is stored on disk, its t_ctid is initialized with its own TID (location). If the tuple is ever updated, its t_ctid is changed to point to the replacement version of the tuple.

So t_ctid is either a self-reference (this is the newest version) or a pointer to a successor. The header comment also warns about the obvious hazard:

Beware however that VACUUM might erase the pointed-to (newer) tuple before erasing the pointing (older) tuple. Hence, when following a t_ctid link, it is necessary to check to see if the referenced slot is empty or contains an unrelated tuple. Check that the referenced tuple has XMIN equal to the referencing tuple’s XMAX to verify that it is actually the descendant version.

That XMIN/XMAX check is the chain-integrity test, and it appears everywhere — in the index scan, in the pruner, and in the row-locking code. It’s how a reader knows it hasn’t followed a link into a recycled slot.

The actual update, in heap_update() (src/backend/access/heap/heapam.c):

	newtup->t_data->t_infomask &= ~(HEAP_XACT_MASK);
	newtup->t_data->t_infomask2 &= ~(HEAP2_XACT_MASK);
	HeapTupleHeaderSetXmin(newtup->t_data, xid);
	HeapTupleHeaderSetCmin(newtup->t_data, cid);
	newtup->t_data->t_infomask |= HEAP_UPDATED | infomask_new_tuple;
	newtup->t_data->t_infomask2 |= infomask2_new_tuple;
	HeapTupleHeaderSetXmax(newtup->t_data, xmax_new_tuple);

The new version gets the updater’s XID as its xmin. Then, at the very end of the operation, the old version is finalized:

	/* Clear obsolete visibility flags, possibly set by ourselves above... */
	oldtup.t_data->t_infomask &= ~(HEAP_XMAX_BITS | HEAP_MOVED);
	oldtup.t_data->t_infomask2 &= ~HEAP_KEYS_UPDATED;
	/* ... and store info about transaction updating this tuple */
	Assert(TransactionIdIsValid(xmax_old_tuple));
	HeapTupleHeaderSetXmax(oldtup.t_data, xmax_old_tuple);
	oldtup.t_data->t_infomask |= infomask_old_tuple;
	oldtup.t_data->t_infomask2 |= infomask2_old_tuple;
	HeapTupleHeaderSetCmax(oldtup.t_data, cid, iscombo);

	/* record address of new tuple in t_ctid of old one */
	oldtup.t_data->t_ctid = heaptup->t_self;

One line — oldtup.t_data->t_ctid = heaptup->t_self — is the entire mechanism of MVCC at the storage layer. The old version records where its successor lives, and the old version’s xmax records who did the update.

Notice also HEAP_XMAX_BITS, which is masked out before the new value is written:

#define HEAP_XMAX_BITS (HEAP_XMAX_COMMITTED | HEAP_XMAX_INVALID | \
						HEAP_XMAX_IS_MULTI | HEAP_LOCK_MASK | HEAP_XMAX_LOCK_ONLY)

Everything about xmax is recomputed from scratch on every write, because the lock state can change independently of the row’s identity.

Visibility: the rule

Visibility is decided by HeapTupleSatisfiesMVCC(), and the rule is compact:

the tuple is visible iff xmin is committed-and-not-in-snapshot AND (xmax is invalid / lock-only / in-snapshot-and-not-committed)

The Cmin/Cmax comparison against the snapshot’s curcid is what distinguishes “my own earlier command updated this row” from “my own later command will update this row” — the TM_SelfModified versus TM_Invisible split. And one detail that is easy to miss:

	if (tuple->t_infomask & HEAP_XMAX_COMMITTED)
	{
		if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
			return TM_Ok;
		if (!ItemPointerEquals(&htup->t_self, &tuple->t_ctid))
			return TM_Updated;	/* updated by other */
		else
			return TM_Deleted;	/* deleted by other */
	}

The same t_ctid field that carries the HOT chain also distinguishes UPDATE from DELETE. t_ctid != t_self means “this version was updated”; t_ctid == t_self means “this version was deleted”. One field, two questions, answered by the same comparison.

HOT: updating without touching the index

The obvious cost of an UPDATE is that it creates a new index entry for the new version. Heap-Only Tuples avoid that. From the manual:

To help reduce the overhead of updates, PostgreSQL has an optimization called heap-only tuples (HOT).

HOT applies when both of these hold:

• The update does not modify any column referenced by an index (excluding summarizing indexes like BRIN).
• There is sufficient free space on the page containing the old row.

Then the new version is written to the same page, no index entry is created, and the chain is walked from the root tuple via t_ctid. The flags make this possible:

	if (use_hot_update)
	{
		/* Mark the old tuple as HOT-updated */
		HeapTupleSetHotUpdated(&oldtup);
		/* And mark the new tuple as heap-only */
		HeapTupleSetHeapOnly(heaptup);
		/* Mark the caller's copy too, in case different from heaptup */
		HeapTupleSetHeapOnly(newtup);
	}

HEAP_HOT_UPDATED marks the predecessor (“my successor is heap-only”); HEAP_ONLY_TUPLE marks the successor (“no index entry points at me”). The chain looks like this:

  btree index entry ──► (blk, offnum=1)   root tuple
                                    t_ctid = (blk, offnum=2)
                                    t_infomask2 |= HEAP_HOT_UPDATED
                        lp[2] ──► version 2
                                    t_ctid = (blk, offnum=3)
                                    t_infomask2 |= HEAP_HOT_UPDATED
                        lp[3] ──► version 3
                                    t_ctid = (blk, offnum=3)   (self — end)
                                    t_infomask2 |= HEAP_ONLY_TUPLE

The reader follows the chain in heap_hot_search_buffer() (src/backend/access/heap/heapam_indexscan.c):

		/* Check to see if HOT chain continues past this tuple; if so fetch
		 * the next offnum and loop around.
		 */
		if (HeapTupleIsHotUpdated(heapTuple))
		{
			Assert(ItemPointerGetBlockNumber(&heapTuple->t_data->t_ctid) ==
				   blkno);
			offnum = ItemPointerGetOffsetNumber(&heapTuple->t_data->t_ctid);
			at_chain_start = false;
			prev_xmax = HeapTupleHeaderGetUpdateXid(heapTuple->t_data);
		}
		else
			break;				/* end of chain */

Note the assertion: a HOT chain never crosses a page boundary. The successor is always in the same block. That is why HOT requires free space on the same page — a chain that hopped pages would need a different mechanism to find the next version.

The chain-integrity check follows immediately after:

		/*
		 * The xmin should match the previous xmax value, else chain is
		 * broken.
		 */
		if (TransactionIdIsValid(prev_xmax) &&
			!TransactionIdEquals(prev_xmax,
								 HeapTupleHeaderGetXmin(heapTuple->t_data)))
			break;

Pruning: reclaiming the space

Dead versions accumulate. When a row is updated ten times, there are ten tuples on the page, and nine of them are garbage once no transaction can see them.

Pruning happens opportunistically, during ordinary scans, via heap_page_prune_opt(). The trigger is fillfactor-aware:

	minfree = RelationGetTargetPageFreeSpace(relation,
											 HEAP_DEFAULT_FILLFACTOR);
	minfree = Max(minfree, BLCKSZ / 10);

	if (PageIsFull(page) || PageGetHeapFreeSpace(page) < minfree)

and it needs a cleanup lock, not merely an exclusive lock, because pruning can destroy line pointers other backends may hold references to.

The chain surgery is in heap_prune_chain(). Its header comment is the clearest statement of the algorithm in the whole tree:

The root line pointer is redirected to the tuple immediately after the latest DEAD tuple. If all tuples in the chain are DEAD, the root line pointer is marked LP_DEAD.

Three outcomes:

The important subtlety: the t_ctid links are not rewritten during pruning. The chain is repaired by replacing the root line pointer’s storage with a redirect, not by patching t_ctid:

		ItemIdSetRedirect(fromlp, tooff);

with

#define ItemIdSetRedirect(itemId, link) \
( \
	(itemId)->lp_flags = LP_REDIRECT, \
	(itemId)->lp_off = (link), \
	(itemId)->lp_len = 0 \
)

The root keeps its offset number, so index entries pointing at it stay valid, but loses its storage (lp_len = 0) and repurposes lp_off to hold the offset number of the target. The reader follows the redirect at the start of a chain:

		/* check for unused, dead, or redirected items */
		if (!ItemIdIsNormal(lp))
		{
			/* We should only see a redirect at start of chain */
			if (ItemIdIsRedirected(lp) && at_chain_start)
			{
				/* Follow the redirect */
				offnum = ItemIdGetRedirect(lp);
				at_chain_start = false;
				continue;
			}
			/* else must be end of chain */
			break;
		}

Now, the freed tuple bytes are still sitting there in the middle of the page, unreachable. PageRepairFragmentation() moves the survivors downward to close the gap:

		/* shift the target offset down by the length of this tuple */
		upper -= itemidptr->alignedlen;
		/* point the copy_head to the start of this tuple */
		copy_head = itemidptr->itemoff;

		/* update the line pointer to reference the new offset */
		lp->lp_off = upper;

Note that lp_off is rewritten for every moved tuple. The line pointers are the only thing that has to stay stable; the tuples can go anywhere.

Two side structures

The free space map

The FSM is a per-relation array of pages, each page holding a tree of free-space values per heap page. It’s consulted when a tuple needs to be placed and the current target page is full, to find a page with room.

The visibility map

The VM is a bitmap with two bits per heap page — all-visible and all-frozen:

/* Number of bits for one heap page */
#define BITS_PER_HEAPBLOCK 2

/* Flags for bit map */
#define VISIBILITYMAP_ALL_VISIBLE	0x01
#define VISIBILITYMAP_ALL_FROZEN	0x02

The VM page is nearly all bitmap:

/*
 * Size of the bitmap on each visibility map page, in bytes. There's no
 * extra headers, so the whole page minus the standard page header is
 * used for the bitmap.
 */
#define MAPSIZE (BLCKSZ - MAXALIGN(SizeOfPageHeaderData))

8168 bytes of bitmap per VM page, four heap pages per byte, so 32 672 heap pages per VM page. The VM fork is about 1/32672 the size of the heap fork.

When every tuple on a heap page is visible to everyone, that page’s all-visible bit is set, and readers can skip the page entirely. This is why SELECT count(*) on an untouched table is nearly instant.

Look at it yourself

The pageinspect extension exposes all of this. It lives in contrib/pageinspect/ and is not installed by default. The raw-page functions require superuser:

CREATE EXTENSION pageinspect;

-- the line pointer array, and the header of every tuple on the page
SELECT lp, lp_off, lp_len, lp_flags, lp_flags = 1 AS normal,
       t_xmin, t_xmax, t_ctid, t_hoff
FROM heap_page_items(get_raw_page('mytable', 0));

-- the decoded flag names
SELECT (heap_tuple_infomask_flags(t_infomask, t_infomask2)).*
FROM heap_page_items(get_raw_page('mytable', 0));

-- where does each column live inside the tuple
SELECT t_ctid, s.*
FROM heap_page_items(get_raw_page('mytable', 0)) h,
     LATERAL unnest(tuple_data_split('mytable'::regclass,
                                     h.t_data, h.t_infomask,
                                     h.t_infomask2, h.t_bits)) s;

heap_page_items gives you the line pointer array and the raw tuple headers; tuple_data_split gives you the byte range of every column within a tuple. These two together are enough to verify everything in this article by hand.

What it all means in practice

A few consequences fall out of the layout, and they’re worth having in your head when you’re reasoning about a slow table:

Row width is expensive in a way that row count is not. The 23-byte header is paid by every row, but the alignment rules mean a table with one wide text column can waste more space in padding than a table with many narrow columns. MaxHeapTuplesPerPage is 291 on an 8 kB page:

#define MaxHeapTuplesPerPage	\
	((int) ((BLCKSZ - SizeOfPageHeaderData) / \
			(MAXALIGN(SizeofHeapTupleHeader) + sizeof(ItemIdData))))

(8192 − 24) / (24 + 4) = 291. A page of 291 minimal rows has 291 tuples of 24 bytes plus 291 line pointers of 4 bytes, in 8192 bytes.

HOT updates are dramatically cheaper than cold ones. If you can update a row without touching an indexed column, and there’s room on the page, PostgreSQL writes a new tuple and nothing else. No index churn, no dead-index-entry cleanup. This is why fillfactor matters: a lower fillfactor leaves room on the page for the new version, and the chance of a HOT update goes up.

The 4-byte line pointer is a per-row tax on every page. It is the price of the indirection that makes VACUUM, HOT, and page defragmentation possible. It’s also why MaxHeapTupleSize is 8160 and not 8168.

An UPDATE never reuses the old tuple’s bytes. It appends a new version and leaves the old one for VACUUM to reclaim. A table that is updated constantly will bloat until vacuum catches up, and the bloat is not fragmentation — it’s whole tuples.

The t_ctid field is the load-bearing structure. It answers three questions at once: where is the newest version of this row, was this version updated or deleted, and where does the next HOT chain member live. Six bytes, three jobs.