What is index cardinality

The PostgreSQL cost-based query optimizer relies heavily on cardinality estimates to determine whether an Index Scan is faster and cheaper than scanning the entire table via a S...

🟢 Junior Level

Cardinality refers to the number of unique (distinct) values contained within a specific database table column.

Why Cardinality Matters

The PostgreSQL cost-based query optimizer relies heavily on cardinality estimates to determine whether an Index Scan is faster and cheaper than scanning the entire table via a Sequential Scan (Seq Scan).

High Cardinality: A large number of unique values relative to table size (e.g., email, user_id, uuid, order_number). An index is exceptionally effective because an equality search isolates a single row or an extremely small subset.
Low Cardinality: Very few distinct values across thousands or millions of rows (e.g., gender with 'M'/'F', is_active with true/false, order status). A standard index is usually ineffective because any single value matches a huge percentage of the table.

-- Table 'users' containing 1,000,000 rows:

-- High Cardinality (~1,000,000 distinct values) -> Index is highly effective ✅
SELECT COUNT(DISTINCT email) FROM users; 

-- Low Cardinality (2 distinct values across 1M rows) -> Index is ineffective ❌
SELECT COUNT(DISTINCT is_active) FROM users; 

Rule of Thumb

Create standard B-tree indexes primarily on columns with high cardinality. For low-cardinality columns, only index them if you are querying heavily skewed rare values using Partial Indexes (e.g., indexing only the 1% of rows where is_active = false).

🟡 Middle Level

Cardinality vs. Selectivity

While frequently conflated in informal discussion, cardinality and selectivity represent two distinct statistical metrics in database query optimization:

Metric	Formal Definition	Formula / Representation
Cardinality	The total count of distinct values in a column	`COUNT(DISTINCT column_name)`
Selectivity	The fraction of total table rows that satisfy a specific query filter predicate	$\text{Selectivity} = \frac{\text{Rows matching predicate}}{\text{Total rows in table}}$

[!NOTE] The Selectivity Paradox: In database optimization terminology, “High Selectivity” means the query filter is highly selective — it matches a very small percentage of rows (e.g., 0.01% of the table). High cardinality on a column produces high selectivity for equality lookups (WHERE id = 42), making index access vastly cheaper than sequential scans.

How PostgreSQL Measures Cardinality

PostgreSQL collects statistical telemetry during ANALYZE (executed in the background by autovacuum) and records it in pg_statistic, accessible via the human-readable system view pg_stats:

SELECT 
    attname AS column_name,
    n_distinct,               -- Estimated distinct values
    null_frac,                -- Fraction of NULL entries
    avg_width,                -- Average column entry byte width
    correlation               -- Physical disk vs logical sort correlation
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'customer_id';

Deciphering `n_distinct`:

Positive Number ($> 0$): A fixed, absolute count of distinct values. For example, n_distinct = 50 means PostgreSQL estimates there are exactly 50 distinct values in the table, regardless of total row count.
Negative Number ($< 0$): A distinct value ratio relative to total table rows. For example:
- n_distinct = -1.0: 100% unique values (every row is distinct, typical for Primary Keys and unique constraints).
- n_distinct = -0.2: 20% of total rows are distinct (if the table grows to 10M rows, the planner calculates $10\text{M} \times 0.2 = 2\text{M}$ distinct values).

Planner Execution Strategy Thresholds

PostgreSQL’s cost-based query planner compares random_page_cost against seq_page_cost to select an execution strategy based on estimated selectivity:

0%                                  ~5%                      ~20%                       100%
┌────────────────────────────────────┬────────────────────────┬───────────────────────────┐
│             Index Scan             │    Bitmap Index Scan   │          Seq Scan         │
└────────────────────────────────────┴────────────────────────┴───────────────────────────┘
 (Direct B-tree Seek to Heap TID)      (Bitmaps TIDs in RAM,    (Sequential reading of all
                                       reads heap in order)     pages is faster than random I/O)

Data Skew & Most Common Values (MCV)

A column may have low overall cardinality, but significant data skew:

In an orders table of 10,000,000 rows:
- status = 'DELIVERED': 9,500,000 rows (95% of table)
- status = 'PROCESSING': 490,000 rows (4.9% of table)
- status = 'CANCELLED': 10,000 rows (0.1% of table)

