MENU


Indexes

An index is a sorted copy of some columns that lets MySQL jump to matching rows instead of reading the whole table. It speeds up filters, joins, sorting and grouping, and slows every write. To show it, shop gets a million deterministic orders from a recursive CTE (Section 3.6.8) joined to itself:

CREATE TABLE big_orders (

id INT UNSIGNED AUTO_INCREMENT PRIMARY KEY, customer_id INT UNSIGNED NOT NULL,

status ENUM('pending','paid','shipped','cancelled') NOT NULL,

ordered_at DATETIME NOT NULL, total DECIMAL(8,2) NOT NULL

);

INSERT INTO big_orders (customer_id, status, ordered_at, total)

WITH RECURSIVE s (n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM s WHERE n < 1000),

seq (n) AS (SELECT (a.n - 1) * 1000 + b.n FROM s AS a CROSS JOIN s AS b)

SELECT 1 + CRC32(CONCAT('c', n)) % 50000,

CASE WHEN n % 100 < 2 THEN 'pending' WHEN n % 100 < 6 THEN 'cancelled'

WHEN n % 100 < 26 THEN 'paid' ELSE 'shipped' END,

'2024-01-01' + INTERVAL n * 84 SECOND,

5 + CRC32(CONCAT('t', n)) % 20000 / 100

FROM seq ORDER BY n;

Listing 3.96: A million orders for the index experiments

Query OK, 0 rows affected (0.049 sec)

Query OK, 1000000 rows affected (7.611 sec)

Records: 1000000 Duplicates: 0 Warnings: 0

Output of Listing 3.96 That is 50,000 customers with about 20 orders each, 2% pending and 74% shipped. Timings come from this book's WSL2 machine (MySQL 9.7.2, a 128 MiB buffer pool shared with other databases), each taken after the table and indexes had been read once.

3.11.1 How a B+Tree Index Works in InnoDB

InnoDB stores every index, the table included, as a B+tree of 16 KiB pages. Leaves hold entries in key order, linked both ways; internal pages hold a separator key and a child page number per entry. A lookup reads one page per level; with hundreds of children per page the tree stays shallow. A range descends once, then walks the leaves.Figure 3.9: The PRIMARY B+tree of big_orders, and the path a lookup of id 567890 takes (keys schematic)SELECT ... INTO @var keeps results off the screen, so only the timings print:

SELECT total INTO @t FROM big_orders WHERE id = 567890;

SELECT COUNT(*), SUM(total) INTO @n, @s FROM big_orders WHERE customer_id = 4242;

Listing 3.97: A primary key lookup against a full scan

Query OK, 1 row affected (0.000 sec)

Query OK, 1 row affected (0.166 sec)

Output of Listing 3.97 The key lookup was too quick to time; the scan of the unindexed customer_id read every leaf, and only it grows with the table. After ANALYZE TABLE, mysql.innodb_index_stats counts 2,399 leaf pages for PRIMARY, about 417 rows each: 15/16 full, because rows arrived in key order (random inserts split pages and leave them half to 15/16 full). Page 4 of the .ibd file is the root, and sudo xxd -s $((4 * 16384 + 64)) -l 2 on it prints PAGE_LEVEL, 0002: three levels.

3.11.2 Clustered Indexes and Secondary Index Lookups

In InnoDB the table is its primary key B+tree, the clustered index. Without a primary key, InnoDB clusters on the first all-NOT NULL UNIQUE index, or on a hidden 6-byte row id (GEN_CLUST_INDEX; Section 3.4.2). Every other index is secondary: its entries hold the indexed columns plus the primary key, and reaching the row takes a second descent.Figure 3.10: A secondary index lookup: find the primary keys, then fetch each row from the clustered index (values schematic)

CREATE INDEX idx_customer ON big_orders (customer_id);

SELECT COUNT(*), SUM(total) INTO @n, @s FROM big_orders WHERE customer_id = 4242;

SELECT stat_name, stat_value, stat_description FROM mysql.innodb_index_stats

WHERE database_name = 'shop' AND table_name = 'big_orders'

AND index_name = 'idx_customer' AND stat_name LIKE 'n_diff%';

SELECT COUNT(*), SUM(total) INTO @n, @s FROM big_orders FORCE INDEX (idx_customer)

