Composite Index + Prefix Rule

DatabasesMiddb

The Question

What is a composite index and how does the prefix rule apply?

What a Strong Answer Covers

• Leftmost prefix rule.

Senior-Level Answer

A composite index (also called a multi-column index) is an index built on two or more columns in a defined order. The key principle governing its use is the leftmost prefix rule: the database can use the index only when the query's predicates include the leading columns of the index in order, without skipping.

For a composite index on `(last_name, first_name, birth_year)`, the following queries can use the index: filtering on `last_name` alone, `last_name + first_name`, or `last_name + first_name + birth_year`. Filtering on `first_name` alone or `birth_year` alone cannot use the index because the leftmost column (`last_name`) is absent from the predicate.

The prefix rule exists because composite indexes are sorted first by the leftmost column, then by the next column within each group of equal leftmost values, and so on. Scanning the index without the leftmost column would require a full index scan — at which point a full table scan may be comparable or cheaper.

Range predicates on an intermediate column stop the index from being used for filtering on subsequent columns. For `WHERE last_name = 'Smith' AND first_name LIKE 'J%' AND birth_year = 1985`, the index is used for `last_name` (equality) and `first_name` (range), but `birth_year` cannot be satisfied from the index — it requires a post-filter on qualifying rows.

Composite index column order should reflect your most selective and most commonly used filter first. Equality predicates should come before range predicates in the index definition, as range predicates terminate prefix utilization. Covering indexes extend this concept: by including all columns referenced in the query (SELECT + WHERE + ORDER BY), the database can satisfy the query entirely from the index without touching the heap table, eliminating a second I/O lookup.

What Separates a 2/3 from a 3/3

Common Mistakes

• Thinking the index on (A, B, C) can be used for filtering on B or C alone — only leading prefixes are usable.
• Not knowing that a range predicate on column B stops the index from filtering on column C.
• Putting low-selectivity columns first in the index definition — high-selectivity (most distinct values) columns first produces smaller, faster scans.
• Confusing a composite index with multiple single-column indexes — a composite index is one sorted structure, not two independent indexes merged.

Follow-Up Questions

• You have an index on (country, city, zip). Which of these queries can use it: WHERE city = 'NYC', WHERE country = 'US' AND zip = '10001', WHERE country = 'US' AND city = 'NYC'? — Only WHERE country='US' AND city='NYC' uses the full (A,B) prefix. WHERE city='NYC' alone skips the first column. WHERE country AND zip skips city — index used for country only.
• What is a covering index and why is it faster than a regular composite index? — All queried columns are in the index — no heap lookup needed. The database satisfies the query entirely from the index pages, halving I/O.
• Why should equality predicates come before range predicates in composite index column order? — Equality columns can fully narrow the scan. A range predicate stops subsequent columns from being used for filtering — so put equality columns first to maximize prefix utilization.
• Can MySQL use an index on (A, B) to satisfy ORDER BY B when filtering WHERE A = constant? — Yes — filtering on A = constant effectively collapses the first dimension, and rows are then ordered by B within that group. The ORDER BY B can use the index.

Related Questions

• ACID
• Indexes
• Clustered vs Non-clustered
• Isolation Levels
• Normalization