PostgreSQL stores the most frequent values and their exact percentages in the most_common_vals (MCV) and most_common_freqs (MCF) arrays inside pg_stats.
When you execute:

-- Query 1: Planner detects 'DELIVERED' in MCV (95%) -> Chooses fast Seq Scan
EXPLAIN SELECT * FROM orders WHERE status = 'DELIVERED';

-- Query 2: Planner detects 'CANCELLED' in MCV (0.1%) -> Chooses Index Scan
EXPLAIN SELECT * FROM orders WHERE status = 'CANCELLED';

PostgreSQL dynamically alters its execution plan based on the literal value provided!

🔴 Senior Level

The Four Pillars of PostgreSQL Statistical Catalog

Inside pg_stats, PostgreSQL maintains four mathematical structures to estimate query selectivity:

n_distinct: Distinct value ratio or absolute count.
most_common_vals (MCV) & most_common_freqs (MCF): Exact lists of the top frequent values and their fractional frequencies.
histogram_bounds: An equi-depth histogram dividing non-MCV values into equal-population buckets, utilized to calculate selectivity for range predicates (<, >, BETWEEN).
correlation: The statistical Pearson correlation between physical disk block ordering and logical index key order (ranging from -1.0 to +1.0):
- correlation ≈ 1.0: Rows are physically arranged on disk in the exact same order as the index. An Index Scan produces contiguous sequential disk reads.
- correlation ≈ 0.0: Rows are scattered randomly across physical pages. An Index Scan generates severe random I/O disk thrashing.

The Cross-Column Independence Fallacy & Extended Statistics

By default, PostgreSQL’s query optimizer assumes that separate columns in a table are statistically independent:

\[P(\text{make} = \text{'Audi'} \land \text{model} = \text{'A4'}) = P(\text{make} = \text{'Audi'}) \times P(\text{model} = \text{'A4'})\]

If make = 'Audi' matches 2% of cars and model = 'A4' matches 1% of cars, the planner multiplies the probabilities: $0.02 \times 0.01 = 0.0002$ (0.02%). It estimates that only 200 rows will match out of 1,000,000!
In reality, every single A4 is an Audi. The actual row count is 10,000 (an underestimate by a factor of 50x!).

The Danger:

Because the planner drastically underestimates row count, it chooses a disastrous Nested Loop join, turning a sub-second query into a 10-minute production freeze.

The Solution: Extended Statistics (PostgreSQL 10+)

-- 1. Functional Dependencies (knowing 'model' dictates 'make'):
CREATE STATISTICS stat_cars_dependency (dependencies) 
ON make, model FROM cars;

-- 2. Multivariate Distinct Counts (computes combined distinct combinations for GROUP BY):
CREATE STATISTICS stat_users_city_zip (ndistinct) 
ON city, zip_code FROM users;

-- 3. Multivariate MCV Lists (PG 13+: joint frequent combinations across columns):
CREATE STATISTICS stat_orders_status_priority (mcv) 
ON status, priority FROM orders;

-- Recalculate statistics across the table:
ANALYZE cars, users, orders;

Tuning `default_statistics_target`

For massive tables (> 100M rows) or columns with high skew, the default 100 histogram buckets may provide insufficient sampling resolution:

-- Increase statistics sampling target for a critical column (creates up to 1,000 histogram buckets)
ALTER TABLE orders ALTER COLUMN customer_id SET STATISTICS 1000;
ANALYZE orders;

4 Tricky Questions

1. In `pg_stats`, what does `n_distinct = -0.5` mean, and how does the optimizer calculate expected row counts if the table grows from 1M to 10M rows?

Answer:
A negative n_distinct value indicates a proportional ratio relative to total table rows.
-0.5 means PostgreSQL estimates that 50% of the table rows are distinct values.

When the table has 1,000,000 rows, the optimizer calculates $1,000,000 \times 0.5 = 500,000$ distinct values.
When the table grows to 10,000,000 rows, the optimizer automatically scales its cardinality estimate to $10,000,000 \times 0.5 = 5,000,000$ distinct values without requiring an immediate ANALYZE.
In contrast, if n_distinct were stored as a positive number (e.g., 500), the optimizer would treat the distinct count as statically fixed at 500 regardless of how large the table grew.

