vault

Clustered versus Secondary Indexes

13 min read

Clustered versus Secondary Indexes

A clustered index is not a separate structure bolted onto a table — it is the table: the rows themselves live in the leaf pages of the index B-tree, physically ordered by the index key, so there is no independent “heap” of rows to visit. A secondary index (also called a non-clustered index) is a separate B-tree whose leaves hold the index key plus a pointer back to the row, so answering a query through it costs a second hop to fetch the row. The single most consequential — and most engine-specific — detail is what that pointer is: InnoDB stores the table’s primary key in every secondary-index leaf and re-descends the clustered index to find the row (MySQL 8.4 InnoDB index docs), whereas PostgreSQL stores a physical heap address called a ctid (PostgreSQL system-columns docs). That one difference cascades into why InnoDB begs you for a short primary key and why PostgreSQL fights index bloat with heap-only tuples. A table has at most one clustered index, because rows can be laid out in only one physical order.

Mental Model

The cleanest way to think about it: a clustered index answers “where does the row live?” by being where the row lives, while a secondary index answers “given this other column, where do I find the row?” and then has to follow a pointer to the row’s true home.

flowchart TB
  subgraph INNODB["InnoDB (clustered by primary key)"]
    direction TB
    SEC1["Secondary index B-tree<br/>leaf = (email, <b>PK value</b>)"]
    CLU1["Clustered index B-tree<br/>leaf = <b>the full row</b>, ordered by PK"]
    SEC1 -->|"2nd descent<br/>using PK value"| CLU1
  end
  subgraph PG["PostgreSQL (heap + ctid)"]
    direction TB
    SEC2["Secondary index B-tree<br/>leaf = (email, <b>ctid</b>)"]
    HEAP2["Heap file<br/>unordered rows, addressed by ctid<br/>(block#, item#)"]
    SEC2 -->|"1 pointer deref<br/>to physical page"| HEAP2
  end

How a secondary-index lookup reaches the row in the two dominant open-source engines. What it shows: InnoDB’s secondary leaf stores the logical primary-key value, so a lookup that needs non-indexed columns performs a second B-tree traversal of the clustered index; PostgreSQL’s secondary leaf stores a physical address (ctid = block number + item number within block), so the lookup is a single direct page fetch. The insight to take: InnoDB pays with a logarithmic re-descent (and with PK-sized bloat in every secondary index), PostgreSQL pays with pointer instability — because ctid is physical, anything that moves a row (most updates, VACUUM FULL) invalidates the pointer and forces index maintenance.

Mechanical Walk-through

The clustered index: the table is the index

In an index-organized (clustered) table, the leaf level of the primary B-tree contains the complete rows, sorted by the primary-key value. There is no heap. MySQL’s manual states it directly: “Each InnoDB table has a special index called the clustered index that stores row data. Typically, the clustered index is synonymous with the primary key” (InnoDB index docs). Because the search for a key descends straight to the page holding the row, InnoDB notes the payoff: “Accessing a row through the clustered index is fast because the index search leads directly to the page that contains the row data … the clustered index architecture often saves a disk I/O operation when compared to storage organizations that store row data using a different page from the index record” (ibid.).

InnoDB does not let you opt out — every table is clustered on something. The manual spells out the fallback chain: it uses the declared PRIMARY KEY; failing that, “the first UNIQUE index with all key columns defined as NOT NULL”; and failing that, “InnoDB generates a hidden clustered index named GEN_CLUST_INDEX on a synthetic column that contains row ID values … a 6-byte field that increases monotonically as new rows are inserted” (ibid.). SQL Server, by contrast, makes clustering optional: you may choose a clustered index or a heap, and there can be “at most one clustered index per table” (Winand glossary). Oracle spells the same idea “Index-Organized Table” and applies it “on the primary key only” (ibid.).

The secondary index and the second hop — InnoDB’s flavour

Every index other than the clustered one is a secondary index, and here InnoDB makes its defining design choice: “In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index” (InnoDB index docs). So a query like SELECT name FROM users WHERE email = 'x', where email is a secondary index and name is not in it, executes in two logarithmic phases: descend the email B-tree to find the leaf holding (email, PK), then take that PK and descend the clustered index to reach the row and read name. This is the classic “bookmark lookup” or “double lookup.” A range query that matches a thousand rows performs the clustered re-descent a thousand times unless the index is covering (see Covering Indexes and Index-Only Scans).

