Compare equi-width and equi-depth histograms as used by a query optimizer. Which handles skewed data better, and why do engines usually store one alongside a most-common-value list?

## Why a histogram exists A distinct-value count only answers equality predicates, and only under a uniformity assumption. Range predicates — `created_at > ?`, `amount BETWEEN ? AND ?` — need to know the *shape* of the distribution. A histogram is a compact approximation of that shape: a small set of buckets, each summarizing a slice of the value domain. ## Equi-width Divide the range from min to max into `k` buckets of equal span, then count how many rows land in each. For `amount` from 0 to 1,000 with 10 buckets: 0-100, 100-200, ... 900-1000. - **Cheap to build and update**; boundaries are known in advance, so counting is a single pass with no sorting. - **Terrible under skew.** If 95% of orders are under 50, the first bucket holds 95% of rows and the other nine are near-empty. Estimating `amount < 20` requires interpolating inside that first bucket, and the interpolation assumes rows are spread evenly across 0-100 — which is exactly the assumption the data violates. The error is unbounded: the estimate can be off by an arbitrary factor depending on how the mass sits inside the bucket. - **Sensitive to outliers.** A single row with `amount = 10,000,000` stretches the range, so every real value is crushed into the first bucket. ## Equi-depth (equi-height) Sort (or sample and sort) the values and choose boundaries so each bucket holds approximately the same number of rows — `n/k` each. Store the boundary values. For the same skewed `amount` column with 10 buckets, boundaries might be 0, 5, 9, 14, 19, 26, 35, 51, 90, 240, 1000 — narrow where data is dense, wide where it is sparse. - **Bounded error.** Every bucket carries the same known row count, so any range predicate is estimated as (whole buckets covered) x n/k, plus interpolation inside at most two partial end buckets. With 100 buckets, the interpolation error is confined to under 2% of the table regardless of distribution shape. That guarantee is distribution-independent, which is the whole point. - **More expensive to build** — requires sorting or quantile estimation over a sample rather than a plain counting pass. - **Adapts automatically** to whatever shape the data has, including multi-modal distributions. This is why essentially every mainstream cost-based optimizer uses equi-depth histograms (sometimes under names like *height-balanced* or *quantile* histograms). ## Where equi-depth still fails, and why MCV lists exist Equi-depth assumes it can place boundaries wherever it likes. It cannot split a single repeated value. If one value covers 40% of the table, that value spans many consecutive buckets, and inside them the histogram has no resolution at all — it cannot distinguish that value from its neighbours, and estimates for nearby values inherit the distortion. The standard fix is to handle frequent values separately: 1. Extract the top-k values by frequency into an **MCV list** with exact measured frequencies. 2. Build the histogram over **only the remaining rows**. Now equality on a heavy hitter is answered exactly from the MCV list, and the histogram describes a much smoother residual distribution, so range estimates improve too. This split — MCV list plus equi-depth histogram over the remainder — is the shape you will find in most modern engines, and describing it is what separates a solid answer from a textbook one. ## Bucket count and its cost More buckets means finer resolution and better estimates, at the cost of larger catalog entries, more planning-time work to walk them, and a more expensive statistics-gathering pass (a larger sample is needed to place many boundaries reliably). Defaults are typically in the 100-256 bucket range. Raising the target is a per-column decision worth making for a few known-skewed, heavily-filtered columns — not a global change. ## Practical notes - Histograms are usually built from a **sample**, so boundaries are approximate and small errors are normal. - The **first and last buckets** age fastest: on a monotonically increasing column such as a timestamp or sequence id, new rows fall beyond the recorded maximum, and queries about "recent" data estimate near zero rows until statistics are refreshed. This is the single most common histogram-staleness bug in production. - A histogram describes **one column**. Two histograms cannot tell you anything about the joint distribution of two correlated columns.