Статистика ANALYZE в PostgreSQL: выборка, MCV, гистограмма и n_distinct

В плане стоит rows=141, а запрос вернёт 10 строк: планировщик не видит таблицу, он видит снимок из pg_stats. Снимок строит ANALYZE по случайной выборке в 300 × default_statistics_target строк, и три его части (MCV, гистограмма, n_distinct) ошибаются по-разному. Как оценки превращаются в cost, показано в модели стоимости, как сверять rows с фактом — в статье про EXPLAIN ANALYZE BUFFERS.

Стенд

Таблица на 10 млн строк с тремя столбцами разной формы: u — миллион значений по 10 строк на каждое, s — 30% нулей, 10% единиц и 600 000 редких значений по 10 строк, w — перекошенное число от 0 до 999 999.

docker run -d --name dba-statistics-analyze-histograms -e POSTGRES_PASSWORD=pg postgres:18
docker exec -it dba-statistics-analyze-histograms psql -U postgres

SELECT setseed(0.42);
CREATE TABLE t AS
SELECT g AS id,
       (g::bigint * 7919) % 1000000 AS u,
       CASE WHEN g % 10 < 3 THEN 0
            WHEN g % 10 = 3 THEN 1
            ELSE (g::bigint * 104729) % 1000000 + 2 END AS s,
       floor(1000000 * power(random(), 3))::int AS w
FROM generate_series(1, 10000000) g;

SELECT pg_size_pretty(pg_table_size('t')) AS size,
       count(DISTINCT u) AS u_true, count(DISTINCT s) AS s_true, count(DISTINCT w) AS w_true
FROM t;
SET max_parallel_workers_per_gather = 0;
SET jit = off;
ANALYZE VERBOSE t;

SELECT attname, n_distinct, round(correlation::numeric, 3) AS corr,
       array_length(most_common_vals::text::text[], 1) AS mcv,
       array_length(histogram_bounds::text::text[], 1) AS bounds
FROM pg_stats WHERE tablename = 't' ORDER BY attname;

  size  | u_true  | s_true | w_true
--------+---------+--------+--------
 575 MB | 1000000 | 600002 | 990267

INFO:  analyzing "public.t"
INFO:  "t": scanned 30000 of 73536 pages, containing 4079784 live rows and 0 dead rows; 30000 rows in sample, 10000367 estimated total rows
INFO:  finished analyzing table "postgres.public.t"
system usage: CPU: user: 0.11 s, system: 0.00 s, elapsed: 0.11 s

 attname | n_distinct |  corr  | mcv | bounds
---------+------------+--------+-----+--------
 id      |         -1 |  1.000 |     |    101
 s       |      42687 |  0.095 |   2 |    101
 u       |     975932 | -0.005 |     |    101
 w       |     157139 | -0.002 | 100 |    101

Выборка — ровно 30 000 строк, то есть 300 × default_statistics_target, а значение по умолчанию равно 100. Код берёт именно столько: stats->minrows = 300 * stats->attstattarget (analyze.c, строка 1940). Выбирается она в две стадии (строки 1177–1184): сначала до 30 000 случайных блоков, потом из строк этих блоков отбирается ровно 30 000. Блоков в таблице 73 536, прочитано 30 000, и в них 4 079 784 строки.

n_distinct = -1 у id значит «все значения разные»: отрицательное число — доля от числа строк, положительное — абсолютное количество. Корреляция corr нужна оценке Index Scan, см. модель стоимости.

Опыт 1: список частых значений и равенство

У s в MCV попали два значения. Сравним оценку для частого s = 0 с оценкой для редкого s = 123457:

SELECT most_common_vals, most_common_freqs FROM pg_stats WHERE tablename = 't' AND attname = 's';
EXPLAIN SELECT * FROM t WHERE s = 0;
EXPLAIN SELECT * FROM t WHERE s = 123457;
SELECT count(*) FILTER (WHERE s = 0) AS s0, count(*) FILTER (WHERE s = 123457) AS s123457 FROM t;

 most_common_vals |    most_common_freqs
------------------+-------------------------
 {0,1}            | {0.29996666,0.09916667}

 Seq Scan on t  (cost=0.00..198540.59 rows=2999777 width=24)
   Filter: (s = 0)

 Seq Scan on t  (cost=0.00..198540.59 rows=141 width=24)
   Filter: (s = 123457)

   s0    | s123457
---------+---------
 3000000 |      10

