Statistics

Why are statistics always stale?

Where to spend the buckets

A histogram is a lossy compression of a distribution under a fixed space budget, so the design question is: where do you spend the buckets?

Equi-width histograms spend buckets evenly over the value range. They are catastrophic under skew (a few very common values), because one bucket holds most of the rows, and the uniformity assumption inside that bucket is then maximally wrong.
Equi-depth histograms spend buckets evenly over the mass, so every bucket holds the same number of rows. That equalizes the worst-case error per bucket, and that is why equi-depth won.
Max-diff and V-optimal histograms go further and place boundaries to minimize the variance inside each bucket directly.

The general principle is put the boundary where the error grows fastest. It is the same principle behind every non-uniform quantization scheme.

Now the structural limit. To capture the correlation between k columns you need their joint distribution, whose size is the product of the distinct values: ∏ᵢ V(cᵢ). You can afford only the marginals (one distribution per column), whose total size is the sum of the bucket counts: Σᵢ b.

Independence is not assumed because anyone believes it. It is assumed because the joint distribution is exponential in the number of columns and the marginals are linear. Independence is a convenient falsehood elsewhere; here it is the only thing that fits in the budget.

The escapes and what each costs

Extended / multi-column statistics. Real, but you must name which column groups to build, which means you must already know where the correlation is. All pairs is C(n,2) groups, all subsets is worse, so coverage is always partial and chosen by a human who is guessing. (PostgreSQL's CREATE STATISTICS is an example.)
Functional dependency detection. A functional dependency means one column determines another (postcode determines city). It is cheap where it applies, since it collapses two columns into one. It is useless where the correlation is statistical rather than exact, which is most of the time.
Sampling. The error on a mean falls as 1/√k, but tails and NDV do not behave. And there is a trap specific to joins: a sample of a join is not a join of samples. If you take uniform samples of A and B at rate p, the join of the samples keeps only about p² of the join's rows. At p = 0.01 you keep one ten-thousandth (0.01 × 0.01 = 0.0001) of the result, and small true results vanish to zero. That is why sample-based join cardinality estimation needs correlated or index-assisted sampling, not independent sampling of each side.

Auto-analyze: where staleness is made

Statistics are refreshed by an automatic background job (auto-analyze). The mechanism is worth knowing exactly. PostgreSQL triggers analyze on a table when the number of changed rows exceeds 0.1 × n + 50, where n is the table's row count. That threshold grows with table size.

Worse, and more common: the newly loaded partition has no statistics at all. It falls back to the System R constants, and it is exactly the partition that every query filters on. This is Ananya's bug. On Tuesday the new partition had no statistics, the planner assumed placeholder selectivities, produced "1 row", and picked the nested loop.

Why is this not just negligence? Because statistics collection is a scan, and a scan has a fixed cost per collection. A fixed cost divided by the benefit per refresh derives a natural refresh interval, just as a fixed I/O cost derives a batch size. Staleness is the result of that amortization, not an oversight.

This also tells you the escape: anything that makes collection incremental instead of a full scan moves the fixed cost and therefore moves the interval. Two examples are statistics maintained at write time, and metadata written by the writer itself, as table formats do when they store per-file statistics at commit time. That is a real reason why such formats changed optimizer behavior more than any change to an optimizer did.

In one sentence: bucket boundaries go where error grows fastest; independence is a consequence of a space budget, not a belief; and statistics are stale because collection has a fixed cost that derives a refresh interval.

Case, resolvedConstructed case · Ananya at Kiranamart

The planner expects 1 row

After Tuesday's nightly load the 'Daily Revenue by Segment' report went from 3 seconds to 25 minutes because the planner expected 1 row from the newest partition and 9 million arrived. Where it started: Estimating cost →

Ananya runs the check that Diagnosing a bad plan will formalize: compare estimated and actual rows at each node. The first node with a big error is the scan of Tuesday's partition. Estimate: 1 row. Actual: 9 million. The partition was loaded after the last auto-analyze and holds no statistics, so the planner used placeholders.

She does not touch random_page_cost. Changing it would not flip anything: the planner believed there was 1 row, and for 1 row an index is correct at any reasonable cost ratio. She does not apply the "5%" rule either: that figure comes from a spinning-disk cost ratio, and this fact table lives on NVMe where the crossover is much higher still.

She runs ANALYZE on the new partition. The estimate becomes about 9 million, the planner picks a hash join with a sequential scan, and the report returns to 3 seconds. Then she adds ANALYZE of the new partition as the final step of the nightly load, so statistics exist before the first query arrives. This costs one extra scan of a partition she has just written. That is the fixed cost of collection paid at the cheapest moment, not a refresh interval left to chance.