High Performance MySQL [Ch.5: Indexing for High Performance]

What an index actually is

Think of the index at the back of a book: look the term up, get a page number, turn to the page. An index does the same for rows, except the "pages" are 16 KB InnoDB pages arranged as a B+Tree. The root and internal pages hold only separator keys and pointers to child pages; every value lives in the leaf pages, sorted, and each leaf is linked to its neighbours in both directions. All leaves sit at the same depth, so every lookup costs the same few page reads — about three or four even at millions of rows.

Because keys are sorted, the engine can descend to a value and then walk sideways for a range — that walk is the whole reason ranges are cheap and arbitrary predicates are not. The links run both ways, so the same walk works backwards for ORDER BY … DESC.

What a leaf entry holds depends on the index. In the primary key it is the whole row. In a secondary index it is the indexed columns plus the row's primary key — never a disk address. Keep that in mind: it explains most of what follows.

Index types, and why B-Tree wins

When people say "index" in MySQL they almost always mean a B-Tree. The others exist for narrower jobs.

A hash index stores a hash of the whole key and a pointer to the row. That makes it compact and quick for equality, but the hashes are in random order, so it can't serve a range or an ORDER BY, and an index on (a, b) hashes both columns together, so a query on a alone can't use it. Low-cardinality columns are its worst case: many rows share one hash, and the engine walks a chain of them on every lookup.

You can only declare hash indexes on MEMORY tables, but InnoDB can build one by itself: the adaptive hash index watches for B-Tree pages that are looked up very often and adds an in-memory hash on top of them. It is on by default in MySQL 8.0 and off by default from 8.4, and it needs no schema change either way.

The three things an index can do

The book's three-star rating: an index earns a star for each job it does for a given query. Most of the win is in the first.

The first star also changes how the disk is read: rows that sit next to each other in the index are read page after page instead of jumping around the table, and an index that delivers order saves the temporary table and the sort that GROUP BY and ORDER BY would otherwise need.

Indexes are not free. Every INSERT, UPDATE and DELETE updates every index on the table, each index takes buffer pool memory, and the optimizer weighs each one when it plans a query. On a tiny table that fits in a few pages a scan is already cheap and an index adds little. The bigger the table, the more one well-chosen index pays for its upkeep.

The leftmost prefix rule

A multicolumn index sorts by the first column, then the second within it, and so on. Lookups have to start at the left and cannot skip a column. Given idx_orders_customer_status_placed (customer_id, status, placed_at):

-- uses the index
WHERE customer_id = 42
WHERE customer_id = 42 AND status = 'paid'
WHERE customer_id = 42 AND status = 'paid' AND placed_at >= '2026-01-01'

-- cannot use it
WHERE status = 'paid'                      -- skips the first column
WHERE customer_id = 42 AND placed_at > ?   -- status skipped, placed_at unusable
WHERE DATE(placed_at) = '2026-01-01'       -- column wrapped in a function

Put differently, the same index can answer five shapes of question, and every one of them starts from the left:

The limit hides in the last row: nothing to the right of the first range can narrow the search. In customer_id = 42 AND status LIKE 'p%' AND placed_at = '2026-01-04', the LIKE is a range, so MySQL walks every 'p…' status of customer 42 and only filters placed_at on the entries it has already read.

MySQL 8.0 softens the "can't skip the first column" rule in one case. When the leading column has very few distinct values and every column the query needs is in the index, the optimizer can do a skip scan: one range per leading value. EXPLAIN shows Using index for skip scan. It reads more than a pinned prefix would, and it disappears as soon as you select a column outside the index.

Keep the column alone

MySQL can only search an index for the column itself. Wrap the column in arithmetic, a function or a cast and the sorted order no longer helps: the engine has to compute the expression for every row and compare. Move the work to the constant side instead.

-- the column is inside an expression: full scan
WHERE id + 1 = 5
WHERE YEAR(reported_at) = 2020
WHERE DATEDIFF(CURRENT_DATE, reported_at) <= 10

-- same rows, the column is alone: index range
WHERE id = 4
WHERE reported_at >= '2020-01-01' AND reported_at < '2021-01-01'
WHERE reported_at >= CURRENT_DATE - INTERVAL 10 DAY

Some versions of the mistake are harder to see:

• Implicit casts. Comparing a string column to a number (WHERE phone = 5551234 on a VARCHAR) makes MySQL convert every row's value to a number, so the index is useless. Quote the literal. The reverse, a number column compared to a string, is fine: only the constant is converted.
• Leading wildcards. LIKE 'abc%' is a range on the index; LIKE '%abc' could start anywhere, so it is a scan.
• Collation or charset mismatches in joins. Joining two string columns with different collations forces a conversion on one side, and that side loses its index.