WHERE customer_id <= 5000;

Listing 3.98: A secondary index, and the primary key hidden in its entries

Query OK, 0 rows affected (2.439 sec)

Records: 0 Duplicates: 0 Warnings: 0

Query OK, 1 row affected (0.000 sec)

+--------------+------------+------------------+

| stat_name | stat_value | stat_description |

+--------------+------------+------------------+

| n_diff_pfx01 | 49961 | customer_id |

| n_diff_pfx02 | 1000064 | customer_id,id |

+--------------+------------+------------------+

2 rows in set (0.000 sec)

Query OK, 1 row affected (0.224 sec)

Output of Listing 3.98 The customer query fell from 0.17 s to under a millisecond. n_diff_pfx02 counts (customer_id, id) pairs, exposing the hidden column: a CHAR(36) UUID key adds 36 bytes or more to every secondary entry. Many matches mean many descents: forced (Section 3.12.8), the index took 0.22 s for 100,000 orders, no faster than the optimizer's own scan (Section 3.11.5). With two million rows and a cold cache, the same test took 8.4 s against 0.55 s.

3.11.3 Creating Primary, Unique, and Plain Indexes

A table has one PRIMARY KEY (never NULL), any number of UNIQUE indexes (no duplicates, many NULLs allowed) and plain INDEXes (synonym KEY). Declare them in CREATE TABLE or add them with ALTER TABLE ... ADD INDEX or CREATE INDEX; ALGORITHM = INPLACE, LOCK = NONE demands an online build (Section 3.4.6). Foreign keys get an index automatically.

INSERT INTO customers (email, name, country) VALUES ('chen@example.com', 'Chen Two', 'MY');

EXPLAIN FORMAT=TRADITIONAL SELECT id FROM customers WHERE email = 'chen@example.com'\G

Listing 3.99: A duplicate rejected, and a lookup through the unique index

ERROR 1062 (23000): Duplicate entry 'chen@example.com' for key 'customers.email'

*************************** 1. row ***************************

id: 1

select_type: SIMPLE

table: customers

partitions: NULL

type: const

possible_keys: email

key: email

key_len: 1022

ref: const

rows: 1

filtered: 100.00

Extra: Using index

1 row in set, 1 warning (0.000 sec)

Output of Listing 3.99 In the traditional plan, type: const means one row via a unique index, key the index used, rows the estimate, and Using index that the index alone answered (id is in every entry). Without an index: type: ALL, key: NULL, rows near the table size. MySQL 9.7 prints the tree format by default (explain_format = TREE; Section 3.12.2).

3.11.4 Composite Indexes and Column Order

A composite index sorts by its first column, then the second, like a phone book, and seeks on a leftmost prefix only: (customer_id, status, ordered_at) serves customer_id, then status, then ordered_at, never status alone. Put equality columns first and one range or sort column last; a range or a gap stops the narrowing.

ALTER TABLE big_orders DROP INDEX idx_customer,

ADD INDEX idx_cust_status_date (customer_id, status, ordered_at);

EXPLAIN SELECT * FROM big_orders WHERE customer_id = 4242 AND ordered_at >= '2026-01-01'\G

CREATE INDEX idx_status_date ON big_orders (status, ordered_at);

SELECT COUNT(*) INTO @n FROM big_orders WHERE ordered_at >= '2026-08-29';

SELECT /*+ NO_SKIP_SCAN(big_orders) */ COUNT(*) INTO @n FROM big_orders

WHERE ordered_at >= '2026-08-29';

Listing 3.100: The leftmost prefix, and skip scan when the prefix is missing

Query OK, 0 rows affected (2.380 sec)

Records: 0 Duplicates: 0 Warnings: 0

*************************** 1. row ***************************

EXPLAIN: -> Index lookup on big_orders using idx_cust_status_date (customer_id = 4242), with

index condition: (big_orders.ordered_at >= TIMESTAMP'2026-01-01 00:00:00') (cost=1.25

rows=15)

1 row in set (0.001 sec)

Query OK, 0 rows affected (2.068 sec)

Records: 0 Duplicates: 0 Warnings: 0

Query OK, 1 row affected (0.001 sec)

Query OK, 1 row affected (0.221 sec)

