Primary versus secondary: identity is not location

Should an index entry hold a physical address or a primary key, and what does each choice cost when rows move?

The constraint is that rows move. Page splits move them. Compaction moves them. An update that no longer fits in its page moves them. Vacuum moves them. But a reference written into an index was written at some moment in the past. So there are exactly two ways to build a reference, and nothing forces the choice except which cost you would rather pay.

Early binding: the reference is a physical address. PostgreSQL index entries hold a TID, a tuple identifier of the form (block, offset): which page, which slot in it. Lookup takes one hop: descend the index, land on the table page, done. The price: when a row moves, every index entry that points at it is now wrong, so whoever moved it must find and fix them.

PostgreSQL pays this price by creating a new row version and new index entries in every index on the table, even indexes on columns the update never touched. The escape is the HOT (heap-only tuple) update: if the new version fits on the same page and no indexed column changed, it is chained off the old version and no index is touched at all. The very existence of HOT is a confession of how expensive early binding is.

Late binding: the reference is a primary key. InnoDB (MySQL's default storage engine) secondary indexes store the PK value, not an address. Rows can move freely inside the clustered index and no secondary index notices. The price: a second descent on every secondary lookup. First find the PK in the secondary B-tree, then find the row in the clustered B-tree.

This is a pattern we have seen elsewhere in storage. When the underlying medium cannot update in place (flash memory, object storage), it grows an indirection layer (a lookup table that maps names to current locations) plus a garbage collector to clean up. Here the table does not forbid update in place, but it relocates rows, and it grows the same organ for the same reason. This suggests a broader statement:

Two consequences matter in practice and are rarely stated as consequences.

PK width is a table-wide multiplier under late binding. In InnoDB every secondary index entry contains the full primary key. Worked example: a table has a 36-byte UUID (as text) primary key and six secondary indexes. You store the UUID once in the clustered index and once in each of six secondary indexes: 7 copies per row, and each copy lowers the fanout of its tree. Under early binding (PostgreSQL), the TID is 6 bytes regardless of what the PK looks like. The same schema decision costs wildly different amounts in the two systems.

Under clustering, the PK is the write order. A random PK, such as a UUIDv4, means every insert lands at a random point in the clustered index. It splits a random page, has no write locality, and its working set (the set of pages that must stay in memory to avoid disk reads) is the whole index. UUIDv7 and ULID exist to restore monotonicity: their leading bits are a timestamp, so new keys are always near the right edge of the tree. The lesson: choosing a primary key looks like a logical modelling decision and is actually a physical layout decision. (This is Priya's third symptom.)