In an engine that stores table rows clustered by the primary key — InnoDB, for example — how does the choice of primary key affect physical storage, secondary index lookups, and insert throughput?

## Clustered versus heap storage Engines organise table rows in one of two ways. In a **heap**, rows live wherever there is room and every index — including the primary key's — stores a physical row locator. In a **clustered** or index-organised layout, the primary key's B-tree *is* the table: internal pages route by key, and leaf pages contain the entire rows, ordered by key. InnoDB is the canonical clustered engine; PostgreSQL heaps are the canonical alternative. The distinction changes how much your key choice matters, and it is why the same advice does not transfer between engines. ## Consequence 1: secondary indexes carry the primary key In a clustered engine rows move as pages split and merge, so a physical address is not a stable pointer. Secondary index entries therefore store the **primary key value** as the row locator. Two things follow. *Lookup cost.* Reading a row through a secondary index means descending the secondary B-tree to find the key, then descending the clustered B-tree to reach the row — roughly double the logical I/O of a primary key lookup. This second step is often called a bookmark lookup. It disappears when the secondary index *covers* the query, i.e. contains every column the query needs (the primary key columns come along for free, which is why key columns are effectively present in every index). *Index size.* The key is duplicated into every entry of every secondary index. Replacing an 8-byte key with a 36-character textual UUID on a table with five secondary indexes and 100M rows adds gigabytes of index, and those bytes compete for buffer-pool memory with the data you actually query. ## Consequence 2: insert order is physical order Inserts land where the key sorts. *Monotonic keys* (auto-increment, sequence, time-ordered id) always append to the rightmost leaf. Pages fill densely, writes are sequential, splits are cheap right-edge splits, and the recently written pages — the ones most likely to be read again — stay hot in cache. The downside is contention: many concurrent inserters serialise on that last page and, in some configurations, on the counter that hands out values. *Random keys* (version-4 UUID, hash) insert into arbitrary existing pages. Each insert may dirty a different page, so a batch of N inserts touches N pages instead of a handful; pages split near the middle leaving both halves half-full, wasting space and increasing the tree's page count; and once the index exceeds RAM, every insert becomes a read-modify-write of a page that has to be fetched from disk. Throughput does not degrade gently — it falls off a cliff at the point the index stops fitting in memory. Time-ordered identifiers (UUIDv7, ULID, snowflake-style) exist precisely to recover locality while keeping decentralised generation. *Updates that change the key* physically relocate the row and force every secondary index entry to be rewritten, which is one more reason key values should never change. ## Consequence 3: ordering you can exploit Range scans and ordered reads on the primary key are sequential page reads with no sort. For a child table keyed `(order_id, line_no)`, all lines of an order sit on the same page or two — fetching them is one seek. That is a genuine design tool: choosing the leading key column chooses which access pattern is cheap. ## If you declare no primary key InnoDB will use the first suitable unique NOT NULL index; failing that it invents a hidden 6-byte row id from a shared counter. The table works, but you have an identifier you cannot query, replication and change-data-capture tools struggle to identify rows, and the hidden counter is a global contention point. Always declare a key. ## Practical guidance - Prefer a narrow key: a 64-bit integer or a 16-byte binary UUID, not a 36-character string. - Prefer a key whose insert order has locality: sequence or time-ordered id rather than random UUID, unless the write-hotspot on the right edge is the greater problem. - If external identifiers must be opaque and unguessable, you can still store a compact internal clustered key and carry the public identifier in a separate indexed column. - Remember this is engine-dependent. In a heap-organised engine, random keys cost less because index entries point at physical locations and the table itself is not reordered — though random insertion still fragments the primary key's own index.