Why the Primary Key Is in Every Secondary Index

InnoDB does not store rows in a heap with indexes pointing into it. The table is an index: a B-tree keyed on the primary key, with the full row stored in the leaf. This is what “clustered index” means, and much of MySQL’s indexing advice is a downstream consequence of it.

What does a MySQL secondary index actually store?

Since there is no fixed row location to point at — rows move as pages split — a secondary index cannot store a physical address. It stores the primary key value instead.

So an index on (email) in a table with primary key id physically contains (email, id). You did not declare id; it is there regardless.

Two consequences follow immediately.

Every secondary index inherits the primary key’s width. A BIGINT primary key adds 8 bytes to every entry of every secondary index. A 36-character UUID stored as CHAR(36) adds 36 — the value is ASCII, so it costs one byte per character under the compact row formats InnoDB has defaulted to since 5.7; the general formula is M times the width of the widest character in the charset. On a table with five indexes and a hundred million rows, the 28-byte difference is fourteen gigabytes, and those bytes displace other pages in the buffer pool.

Some queries are covered by accident. SELECT id FROM users WHERE email = ? never touches the clustered index, because id is already in the secondary index. This is why MySQL developers often get covering-index behavior without having asked for it, and why the same query rewritten to select one more column can turn into a second traversal.

The second traversal

When a secondary index does not contain everything the query needs, the engine takes the primary key from the index entry and performs a second B-tree descent through the clustered index to find the row.

-- One traversal: email index contains email and id.
SELECT id FROM users WHERE email = '[email protected]';

-- Two traversals: email index, then clustered index for last_login_at.
SELECT id, last_login_at FROM users WHERE email = '[email protected]';

For a single row this is a few extra page reads. For a range scan returning thousands of rows it is thousands of descents, each potentially a random read, and it is the point at which the optimizer abandons the index and scans the table instead — the same crossover, argued from the row estimate for PostgreSQL. SQL Server names the same second read in the plan as a Key Lookup operator; InnoDB performs it without naming it.

What makes a good InnoDB primary key?

Keep it narrow, because it is duplicated into every secondary index.

Keep it monotonically increasing where you can. Inserts in ascending order leave index pages about 15/16 full; random order leaves them anywhere from 1/2 to 15/16 full, because the insert lands in an arbitrary page and splits it. A randomly distributed UUID as a primary key is the combination of both problems: wide and unordered.

If a random identifier is required externally, one common resolution is an auto-increment primary key for storage with a unique secondary index on the UUID for lookups. That keeps the clustered index narrow and ordered while preserving the external contract, at the cost of one extra index.

Where PostgreSQL differs

PostgreSQL uses a heap with all indexes pointing into it, including the primary key index. There is no clustered index and no implicit primary key inside secondary indexes. So the “narrow primary key” argument is much weaker there, and advice about UUID keys that is well justified for InnoDB is often repeated for PostgreSQL where the mechanism does not exist.

This is a good example of why the mechanism matters more than the rule. The rule does not transfer; the reasoning shows you why.