Output of Listing 3.100 The plan seeks on customer_id alone, because status is missing, and checks the date inside the index (index condition pushdown). Skip scan (MySQL 8.0.13) answered the date query in a millisecond, against 0.22 s without it, by seeking each status in turn. It needs one table, no GROUP BY or DISTINCT, only indexed columns, constant equalities before the skipped columns, and a range after them.

3.11.5 Covering Indexes

An index covers a query that uses only its columns, skipping the second descent; plans say Using index or "Covering index". Every entry holds the primary key, so (customer_id, status, ordered_at) already covers SELECT id, ordered_at, and appending id duplicates it.

SELECT COUNT(*), SUM(total) INTO @n, @s FROM big_orders WHERE customer_id <= 5000;

SELECT COUNT(*), MAX(ordered_at) INTO @n, @m FROM big_orders WHERE customer_id <= 5000;

Listing 3.101: The 100,000 orders of Section 3.11.2, without and with a covering index

Query OK, 1 row affected (0.216 sec)

Query OK, 1 row affected (0.021 sec)

Output of Listing 3.101 SUM(total) needs the rows, so the optimizer scanned the table; MAX(ordered_at) read only the index, ten times faster. SELECT * never can.

3.11.6 Cardinality, Selectivity, and Index Statistics

Cardinality counts distinct values in an index prefix; selectivity divides it by the rows. InnoDB estimates it from 20 random pages per index (innodb_stats_persistent_sample_pages) and refreshes it after 10% of rows change; ANALYZE TABLE refreshes it now. SHOW INDEX and information_schema.STATISTICS report it, and information_schema.TABLES the sizes.

ANALYZE TABLE big_orders;

SELECT index_name, column_name, cardinality FROM information_schema.STATISTICS

WHERE table_schema = 'shop' AND table_name = 'big_orders' AND seq_in_index = 1;

SELECT data_length DIV 1048576 AS data_mib, index_length DIV 1048576 AS index_mib

FROM information_schema.TABLES WHERE table_schema = 'shop' AND table_name = 'big_orders';

SELECT SUM(total) INTO @s FROM big_orders WHERE status = 'pending';

SELECT SUM(total) INTO @s FROM big_orders IGNORE INDEX (idx_status_date)

WHERE status = 'pending';

SELECT SUM(total) INTO @s FROM big_orders WHERE status = 'shipped';

SELECT SUM(total) INTO @s FROM big_orders IGNORE INDEX (idx_status_date)

WHERE status = 'shipped';

Listing 3.102: Statistics and sizes, and an index that helps one value and hurts another

+--------------------+---------+----------+----------+

| Table | Op | Msg_type | Msg_text |

+--------------------+---------+----------+----------+

| shop.big_orders | analyze | status | OK |

+--------------------+---------+----------+----------+

1 row in set (0.036 sec)

+----------------------+-------------+-------------+

| INDEX_NAME | COLUMN_NAME | CARDINALITY |

+----------------------+-------------+-------------+

| idx_cust_status_date | customer_id | 50742 |

| idx_status_date | status | 3 |

| PRIMARY | id | 997984 |

+----------------------+-------------+-------------+

3 rows in set (0.001 sec)

+----------+-----------+

| data_mib | index_mib |

+----------+-----------+

| 37 | 39 |

+----------+-----------+

1 row in set (0.001 sec)

Query OK, 1 row affected (0.039 sec)

Query OK, 1 row affected (0.196 sec)

Query OK, 1 row affected (1.147 sec)

Query OK, 1 row affected (0.295 sec)

Output of Listing 3.102 The sample missed a status (STATS_SAMPLE_PAGES enlarges it); two secondary indexes outweigh the data. Averages hide skew: for the 2% pending orders the index was five times faster than a scan, but for the 74% shipped ones the optimizer still chose it, at almost four times the cost. Keep such columns out of the lead, or use a histogram (Section 3.12.1).

3.11.7 Prefix, Descending, and Invisible Indexes

A prefix index, (body(20)), stores the first n characters, as TEXT and BLOB require; pick the shortest n whose COUNT(DISTINCT LEFT(col, n)) nears the full count, and expect no covering or sorting from it. A descending index (honored since 8.0) serves mixed sort directions. An invisible index is maintained but ignored, a reversible trial of a drop.

