The idea: a secondary index points at the primary key
InnoDB stores a table inside its primary key: the clustered index (PRIMARY) is a B+ tree whose leaf pages hold the whole rows, sorted by id. Every other index is a secondary index. Its leaf entries hold the index columns plus the primary key, and nothing else. To read a column that is not in the entry, InnoDB takes the id from the entry and does a clustered lookup: a second B+ tree search, in PRIMARY. Most of what EXPLAIN tells you about an index is how many entries it reads and how many of those lookups it needs.
CREATE TABLE t ( id INT PRIMARY KEY, a INT NOT NULL, b INT NOT NULL, c VARCHAR(10) NOT NULL, d INT NOT NULL, KEY idx (a, b, c), KEY idx_d (d) ) CHARSET utf8mb4;
The animation uses 12 rows in 4 leaf pages of 3 rows. It counts entries (secondary-index entries read, including the one read that shows a range has ended), lookups (clustered lookups), pages (how often the next row needed is on a different PRIMARY page than the last one) and sent (rows returned).
Reading the EXPLAIN row
| Column | What it says |
|---|---|
type | the access method: const (one row by primary or unique key), ref (equality on an index prefix), range (one or more key ranges), index (the whole index in order), ALL (the whole table), index_merge (several indexes combined) |
key | the index used, NULL for none |
key_len | bytes of the index key used for the seek: it tells you how many leading columns were used. Here INT NOT NULL = 4, VARCHAR(10) in utf8mb4 = 10 × 4 + 2 = 42 (add 1 for a nullable column), so 4 = (a), 8 = (a, b), 50 = (a, b, c) |
rows | the optimizer's estimate of rows to examine (the page shows exact counts) |
Extra | Using index (covering), Using where (the server filters rows), Using index condition (ICP), Using MRR, Using index for skip scan, Using union / sort_union / intersect(…) |
Covering index: Using index
SELECT * FROM t WHERE a = 1 AND b = 2 seeks to (1, 2) in idx and reads 3 entries, then one more, (1, 3, dan), which is past the range and stops the scan. c is in the entry but d is not, so each match costs a lookup: 3 lookups on 3 different pages. SELECT id, a, b with the same WHERE needs only columns that are in the entry (the id is always there), so the index covers the query: Extra: Using index, 0 lookups (Demo: covering index vs SELECT *). Adding a column to an index to make a hot query covering is one of the cheapest big wins in MySQL tuning.
Leftmost prefix and skip scan
idx(a, b, c) is sorted by a, then b within each a, then c. A seek needs a leftmost prefix of the key: a, or a and b, or all three. For WHERE b = 2 the matching entries are spread over every a, so there is no single place to seek to. With SELECT * the optimizer reads the whole table: type ALL, 12 rows read, 5 sent.
MySQL 8.0.13 added the skip scan. If the query is covering, it reads the first entry to learn the first a, seeks to (a, 2), reads while b = 2, then jumps to the next a and repeats: type range, Extra: Using index for skip scan. In the demo it reads 9 of the 12 entries and never touches (2, 1, kim), (2, 1, ned) and (3, 1, tom). On a real table with few distinct a values and millions of rows it reads a tiny fraction (Demo: leftmost prefix). It is switched by optimizer_switch='skip_scan=on'.
MongoDB compound indexes follow the same prefix rule; see MongoDB Indexes: Compound, ESR, Multikey, Covered.
A range ends the usable prefix
For a = 1 AND b = 2 AND c = 'jon' all three columns are equalities, so the seek uses the whole key (key_len 50) and lands on the one entry. Change b = 2 to b >= 2: inside the range the entries are ordered by b first, and c = 'jon' can sit anywhere in it. The seek can only use (a, b) (key_len 8), and c is checked on every entry from (1, 2) to the end of a = 1: 5 entries read instead of 2 (Demo: a range on b stops c). Put the equality columns first in a composite index and the range column last.
Index Condition Pushdown: Using index condition
MySQL is split in two layers: the server (optimizer, WHERE evaluation) and the storage engine (InnoDB). Without ICP, InnoDB returns every row of the index range to the server, and the server applies the rest of the WHERE. For a = 1 AND c LIKE '%a%' the seek uses only a (a pattern that starts with % can't be a seek), so all 5 entries with a = 1 are looked up and the server throws away 3 rows (Extra: Using where).
With Index Condition Pushdown (on by default since 5.6) the server hands the part of the WHERE that uses only index columns to InnoDB. InnoDB checks c LIKE '%a%' on the entry, and looks up only the entries that pass: 2 lookups instead of 5 (Demo: Index Condition Pushdown). ICP is for secondary indexes only (in the clustered index the whole row is already there) and is not used when the index is covering, because then there are no lookups to save.
Multi-Range Read: Using MRR
The ids in a secondary index range are in index order, not in id order. Looking them up one by one jumps around PRIMARY: for a >= 2 the ids come out as 9, 1, 12, 5, 7, 11, 3, and every lookup lands on a different page than the one before (7 page reads for 4 pages). On disk that is random I/O. Multi-Range Read first collects the ids in a buffer (read_rnd_buffer_size), sorts them, and then looks the rows up in primary-key order: 1, 3, 5, 7, 9, 11, 12, so each page is read once and the reads move forward (Demo: Multi-Range Read). The price is that the rows no longer come out in index order. The optimizer's cost model often decides against MRR; the demo assumes optimizer_switch='mrr=on,mrr_cost_based=off'.
Index merge: union, sort_union, intersect
One range scan uses one index. For a = 1 OR d = 5 neither index alone finds all the rows, so without help the optimizer would scan the table. Index merge scans idx for a = 1 and idx_d for d = 5, merges the two id lists, and looks up each row once (type index_merge, key idx,idx_d, key_len 4,4).
| Extra | When |
|---|---|
Using union(i1,i2) | OR, and every scan returns its ids already in id order: an equality on all columns of the index (for example d = 5 on idx_d), so the lists are merged like in a merge sort |
Using sort_union(i1,i2) | OR, but some scan returns ids in another order (a = 1 on idx(a, b, c) returns them in (b, c) order, and so does any range on a secondary index): collect, sort, drop duplicates |
Using intersect(i1,i2) | AND of two such equality scans: keep the ids found by both |
In the demo the 5 ids from idx and the 3 from idx_d go into the buffer, are sorted, id 2 (found by both) is kept once, and 7 rows are looked up in id order (Demo: index merge). Index merge is often a sign that a composite index is missing; for an OR, rewriting the query as a UNION of two indexed queries is the other common fix.
PostgreSQL does the same things with other names: bitmap scans sort TIDs into page order like MRR and combine indexes with BitmapAnd/BitmapOr like index merge, and an Index Only Scan is a covering index. For the other index kinds see PostgreSQL index types; for how a planner chooses between these paths, How a Query Planner Picks a Plan; for what a leaf page looks like inside, the InnoDB page; and for the whole path of a query, How MySQL Runs a Query.
See also Clustered vs secondary index, side by side: a lookup by primary key next to the same row found through a secondary index and a covering index.
What the page leaves out
Real pages hold hundreds of rows and the B+ trees have internal levels, so a lookup is a full tree descent and usually a buffer pool hit. The page leaves out the cost model and statistics behind the choice of plan (rows and filtered are estimates), EXPLAIN ANALYZE and FORMAT=TREE, the ref, possible_keys and filtered columns, Batched Key Access for joins (MRR applied to the inner table), descending and invisible indexes, functional indexes, index merge intersection in action, and MVCC: a secondary entry may point at a row version the transaction can't see, which forces a lookup even for a covering query when the page was changed recently.