If you really need to search on an expression, MySQL 8.0.13 and later can index it directly — a functional key part such as INDEX ((YEAR(reported_at))). The query then has to use that exact expression.

Multicolumn indexes and column order

Three mistakes account for most bad multicolumn indexes:

• One index per column. Separate indexes on store_id and status are not a composite index. The best MySQL can do is an index merge — read both, intersect or union the primary keys — which EXPLAIN shows as index_merge. It works, but it costs more than one index on (store_id, status), and it is usually a sign that index is missing.
• Indexing every column of the WHERE clause. One wide index in arbitrary order is no better: only its leftmost prefix helps, and every extra column costs on writes.
• The wrong order. The right columns in the wrong order give you a long, mostly useless index.

The familiar rule — most selective column first — only holds when every predicate is an equality. The stronger rule is equality columns first, range column last. The first range predicate exhausts the index's usable ordering; columns to its right can filter rows the engine already read, but cannot narrow the scan.

-- query: WHERE store_id = 7 AND status = 'late' AND rental_date >= '2025-06-01'
KEY (store_id, status, rental_date)   -- one tight range
KEY (rental_date, store_id, status)   -- walks every rental since June

Selectivity is measurable, not guessable: COUNT(DISTINCT col) / COUNT(*). Check the worst case as well as the average — a column that looks selective overall can still have one value covering a third of the table. And let the queries you actually run decide: an index that also serves the ORDER BY or the GROUP BY can be worth more than one that is slightly more selective.

Clustered indexes: the primary key is the table

InnoDB stores rows inside the primary key's B-Tree. Two consequences dominate schema design.

• Secondary indexes store the primary key, not a row pointer. Finding a row through one costs two descents — the secondary tree, then the clustered tree. That second hop is why a wide primary key inflates every index on the table.
• Insert order is physical order. Monotonic keys append to the last page. Random keys insert into the middle, splitting pages, fragmenting the tablespace and dirtying far more of the buffer pool per write.

What clustering buys you: rows with neighbouring keys share pages, so a primary-key range reads few pages, and a primary-key lookup finds the row itself at the end of a single descent. What it costs: changing a primary key value physically moves the row, and the primary key is copied into every secondary index.

That is why an AUTO_INCREMENT surrogate key is the usual default. A natural key such as an email, or a random UUID, is wider and arrives in random order. If you need UUIDs, store them as BINARY(16) with UUID_TO_BIN(uuid, 1), which puts the time part first so new keys land near the end. Sequential keys have a cost of their own under heavy concurrent inserts: every writer targets the same last page. MySQL 8.0's default innodb_autoinc_lock_mode = 2 stops the counter itself from being a bottleneck. After many random inserts or deletes, OPTIMIZE TABLE rebuilds the table and its indexes compactly.

Covering indexes

If an index contains every column a query touches — select list, filters, joins, sort — the engine answers from the index and never reads a row. EXPLAIN reports Using index. Indexes are far smaller than their tables, so this is the largest win available without changing the question being asked.

-- covered by (customer_id, placed_at): no row fetch
SELECT customer_id, placed_at FROM orders WHERE customer_id = 42;

-- one clustered-tree descent per matching row
SELECT customer_id, placed_at, notes FROM orders WHERE customer_id = 42;

Where the row fetch is unavoidable but the filter is weak, a deferred join — index-only subquery to find the primary keys, then join back for the wide columns — pays for itself on large offsets.

Sorting with an index

An index satisfies an ORDER BY only when the sort columns form a leftmost prefix of it and the directions agree — with one allowance: columns pinned to constants by equality predicates may be skipped over. Mix ascending and descending, or sort by columns from two different tables, and MySQL falls back to a filesort. On a large intermediate result that filesort, not the scan, is the cost.

The rentals table used in several challenges has UNIQUE KEY rental_date (rental_date, inventory_id, customer_id) and KEY (store_id, status, rental_date). These read rows straight from the index in order:

-- first column pinned, sort by the next two
WHERE rental_date = '2025-05-25' ORDER BY inventory_id, customer_id

-- range on the first column, sort starts with that column
WHERE rental_date > '2025-05-25' ORDER BY rental_date, inventory_id

-- every column descending: the index is read backwards
ORDER BY rental_date DESC, inventory_id DESC, customer_id DESC LIMIT 10

-- two columns pinned, sort by the third
WHERE store_id = 7 AND status = 'late' ORDER BY rental_date DESC LIMIT 10

These need a filesort:

-- mixed directions
WHERE rental_date = '2025-05-25' ORDER BY inventory_id DESC, customer_id ASC

