Selectivity, Cardinality & Statistics
Selectivity is the fraction of rows matching a predicate. Cardinality is the estimated row count after filters/joins. Planners use statistics (ANALYZE) — n_distinct, MCV, histograms — to choose Seq Scan vs Index Scan. Bad stats mean bad plans.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Overview
Indexes do not “get used.” The planner estimates I/O. The estimate comes from statistics, not from your confidence. This page is the vocabulary: selectivity, cardinality, MCV, histogram, n_distinct.
By the end you should be able to:
- Define selectivity vs cardinality in one sentence each
- Estimate equality selectivity with and without skew
- Explain Seq Scan vs Index Scan with
random_page_cost - Name what ANALYZE collects
- Reach for extended statistics when columns correlate
status boolean vs user_id
Prefer
Index user_id; skip status-alone; ANALYZE after load
user_id is high n_distinct — a few rows per value. status ~0.5 selectivity — random heap fetches lose to seq scan. Stats must be fresh or both estimates lie.
- Equality selectivity ≈ 1/n_distinct if uniform.
- MCV: if 99% are 'active', that equality is not 1/2.
- Prove with Plan Rows vs Actual Rows.
Alternative
Index every column, never ANALYZE
Planner still Seq Scans the boolean. After a 10M import, n_distinct is a fiction and nested loops explode.
- An index is an option, not a command.
- Correlation (physical order vs key) changes heap-fetch cost.
- Functions on columns hide stats — expression indexes get their own.
From stats to scan
Wrong n_distinct is a wrong join algorithm two nodes later.
- 1
ANALYZE samples the table
n_distinct, most-common values, histogram buckets, correlation, null fraction. - 2
Predicate → selectivity
Equality on MCV uses the MCV frequency. Else histogram / 1/n_distinct. - 3
Cardinality = rows × selectivity (then joins)
This number feeds Nested Loop vs Hash Join. - 4
Cost Index vs Seq
random_page_cost × (index + heap pages) vs seq_page_cost × table. - 5
Skip ANALYZE after bulk load
Plan Rows=1, Actual=8e6. Nested loop disaster.
Definitions
| Term | Meaning |
|---|---|
Column cardinality / n_distinct | Distinct values. -1 means “unique-ish” (≈ all rows distinct). -0.1 means “10% distinct.” |
| Selectivity | Fraction of rows matching a predicate. High selectivity = rare = good for index seeks (interview wording is easy to flip — say “few rows”). |
| Plan cardinality | Estimated rows out of a node |
| MCV | Most common values + frequencies (skew) |
| Histogram | Height-balanced buckets for the rest |
| Correlation | How sorted the heap is vs the index (+1 clustered) |
Uniform equality: selectivity ≈ 1 / n_distinct.
status IN ('active','inactive') with two values → ~0.5 — usually Seq Scan.
Why Seq Scan wins
index_cost ≈ random_page_cost × (index_pages + heap_pages_touched)
seq_cost ≈ seq_page_cost × table_pagesHeap pages touched ≈ matching rows × (1 − correlation-ish clustering). Lots of matches + random heap = seq wins. Small tables fit in memory: seq wins. This is correct.
Defaults: seq_page_cost=1, random_page_cost=4 (disk era). SSDs: teams drop random toward 1.1–1.5 so indexes look cheaper. Costs are units, not ms.
ANALYZE and skew
ANALYZE orders;
SELECT attname, n_distinct, correlation
FROM pg_stats
WHERE tablename = 'orders';Always ANALYZE after bulk COPY / restore before you trust EXPLAIN. Autovacuum usually does this; huge loads can outrun it.
Skew: 99% status='ok'. MCV says ok is common → Seq Scan. 'failed' is rare → Index Scan. Same column, opposite plans. 1/n_distinct would have been wrong for both.
Correlated columns: city and zip. Independent assumption multiplies selectivities and underestimates. CREATE STATISTICS … (dependencies) / ndistinct on the pair, then ANALYZE.
Expression / partial indexes have their own stats — sibling. A B-tree on email does not help LOWER(email) estimates.
Decisions
- 1
Table
- nextANALYZE
- 2
ANALYZE
- nextpg_statistic
- 3
pg_statistic
- nextPlanner selectivity
- 4
Planner selectivity
- nextIndex cost < seq cost?
- ?
Index cost < seq cost?
- yesIndex / Bitmap
- noSeq Scan
- 6
Index / Bitmap
- 7
Seq Scan
Lesson map
Selectivity, Cardinality & Statistics
Selectivity is the fraction of rows matching a predicate. Cardinality is the estimated row count after filters/joins. Planners use statistics (ANALYZE) — n_distinct, MCV, histograms — to choose Seq Scan vs Index Scan. Bad stats mean bad plans.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB t["Table"] a["ANALYZE"] s["pg_statistic"] p["Planner selectivity"] t -->|Table to ANALYZE| a a -->|ANALYZE to pg_statistic| s s -->|pg_statistic to Planner selectivity| p
Toy estimator (run this)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Interview Q&A
Selectivity vs cardinality?
Answer
Selectivity is a fraction of rows matching. Cardinality is the count the planner expects (rows × selectivity, then join math).
Why Seq Scan a table that has an index?
Answer
Estimated random I/O for the predicted matches exceeds sequential read. Low selectivity, small table, stale stats, or high random_page_cost.
What does n_distinct = -1 mean?
Answer
“About as many distinct values as rows” (unique). -0.05 means distinct ≈ 5% of rows. Positive is an absolute count.
MCV vs histogram?
Answer
MCV: the frequent values and their frequencies (skew). Histogram: the rest, in buckets. Equality on an MCV uses the frequency, not 1/n_distinct.
When do you ANALYZE?
Answer
After bulk loads, big deletes, restore, and when Plan Rows and Actual Rows diverge by 10×. Autovacuum usually; do not wait during an incident.
Correlation?
Answer
How clustered the heap is with the index order. High correlation → cheaper index scans (fewer random heap pages). Cluster / partition to help.
Why extended statistics?
Answer
Planner assumes independent predicates. city and zip are not. Dependencies / ndistinct / MCV lists on the pair fix AND/OR estimates.
Does more distinct always mean use the index?
Answer
High n_distinct helps equality. A range that still matches 40% of the table does not care that ids are unique.
default_statistics_target?
Answer
More histogram/MCV slots (default 100). Raise per-column with ALTER TABLE … SET STATISTICS for skewed keys, then ANALYZE. Not a substitute for the right index.
How do you see the lie?
Answer
EXPLAIN ANALYZE: Plan Rows vs Actual Rows. That gap is this page.
Pitfalls
On a 10M-row table, estimate rows for user_id=$1 (unique) and active=true (90%). Which scan? Then multiply as if independent user_id AND city vs correlated. Run the playground. If you indexed active alone, drop it.
Go Deeper
Cluster: composites · next EXPLAIN