The critical consequence is size. Because every secondary-index entry embeds a full copy of the primary key, a fat primary key inflates every secondary index on the table. The manual’s advice is blunt: “If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key” (InnoDB index docs). A 36-character textual UUID primary key does not merely bloat the clustered index; it adds ~36 bytes to every leaf entry of every secondary index, multiplying the cost across the whole table.

The secondary index and the physical pointer — PostgreSQL’s flavour

PostgreSQL has no clustered index at all in the InnoDB sense. All PostgreSQL tables are heaps: rows sit in an unordered heap file, and every index — including the one enforcing the primary key — is a secondary structure whose leaf stores the key plus a ctid. The ctid is defined as “the physical location of the row version within its table” (system-columns docs); concretely it is a (block number, item number within the block) pair. A lookup therefore has no second B-tree descent — it dereferences the ctid to jump straight to the heap page. This is cheaper per-hop than InnoDB’s re-descent, and it makes all indexes symmetric (the PK index is not privileged). But the same doc immediately warns of the catch: “a row’s ctid will change if it is updated or moved by VACUUM FULL … ctid should not be used as a row identifier” (ibid.).

That instability is the crux. Under PostgreSQL’s MVCC, an UPDATE does not overwrite a row in place; it writes a new tuple version at a new physical location, hence a new ctid. Naïvely, every index would then need a new leaf entry pointing at the new ctid — expensive, and a source of index bloat. PostgreSQL’s escape hatch is the Heap-Only Tuple (HOT) optimization: when “the update does not modify any columns referenced by the table’s indexes” and “there is sufficient free space on the page containing the old row for the updated row,” no new index entries are created at all; the old and new versions are chained within the single heap page and the indexes keep pointing at the original item identifier, which becomes a redirect (HOT docs). HOT is why a heavily-updated PostgreSQL table whose updates don’t touch indexed columns stays lean, and why updating an indexed column is comparatively expensive — it forces a new entry into every index. (HOT is a topic in its own right; the point here is that it exists precisely because PostgreSQL indexes carry physical pointers.)

There is only one physical order

Because the clustered index dictates the physical row order, you get one per table — you cannot store the same rows sorted two different ways simultaneously. Everything else must be a secondary index that redirects to that one physical layout. PostgreSQL offers a one-shot approximation of clustering via the CLUSTER command, which physically reorders the heap to match an index — but with a giant asterisk: “Clustering is a one-time operation: when the table is subsequently updated, the changes are not clustered” (CLUSTER docs). PostgreSQL will not maintain the order; you must re-run CLUSTER periodically, and the physical/logical correlation decays with every insert and update in between.

Configuration and Examples

InnoDB: choosing a primary key defines your clustering

-- InnoDB: this PRIMARY KEY IS the clustered index.
-- Rows are stored physically sorted by (id).
CREATE TABLE orders (
    id         BIGINT       NOT NULL AUTO_INCREMENT,  -- monotonic → appends
    customer   BIGINT       NOT NULL,
    created_at DATETIME     NOT NULL,
    total      DECIMAL(10,2),
    PRIMARY KEY (id),                 -- clustered index
    KEY idx_customer (customer)       -- secondary index: leaf = (customer, id)
) ENGINE=InnoDB;
  • PRIMARY KEY (id) makes id the clustered key: new rows with an ever-increasing id append to the “right edge,” minimizing page splits. This is why an AUTO_INCREMENT surrogate is the InnoDB default recommendation.
  • KEY idx_customer (customer) builds a secondary index whose every leaf silently stores (customer, id) — the id is appended so InnoDB can re-descend the clustered index. Query WHERE customer = ? returning non-indexed columns therefore does: descend idx_customer, then for each match re-descend the id clustered index.
  • Had the primary key been, say, CHAR(36) for a textual UUID, that 36-byte value would be copied into every idx_customer leaf, roughly tripling the secondary index’s per-row overhead.
-- See the double lookup in the plan:
EXPLAIN SELECT total FROM orders WHERE customer = 42;
-- key: idx_customer  (uses the secondary index to find matching PKs,
--                     then fetches 'total' from the clustered index per row)

PostgreSQL: everything is a heap; ctid is exposed

CREATE TABLE orders (
    id         bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    customer   bigint NOT NULL,
    created_at timestamptz NOT NULL,
    total      numeric(10,2)
);
CREATE INDEX idx_customer ON orders (customer);  -- leaf = (customer, ctid)
 
-- The physical address is a first-class, queryable column:
SELECT ctid, id, customer FROM orders WHERE customer = 42;
--   ctid   | id | customer
-- ---------+----+---------
--  (0,3)   |  7 |       42     -- block 0, item 3
 
