skip to content

What statistics does a relational database keep about a table's columns for query planning, and what does a histogram give the optimizer that a plain distinct-value count cannot?

level: middleimportance: must knowfreq 52%

answer

  1. row count, pages, NDV, null frac, min/max, MCV, histogram
  2. no histogram → uniformity + linear interpolation
  3. equi-depth buckets = equal rows per bucket
  4. MCV holds heavy hitters, histogram holds the rest
  5. sampled, tunable bucket count, goes stale

basics

~20 s

Typically: row count, page count, per-column distinct values, null fraction, min/max, most-common values with frequencies, and a histogram. A distinct-value count only supports an averaged estimate assuming even distribution; a histogram records the actual shape of the data, so skewed values and range predicates are estimated correctly.

solid answer

~60 s

Core statistics are table-level (row count, size in pages) and column-level: number of distinct values, fraction of NULLs, minimum and maximum, average value width, a list of most common values with their frequencies, and a histogram. Without a histogram, the optimizer assumes uniform distribution: an equality predicate is estimated as rows / distinct values, and a range predicate is estimated by linear interpolation between min and max. Both are fine on evenly spread data and badly wrong on skewed data. A histogram divides the column's value range into buckets — usually **equi-depth**, where every bucket holds roughly the same number of rows, so buckets are narrow where data is dense. That records the actual shape: a rare value gets its own narrow region, a dominant value is captured in the most-common-value list, and a range predicate can be estimated by summing whole buckets plus interpolating the partial ones at each end. Histograms are built from a sample, and their resolution is a bucket-count setting. Too few buckets on a highly skewed column, and the skew is smoothed away again.

code

text · 6 lines
text
column: order_amount   (10,000,000 rows, 10 buckets, ~1M rows each)
bounds: 0.01  4.99  9.50  14.20  19.99  27.40  38.10  56.00  120.00  9,800.00  512,000.00
         |<-- narrow buckets: most orders are small -->|   |<- long tail ->|

WHERE order_amount > 1000  -> inside the last bucket -> ~ small fraction of 1M rows
(uniform min/max guess would have said ~ (512000-1000)/512000 = 99.8% of rows)

go deeper

for a junior

List the main statistics and say a histogram describes the real distribution, so skewed data is estimated better than an average.

for a middle

Explain the uniformity and linear-interpolation fallbacks, the equi-depth bucket idea, and how MCV lists and histograms divide the work.

for a senior

Discuss sampling error, bucket-count tuning on plan-critical columns, refresh triggers after bulk changes, and the growing-max-value problem on timestamp columns.

for a principal

Position statistics as a maintenance surface with a cost/accuracy tradeoff: which columns deserve deeper histograms, where per-column stats are structurally insufficient, and when to design queries that don't depend on precise estimates.

