Планировщик: statistics и cost estimation

Планировщик видит запрос как детектив: у него есть подсказки (статистика), но не полная картина. Иногда он делает выводы, которые на 10000% неверны - и тогда запрос на 200ms превращается в запрос на 20 минут.

• **Stripe** обнаружил что plan для payments * customers JOIN ошибался в 500x из-за Zipf-распределения транзакций (топ 0.1% merchantов генерировали 60% payments). Extended statistics на (merchant_id, status) исправили estimate - время запроса упало с 45s до 1.2s.
• **GitLab** в 2021 задокументировал инцидент: после загрузки большого батча issues статистика устарела, планировщик выбрал Nested Loop вместо Hash Join для JOIN notes * issues - база деградировала на 40 минут пока DBA вручную не запустил ANALYZE.
• **Heroku Postgres** автоматически повышает statistics_target до 500 для foreign key колонок (JOIN-ключей) при создании индекса через UI - это эвристика основанная на том, что FK-колонки чаще всего участвуют в JOIN и ошибки estimates там наиболее болезненны.
• **Notion** при sharding (разбиение blocks по workspace_id) столкнулся с проблемой: partition pruning работал неверно из-за устаревшей статистики на partitioned table. После настройки autovacuum_analyze_scale_factor = 0.01 для больших партиций инцидент не повторялся.

pg_statistic: анатомия статистики

PostgreSQL хранит статистику о распределении данных в системной таблице `pg_statistic` (или её удобном представлении `pg_stats`). Эти данные собирает команда `ANALYZE` - и именно на их основе планировщик оценивает количество строк (cardinality), выбирает алгоритм JOIN и порядок операций.

По умолчанию ANALYZE собирает статистику на 100 слотах (default_statistics_target = 100). Это значит histogram_bounds имеет 101 границу - достаточно для равномерных распределений, но мало для скошенных. Увеличение до 500 улучшает точность ценой большего времени ANALYZE и размера pg_statistic.

Гистограммы и Most Common Values

Планировщик использует два механизма оценки selectivity: **MCV (Most Common Values)** для частых значений и **histogram** для остального распределения. При запросе `WHERE status = 'pending'` сначала проверяется MCV - если 'pending' там есть, используется точная частота. Если нет - interpolation по гистограмме.

Гистограмма хранит **равночастотные** (equi-depth) бакеты, не равноширокие. Это означает каждый бакет содержит примерно одинаковое число строк. Для оценки `WHERE amount BETWEEN 100 AND 200` планировщик считает долю бакетов, попадающих в этот диапазон.

Correlation: физический порядок данных

`correlation` в pg_stats показывает насколько физический порядок строк в heap соответствует логическому порядку значений колонки. Диапазон [-1, 1]: 1.0 означает строки физически упорядочены по возрастанию, -1 - по убыванию, 0 - хаотично. Это критически влияет на стоимость Index Scan.

CLUSTER позволяет физически упорядочить таблицу по индексу, подняв correlation до ~1.0. После CLUSTER на orders(user_id) - Index Scan по user_id станет на порядок эффективнее. Но CLUSTER блокирует таблицу и эффект теряется по мере вставки новых строк.

Extended Statistics

Стандартная статистика собирается per-column независимо. Это проблема при условиях на нескольких коррелированных колонках: `WHERE city = 'Moscow' AND country = 'Russia'`. Планировщик перемножает selectivities (0.1 * 0.5 = 0.05), не зная что city зависит от country - реальная selectivity 0.5, ошибка в 10x. PostgreSQL 10+ решает это через `CREATE STATISTICS`.

Extended statistics поддерживают три типа: `ndistinct` (совместная кардинальность нескольких колонок), `dependencies` (функциональные зависимости - city зависит от country), `mcv` (Most Common Values для комбинаций). PostgreSQL 14+ добавил поддержку OR-условий в extended statistics.

Cardinality Estimation для JOIN

При JOIN двух таблиц планировщик оценивает результирующее количество строк по формуле: `rows_A * rows_B / max(ndistinct_A, ndistinct_B)`. Это предполагает что каждое значение join-ключа в A совпадает с каждым в B - так называемый **принцип minmax**. Ошибки здесь каскадируются: неверная оценка JOIN меняет выбор алгоритма и порядок операций.

PostgreSQL 16 улучшил join estimation через Incremental Sort и лучшее использование extended statistics для multi-join запросов. Если после всех настроек estimates всё равно плохие, можно использовать `pg_hint_plan` extension для принудительного указания алгоритма - но это временная мера, не постоянное решение.

Ключевые идеи

• **pg_statistic** хранит MCV (точные частоты топ-значений) и гистограмму (равночастотные бакеты) для каждой колонки; ANALYZE обновляет их по сэмплу.
• **correlation** показывает физическую упорядоченность данных - при correlation ≈ 0 Index Scan дорогой (много random I/O), планировщик предпочтёт Seq Scan.
• **Extended Statistics** (CREATE STATISTICS) решает проблему коррелированных колонок, обучая планировщика зависимостям между ними.
• **Join estimation** ошибается при data skew и устаревшей статистике; каскадные ошибки estimates могут превратить 200ms запрос в 20-минутный.

Связанные темы

Понимание планировщика объединяет несколько тем PostgreSQL:

• EXPLAIN ANALYZE — Единственный способ увидеть расхождение между estimate и actual - диагностика неверной статистики начинается здесь
• Алгоритмы JOIN — Cardinality estimates напрямую определяют выбор между Hash Join, Nested Loop и Merge Join
• VACUUM и autovacuum — autovacuum запускает ANALYZE для поддержания актуальности статистики; настройки autovacuum_analyze_scale_factor критичны

Вопросы для размышления

• Есть ли в вашей схеме таблицы с сильно скошенным распределением данных (например, активность топ-пользователей), и как это отражается на точности планировщика?
• Какие пары колонок в вашей схеме наиболее вероятно имеют функциональные зависимости, и стоит ли для них создать extended statistics?
• Настроен ли autovacuum так, чтобы ANALYZE запускался достаточно часто для таблиц с интенсивными вставками?

Связанные уроки

• alg-21-dp