Internals · Enginesheapclustered indexsecondary indextidprimary key

Physical Layouts Compared: Heap + Secondary Index vs Clustered Index

Two ways to put a table on disk — rows in a heap addressed by indexes, or rows inside the primary-key tree addressed by key — and every difference in query cost, write amplification, index size and bulk-load speed between PostgreSQL and InnoDB follows from that one choice.

▶ Interactive Interview question

Progress

Why this exists

The mechanism as the answer to a problem — read this before the name.

Problem
A secondary index must lead from a value to a row. What should the index leaf store to identify the row: where it is, or what it is?
↓
Naive solution
Store where it is — a physical (page, slot) address. Follow it and you are at the row: one hop, no second search.
↓
Why it breaks
Addresses go stale whenever rows move. In a layout that keeps rows in primary-key order, a page split moves half a page of rows, and every secondary index pointing at them must be rewritten; in a heap, an UPDATE that writes a new version elsewhere needs a new entry in every index.
↓
Better idea
Either accept addresses and never keep rows in key order (a heap, with tricks to keep updates on the same page), or store the primary key and pay a second search in the primary tree for every secondary lookup.
↓
Internal mechanism
PostgreSQL: heap pages, TIDs in every index leaf, HOT updates to avoid index writes. InnoDB: rows in the clustered B+ tree, primary keys in every secondary leaf, MRR to batch the second descents, covering indexes that already contain the PK.
↓
Trade-offs
Heap + TIDs: one-hop secondary lookups and cheap bulk loads, but PK range scans are only sequential if the data happened to arrive in order, and non-HOT updates hit every index. Clustered + PKs: PK ranges are always sequential and updates never touch unrelated indexes, but every secondary lookup costs an extra descent and the PK is stored N times.
↓
Real database
PostgreSQL (heap only), Oracle (heap by default, index-organised tables optional), SQL Server (clustered by default, heap optional), MySQL/InnoDB and SQLite rowid tables (clustered only).

Choose your depth

The same mechanism at four altitudes. Start where you are; come back deeper.

Where the row lives

In a heap layout, the table is a bag of pages and each index leaf says "the row is at page 812, slot 7". In a clustered layout, the table is the primary-key index itself, so a secondary index leaf can only say "the row has id 4711" — and you look that up in the primary tree.

Everything else is a consequence: how many page reads a lookup costs, what an update has to touch, how big indexes are, how fast a PK range is, how fast a bulk load is.

The two chains

Every secondary lookup follows a chain from the indexed value to the row. In a heap layout the chain has a physical address in the middle; in a clustered layout it has a logical key. Read both from left to right and count the searches.

Heap layout (PostgreSQL) vs clustered layout (InnoDB)

PostgreSQL-style
  Secondary Index  ─►  Tuple location (TID = block, line pointer)  ─►  Heap page  ─►  Tuple
     1 descent                    a physical address                   1 page read     (may be a HOT chain: follow ctid within the page)

InnoDB-style
  Secondary Index  ─►  Primary key  ─►  Clustered primary index  ─►  Row
     1 descent          a logical key          1 more descent          in the leaf you reached

by primary key:
  PostgreSQL:  PK index (descent) ─► TID ─► heap page ─► tuple          4 page reads at height 3
  InnoDB:      clustered index (descent) ─► row                          3 page reads at height 3

Why the difference reaches every query

Secondary equality, one row. Heap: one descent plus one heap page — four reads at height 3. Clustered: two descents — six reads, though the upper levels of both trees are cached and the real cost is ~one extra leaf read. Stable under updates in the clustered layout because the PK never goes stale; in the heap layout an UPDATE that cannot be HOT moves the tuple and the old index entry becomes dead weight until VACUUM.

Secondary lookup, many rows. Both layouts degrade to one random page per row: the heap through a bitmap scan (TIDs sorted by page), the clustered tree through MRR (PKs sorted before the second descent). Above a few percent of the table, both lose to a sequential scan. The escape hatch in both is a covering index — and the clustered layout gets it cheaper, because every secondary leaf already carries the PK, while PostgreSQL must also consult the visibility map or fetch the heap tuple to check visibility.

Primary-key range scan. The clustered layout walks linked leaves that *are* the rows: 1,000 rows at ~100 per page is ~10 sequential page reads, always. The heap layout walks index leaves and then fetches heap pages whose order depends on physical correlation — near-sequential right after a load in key order or after CLUSTER, degrading toward random as updates write new versions wherever there is room. The planner reads pg_stats.correlation to guess which.

Update of a non-key column. Clustered: change the record in place, write undo and redo; no index is touched unless its column changed. Heap: write a new tuple version — on the same page with no index writes if HOT applies, otherwise anywhere with a new entry in *every* index. Update of the primary key. Heap: a new tuple and one new entry per index. Clustered: the row is deleted and re-inserted at its new key position (possibly splitting a page), and every secondary index entry is rewritten because each one contains the PK. Do not update primary keys in InnoDB.

PK size amplifies every secondary index in the clustered layout: a CHAR(36) UUID costs 36 bytes per entry per index versus 8 for a bigint; five secondary indexes on 100 M rows is 14 GB of key bytes versus 4 GB. In the heap layout each entry carries a 6-byte TID regardless of PK type. Bulk loads favour the heap: append rows in arrival order, then build indexes from sorted input; a clustered table must place each row at its key position, which is fast only if the input is already in key order.