## What gets stored A cost-based optimizer never looks at your data while planning; it looks at a small summary gathered earlier by an ANALYZE-style command or an automatic background collector. Typical contents: **Table level** - Row count. - Size in pages/blocks, which sets the cost of a full scan. - For indexes: height, number of leaf pages, and a measure of how well index order correlates with physical row order (which controls how random the row lookups will be). **Column level** - **Distinct value count (NDV)** — the basis of the equality estimate. - **Null fraction** — so `IS NULL` and `IS NOT NULL` can be estimated, and joins can discount unmatched rows. - **Minimum and maximum** — the endpoints for range estimation. - **Average width** — feeds memory and sort-size estimates. - **Most-common values (MCV) with frequencies** — an explicit list of the top values and how often each occurs. - **Histogram** — the distribution of everything that is not in the MCV list. ## Estimation without a histogram With only NDV, min, and max, the engine falls back on two assumptions: - *Uniformity*: every distinct value occurs equally often. Equality selectivity = 1 / NDV, so estimated rows = row count / NDV. - *Linear spread*: values are evenly distributed across [min, max]. For `WHERE amount BETWEEN 100 AND 200` with min 0 and max 10,000, it estimates 1% of rows. On a synthetic, evenly generated column this works. On real data it fails in the ways that matter most: - A `status` column that is 99% one value gets the same estimate for every value. - An `amount` column where 90% of orders are under \$50 but the maximum is \$500,000 gets a badly wrong estimate for every range predicate, because linear interpolation across a long tail is meaningless. - A `created_at` column on a growing table has a maximum that is always slightly stale, so "rows from the last hour" — past the recorded maximum — estimates as almost nothing. ## What the histogram adds A histogram partitions the value domain into buckets and records how many rows fall in each. Two shapes exist: - **Equi-width**: buckets span equal value ranges. Simple, but a spike in one range hides inside one bucket. - **Equi-depth (equi-height)**: bucket *boundaries* are chosen so each bucket holds roughly the same number of rows. This is what serious engines use, because resolution automatically concentrates where the data is dense. Where values cluster, buckets are narrow; across a sparse tail, one bucket spans a huge range. With an equi-depth histogram of N buckets, a range predicate is estimated by counting the buckets fully inside the range, then interpolating within the two boundary buckets. Equality on a value that is not a most-common value is estimated as (rows in its bucket) / (distinct values in that bucket) — still an average, but a local one, which is far tighter than a global one. The MCV list and the histogram are complementary: the heavy hitters are pulled out and stored with exact frequencies, and the histogram then describes only the remaining, comparatively better-behaved distribution. That is what lets the optimizer say 49.5M rows for the dominant status value and 100 rows for the rare one, from the same column. ## Practical properties worth knowing - **They are sampled.** Gathering exact statistics on a billion-row table would mean reading it all, so engines sample a fraction of pages. Sampling is why NDV in particular can be off: estimating the number of distinct values from a sample is a statistically hard problem, and it tends to be *under*estimated when values are unevenly spread. - **Bucket count is tunable.** More buckets means finer resolution and a better estimate on skewed columns, at the cost of larger statistics and slower planning. Raising it selectively on the few columns that drive plan choices is a normal tuning step. - **They go stale.** After a bulk load, a large delete, or steady growth, the stored summary describes a table that no longer exists. Statistics need to be refreshed on a schedule or by automatic thresholds, and explicitly after bulk operations. - **They are per column by default.** A histogram on `city` and a histogram on `postal_code` still do not tell the engine those two are correlated; combined estimates multiply the independent selectivities. Capturing that requires multi-column or extended statistics where the engine supports it. - **Expressions are opaque.** A predicate like `WHERE lower(email) = ...` cannot use the histogram on `email`; the engine falls back to a fixed default guess unless statistics are gathered on the expression itself.

  • Why do engines prefer equi-depth histograms over equi-width ones?
    Because resolution automatically follows data density. With equal row counts per bucket, boundaries bunch up where values cluster and spread out across sparse tails, so the dense regions that most predicates hit are described precisely. Equi-width buckets waste resolution on empty ranges and hide spikes inside a single wide bucket.
  • Why is a most-common-value list kept separately instead of relying on the histogram alone?
    Because a single dominant value would otherwise occupy several buckets and distort the rest of the distribution. Pulling heavy hitters out with exact frequencies makes those predicates estimate precisely and leaves a smoother remainder for the histogram, which improves estimates for every other value too.
  • What limits do per-column statistics have even when they are fresh and detailed?
    They describe one column in isolation. Combined predicates are estimated by multiplying independent selectivities, so correlated columns are underestimated, sometimes by orders of magnitude. They also cannot describe expressions over a column, and join result sizes are derived rather than measured, so errors compound through a multi-join plan.

NDV is knowing a city has 200 neighbourhoods, so guessing each holds 1/200 of the population. A histogram is the actual population map: it shows the dense downtown blocks and the empty outskirts.

saying these in an interview costs you the question

  • Thinking statistics are computed fresh at query time rather than gathered periodically and sampled.
  • Believing distinct-value counts alone are enough to handle skewed data.
  • Confusing an index with a statistic — assuming the presence of an index gives the optimizer distribution knowledge.
  • Assuming per-column histograms solve multi-column correlation.
  • Not knowing statistics need refreshing after bulk loads or large deletes.

context

resolving links…