2. Why does the `correlation` metric in `pg_stats` directly determine whether PostgreSQL chooses an `Index Scan` vs a `Bitmap Index Scan`?

Answer:
correlation measures whether physical table rows on disk are clustered in the same sequential order as the B-tree index:

When correlation ≈ 1.0, an Index Scan reads index leaf nodes and fetches heap pages in physical sequential order. Disk read-ahead caching works optimally.
When correlation ≈ 0.0, matching rows are scattered across disparate, non-contiguous heap blocks. An individual Index Scan causes chaotic random disk I/O, incurring high random_page_cost penalties.
To prevent disk head thrashing, the optimizer switches to a Bitmap Index Scan: it reads all matching index pointers into an in-memory bitmap, sorts them by physical disk block number, and then reads each affected heap page sequentially in order.

3. How does the “Cross-Column Independence Fallacy” cause the query planner to choose a devastating Nested Loop instead of a Hash Join?

Answer:
When joining two tables with multiple correlated filter conditions (e.g., WHERE c.state = 'CA' AND c.city = 'San Francisco'), the default optimizer multiplies their independent selectivities, severely underestimating the resulting row count (e.g., predicting 5 rows instead of 50,000).
A Nested Loop join is mathematically optimal for very small row counts ($\le 10$ rows) because it incurs zero startup cost. However, when the outer loop actually iterates 50,000 times instead of 5, the Nested Loop executes 50,000 separate index seeks on the inner table, saturating the CPU and disk. With accurate statistics (via CREATE STATISTICS), the planner would correctly anticipate 50,000 rows and select a Hash Join, building an in-memory hash table in a single pass.

4. Can an index on a low-cardinality column ever be faster than a sequential scan? Under what specific scenario?

Answer:
Yes, in two major production scenarios:

Data Skew Querying Rare Values: If a boolean or status column has 99.9% 'PROCESSED' and 0.1% 'FAILED', querying WHERE status = 'FAILED' uses the index because the optimizer checks the MCV list, identifies that 'FAILED' matches only a tiny fraction of the table, and executes an Index Scan.
Partial Indexes: Creating a targeted partial index (CREATE INDEX idx_failed ON orders(order_id) WHERE status = 'FAILED') indexes only the 0.1% rare rows. The physical index is tiny, permanently cached in RAM, and avoids indexing the 99.9% majority data.

🎯 Interview Cheat Sheet

Core Concepts

Cardinality: The count of unique values in a column (COUNT(DISTINCT col)).
Selectivity: The fraction of total rows matching a filter ($\frac{\text{matching rows}}{\text{total rows}}$). High selectivity means matching < 5% of rows.
Planner Logic: High selectivity (< 5%) $\rightarrow$ Index Scan; Moderate selectivity (5–20%) $\rightarrow$ Bitmap Index Scan; Low selectivity (> 25%) $\rightarrow$ Seq Scan.

Statistical Indicators in `pg_stats`

n_distinct: Negative values (-1.0) indicate proportional uniqueness (-1.0 = 100% unique primary key); positive values indicate absolute unique counts.
correlation: Measures physical disk clustering relative to the index (-1.0 to +1.0). Low correlation (< 0.3) triggers Bitmap Scans due to random I/O penalties.
most_common_vals (MCV): Allows PostgreSQL to change execution plans dynamically depending on the literal constant queried.

Advanced Architectural Fixes

Extended Statistics (CREATE STATISTICS): Use for correlated columns (e.g., make/model, state/city) to eliminate the Cross-Column Independence Fallacy.
Partial Indexes for Skewed Data: Do not index low-cardinality columns globally; index only the rare subset using a WHERE clause.

Red Flags (What NOT to Say)

❌ “A column with high cardinality is bad for an index because the index becomes too big.” (High cardinality is the primary prerequisite for an effective, high-selectivity B-tree index).
❌ “Negative n_distinct means the column has negative numbers.” (It represents a percentage ratio: -1.0 = 100% distinct).
❌ “Postgres automatically knows when two columns in a query are related.” (Standard statistics assume column independence; extended statistics must be created manually).

What are indexes and why are they needed — Index fundamentals and scan types
What is a composite index — Multi-column indexing and column ordering
Why is ANALYZE needed — Statistics sampling and catalog maintenance
How to optimize slow queries — Diagnosing cost and row estimation errors