Для частого значения оценка почти точна: 2 999 777 против 3 000 000 — это частота из MCV, умноженная на число строк. Для редкого значения оценка завышена в 14 раз. Ответ в коде var_eq_const (selfuncs.c, строки 423–436):

			for (i = 0; i < sslot.nnumbers; i++)
				sumcommon += sslot.numbers[i];
			selec = 1.0 - sumcommon - nullfrac;
			CLAMP_PROBABILITY(selec);

			/*
			 * and in fact it's probably a good deal less. We approximate that
			 * all the not-common values share this remaining fraction
			 * equally, so we divide by the number of other distinct values.
			 */
			otherdistinct = get_variable_numdistinct(vardata, &isdefault) -
				sslot.nnumbers;
			if (otherdistinct > 1)
				selec /= otherdistinct;

Всё, что не попало в MCV, делится поровну между n_distinct − 2 значений. Подставим числа из pg_stats: (1 − 0,29996666 − 0,09916667) / (42 687 − 2) × 10 000 367 = 141. Формула верна, врёт её вход: n_distinct = 42 687, а настоящих значений 600 002.

Опыт 2: MCV и гистограмма вместе

Для условия w < 100000 планировщик складывает два вклада: MCV-значения, которые меньше константы, и долю гистограммы, которая покрывает все остальные строки. Гистограмма строится по равной частоте: 101 граница делят значения вне MCV на 100 корзин с одинаковым числом строк, ширина корзин разная.

DBA / 01koddo

Оценка w < 100000 из MCV и гистограммы

Сначала оценка планировщика и факт:

EXPLAIN SELECT * FROM t WHERE w < 100000;
SELECT count(*) FROM t WHERE w < 100000;

 Seq Scan on t  (cost=0.00..198540.59 rows=4605791 width=24)
   Filter: (w < 100000)

  count
---------
 4642662

Код scalarineqsel (selfuncs.c, строки 707–720) умножает результат гистограммы на долю строк вне MCV и прибавляет вклад MCV:

	selec = 1.0 - stats->stanullfrac - sumcommon;

	if (hist_selec >= 0.0)
		selec *= hist_selec;
	else
	{
		/*
		 * If no histogram but there are values not accounted for by MCV,
		 * arbitrarily assume half of them will match.
		 */
		selec *= 0.5;
	}

	selec += mcv_selec;

Повторим вычисление запросом: найдём корзину, в которую попала константа, и возьмём долю внутри неё линейной интерполяцией.

WITH st AS (
  SELECT most_common_vals::text::int[] AS mv, most_common_freqs AS mf, histogram_bounds::text::int[] AS hb
  FROM pg_stats WHERE tablename = 't' AND attname = 'w'),
mcv AS (
  SELECT coalesce(sum(f) FILTER (WHERE v < 100000), 0) AS below, sum(f) AS total
  FROM st, unnest(mv, mf) AS m(v, f)),
bin AS (
  SELECT i - 1 AS full_bins, hb[i] AS lo, hb[i+1] AS hi
  FROM st, generate_series(1, array_length(hb, 1) - 1) i
  WHERE hb[i] <= 100000 AND hb[i+1] > 100000)
SELECT full_bins, lo, hi,
       round((100000 - lo)::numeric / (hi - lo), 4) AS bin_part,
       round((full_bins + (100000 - lo)::numeric / (hi - lo)) / 100, 4) AS hist_sel,
       round(below::numeric, 4) AS mcv_below,
       round(((1 - total) * (full_bins + (100000 - lo)::numeric / (hi - lo)) / 100 + below) * 10000000) AS hand_rows
FROM bin, mcv;

 full_bins |  lo   |   hi   | bin_part | hist_sel | mcv_below | hand_rows
-----------+-------+--------+----------+----------+-----------+-----------
        43 | 97967 | 104259 |   0.3231 |   0.4332 |    0.0482 |   4605682

Ручной расчёт даёт 4 605 682 против 4 605 791 в плане; расходятся 109 строк (0,002%). Факт — 4 642 662, ошибка 0,8%: внутри корзины планировщик считает значения распределёнными равномерно. Для широкого диапазона в сотню корзин этого достаточно, а вот условие на одно значение гистограмма вообще не оценивает — им занимается var_eq_const из опыта 1.

Опыт 3: n_distinct и statistics target

Почему n_distinct для s равен 42 687 при 600 002 настоящих значений? Оценку считает формула Хааса и Стокса stadistinct = (n * d) / ((n - f1) + f1 * n / N) (analyze.c, строки 2630–2638).

В коде f1, d, n и N считаются из счётчиков выборки; здесь n — строк в выборке, N — строк в таблице, d — различных значений в выборке, f1 — значений, которые встретились ровно один раз. Подставим числа из выборки такого же размера. TABLESAMPLE BERNOULLI (0.3) берёт около 30 000 строк, но это не копия выборки ANALYZE, поэтому ответ совпадает с pg_stats приблизительно:

