A 50-million-row orders table has a `status` column with three possible values, where roughly 99% of rows are 'COMPLETED', 1% are 'PENDING', and a handful are 'FAILED'. Is a plain B+Tree index on `status` worth creating? Explain your reasoning.
answer
- 3 values ≠ automatically useless — check skew
- uniform estimate 50M/3 ≈ 16.7M → index rejected
- rare value + MCV/histogram → index chosen
- queue pattern: only the rare side is queried
- status changes = index maintenance on every transition
basics
~20 sIt depends on which value you query. Searching 'COMPLETED' matches ~49.5 million rows, so the optimizer will scan and ignore the index. Searching 'PENDING' or 'FAILED' is highly selective and the index helps a lot. Skewed low-cardinality columns are worth indexing only for their rare values.
solid answer
~60 sCardinality alone says no — three distinct values — but the data is skewed, so the answer is per value. - `status = 'COMPLETED'` matches about 49.5M rows. Any index path would mean tens of millions of scattered row fetches; a sequential scan is far cheaper, so the optimizer will ignore the index. - `status = 'PENDING'` matches about 500K rows — 1% — which is borderline but often still worth an index, especially if the query also has an ordering or a further filter. - `status = 'FAILED'` matches a few rows and is an excellent index candidate. So the index is justified *if* the workload queries the rare values, and the engine must have per-value information (a most-common-value list or histogram) to see that; without it, the uniform assumption estimates ~16.7M rows for every value and the index never gets used. In practice a better shape is usually a composite index leading with `status` plus the column you also filter or sort by, or a filtered index restricted to the rare values — both cut the index far smaller than a full-column index.
code
sql · 7 linesCREATE INDEX idx_orders_status_created ON orders (status, created_at);
SELECT order_id
FROM orders
WHERE status = 'PENDING'
ORDER BY created_at
LIMIT 100;go deeper
Say the answer depends on which value is searched: rare values benefit, the 99% value does not, because the index would fetch almost every row anyway.
Quantify it — 49.5M versus 500K versus a handful — and explain the crossover, plus that the planner needs per-value statistics to distinguish them.
Argue from the workload, propose a composite or restricted index instead of the full-column one, and weigh the maintenance cost on a column that is updated on every state transition.
Treat it as a design question about the queue access pattern: whether the pending set belongs in the same table at all, what the steady-state size of the hot subset is, and how index shape follows from that.
## The naive rule and why it is incomplete The rule of thumb "don't index low-cardinality columns" comes from the uniformity assumption. With 50,000,000 rows and 3 distinct values, the default estimate for any equality predicate is 50,000,000 / 3 ≈ 16,700,000 rows — a third of the table. No optimizer will choose an index path for that, because performing 16.7 million individual row fetches, each hitting a more-or-less random page, costs vastly more than reading the table's pages in order. But the rule assumes even distribution, and real status columns are almost never even. The distribution here is 99 / 1 / ε. The correct framing is therefore not "is this column low-cardinality?" but "what fraction of the table does the predicate I actually run keep?" ## Value-by-value analysis - **'COMPLETED' — ~49,500,000 rows (99%).** Hopeless for an index. If anything, this is the query you want to avoid running unfiltered at all; it is asking for the whole table and should be paginated, aggregated, or served from a different structure. - **'PENDING' — ~500,000 rows (1%).** This is the interesting case. One percent is usually inside the range where an index wins, but 500,000 row lookups is still a lot of work in absolute terms. Whether it pays depends on what else the query does: if it is `WHERE status = 'PENDING' ORDER BY created_at LIMIT 100`, an index that carries the ordering can stop after 100 rows and is a dramatic win. If the query aggregates all 500,000 rows, the margin is thinner. - **'FAILED' — tens or hundreds of rows.** Textbook high selectivity. The index turns a 50-million-row scan into a handful of page reads. A queue-shaped workload — "find work that still needs doing" — is exactly the pattern where a skewed status column deserves an index, because the workload only ever asks for the rare side. ## The optimizer has to *know* about the skew An index only helps if the planner picks it, and it will only pick it if its estimate for `status = 'FAILED'` is small. With nothing but a distinct-value count it estimates 16.7 million for every value and rejects the index for all three. What rescues the case is per-value statistics: a most-common-values list with frequencies, or a histogram. With those in place the engine estimates ~49.5M for 'COMPLETED' (scan) and ~100 for 'FAILED' (index), from the same index and the same column. So on skewed columns, making sure statistics are gathered with enough detail is part of making the index usable at all. ## Better index shapes for this case A full-column index on a 99%-skewed column stores 50 million entries, and 49.5 million of them are for a value that will never be looked up through the index. You pay for those entries on every insert, on every status transition, in storage and in cache footprint — all to serve queries that only ever touch 1% of them. Two standard refinements: 1. **Composite index leading with `status`.** `(status, created_at)` serves "oldest pending items first" directly: the engine seeks to the `status` value and walks entries already in `created_at` order, so a `LIMIT` stops early with no sort. It costs the same number of entries as the single-column index but is far more useful. 2. **An index restricted to the rare values**, where the engine supports indexing a subset of rows. That version holds ~500,000 entries instead of 50,000,000: dramatically smaller, cheaper to maintain, and it stops paying maintenance cost for rows in the state you never search for. Rows transitioning into the terminal state fall out of the index entirely. ## A note on how you'd defend the answer The strong answer is not "yes" or "no" — it is "show me the queries". Ask which predicate values appear in the workload, whether the query has an ordering or a limit, and how skewed the data really is. Then note the write-side cost, since `status` is by definition a column that gets updated: every transition is index maintenance. A column that is both low-cardinality and frequently updated is the worst-case candidate for a wide index, and the best candidate for a narrow, restricted one.
- What would make you reverse your answer and drop the index entirely?If the workload never filters on the rare values — for example every query is a dashboard count grouped by status, which reads everything anyway. Also if the rare state is transient and tiny enough that the table's hot pages are all cached, or if `status` churns so heavily that maintenance cost on a write-heavy table outweighs the read benefit.
- The index exists and the statistics show the skew, yet the plan still scans for `status = 'FAILED'`. What would you check?Whether the value in the query is a bound parameter, since some engines plan generically for parameters and fall back to an average-selectivity estimate rather than the per-value one. Also check for a type mismatch or a function wrapping the column that makes the predicate unusable by the index, and confirm the statistics were actually refreshed after the data grew.
saying these in an interview costs you the question
- Answering "never index a low-cardinality column" as an absolute rule without asking about skew or which values are queried.
- Believing an index on a boolean or 3-value column helps every predicate on it equally.
- Ignoring that the optimizer needs per-value statistics to see the skew at all.
- Forgetting the write-side cost of indexing a column that changes state on nearly every row.
- Assuming the full-column index is the only option, and not considering a composite or restricted index.