skip to content

What do the terms "cardinality" and "selectivity" mean when a database query optimizer reasons about a column or a filter predicate, and how do they decide whether using an index pays off?

level: juniorimportance: must knowfreq 68%

answer

  1. cardinality = count of distinct values
  2. selectivity = fraction kept; high selectivity = few rows
  3. rows ≈ total / NDV under uniformity
  4. index cost ≈ one random fetch per matched row
  5. crossover: scan wins past a small percentage

basics

~20 s

Cardinality is a row count: how many distinct values a column holds, or how many rows a plan step returns. Selectivity is the fraction of rows a predicate keeps. Indexes pay off when that fraction is tiny, because each match costs a separate row lookup.

solid answer

~60 s

**Cardinality** is a count of rows. *Column* cardinality is the number of distinct values in the column: a primary key has cardinality equal to the row count, an `is_active` flag has cardinality 2. *Estimated* cardinality of a plan step is how many rows the optimizer thinks that step will emit. **Selectivity** is the fraction of rows that survive a predicate: matching rows / total rows. The naming trips people up — a *highly selective* predicate keeps a *small* fraction. The optimizer prices an index access as: descend the tree, walk the matching key range, then fetch each matching row from the table — roughly one scattered read per row. So a predicate keeping 20 rows out of 10 million is an easy index win. A predicate keeping 3 million rows means 3 million scattered fetches, which costs far more than reading the table sequentially. So high-cardinality column plus an equality predicate gives high selectivity and a useful index; a low-cardinality column means each value matches a big slice of the table and the index rarely earns its keep.

code

text · 4 lines
text
-- 10,000,000 rows, order_id unique, status has 3 values
WHERE order_id = 88213      -> est. 1 row      -> index seek + 1 lookup
WHERE status = 'COMPLETED'  -> est. 9,900,000  -> full scan (index would
                                                  cost ~9.9M random fetches)

go deeper

for a junior

Define both terms cleanly, give a unique-id column versus a boolean column as examples, and say indexes help when few rows match.

for a middle

Add the rows ≈ total/NDV estimate, the uniformity assumption, and the cost model that makes index lookups lose past a crossover point.

for a senior

Talk about per-value selectivity versus per-column cardinality, skew, and how estimation errors at the leaves propagate into join order choices.

for a principal

Frame selectivity as the input to the whole cost model and discuss where estimation is structurally unreliable — skew, correlation, multi-predicate independence assumptions — and what design choices reduce dependence on good estimates.

## Two words people mix up **Cardinality** always means *a count of rows*, but it shows up in two places: - **Column cardinality**, also called NDV (number of distinct values): how many different values the column actually contains. `order_id` in a 10-million-row orders table has cardinality 10,000,000 (unique). `country_code` might have cardinality 200. `is_deleted` has cardinality 2. - **Estimated cardinality of a plan step**: how many rows the optimizer predicts a scan, filter, or join will emit. Every cost estimate in a plan is built on these numbers. **Selectivity** is a ratio between 0 and 1: rows matching the predicate divided by total rows. `WHERE order_id = 5` on 10 million unique ids has selectivity 0.0000001. `WHERE is_deleted = false` might have selectivity 0.97. The vocabulary is inverted from intuition: *high selectivity* = small fraction returned = picky predicate. Some engines and books use *density* for the inverse (average fraction per distinct value); density = 1 / cardinality under a uniformity assumption. ## How the optimizer turns them into a decision For an equality predicate on a column with no better information, the classic estimate is: estimated rows ≈ total rows / distinct values That is the uniform-distribution assumption. For a range predicate the engine interpolates between the stored minimum and maximum, or reads a histogram if one exists. With an estimated row count in hand, the optimizer compares access paths: - **Full table scan**: read every page, sequentially. Cost is roughly the table's page count, and sequential reads are cheap per page — the storage layer reads ahead, and on spinning disks there is no seek per row. - **Index access with row lookups**: a few page reads to descend the B+Tree, a walk over the matching leaf entries, then — for each matching entry — a fetch of the actual row, which lands on an essentially random page. Cost grows roughly linearly with the number of matching rows, and each of those fetches is a random access. The crossover point is why selectivity is the whole game. When matches are few, the index does a handful of reads instead of thousands. When matches are many, the index performs *more* I/O than the scan: it can touch the same table page repeatedly, in an unhelpful order, plus pay for the index reads on top. Engines put the practical crossover surprisingly low — often somewhere in the single-digit to low-double-digit percentage of the table, depending on how wide the rows are and how much is cached. ## Why a column's cardinality is only half the story Cardinality is a property of the column; selectivity is a property of *a predicate on a value*. They coincide only when the data is evenly distributed. In real systems it usually is not: a `status` column with three values may be 99% `COMPLETED`, so `status = 'COMPLETED'` is useless to an index while `status = 'FAILED'` is extremely selective. Two queries, same column, same index, opposite verdicts. That gap between per-column cardinality and per-value selectivity is exactly what histograms exist to close. A second subtlety: selectivity applies to a *combination* of predicates too. If a query filters on three columns, the engine has to estimate the combined fraction, and by default it assumes the predicates are independent and multiplies their selectivities. When the columns are correlated, that multiplication underestimates badly. ## What this means in practice - Index the columns your queries filter on with *high selectivity*: identifiers, foreign keys, emails, timestamps used in narrow ranges. - Don't reflexively index every boolean or small enum. If the value you actually search for is rare, there are targeted tools for that; if the value you search for is the common one, no index shape will help — the query is asking for most of the table. - Selectivity is estimated from statistics, not measured at plan time. If the statistics are wrong or stale, the estimate is wrong, and the plan is chosen on a fiction. - When you read a plan, compare estimated rows against actual rows at each step. A large discrepancy at the bottom of the plan is the root cause of most bad plans, because the error compounds upward through joins.

  • Why is it called "high selectivity" when fewer rows come back?
    Selectivity describes how strongly the predicate *selects against* rows — how discriminating it is. A predicate that eliminates almost everything is highly selective. The numeric ratio (matching/total) moves the opposite way, which is why people misread it. Some engines report the inverse under the name density, so always check which number you are looking at.
  • Where does the optimizer get the numbers it uses to estimate selectivity?
    From stored table statistics, gathered by an ANALYZE-style operation or an automatic background job. Typically that includes row count, page count, per-column distinct-value counts, null fraction, min/max, most-common-value lists and histograms. They are sampled and periodically refreshed, so they are an approximation of the data, not a live measurement.
  • If an index exists on a column, does the optimizer always use it when that column is filtered?
    No. It compares the estimated cost of the index path against alternatives, and a low-selectivity predicate makes the index path more expensive than a scan. The index is a candidate, never an obligation.

A phone book index helps when you want one name. If you want everyone whose surname starts with S, flipping to each entry and back is slower than reading the book front to back.

saying these in an interview costs you the question

  • Saying high selectivity means many rows are returned.
  • Treating cardinality and selectivity as synonyms, ignoring that a low-cardinality column can still have very selective individual values.
  • Claiming an index is always faster than a full scan because it is O(log n) — ignoring the per-row lookup cost after the index probe.
  • Assuming an existing index forces the optimizer to use it.
  • Believing selectivity is measured at execution time rather than estimated from stored statistics.

context

resolving links…