-- One-shot physical reordering (NOT maintained afterwards):
CLUSTER orders USING idx_customer;   -- heap now sorted by customer …
-- … until the next UPDATE/INSERT drifts it out of order again.
  • The id primary key is not special storage-wise: it is a unique B-tree over the heap exactly like idx_customer, differing only in that it enforces uniqueness.
  • ctid (0,3) is the literal heap coordinate; an UPDATE that changes an indexed column (or overflows the page) will relocate the row and change this value.
  • CLUSTER … USING idx_customer improves the correlation between customer’s logical order and physical order — which, as The Index versus Sequential Scan Decision explains, is exactly what the planner’s cost model rewards via the pg_stats.correlation statistic (pg_stats docs).

Failure Modes and Common Misunderstandings

  • The random-UUID clustered key (InnoDB). Choosing a random UUID (v4) as the InnoDB primary key is doubly punishing. First, inserts land at random points in the clustered B-tree instead of appending, causing constant page splits and fragmentation. Second, every secondary index leaf carries a copy of that bulky random key, bloating them all — the manual’s “keep the primary key short” advice (InnoDB index docs) is aimed squarely at this. The common fixes are an AUTO_INCREMENT surrogate, or a time-ordered UUID variant (UUIDv7) stored as BINARY(16) so it is both compact and monotonic.

  • Assuming PostgreSQL has a “clustered index.” A frequent migration surprise: PostgreSQL’s primary key does not physically order the table, and CLUSTER is a maintenance command, not a permanent property. “when the table is subsequently updated, the changes are not clustered” (CLUSTER docs). If you rely on physical ordering for range-scan performance, you must schedule periodic re-clustering (and it takes an ACCESS EXCLUSIVE lock).

  • Updating an indexed column in PostgreSQL is expensive. Because a non-HOT update writes a new tuple at a new ctid, it must insert a new entry into every index on the table, and leaves dead entries behind for VACUUM to reclaim — index bloat. Updating a column that is not indexed, on a page with free space, triggers the far cheaper HOT path (HOT docs). A common tuning move is lowering fillfactor to reserve intra-page space so more updates stay HOT.

  • Confusing the second B-tree descent with I/O count. In InnoDB the secondary→clustered re-descent is logical (log-n traversal), and the clustered index’s upper levels are usually cached, so it is not necessarily a physical disk seek. The real cost multiplier appears in range scans returning many rows, each triggering its own descent — which is exactly the situation a covering index eliminates.

  • “Secondary index is always slower.” Not per se — a single-row equality lookup through a secondary index is cheap. The asymmetry bites for (a) large result sets needing non-indexed columns, and (b) InnoDB’s PK bloat in the index itself. For point lookups both models are fast.

Alternatives and When to Choose Them

The choice between an index-organized (clustered) table and a heap-plus-secondary-indexes table is a storage-engine decision, not usually a per-query one, and it is often made for you by the engine (InnoDB always clusters; PostgreSQL never does). Where you do have a choice (SQL Server, Oracle IOTs), cluster the table when its dominant access pattern is range scans or lookups on the primary key and rows are read mostly through that key — the rows arrive pre-sorted and adjacent, turning random I/O into sequential I/O. Prefer a heap when the table has many equally-important secondary access paths (so no single physical order helps most queries) or when the “natural” key is wide/random (making a clustered layout fragment badly). This is a facet of the broader on-disk trade-off explored in Heap Files and Index-Organized Tables and B-Tree and B-Plus-Tree Storage Engines.

Production Notes

The InnoDB “short primary key” rule is one of the highest-leverage schema decisions in MySQL practice: because the PK is copied into every secondary index, a poorly chosen 30+ byte natural key can double or triple total index size on a wide-index table, worsening buffer-pool hit rates for all indexed access, not just PK access. The widely-repeated production pattern — surrogate BIGINT AUTO_INCREMENT primary key even when a natural key exists, with the natural key demoted to a UNIQUE secondary index — is a direct response to this and to the append-friendliness of monotonic keys.

On the PostgreSQL side, the load-bearing production fact is that ctid instability drives index bloat, and HOT is the mitigation. Teams monitoring PostgreSQL write-heavy tables watch the HOT-update ratio (pg_stat_user_tables.n_tup_hot_upd versus n_tup_upd); a low ratio signals updates touching indexed columns or pages too full for in-place versioning, and is a cue to drop fillfactor or reconsider which columns are indexed. Note also that PostgreSQL’s CLUSTER improving correlation is not just about scan locality — it directly lowers the planner’s estimated cost of an index scan (see The Index versus Sequential Scan Decision).

See Also

Graph View

Backlinks