Part 4 of 8 · 3 min read
Primary, secondary, clustered and covering
The four kinds of index named in every database manual, and where the row itself lives.
Think of a book. The table of contents (ordered by chapter) is the main arrangement. The index at the back (ordered by topic) points into the same pages. A third list, a short summary at the front, answers some questions without opening the book at all.
The book "Designing Data-Intensive Applications" names the kinds.
Primary and secondary index
A primary key index finds a row by its unique primary key. A secondary index finds rows by another column, and many rows may share the same value.
Example: the primary index finds the order with id 101. A secondary index on user_id finds all orders of user 7.
A secondary index can be built from a key-value index in two ways, as the book says: store a list of matching row identifiers as the value, or make each key unique by adding the row identifier to it. Both work with the tree structures of module 4.
Where does the row itself live? The book describes two layouts.
Heap file. Rows are stored in no particular order in a file called the heap. Each index entry holds a pointer to the row's place in the heap. This avoids duplicating the row for every index. The cost is an extra hop: find the entry, then jump to the heap. If an updated row grows too large for its slot, it must move, and either all indexes are updated or a forwarding pointer is left behind.
Clustered index. The row itself is stored inside the index, in key order. There is no separate jump. In MySQL's InnoDB engine, the book says, the primary key is always a clustered index, and secondary indexes point to the primary key and not to a heap location. SQL Server allows one clustered index per table.
Clustered index
A clustered index stores the full rows inside the index structure, ordered by the index key.
Example: in InnoDB, rows of orders are stored in order of id. Reading orders 100 to 200 reads a stretch of neighbouring pages.
A third form sits between the two.
Covering index
A covering index includes extra columns inside the index, so that some queries can be answered from the index alone, without visiting the table.
Example: an index on (user_id) that also stores total answers SELECT total FROM orders WHERE user_id = 7 without touching the table.
A worked example in InnoDB. orders(id PRIMARY KEY, user_id, total, note) with a secondary index on user_id.
Query A: SELECT * FROM orders WHERE user_id = 7.
- Search the secondary index for
user_id = 7. Find 12 entries, each holding the primary key of an order. - For each of the 12 keys, search the primary (clustered) index to get the full row. That is 12 more tree lookups.
- Total: 1 + 12 lookups.
Query B: SELECT total FROM orders WHERE user_id = 7 with a covering index on (user_id, total).
- Search the covering index. The 12 entries already hold
total. - Total: 1 lookup. The table is never touched.
This is about 13 times fewer lookups. The price: the covering index is bigger, and each insert and each change of total must update it.
The book adds a caution for clustered and covering indexes. As with any duplication of data, they speed reads but take more storage and add work on writes. The database must also work harder to keep the copies consistent, so applications never see a mismatch.
| Kind | Where the row lives | Strength | Cost |
|---|---|---|---|
| Heap with secondary indexes | Heap file | One copy of rows | Extra hop on reads |
| Clustered | Inside the index | No extra hop, good for ranges | Only one order of rows per table |
| Covering | Some columns copied into the index | Some queries skip the table | More space, slower writes |
Read it as
Ask three things about any index: which column orders it, what the entry points to, and which extra columns it carries.
Check yourself:
- In InnoDB, what does a secondary index entry point to?
- Why can a covering index answer a query without visiting the table?