Planner statistics, and how the estimates go wrong

Growth edge 9 asked for exactly this and named why: pev2 and query-execution-plan gave the spoke the symptom — estimate_factor, the planner's guessed row count against the actual, over or under — and neither said where the guess comes from. Written from the PostgreSQL documentation (T1).

What the planner is actually doing

"The planner thus needs to make an estimate of the selectivity of WHERE clauses, that is, the fraction of rows that match each condition in the WHERE clause."

Everything else is machinery for that one number. Table size comes from pg_class: "the total number of entries in each table and index, as well as the number of disk blocks occupied… kept in the table pg_class, in the columns reltuples and relpages." Column-level statistics come from ANALYZE into pg_statistic, read through the pg_stats view — the docs recommend the view, since "pg_stats is designed to be more easily readable" and pg_statistic is superuser-only.

The distribution is stored as most_common_vals with their frequencies for the values that repeat, and histogram_bounds for everything else, plus n_distinct. Their resolution is a knob: "the maximum number of entries in the most_common_vals and histogram_bounds arrays for each column, can be set on a column-by-column basis using the ALTER TABLE SET STATISTICS command, or globally by setting the default_statistics_target configuration variable. The default limit is presently 100 entries."

Two admissions in the documentation matter more than the mechanism. The statistics "are always approximate even when freshly updated" — they come from a sample, not a scan. And the table-level numbers are stale by design: "For efficiency reasons, reltuples and relpages are not updated on-the-fly, and so they usually contain somewhat out-of-date values."

The independence assumption, which is where plans die

One column at a time, this works. The failure is structural and the docs demonstrate it on a table of ten thousand rows where two columns hold identical values:

"The planner estimates the selectivity for each condition individually, arriving at the same 1% estimates as above. Then it assumes that the conditions are independent, and so it multiplies their selectivities, producing a final selectivity estimate of just 0.01%."

WHERE a = 1 estimates 100 rows and returns 100. WHERE a = 1 AND b = 1 estimates 1 row and returns 100 — "a significant underestimate, as the actual number of rows matching the conditions (100) is two orders of magnitude higher." The planner has no way to know: "Regular statistics, because of their per-individual-column nature, cannot capture any knowledge about cross-column correlation."

An estimate_factor of 100× on the first node of a plan is how a nested loop gets chosen for a join that will run 400,000 times. This is the mechanism under the number pev2 ranks nodes by, and it explains why that number is usually an underestimate rather than a random error — multiplying selectivities can only ever shrink the estimate.

The remedy, and its cost

CREATE STATISTICS builds a multi-column statistics object, in three kinds, and the docs work the same example through all three. Functional dependencies (CREATE STATISTICS stts (dependencies) ON a, b FROM t) take the estimate from 1 back to 100. N-distinct fixes grouping — a GROUP BY a, b estimated at 1,000 rows against an actual 100. MCV lists are the strongest, and the documentation says why:

"Compared to functional dependencies, MCV lists have two major advantages. Firstly, the list stores actual values, making it possible to decide which combinations are compatible."

Which shows up as the case the other two cannot handle: WHERE a = 1 AND b = 10 on a table where a always equals b estimates 1 and returns 0, and a <= 49 AND b > 49 likewise. Knowing the correlation is not enough; you have to know the values to rule a combination out.

The cost is that all three are opt-in per column pair. Nothing in Postgres discovers correlated columns for you, so the fix requires already suspecting which pair is lying — which is what makes pev2's ranking and hypopg's what-if testing the practical entry points to this mechanism rather than the catalog views.

Where this leaves the corpus

The chain is complete for the first time: ANALYZE samples → pg_statistic holds an approximate distribution → the planner multiplies per-column selectivities under an independence assumption it cannot verify → the plan is chosen for the estimate and paid for at the actual → EXPLAIN ANALYZE prints both numbers → pev2 ranks the discrepancy → CREATE STATISTICS is the fix, if you already know where to point it.

Still open: autovacuum's role in letting statistics go stale (named in growth edge 9 and not covered by these documentation pages), what ANALYZE's sampling costs on a large table, and how correlation feeds index-scan cost estimation.

Related

postgresql · query-execution-plan · pev2 · hypopg · pg-stat-statements · multiversion-concurrency-control · operational-databases