Chapter 3: Clustered vs. Non-Clustered Indexes — The Physical Map of Data

1. Definition

Clustered Index: A storage structure where the leaf nodes of the B+Tree contain the actual row data. A table can have only one clustered index (typically the Primary Key) because data can only be physically sorted in one order.

Non-Clustered Index (Secondary Index): A structure where leaf nodes do not contain row data, but rather a pointer to the data. In MySQL InnoDB, this pointer is the Primary Key value; in MyISAM it is typically a physical file offset, whereas PostgreSQL uses a Tuple ID (CTID).

2. Technical Depth: The Double Lookup (Bookmark Lookup)

In InnoDB, querying via a secondary index involves two B+Tree traversals:

1. First Hop: Search the secondary index tree to find the Primary Key (e.g., ID=55) associated with the search term.
2. Second Hop (Back-to-Table): Use ID=55 to search the clustered index tree to retrieve the full row data.

This “Back-to-Table” operation generates additional random I/O and is a common bottleneck for high-concurrency queries.

3. Visualizing the Invisible: InnoDB Index Structure

flowchart TD
    subgraph Secondary [Secondary Index (by Name)]
        IndexLeaf[Leaf Node: Key='Alice', PK=101]
    end

    subgraph Clustered [Clustered Index (by PK)]
        DataLeaf[Leaf Node: PK=101, RowData={Alice, 25, NYC}]
    end

    Query[Query: SELECT * FROM users WHERE Name='Alice']
    
    Query -->|1. Lookup Name| Secondary
    Secondary --"Get PK=101"--> Query
    Query -->|2. Lookup PK in Clustered Tree| Clustered
    Clustered -->|Return Row Data| Query

4. Real-World Case: Uber’s Postgres to MySQL Migration (2013-2016)

Background: Uber initially relied heavily on PostgreSQL. Postgres uses a “Heap Table” model where all indexes (including the primary key) are secondary indexes pointing to a CTID (physical location) in the Heap.

Challenge: Write Amplification

• Postgres utilizes MVCC, where updating a row often creates a new version at a new physical location (new CTID).
• Consequently, every index pointing to that row must be updated with the new CTID pointer.
• For massive tables with dozens of indexes, a single user update could trigger ten or more index writes.

Technical Choice: Uber migrated to MySQL (InnoDB).

• The InnoDB Advantage: In InnoDB, secondary indexes point to the Primary Key value, not a physical address. When data moves (due to updates or page splits), secondary indexes remain untouched as long as the Primary Key is stable.
• This significantly reduced I/O overhead for updates, particularly in high-volume replication scenarios.

Note: While Postgres later introduced HOT (Heap-Only Tuples) to mitigate this, Uber’s case remains a classic study in architectural trade-offs between storage models.

5. Detailed Defense & Optimization

A. Covering Indexes

The ultimate solution to eliminate double lookups.

• Strategy: For a query like SELECT age FROM users WHERE name = 'Alice', create a composite index on (name, age).
• Result: The data already exists in the secondary index leaf node (Key='Alice', age=25, PK=101). The engine returns the result directly without touching the clustered index.

B. Primary Key Selection

• Compactness: Since every secondary index includes the Primary Key, a large PK (like a raw UUID) causes index bloat.
• Stability: Primary keys should be static. Updating a PK requires rewriting the clustered index entry and every single secondary index entry.

C. Index Selectivity

• Avoid single-column indexes on low-selectivity fields (e.g., Gender). The optimizer will likely conclude that a sequential scan is faster than performing millions of bookmark lookups and ignore the index entirely.

6. References

• Uber Engineering: Why We Moved from Postgres to MySQL
• MySQL Reference: Clustered and Secondary Indexes
• PostgreSQL Documentation: Index Types