Composite Indexes and the Leftmost Prefix Rule in MySQL

"But the index is there!" I hear this from developers about once a month. Usually it's a multi-column index and the query doesn't use its columns in an order the optimizer can exploit. The leftmost prefix rule is the most useful thing I know about MySQL indexing, and it takes ten minutes to learn.

How a composite index is stored

An InnoDB secondary index on (customer_id, status, created_at) is a B-tree sorted first by customer_id, then by status within each customer, then by created_at within each status. Think of a phone book sorted by last name, then first name, then street. You can find everyone named Smith fast, and every Smith called John fast, but you cannot efficiently find everyone called John regardless of last name – the Johns are scattered across the whole book.

That is the leftmost prefix rule: a query can use the index for an equality or range condition on a leading, contiguous subset of the columns, and once a range condition is hit, the columns after it can no longer be used for lookups (only for filtering and possibly sorting).

A test table

CREATE TABLE orders (
  id          BIGINT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
  customer_id INT UNSIGNED NOT NULL,
  status      TINYINT UNSIGNED NOT NULL,
  created_at  DATETIME NOT NULL,
  total       DECIMAL(10,2) NOT NULL,
  KEY idx_cust_status_created (customer_id, status, created_at)
) ENGINE=InnoDB;

Fill it with a few hundred thousand rows from a real dataset or a generator so the optimizer has meaningful statistics; on a nearly empty table EXPLAIN will happily choose full scans.

Queries that use the index

EXPLAIN SELECT * FROM orders WHERE customer_id = 4411;
EXPLAIN SELECT * FROM orders WHERE customer_id = 4411 AND status = 2;
EXPLAIN SELECT * FROM orders WHERE customer_id = 4411 AND status = 2 AND created_at >= '2017-12-01';

All three show key: idx_cust_status_created. The interesting column is key_len: 4 for the first (only customer_id, an INT), 5 for the second (plus the one-byte TINYINT), 10 for the third (plus the 5-byte DATETIME). key_len tells you exactly how many leading columns are being used for the lookup.

Queries that can't

EXPLAIN SELECT * FROM orders WHERE status = 2;
EXPLAIN SELECT * FROM orders WHERE created_at >= '2017-12-01';
EXPLAIN SELECT * FROM orders WHERE status = 2 AND created_at >= '2017-12-01';

None of these starts with customer_id, so the result is type: ALL and key: NULL, or at best an index scan (type: index) reading the whole index. If these queries matter, they need their own index starting with status or created_at.

The subtle case is skipping a middle column:

EXPLAIN SELECT * FROM orders WHERE customer_id = 4411 AND created_at >= '2017-12-01';

key_len is 4: only customer_id is used for the lookup. All orders for that customer are read and then filtered by date. On 5.7 Extra shows Using index condition, meaning the filter happens inside the storage engine, which is cheaper but still not a real range scan. If this query is common, (customer_id, created_at) is the right index for it.

A range condition ends the prefix

EXPLAIN SELECT * FROM orders
WHERE customer_id = 4411 AND status IN (1,2,3) AND created_at >= '2017-12-01';

IN on status is a set of equalities, so the optimizer can still use created_at for each value (key_len 10). But swap in a real range:

EXPLAIN SELECT * FROM orders
WHERE customer_id = 4411 AND status > 1 AND created_at >= '2017-12-01';

Now key_len drops to 5. Everything after the first range predicate is filtered, not sought. When I design an index I put equality columns first and the range column last, every time.

ORDER BY and covering indexes

Because the index is sorted, this query needs no sort:

EXPLAIN SELECT id, created_at FROM orders
WHERE customer_id = 4411 AND status = 2 ORDER BY created_at DESC LIMIT 20;

Extra should not contain Using filesort. It also shows Using index, because id (the primary key is appended to every secondary index in InnoDB), created_at, customer_id and status are all in the index – a covering index that never touches the table rows. Adding total to the SELECT list would remove Using index and force a lookup per row.

Don't trust EXPLAIN alone

Measure too. Enable the handler counters and run the query:

FLUSH STATUS;
SELECT * FROM orders WHERE customer_id = 4411 AND status = 2 AND created_at >= '2017-12-01';
SHOW SESSION STATUS LIKE 'Handler_read%';

Handler_read_key and Handler_read_next should be small and proportional to the result size. A large Handler_read_rnd_next means a table scan happened regardless of what the plan promised.

Notes

• Redundant indexes: with (customer_id, status, created_at) in place, a separate index on (customer_id) is redundant and only costs write performance. pt-duplicate-key-checker from Percona Toolkit finds these.
• Column order is not about cardinality first: put the columns used with equality in the most queries first, then the range column. High cardinality first is a rule of thumb that only applies when all columns are used with equality.
• EXPLAIN on 5.7 has EXPLAIN FORMAT=JSON, which shows used_key_parts explicitly, so you do not need to compute key_len by hand.
• Functions on indexed columns (WHERE DATE(created_at) = '2017-12-01') disable the index for that column entirely. Rewrite as a range: created_at >= '2017-12-01' AND created_at < '2017-12-02'.

Next I'd read up on index condition pushdown and how the optimizer chooses between two candidate indexes. That's where it gets murky.