-- store_id is not in this index
WHERE rental_date = '2025-05-25' ORDER BY inventory_id, store_id

-- inventory_id is skipped and not pinned
WHERE rental_date = '2025-05-25' ORDER BY customer_id

-- a range on the first column, sort skips it
WHERE rental_date > '2025-05-25' ORDER BY inventory_id, customer_id

-- IN is a range here: several blocks, each sorted on its own
WHERE store_id = 7 AND status IN ('late', 'lost') ORDER BY rental_date DESC

A few rules fall out of those examples:

• EXPLAIN tells you. Using filesort in Extra means MySQL sorts after reading; Backward index scan means it walks the index from the end.
• A filesort ignores LIMIT while reading. To return the top 10 it still has to read every matching row first. With index order, LIMIT 10 stops after about 10 entries.
• Mixed directions need a matching index. Since MySQL 8.0 an index can be declared as (inventory_id DESC, customer_id ASC), and then that mixed sort is free.
• In a join, only the first table's index can sort. Sorting by a column of a later table always means a filesort, so the table you sort by has to drive the join. STRAIGHT_JOIN forces that order when the optimizer picks another.
• For IN, split the query. One index-ordered branch per value, combined with UNION ALL and sorted at the end, reads far fewer rows than a filesort of everything that matches.
• The primary key is the hidden last column. KEY (customer_id) is stored as (customer_id, id), so WHERE customer_id = 42 ORDER BY id DESC is already index-ordered.

Prefix indexes on long strings

Indexing the first n characters keeps the tree small. Pick n by raising it until the prefix's selectivity approaches the full column's, then check the worst-case bucket rather than the average. The cost is real: a prefix index cannot cover a query, and cannot be used for sorting or grouping.

SELECT COUNT(DISTINCT LEFT(title, 8))  / COUNT(*) AS sel8,
       COUNT(DISTINCT LEFT(title, 16)) / COUNT(*) AS sel16,
       COUNT(DISTINCT title)           / COUNT(*) AS full_sel
FROM bugs;

ALTER TABLE bugs ADD INDEX idx_title (title(16));

For TEXT and BLOB columns this is not optional: MySQL can only index them with a prefix length.

Redundant, duplicate and unused indexes

Every index is paid for on every write and in every optimizer decision. An index on (A) is redundant when (A, B) exists — extending the wider index usually beats adding a second one. Duplicates arrive quietly, through separate UNIQUE, PRIMARY KEY and INDEX declarations on the same column. And an index merge in EXPLAIN is not a feature to celebrate; it is the optimizer reporting that no single index fits the query.

Be careful with one case: (A, id) on an InnoDB table looks redundant, because (A) already ends with the primary key. But replacing (A) with (A, B) breaks queries that relied on WHERE A = ? ORDER BY id.

MySQL 8.0 helps on both sides of the problem:

-- indexes made redundant by another index
SELECT * FROM sys.schema_redundant_indexes;

-- indexes not used since the server started
SELECT * FROM sys.schema_unused_indexes;

-- hide an index from the optimizer before you drop it
ALTER TABLE rentals ALTER INDEX idx_customer INVISIBLE;

An invisible index is still maintained on every write, but the optimizer ignores it. If nothing slows down, drop it; if something does, make it VISIBLE again instantly, without a rebuild. Read the unused list carefully: it only covers the time since the last restart, and a monthly report may not have run yet.

Indexes and locking

InnoDB locks the index records it reads, not the rows you meant to change. An UPDATE or SELECT … FOR UPDATE that scans 10,000 index entries to find 10 rows can lock all 10,000 of them, and other transactions that touch them wait.

• REPEATABLE READ, the default, takes next-key locks: the record plus the gap before it, so no new row can be inserted into the scanned range until the transaction ends.
• READ COMMITTED releases locks on rows that turned out not to match, and takes gap locks only for foreign key and duplicate key checks.
• Index condition pushdown (since 5.6) checks conditions on index columns while still inside the index, before the row is fetched. EXPLAIN shows Using index condition. It works on secondary indexes only, and it means fewer rows are fetched and locked.

So a tight index is also a concurrency tool: the fewer entries a write has to walk, the fewer rows it locks. The QueryCrack sandbox only runs plain SELECT statements, so you won't take locks here, but the read count you are minimising is the same number that decides how much a write would lock.

How this shows up in your verdict

You cannot add indexes here — every challenge ships a fixed schema. What you change is whether the query lets the engine use them, and the grader reads that straight off the handler counters. To see what you are working with, Run SHOW INDEX FROM bugs, then EXPLAIN your query and check which index lands in the key column.

Common questions