Cardinality Estimation: Equi-Depth Histograms and Selectivity Math

The Problem: Guessing Row Counts Before Running the Query

Every SQL query has many possible execution plans — different join orders, join algorithms (hash vs. nested-loop vs. merge), and access paths (sequential scan vs. index scan). A cost-based optimizer must pick one before executing, and its cost model is driven almost entirely by one input: the estimated cardinality (row count) flowing out of each operator.

The atomic quantity is selectivity: the fraction of rows a predicate passes, a number in [0, 1]. If a table has N rows and a filter's selectivity is s, the estimated output is N × s. For an equality like x = 42 on a column with d distinct values, the naïve estimate assumes uniformity: selectivity = 1/d. For a range like x < 100, you need to know the shape of the distribution — and that is exactly what a histogram captures.

• Too-low estimates → optimizer picks nested loops / index scans that blow up.
• Too-high estimates → needless hash tables, sorts spilling to disk.
• Errors compound multiplicatively up a join tree.

How an Equi-Depth Histogram Works, Step by Step

Where an equi-width histogram slices the value axis into equal ranges, an equi-depth histogram slices the row axis into equal counts. Construction:

1. Sample or read the column and sort the values.
2. Choose B buckets. Each bucket should hold N/B rows.
3. Walk the sorted values, cutting a new boundary every N/B rows. The stored boundaries are the quantiles (percentiles) of the data.

Because every bucket has equal frequency, boundaries bunch up where data is dense and spread out where it's sparse — so a skewed column gets fine resolution exactly where it matters. PostgreSQL stores these boundaries as an array in pg_stats.histogram_bounds.

histogram_bounds (B=4, N=1000, 250 rows each):
  [1, 12, 40, 95, 8000]
  bucket0: 1..12   (250 rows)
  bucket1: 12..40  (250 rows)
  bucket2: 40..95  (250 rows)
  bucket3: 95..8000(250 rows)

To estimate x < 60: 60 falls in bucket2 (40..95). Assume values are uniform within the bucket, so the fraction below 60 is (60−40)/(95−40) ≈ 0.36. Rows = 2 full buckets + 0.36 of bucket2 = 250+250+90 = 590.

Complexity and a Worked Selectivity Trace

Build: sorting the sample is O(n log n); with a sample of size m (Postgres samples ~300 × statistics_target rows), it's O(m log m). Streaming quantile sketches (e.g. GK, t-digest) build in O(n) time and sublinear space. Space: O(B) — one boundary and an implicit equal count per bucket. Query-time lookup: a range predicate is answered in O(log B) by binary-searching the boundary array (usually B≈100, so it's effectively constant).

Worked equality estimate combining an MCV list and histogram, N = 1,000,000, distinct d = 5,000:

-- WHERE city = 'Paris'
if 'Paris' in MCV list:
    sel = mcv_frequency['Paris']      = 0.08
else:
    -- spread remaining freq over non-MCV distinct vals
    sel = (1 - sum(mcv_freqs)) / (d - n_mcv)
    sel = (1 - 0.30) / (5000 - 100) = 0.70/4900 = 0.000143
rows = N * sel

For a conjunction a = 1 AND b = 2, the classic model multiplies selectivities: s(a) × s(b) — the independence assumption. This is the single biggest source of error when columns are correlated.

Where It's Used in Real Database Systems

Equi-depth histograms are the workhorse statistic in essentially every production RDBMS:

• PostgreSQL — ANALYZE builds an MCV list plus an equi-depth histogram_bounds array. The number of buckets is default_statistics_target (default 100), tunable per column with ALTER TABLE ... SET STATISTICS. Correlation is patched with CREATE STATISTICS (extended stats) for dependent columns.
• Oracle — height-balanced histograms historically; modern Oracle uses hybrid and top-frequency histograms and gathers them via DBMS_STATS.
• SQL Server — maintains statistics objects with up to 200 equi-depth-style steps, auto-updated as tables change.
• MySQL/InnoDB — added equi-height (and singleton) histograms in 8.0 via ANALYZE TABLE ... UPDATE HISTOGRAM.
• DuckDB, Spark, Presto/Trino — analytics engines carry equi-depth stats for join-order optimization on huge tables.

Statistics are refreshed by an ANALYZE-style job (auto-triggered after enough row churn), because a histogram over stale data is worse than none.

Equi-Depth vs. the Alternatives — the Tradeoff

The decisive contrast is with the equi-width histogram, which fixes bucket width instead of height. Equi-width is trivial to build (no sort of counts needed — just divide the range) and gives O(1) bucket lookup by arithmetic, but it collapses on skew: if 90% of salaries cluster in one \$30k range, that entire mass lands in a single bucket, and any range query inside it degrades to the same uniform-guess error you were trying to avoid.

Equi-depth spends its resolution where the rows are, so worst-case per-bucket error is bounded by the bucket's row share (N/B) regardless of skew — a strictly better error profile for real, non-uniform data. The cost is construction: you must know the quantiles, requiring a sort or a quantile sketch.

• vs. MCV list: histograms model ranges; MCV lists model exact spikes. Real optimizers use both — MCV for frequent values, histogram for the rest.
• vs. HyperLogLog: HLL estimates distinct-count (NDV), a different question; it feeds the 1/d term, it doesn't replace the histogram.
• vs. sampling at query time: more accurate but too slow for planning.

Pitfalls, Failure Modes, and Why It Matters

Histograms fail in predictable, painful ways:

• Correlation / independence violation: city='Paris' AND country='France' multiplies to a tiny selectivity, but the rows fully overlap. Multiplying independent selectivities under-estimates by orders of magnitude — the #1 real-world estimation bug. Fix: multi-column / extended statistics.
• Uniform-within-bucket assumption: if a single value dominates a bucket that isn't in the MCV list, range estimates skew.
• Stale statistics: bulk load 10× the rows without re-running ANALYZE and the optimizer plans for the old size. Auto-analyze mitigates but lags.
• Out-of-range / growing keys: a timestamp or auto-increment column whose newest values exceed the last histogram bound gets a near-zero estimate — classic \"today's data is invisible\" bug.
• Error compounding: a 2× error per join over a 6-way join can become 64×, choosing a catastrophic join order.

Its significance is quiet but enormous: the difference between a query plan that finishes and one that never does often traces back to a single histogram bucket. Understanding selectivity math is what lets an engineer read EXPLAIN ANALYZE and spot the estimated vs. actual rows gap that explains a slow query.

Equi-depth vs. equi-width histograms and other cardinality-estimation summaries

Structure	What is equalized	Handles skew?	Space	Typical use
Equi-width histogram	Bucket value-range width (e.g. every 10 units)	Poorly — dense ranges get one huge bucket	O(B)	Simple, legacy; teaching examples
Equi-depth histogram	Row count per bucket (~N/B each)	Well — boundaries pack into dense regions	O(B)	PostgreSQL, Oracle, SQL Server default
Most-Common-Values (MCV) list	Exact freq of top-k frequent values	Handles spikes exactly, not ranges	O(k)	Combined with histogram in Postgres
End-biased / max-diff histogram	Minimizes error at bucket boundaries	Very well for skewed data	O(B)	Oracle 'hybrid', research systems
HyperLogLog sketch	Distinct-count (NDV), not per-range	N/A — cardinality of distinct only	O(log log n)	Distinct estimation, big-data engines