A table has a single B+Tree index whose key is the column list (a, b, c). Which filter combinations can that index serve efficiently, and which cannot? Explain the leftmost-prefix rule behind your answer.
answer
- Dictionary ordering: first letter, then second
- Seek needs a contiguous range
- Prefixes are free indexes
- Break the chain → rest is filter only
- Skip scan only at tiny leading cardinality
basics
~20 sThe index is sorted by a, then by b within equal a, then by c. It helps when the filter pins a leading prefix: a alone, a and b, or all three. Filters on only b, only c, or b and c cannot seek in it.
solid answer
~60 sA composite index stores entries sorted by the concatenation of its key columns in declared order: first by `a`, then by `b` among rows with equal `a`, then by `c`. A B+Tree can only descend to one contiguous range of that ordering, so the engine narrows the search only while it knows the value of every key column starting from the left. So `a = ?`, `a = ? AND b = ?`, and `a = ? AND b = ? AND c = ?` all get an efficient seek. `b = ?` alone does not: rows with `b = 5` are scattered across the whole index because `a` dominates the sort. Same for `c` alone or `b AND c`. Two caveats worth saying aloud. The index may still be *read* end-to-end as a full index scan for a non-prefix predicate if it is much narrower than the table. And some engines do an index skip scan, looping over the few distinct leading values when `a` has very low cardinality. Neither is as good as a true prefix seek.
code
sql · 13 linesCREATE INDEX idx_abc ON t (a, b, c);
-- seeks (leading prefix)
SELECT * FROM t WHERE a = 7;
SELECT * FROM t WHERE a = 7 AND b = 3;
SELECT * FROM t WHERE a = 7 AND b = 3 AND c = 'x';
-- cannot seek (no leading column)
SELECT * FROM t WHERE b = 3;
SELECT * FROM t WHERE b = 3 AND c = 'x';
-- seeks on a only; c applied as a filter afterwards
SELECT * FROM t WHERE a = 7 AND c = 'x';go deeper
State the rule and the pass/fail list: entries are sorted left to right, so you must filter on a leading prefix. Being able to name which of three example queries uses the index is enough.
Explain why — a B+Tree seek needs one contiguous range in the sort order — and note that a missing prefix column downgrades the plan to a scan or filter rather than to nothing.
Add the degraded modes (full index scan, skip scan, prefix seek plus residual filter) and turn the rule into design advice: pick leftmost by which prefixes your query shapes need, and drop indexes that are prefixes of others.
Frame it as access-path budgeting: each composite index buys N prefix access paths at one write cost, so index-set design is about covering query shapes with the fewest keys while keeping write amplification bounded.
## One tree, not three An index on `(a, b, c)` is a single B+Tree whose key is an ordered tuple. It is not three indexes. Every entry holds `(a_value, b_value, c_value)` plus a row pointer, and entries are ordered lexicographically: compare `a`; only on a tie compare `b`; only on a further tie compare `c`. This is exactly how words are ordered in a dictionary by their first letter, then second, then third. ## Why a prefix is required A B+Tree search is a descent from the root to one leaf position, followed by a walk forward. That mechanism can only answer the question "where does the ordering region I care about start, and where does it end?" The region has to be **contiguous** in the sort order. - `a = 7` is contiguous: every entry with `a = 7` sits together. - `a = 7 AND b = 3` is contiguous: inside the `a = 7` block, entries are sorted by `b`. - `b = 3` alone is **not** contiguous: `(1,3,…)`, `(2,3,…)`, `(9,3,…)` are spread across the entire tree with unrelated entries between them. There is no single start position to descend to. Hence the rule: an index on `(c1, c2, …, cn)` can be seeked using predicates on `c1`, `c1+c2`, `c1+c2+c3`, and so on — a **leftmost prefix** of the key. Break the chain and everything to the right of the break stops contributing to the seek. ## What "cannot use the index" really means It does not always mean the index is untouched. Three degraded modes exist: 1. **Full index scan.** The engine reads every leaf entry and filters in memory. Still cheaper than a table scan when the index is far narrower than the row, but the cost is proportional to the whole table. 2. **Index skip scan.** Some engines synthesize the missing leading column: if `a` has only 4 distinct values, they run four seeks (`a = v1 AND b = 3`, `a = v2 AND b = 3`, …). This only pays off at very low leading-column cardinality and is not something to rely on when designing. 3. **Partial prefix.** `a = ? AND c = ?` seeks on `a` only; `c` is then applied as a filter to each entry in the `a` block. The `c` column narrows the rows returned but not the pages read. ## Consequences for design - The number of useful access paths from one index equals the number of its prefixes, so `(a, b, c)` gives you `(a)`, `(a, b)`, and `(a, b, c)` for free. A separate index on `(a)` is redundant. - Order the key so the column that the most query shapes filter on sits leftmost; a column no query ever filters on independently should not be leftmost. - The rule is about the *index key*, not about how the predicates are written in the query. - Equality on the leading columns is what keeps the tail columns useful; a range on a leading column weakens everything after it (a separate ordering concern). ## The interview version Say: entries are sorted by the concatenated key, a tree seek needs a contiguous range, therefore only a leading prefix of the key can be used to seek. Then give the concrete pass/fail list, then mention full-index-scan and skip-scan as the nuance.
- Does an index on (a, b) make a separate index on (a) redundant?Yes, for lookup purposes: any query that could seek on the single-column index can seek the same way on the leading prefix of the composite one. The composite index is slightly wider, so its scans read a few more pages, but that rarely justifies keeping both. The single-column index still costs writes and space on every insert, update and delete, so it is usually dropped.
- Is an index on (a, b) interchangeable with one on (b, a)?No. They support different prefixes: the first serves `a = ?` and `a = ? AND b = ?`, the second serves `b = ?` and the same two-column predicate. Only the combined equality predicate works well on both. Which one you build depends on whether queries also filter on `a` alone or `b` alone.
- If a query filters on b only and the plan still shows the index being used, what is happening?Almost certainly a full index scan or a skip scan rather than a seek. A full index scan reads every leaf entry and applies the `b` predicate in memory, which the planner may still prefer because the index is narrower than the table. A skip scan iterates the distinct leading values and seeks under each, and is only cheap when the leading column has very few distinct values.
A phone book sorted by (last name, first name). You can find all Smiths, and all Smiths named John. You cannot find every John without reading the whole book — Johns are scattered under every last name.
saying these in an interview costs you the question
- Believing CREATE INDEX on (a, b, c) creates three separate usable indexes
- Claiming any query mentioning any indexed column gets an efficient index seek
- Saying the order of columns in the index definition does not matter
- Confusing the index key order with the order predicates appear in the WHERE clause
- Assuming skip scan makes leading-column order irrelevant in practice