CREATE TEMP TABLE smp AS SELECT s FROM t TABLESAMPLE BERNOULLI (0.3);
WITH c AS (SELECT s, count(*) AS k FROM smp GROUP BY s),
agg AS (SELECT sum(k) AS n, count(*) AS d, count(*) FILTER (WHERE k = 1) AS f1 FROM c)
SELECT n, d, f1, round(n * d / ((n - f1) + f1 * n / 10000000.0)) AS duj1 FROM agg;

   n   |   d   |  f1   | duj1
-------+-------+-------+-------
 30094 | 17806 | 17583 | 42650

Выборка — 0,3% таблицы, а у каждого редкого значения 10 строк, так что из десяти копий в неё попадает в среднем 0,03, и почти все 17 806 значений встречаются по одному разу. Знаменатель n − f1 = 12 511 почти целиком состоит из двух частых значений: они дают 0,399 × 30 094 ≈ 12 007 строк выборки. Формула читает эти повторы как признак того, что различных значений мало.

Сколько стоит ошибка и что даёт большая выборка? Для default_statistics_target 100 и 1000 (ALTER TABLE t ALTER s SET STATISTICS ..., то же для u) выполнено по пять ANALYZE t, после каждого прочитан n_distinct из pg_stats; у u отрицательное значение умножено на reltuples. Настоящие значения: s — 600 002, u — 1 000 000.

При target 100 оценка s занижена в 14 раз, при 1000 — в 2,1 раза: формула та же, выборка в 300 000 строк. У u повторы в выборке случайны, а не созданы частыми значениями, поэтому оценка близка к истине, но прыгает от запуска к запуску. Что делает ANALYZE при target 1000:

ANALYZE VERBOSE t;
EXPLAIN SELECT * FROM t WHERE s = 123457;

INFO:  "t": scanned 73536 of 73536 pages, containing 10000000 live rows and 0 dead rows; 300000 rows in sample, 10000000 estimated total rows
system usage: CPU: user: 0.69 s, system: 0.03 s, elapsed: 0.73 s

 Seq Scan on t  (cost=0.00..198536.00 rows=21 width=24)
   Filter: (s = 123457)

Теперь читается вся таблица, ANALYZE занимает 0,73 с вместо 0,11 с, а оценка rows упала со 141 до 21 при факте 10. Если настоящее число значений известно, его можно задать: ALTER TABLE ... ALTER ... SET (n_distinct = ...) действует при следующем ANALYZE (документация: ALTER TABLE).

ALTER TABLE t ALTER s SET (n_distinct = 600002);
ANALYZE t;
EXPLAIN SELECT * FROM t WHERE s = 123457;

 Seq Scan on t  (cost=0.00..198536.00 rows=10 width=24)
   Filter: (s = 123457)

Оценка 10 совпала с фактом. Убери контейнер вместе с томом данных:

docker rm -f -v dba-statistics-analyze-histograms

Что из этого следует

• Частые значения оцениваются хорошо: в опыте 1 s = 0 дал 2 999 777 строк против 3 000 000. Редкие получают «остаток поровну», и их оценка целиком зависит от n_distinct: 141 при 42 687, 21 при 283 050, 10 при заданных вручную 600 002.
• Гистограмма точна для диапазонов (0,8% ошибки при w < 100000) и не оценивает равенство: корзин 100, а значений в w 990 267.
• n_distinct занижается, когда частые значения дают в выборке много повторов, а остальные встречаются редко. Target 1000 вместо 100 улучшил оценку в 6,6 раза, но не до конца, и ANALYZE стал дольше в 6,6 раза (0,73 с против 0,11 с на 575 МБ).
• Известный n_distinct лучше зафиксировать: положительное число — количество значений, отрицательное — доля строк, и вторая форма остаётся верной, пока таблица растёт.

Чек-лист

1. Если rows для равенства с редким значением расходится с фактом в разы, сравни pg_stats.n_distinct с count(DISTINCT col).
2. Пересчитай оценку вручную: (1 − сумма частот MCV) / (n_distinct − число MCV) × reltuples; совпадение значит, что ошибка во входных данных, а не в планировщике.
3. Поднимай SET STATISTICS на отдельных столбцах, а не default_statistics_target целиком: стоимость ANALYZE растёт вместе с выборкой.
4. После изменения target или n_distinct запусти ANALYZE и сверь rows до и после.
5. Не пугайся разброса: повторный ANALYZE берёт другую выборку, n_distinct у u менялся от 927 361 до 1 065 986.