CREATE INDEX idx_body ON reviews (body);

SELECT id INTO @i FROM big_orders ORDER BY customer_id, ordered_at DESC LIMIT 1;

CREATE INDEX idx_cust_date_desc ON big_orders (customer_id, ordered_at DESC);

SELECT id INTO @i FROM big_orders ORDER BY customer_id, ordered_at DESC LIMIT 1;

ALTER TABLE big_orders ALTER INDEX idx_cust_date_desc INVISIBLE;

Listing 3.103: A prefix on TEXT, a mixed-order sort, and hiding an index

ERROR 1170 (42000): BLOB/TEXT column 'body' used in key specification without a key length

Query OK, 1 row affected (0.223 sec)

Query OK, 0 rows affected (2.590 sec)

Records: 0 Duplicates: 0 Warnings: 0

Query OK, 1 row affected (0.003 sec)

Query OK, 0 rows affected (0.019 sec)

Records: 0 Duplicates: 0 Warnings: 0

Output of Listing 3.103 Without the descending index MySQL sorted a million rows to return one (0.22 s); with it, the first entry is the answer, and a backward scan serves ORDER BY customer_id DESC, ordered_at. Hidden, it leaves the plans; /*+ SET_VAR(optimizer_switch = 'use_invisible_indexes=on') */ restores it for one statement. Watch the slow query log (Section 3.13.8), then drop it or unhide it. A primary key cannot be hidden (error 3522).

3.11.8 Hash Indexes and the Adaptive Hash Index

A hash index maps a key to a bucket: one probe for =, but no order, so no ranges, prefixes or sorting. Only MEMORY and NDB tables build them:

CREATE TABLE email_lookup (email VARCHAR(255) NOT NULL, id INT UNSIGNED NOT NULL,

INDEX USING HASH (email)) ENGINE = MEMORY;

INSERT INTO email_lookup SELECT email, id FROM customers;

EXPLAIN SELECT id FROM email_lookup WHERE email LIKE 'chen%'\G

Listing 3.104: A prefix search cannot use a MEMORY hash index

Query OK, 0 rows affected (0.014 sec)

Query OK, 8 rows affected (0.007 sec)

Records: 8 Duplicates: 0 Warnings: 0

*************************** 1. row ***************************

EXPLAIN: -> Filter: (email_lookup.email like 'chen%') (cost=3.4 rows=1)

-> Table scan on email_lookup (cost=3.4 rows=8)

1 row in set (0.000 sec)

Output of Listing 3.104 Equality does use the hash index (Index lookup on email_lookup using email). InnoDB given USING HASH builds a B+tree instead, with note 3502. Its own adaptive hash index hashes hot B+tree pages in memory to speed repeated equality lookups, but its latches contend under concurrent joins and scans, so MySQL 8.4 turned it off by default (@@innodb_adaptive_hash_index is 0 here). Being server-wide, it was not benchmarked here.

3.11.9 When an Index Costs More Than It Saves

Each secondary index is one more B+tree for every INSERT, DELETE and relevant UPDATE to change, plus disk and buffer-pool memory, invisible or not:

CREATE TABLE ins_lean (PRIMARY KEY (id)) SELECT * FROM big_orders WHERE id <= 500000;

CREATE TABLE ins_heavy LIKE big_orders;

INSERT INTO ins_heavy SELECT * FROM big_orders WHERE id <= 500000;

Listing 3.105: The same half-million rows loaded with one index and with four

Query OK, 500000 rows affected (3.086 sec)

Records: 500000 Duplicates: 0 Warnings: 0

Query OK, 0 rows affected (0.202 sec)

Query OK, 500000 rows affected (8.733 sec)

Records: 500000 Duplicates: 0 Warnings: 0

Output of Listing 3.105 Three secondary indexes nearly tripled the load time, and two already outweighed the table in Section 3.11.6. Prune with evidence:

  • sys.schema_redundant_indexes flags an index like idx_customer once another starts with its column; exact duplicates draw warning 1831.

  • sys.schema_unused_indexes counters restart with the server and each ALTER TABLE.

  • No index can seek on YEAR(ordered_at) = 2026 or LIKE '%.com'; rewrite the predicate (Section 3.12.9) or index the expression (Section 3.4.8).