Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 75 ยท Indexes and Performance

How MySQL Indexes Work

Understand MySQL indexes from the inside: B-trees, the clustered primary key, secondary indexes that hold the primary key, covering indexes, selectivity and cardinality.

An index is the difference between a query that takes a millisecond and one that reads the whole table. Almost every performance problem in a MySQL application ends with "add the right index" or "stop defeating the index you have." To do that reliably you need a mental model of what an index actually is, not a list of rules.

This lesson builds that model for InnoDB: the B-tree, the clustered primary key, secondary indexes, covering indexes, and the two numbers that decide whether an index is worth having, selectivity and cardinality. The live examples run on SQLite, whose indexes are also B-trees and whose EXPLAIN QUERY PLAN shows the same decisions in different words. Statements that only work on a MySQL server (SHOW INDEX, ANALYZE TABLE) are shown read-only.

What an index is

A sorted tree Keys in order, found by a short descent.
Pointers to rows In InnoDB, the primary key value.
Extra copy of data Costs disk, memory and write time.
1 / 2

Why a sorted tree

Without an index, finding WHERE email = '[email protected]' means reading every row and testing it. That is a full table scan, and its cost grows with the table. A B-tree (InnoDB uses the B+tree variant) keeps keys in sorted order inside pages, with a small tree of branch pages above them. The search starts at the root page, picks the child whose range contains the key, and repeats until it reaches a leaf page. Because each page holds hundreds of keys, three or four page reads find one key among hundreds of millions.

Sorted order buys more than point lookups:

  • Ranges: WHERE total BETWEEN 100 AND 200 finds the first key, then walks along the linked leaf pages until the range ends.
  • Ordering: ORDER BY total can read the index in order instead of sorting.
  • Prefix matches: WHERE name LIKE 'Ad%' is a range over the sorted keys. LIKE '%da' is not, because the start of the string is unknown, so it cannot use the index for seeking.
  • Min and max: the smallest and largest keys sit at the two ends of the tree.

Hash indexes (the MEMORY engine) can only answer equality, which is why B-trees are the default for InnoDB. MySQL also has FULLTEXT indexes (see Full-Text Search) and SPATIAL R-tree indexes (see Spatial Data and Geometry).

The clustered index and secondary indexes

As you saw in InnoDB Architecture, an InnoDB table is its primary key B+tree, and the leaf pages contain whole rows. Every other index is a secondary index whose leaf entries are the indexed columns plus the primary key.

flowchart TD
  Q["WHERE email = '[email protected]'"] --> S["Secondary index<br/>(email) tree"]
  S -->|"leaf holds email + id"| P["id = 42"]
  P --> C["Clustered index<br/>(id) tree"]
  C -->|"leaf holds the full row"| R["Row 42"]

A secondary lookup first finds the primary key, then descends the clustered tree for the row.

That second descent is called a bookmark lookup (or "back to the table"). For a handful of rows it is cheap. For thousands of rows it means thousands of random reads in the clustered tree, which is why the optimizer sometimes ignores a secondary index and scans the table instead.

The model gives you three practical rules:

  1. Primary key lookups are the fastest and should be used for single-row access whenever possible.
  2. Keep the primary key short. Its value is stored in every entry of every secondary index. A BIGINT UNSIGNED (8 bytes) key makes each entry far smaller than a 36-character UUID string.
  3. Insert primary keys in increasing order when you can, so new rows append to the right edge of the tree instead of splitting pages in the middle.

This live example creates a table, runs the same lookup without and then with an index, and shows what the primary key does for free:

SQL Scan, search and covering

Press Run (or Ctrl + Enter) to see the result here.

The first plan says SCAN, the second SEARCH ... USING INDEX, and the last COVERING INDEX. In MySQL's EXPLAIN these map to type: ALL, type: ref, and Extra: Using index. The next lessons read those columns in detail, in EXPLAIN and EXPLAIN ANALYZE.

Covering indexes

A covering index contains every column a query needs, so MySQL answers it from the index alone and never touches the clustered tree. In plan 4 above, id and email are both in the email index, because every secondary index carries the primary key. No row lookup is needed.

You can design covering indexes on purpose by adding the selected columns to the end of an index:

SQL
-- Typical query:
SELECT customer_id, total
FROM orders
WHERE status = 'paid' AND placed_at >= '2025-01-01';

-- An index that holds everything the query touches (and the primary key automatically):
ALTER TABLE orders ADD INDEX idx_status_placed_cust_total (status, placed_at, customer_id, total);