Per operation — page touches at height 3, 100 rows per page, five indexes

Operation	Heap + secondary indexes (PostgreSQL)	Clustered index (InnoDB)	Edge
PK point lookup	4 reads (index + heap)	3 reads (row in the leaf)	clustered
Secondary equality → 1 row	4 reads	6 reads (two descents; ~1 extra real I/O)	heap
Secondary → 2,000 rows	bitmap: ~900 heap pages	MRR: ~950 leaf pages	even — add a covering index
Covering index read	index leaves + visibility map (or heap fetch)	index leaves only (PK is in the leaf)	clustered
PK range, 1,000 rows	~8 index + 10–1,000 heap pages, depends on correlation	~13 pages, sequential by construction	clustered
UPDATE non-key column	HOT: 1 page; else 1 + one entry per index	in place + undo/redo; indexes untouched	even (heap only with HOT)
UPDATE primary key	new tuple + 5 index entries	row moves + all 5 secondary entries rewritten	heap
Index size per entry	6-byte TID	full PK (8 B bigint … 36 B UUID)	heap
Bulk load, unordered input	append pages, build indexes after	insert at key position, splits	heap
Dead-version cleanup	VACUUM scans the table	purge follows undo in commit order	depends

What each layout depends on

The heap layout is only as good as HOT and VACUUM: keep indexed columns out of hot update paths, leave free space in pages (fillfactor), and let autovacuum keep dead entries from accumulating, and it is close to ideal for mixed workloads. Its PK range performance is a property of the data's history, not of the layout.

The clustered layout is only as good as its primary key: short, monotonic and immutable makes inserts append, indexes small and updates cheap; wide, random or changing keys make every one of those worse at once. Its secondary lookups are a fixed extra descent, mitigated by caching, MRR and covering indexes.

Choose (or prefer) the heap layout when the workload is dominated by secondary-index lookups of few rows, when bulk loading and rebuilding are routine, when primary keys are wide or not under your control, or when you need PostgreSQL for other reasons — and tune fillfactor, keep hot columns unindexed, and watch n_dead_tup.
Choose (or prefer) the clustered layout when access is by primary key or by ranges of it (time-series with (device_id, ts), order lines with (order_id, line_no)), when the PK is a short monotonic integer, and when in-place updates of non-key columns are the dominant write — and never update the PK, never use UUIDv4 as the PK.
In either, a covering index is the tool for "secondary index returning many rows"; the clustered layout gets it slightly cheaper.
PostgreSQL has no clustered tables; CLUSTER reorders the heap once and does not maintain the order. InnoDB has no heap tables; if you do not declare a PK it invents a hidden one, and you inherit every property above without having chosen it.

Key points

Heap layout: index leaves hold physical TIDs; one descent plus one heap read reaches a row. Clustered layout: index leaves hold the PK; two descents.
Clustered PK range scans are physically sequential by construction; heap range scans depend on correlation the engine does not maintain.
Heap secondary indexes point at tuples that move on non-HOT updates; clustered secondary indexes never go stale, but pay the PK size in every entry.
Non-key updates: in place in the clustered tree, new version (HOT or not) in the heap. PK updates: expensive in both, worst in the clustered layout.
Covering indexes rescue the many-rows secondary case in both; bulk loads favour the heap.
The heap layout depends on HOT and VACUUM; the clustered layout depends on the primary key being short, monotonic and immutable.

Heap + secondary index vs clustered index

Two physical layouts, one query

PostgreSQL: Secondary Index → Tuple location → Heap page → Tuple. InnoDB: Secondary Index → Primary key → Clustered primary index → Row. Pick a query and step through both paths.

SELECT * FROM users WHERE email = 'ada@x.io'

PostgreSQL implementation

email B-tree: root → inner → leaf3 pages
Heap page 8121 page

Leaf entry: (ada@x.io → TID (812,7)). A physical address.

pages so far

stage

1 / 2

MySQL / InnoDB implementation

email B-tree: root → inner → leaf3 pages
Clustered tree: root → inner → leaf3 pages

Leaf entry: (ada@x.io → id 4711). A primary key, not an address.

pages so far

stage

1 / 2

Educational simulation — page counts assume ~10M rows, 3-level trees, 100 rows per page and five indexes on the table; real numbers depend on cache state, fill factor and row width.

1/2

When to use — and when not

Use it when

This comparison fits when choosing between PostgreSQL and MySQL for a workload, designing a primary key, or explaining why the same query costs differently on the two engines.
When deciding whether a covering index or a PK redesign is the fix for a slow secondary lookup.

Avoid it when

This comparison matters little when the working set fits in memory and the table is small: both layouts are a handful of cached page reads.
Do not choose an engine on layout alone; replication, tooling, extensions and team knowledge weigh more.

Failure modes

A UUIDv4 primary key on InnoDB: random splits, inflated secondary indexes, cold pages on every insert.
Frequent updates of indexed columns on a PostgreSQL table with fillfactor 100: no HOT, every index written per update, VACUUM behind.
Assuming a PK range scan is sequential on PostgreSQL after years of updates — correlation near zero, random heap reads.
Updating primary keys on InnoDB as part of a data migration: every row moves, every secondary index is rewritten.
Expecting an Index Only Scan to be heap-free on PostgreSQL right after a bulk update: the visibility map is not yet set, so it fetches heap pages.