EXPLAIN shows Using index in Extra when it works. The trade-off is size: every extra column makes the index bigger, slower to maintain and less likely to stay in the buffer pool. Cover your hottest queries, not all of them. Selecting * almost never benefits from a covering index, which is one more reason to list columns.

Selectivity and cardinality

An index only helps when it narrows the search. Two numbers describe that:

  • Cardinality: the number of distinct values in the indexed column(s). MySQL stores an estimate for each index, visible in SHOW INDEX FROM orders (the Cardinality column) and information_schema.statistics.
  • Selectivity: cardinality divided by the number of rows. A unique email column has selectivity 1.0. A column holding only 0 and 1 has a selectivity near zero.

A boolean or status column with two or three values has poor selectivity: WHERE active = 1 matches half the table, and reading half the table through an index (with a bookmark lookup for each row) is slower than just scanning it, so the optimizer will usually pick the scan. Such a column is useful as part of a composite index next to a selective column, which is the subject of Designing Composite Indexes.

The next example measures selectivity with plain SQL, then lets SQLite gather index statistics with ANALYZE, much like ANALYZE TABLE does in MySQL:

SQL Measuring selectivity

Press Run (or Ctrl + Enter) to see the result here.

stat reads as "5000 rows, 100 rows per distinct value" for the city index and "5000 rows, 2500 per value" for the active index. A city lookup is expected to find 100 rows and an active lookup 2,500, so the planner prefers the city index. MySQL makes the same kind of estimate from its stored cardinality.

How MySQL keeps statistics

InnoDB estimates cardinality by sampling a number of index pages (20 by default, innodb_stats_persistent_sample_pages) and stores the result persistently. It refreshes automatically after about 10% of a table changed, and you can force it:

SQL
ANALYZE TABLE orders;
SHOW INDEX FROM orders;

If the optimizer picks a poor index after a big data load, stale or inaccurate statistics are a prime suspect. For skewed columns that have no index, MySQL 8.0 can also build a histogram: ANALYZE TABLE orders UPDATE HISTOGRAM ON status WITH 16 BUCKETS;, so it estimates filter selectivity better even though it cannot seek on them.

The cost of indexes

Indexes are not free:

  • Writes get slower. Each INSERT and DELETE updates every index, and each UPDATE of an indexed column updates that index.
  • Disk and memory. Each index is a copy of its columns. A table with ten indexes can be mostly index, and indexes compete with data for the buffer pool.
  • Optimizer choices. More indexes mean more options to evaluate, and sometimes worse choices.

Create the indexes your queries need, and remove the ones nothing uses (see The Data Dictionary, information_schema and sys Schema). Foreign key columns need an index too, and InnoDB creates one automatically if you forget (see Foreign Keys in MySQL).

InnoDB limits an index key to 3,072 bytes (for the default DYNAMIC row format) and a composite index to 16 columns. With utf8mb4, one VARCHAR(255) column can need 1,020 bytes, so very wide string keys are limited in practice. A prefix index such as INDEX (title(40)) indexes only the first characters and is covered in the next lesson.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In InnoDB, what does a secondary index entry store besides the indexed columns?

    The primary key value is stored so InnoDB can find the full row in the clustered index. It also makes the primary key available for free when the query only needs it, which helps covering indexes.
  2. 2. Which query can be answered entirely from an index on (email)?

    id (the primary key) and email are both in the secondary index. The other queries need columns that only exist in the clustered index, so they need a bookmark lookup.
  3. 3. Why is a single index on a 0/1 flag column usually not chosen for WHERE flag = 1?

    Low selectivity means little narrowing. Reading half the table through an index plus a lookup per row costs more than a sequential scan, so the optimizer prefers the scan.
  4. 4. Which pattern cannot use an index to seek on the start of the key?

    A leading wildcard means the beginning of the value is unknown, so the sorted order cannot be used to find a starting point.

Summary

  • An index is a sorted B+tree, found by a short descent, that supports equality, ranges, ordering and prefix matches.
  • An InnoDB table is its clustered primary key tree. Secondary indexes store the indexed columns plus the primary key, so they need a second descent unless they cover the query.
  • Keep primary keys short and increasing, because they are copied into every secondary index.
  • A covering index answers a query without touching the table. EXPLAIN shows Using index.
  • Selectivity (distinct values divided by rows) decides whether an index narrows the search. Low-selectivity columns work best inside composite indexes.
  • InnoDB cardinality is sampled and can be refreshed with ANALYZE TABLE. Every index costs writes, disk and memory.

Next: Designing Composite Indexes, where column order makes or breaks an index.