planner

Планировщик запросов (Query Planner)

Предпосылки: страницы и кортежи, B-tree (типы сканирования: Index Scan, Bitmap Index Scan, Index Only Scan), BRIN (корреляция физического и логического порядка), хеш-таблица (для понимания Hash Join).

← SP-GiST | Порядок соединения →

Таблица orders — 10 млн строк, индекс по status. Запрос WHERE status = 'pending' может выполняться Index Scan (быстро обойти 5000 строк через индекс) или Seq Scan (прочитать все 10 млн строк). Разница — 2 мс vs 3 секунды. Выбор делает планировщик, и он основывает решение на статистике: если ‘pending’ — это 0.05% строк, Index Scan; если 80% — Seq Scan дешевле.

Масштаб задачи растёт с количеством таблиц: запрос с тремя JOIN’ами даёт 6 вариантов порядка соединения, для каждого — три алгоритма (nested loop, hash, merge), плюс выбор метода доступа к каждой таблице. Даже такой простой запрос может иметь сотни возможных планов.

Статистика — входные данные планировщика

Планировщик не может выбирать план вслепую. Ему нужна информация о данных: размеры таблиц, распределение значений, корреляции. На основе этой информации планировщик оценивает selectivity — долю строк, которые пройдут каждое условие фильтрации (от 0.0 до 1.0). Чем точнее selectivity, тем ближе оценка числа строк к реальности, и тем вероятнее выбор оптимального плана.

Статистику собирает команда ANALYZE и хранит в системных каталогах — служебных таблицах PostgreSQL, описывающих структуру и содержимое базы данных. Вызвать её можно для конкретной таблицы — ANALYZE table_name — или для всей базы, просто ANALYZE. В штатном режиме запускать её вручную не нужно: фоновый процесс autovacuum отслеживает количество изменённых строк и автоматически запускает ANALYZE, когда число изменений превышает порог (см. VACUUM). Но после массовых операций — bulk load, крупный DELETE — стоит запустить ANALYZE явно, не дожидаясь autovacuum: пока статистика устаревшая, планировщик работает с неверной картиной данных и выбирает неоптимальные планы.

Статистика уровня таблицы

Системная таблица pg_class хранит метаданные о каждой таблице и индексе в базе. Для планировщика важны два поля: reltuples — приблизительное количество строк, и relpages — количество занятых страниц. Префикс «rel» — от «relation»: так в терминологии PostgreSQL называются таблицы и индексы.

SELECT relname, reltuples, relpages
FROM pg_class
WHERE relname = 'users';

Отношение reltuples / relpages показывает среднее количество строк на страницу — плотность данных. Планировщик использует эту плотность при оценке index scan: зная количество строк после фильтрации, он делит на плотность и получает число страниц heap, за которыми нужно обратиться.

Статистика уровня колонки

Представление pg_stats — удобная обёртка над системной таблицей pg_statistic, которая хранит детальную статистику по каждой колонке. В отличие от pg_class, которая знает только общие размеры таблицы, pg_stats описывает распределение значений внутри колонки.

null_frac — доля NULL-значений в колонке (от 0.0 до 1.0).

n_distinct — количество уникальных значений. Положительное число (например, 42) означает точное количество. Отрицательное (например, -0.5) — долю от общего числа строк: при 100 000 строк и n_distinct = -0.5 уникальных значений примерно 50 000.

most_common_vals (MCV) и most_common_freqs — массив самых частых значений и их точных частот:

SELECT attname, most_common_vals, most_common_freqs
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'status';
 
-- Результат:
-- most_common_vals:  {pending, completed, shipped, cancelled}
-- most_common_freqs: {0.45, 0.30, 0.20, 0.05}

Для запроса WHERE status = 'pending' планировщик берёт частоту напрямую из MCV: selectivity = 0.45, то есть 45% строк пройдут фильтр.

histogram_bounds — границы корзин гистограммы для значений, не попавших в MCV. Гистограмма компактно описывает распределение: весь диапазон делится на корзины примерно равной высоты, то есть каждая содержит одинаковую долю строк:

histogram_bounds: {18, 25, 32, 41, 55, 80}

Это 5 корзин, в каждой примерно 20% строк (не попавших в MCV): [18, 25), [25, 32), [32, 41), [41, 55), [55, 80]. Для диапазонных запросов (например, WHERE age > 50) планировщик определяет, какую долю корзин покрывает условие, и суммирует их доли. Гистограмма не используется для условий равенства (=) — для них планировщик обращается к n_distinct или MCV.

correlation — степень соответствия физического порядка строк в heap и логического порядка значений в колонке. Значение около 1.0 или -1.0 означает предсказуемый порядок (строки лежат компактно), а значение около 0 — хаотичное расположение. Correlation напрямую влияет на стоимость index scan: при высокой корреляции последовательные по индексу строки лежат на соседних страницах heap, и чтение обходится почти как sequential I/O. При низкой корреляции каждая строка может оказаться на другой странице — это random I/O, и на HDD запрос, который при correlation ≈ 1.0 занимал бы 10 мс, может растянуться до сотен миллисекунд. Например, таблица events с колонкой created_at, куда только добавляются записи (append-only), будет иметь correlation ≈ 1.0: timestamp монотонно растёт, строки ложатся в конец heap в том же порядке.

Почему MCV и гистограмма разделены

Если распределение сильно перекошено (skewed), объединённая гистограмма теряет информацию о популярных значениях. Допустим, колонка country содержит USA = 40%, India = 25%, а остальные 50 стран — по <1%. Если всё засунуть в гистограмму, ‘USA’ окажется в одной корзине с ‘Uganda’, и планировщик не узнает, что ‘USA’ — это 40% таблицы. Вместо этого PostgreSQL выделяет популярные значения в MCV с точными частотами, а гистограмму строит только по оставшимся (редким) значениям.

Вычисление selectivity

Статистика по колонкам описывает распределение данных, но планировщику нужна конкретная цифра: какая доля строк пройдёт каждое условие WHERE. Этот расчёт превращает статистику в оценку числа строк.

Условие равенства (=)

Если значение есть в MCV, selectivity берётся напрямую из most_common_freqs. Если нет — оставшаяся доля строк делится поровну между оставшимися уникальными значениями:

selectivity = (1 - sum(mcv_freqs) - null_frac) / (n_distinct - mcv_count)

Диапазонные условия (>, <, BETWEEN)

Используется гистограмма. Планировщик определяет, какие корзины покрывает условие, и суммирует их доли. Внутри корзины предполагается равномерное распределение: если граница условия попадает в середину корзины, берётся пропорциональная часть.

Когда статистика недоступна

Не для всех условий планировщик может вычислить selectivity из собранной статистики. Если условие содержит функцию или выражение от колонки (WHERE age * 2 > 60), сравнение двух колонок (WHERE start_date < end_date) или пользовательские типы и операторы — планировщик подставляет захардкоженную константу:

Ситуация	Константа
Неизвестное условие равенства	0.005 (0.5%)
Неизвестное условие неравенства	0.3333 (33%)
LIKE 'prefix%' без статистики	0.005

Эти константы — «лучшая догадка», и планировщик может ошибиться в оценке строк на порядки, что приведёт к выбору заведомо медленного плана. Решение — переписать запрос так, чтобы условие было на «голую» колонку (WHERE age > 30), или создать expression index.

Cost Model — как сравниваются планы

Зная selectivity для каждого условия, планировщик может оценить число строк на каждом этапе плана. Но чтобы сравнить планы между собой, нужна единая метрика. Эту роль выполняет cost — безразмерное число, отражающее примерную стоимость выполнения. Cost нужен не для предсказания реального времени, а для ранжирования: план с cost = 100 предпочтительнее плана с cost = 500.

Базовые константы

Параметр	Default	Описание
seq_page_cost	1.0	Стоимость последовательного чтения одной страницы
random_page_cost	4.0	Стоимость случайного чтения одной страницы
cpu_tuple_cost	0.01	Стоимость обработки одной строки
cpu_index_tuple_cost	0.005	Стоимость обработки одной записи индекса
cpu_operator_cost	0.0025	Стоимость одной операции сравнения

PostgreSQL не определяет оборудование автоматически — это статические параметры, которые администратор настраивает вручную. Соотношение random_page_cost к seq_page_cost по умолчанию 4:1, что отражает реальность HDD: случайное чтение требует перемещения головки диска (seek), которое на порядок дороже последовательного чтения (HDD vs SSD). На SSD механического seek нет, и random I/O обходится почти так же дёшево, как sequential, поэтому типичная рекомендация — random_page_cost = 1.1 при seq_page_cost = 1.0.

Формула cost для Seq Scan

cost = (relpages × seq_page_cost) + (reltuples × cpu_tuple_cost)
         ↑                            ↑
      I/O cost                     CPU cost

С условием WHERE добавляется стоимость проверки:

filter_cost = reltuples × cpu_operator_cost

Формула cost для Index Scan

cost = (index_pages × random_page_cost × cache_adjustment) +
       (index_tuples × cpu_index_tuple_cost) +
       (heap_pages × random_page_cost × correlation_adjustment) +
       (rows × cpu_tuple_cost)

Два ключевых фактора делают эту формулу менее предсказуемой, чем seq scan. Correlation определяет, насколько кучно лежат нужные строки в heap: при correlation ≈ 1.0 число страниц heap близко к числу страниц при sequential чтении, при correlation ≈ 0 каждая строка может потребовать отдельного random I/O. Параметр effective_cache_size подсказывает планировщику, сколько данных вероятно уже в памяти (shared_buffers + OS page cache). Чем больше значение, тем меньше планировщик «штрафует» random I/O, считая что страницы уже закешированы, и тем охотнее выбирает index scan — для больших таблиц с горячими данными это может ускорить запросы в разы, но при неверной настройке приведёт к выбору index scan там, где seq scan был бы быстрее.

Методы доступа к таблице

Cost model оценивает стоимость плана, но конкретный план строится из методов доступа — способов, которыми PostgreSQL читает данные из таблицы. Каждый метод имеет свой профиль затрат, и планировщик выбирает тот, чей cost минимален при данной selectivity, correlation и размере таблицы.

Seq Scan

Последовательное чтение всех страниц таблицы. Seq scan выгоден, когда нужна большая доля строк (высокая selectivity), нет подходящего индекса или таблица маленькая. I/O дешёвый (sequential), но читаются все страницы без исключения.

Index Scan

Поиск через индекс, затем переход в heap за каждой строкой. Index scan выигрывает при низкой selectivity (мало строк после фильтрации), наличии подходящего индекса и высокой correlation, когда строки лежат компактно в heap. I/O дорогой (random обращения к heap), но объём данных мал.

Bitmap Index Scan

Сначала сканируется индекс и собирается битовая карта страниц heap, содержащих подходящие строки. Затем эти страницы читаются в порядке их физического расположения, что превращает random I/O в quasi-sequential. Bitmap scan занимает промежуточную нишу: при средней selectivity (примерно 5–20% строк) index scan уже генерирует слишком много случайных обращений к heap и запрос ощутимо замедляется, а seq scan по-прежнему читает лишние данные. Bitmap scan решает эту проблему, объединяя точность индекса с упорядоченным чтением.

Index Only Scan

Все нужные данные берутся прямо из индекса, без обращения к heap. Это возможно, когда все запрашиваемые колонки входят в индекс и visibility map подтверждает, что соответствующие страницы heap полностью видимы (all-visible) — иначе PostgreSQL всё равно обратится к heap для проверки видимости строки.

Алгоритмы соединения (JOIN)

Методы доступа определяют, как PostgreSQL читает отдельные таблицы. Когда запрос объединяет несколько таблиц, планировщик дополнительно выбирает алгоритм соединения — способ сопоставить строки из разных источников. Три основных алгоритма различаются по структуре данных и профилю затрат.

Nested Loop Join

Два вложенных цикла: внешний перебирает строки одной таблицы, внутренний ищет соответствия в другой.

outer.each do |outer_row|
  inner.each do |inner_row|
    if outer_row.key == inner_row.key
      result << combine(outer_row, inner_row)
    end
  end
end

Без индекса стоимость O(N × M), с индексом на inner-таблице — O(N × log M). Nested loop выгоден, когда внешняя таблица маленькая (после фильтрации) и на внутренней есть индекс по ключу соединения.

Hash Join

Построить хеш-таблицу из одной таблицы (build), пройти по второй (probe) и искать соответствия за O(1).

Фаза Build:

hash_table = {}
build_input.each do |row|
  key = row.join_key
  hash_table[key] ||= []
  hash_table[key] << row
end

Фаза Probe:

probe_input.each do |row|
  key = row.join_key
  matches = hash_table[key]
  # ...
end

Стоимость O(N + M). Hash join требует условие соединения на равенство (хеш не работает для диапазонов) и достаточно памяти для хеш-таблицы. Память ограничена параметром work_mem — лимит на объём оперативной памяти, который одна операция сортировки или хеширования может использовать (по умолчанию 4 MB). Если хеш-таблица не помещается в work_mem, PostgreSQL разбивает данные на пакеты (batches) и сбрасывает часть на диск. Каждый batch потом обрабатывается отдельно — это добавляет I/O и может замедлить запрос в разы по сравнению с полностью in-memory hash join. Hash join выгоден, когда обе таблицы большие, нет подходящего индекса и условие — равенство.

Merge Join

Если обе таблицы отсортированы по ключу соединения, можно пройти их параллельно за один проход.

while left_idx < left.size && right_idx < right.size
  if left[left_idx].key < right[right_idx].key
    left_idx += 1
  elsif left[left_idx].key > right[right_idx].key
    right_idx += 1
  else
    # Совпадение: нужно обработать все дубликаты с обеих сторон.
    # Merge join запоминает позицию начала группы дубликатов в правой таблице
    # и для каждой совпадающей строки слева перематывает правую обратно
    # к началу группы, генерируя все комбинации.
    emit_all_matches(left, right, left_idx, right_idx)
  end
end

Если данные уже отсортированы (например, читаются из индекса), стоимость O(N + M). Если нужна предварительная сортировка — O(N log N + M log M). Merge join выгоден, когда данные уже отсортированы по ключу соединения или когда сортировка и так нужна для ORDER BY (тогда она не «лишняя»). В отличие от hash join, merge join работает и для диапазонных условий соединения.

Сводка по алгоритмам

Алгоритм	Стоимость	Требования	Лучший сценарий
Nested Loop	O(N × M) или O(N × log M)	Индекс для эффективности	Маленькая внешняя таблица + индекс
Hash Join	O(N + M)	Равенство, память для хеш-таблицы	Большие таблицы без индекса
Merge Join	O(N + M)	Отсортированные данные	Данные из индексов или нужен ORDER BY

Диагностика: EXPLAIN и EXPLAIN ANALYZE

Планировщик выбирает план на основе оценок — и эти оценки могут расходиться с реальностью. Чтобы проверить, какой план выбран и насколько точны его оценки, PostgreSQL предоставляет команды EXPLAIN и EXPLAIN ANALYZE.

EXPLAIN

Показывает план выполнения без выполнения запроса.

EXPLAIN SELECT * FROM users WHERE age > 30;

Seq Scan on users  (cost=0.00..1750.00 rows=33000 width=64)
  Filter: (age > 30)

В выводе Seq Scan on users — выбранный метод доступа, cost=0.00..1750.00 — startup cost и total cost, rows=33000 — оценка количества строк, width=64 — средний размер строки в байтах.

EXPLAIN ANALYZE

Реально выполняет запрос и показывает фактические числа рядом с оценками.

EXPLAIN ANALYZE SELECT * FROM users WHERE age > 30;

Seq Scan on users  (cost=0.00..1750.00 rows=33000 width=64)
                   (actual time=0.015..12.340 rows=32847 loops=1)
  Filter: (age > 30)
  Rows Removed by Filter: 67153
Planning Time: 0.082 ms
Execution Time: 13.521 ms

К оценкам добавляются реальные числа: actual time — фактическое время в миллисекундах, actual rows — реальное количество строк, loops — сколько раз выполнялся узел (для nested loop inner будет > 1).

Диагностика плохих планов

Самый информативный сигнал — расхождение между rows (оценка) и actual rows (реальность). Разница в разы говорит о том, что планировщик принял решение на основе неверных данных. Типичные причины: устаревшая статистика (давно не было ANALYZE), невычислимая selectivity (функции от колонок, сложные выражения) и неучтённая корреляция между колонками — планировщик по умолчанию предполагает, что условия на разные колонки независимы.

Недооценка числа строк приводит к тому, что планировщик выбирает index scan, рассчитывая на 1 000 строк, а реально приходит 10 000 — объём random I/O оказывается в 10 раз больше ожидаемого, и запрос, который должен был выполниться за 50 мс, работает секунду. Переоценка даёт обратный эффект: планировщик выбирает seq scan или hash join для «большого» результата, хотя на деле строк мало и nested loop с индексом был бы в разы быстрее.

Параметры enable_*

Когда EXPLAIN ANALYZE показывает расхождение, но причина неочевидна, полезно проверить, что произойдёт при запрете конкретной стратегии. Параметры enable_* не отключают метод полностью — они добавляют к его cost огромный штраф, и планировщик выберет метод только если альтернатив нет.

Методы доступа к таблице:

Параметр	Что штрафуется
enable_seqscan	Sequential Scan
enable_indexscan	Index Scan
enable_indexonlyscan	Index Only Scan
enable_bitmapscan	Bitmap Index Scan

Алгоритмы соединения:

Параметр	Что штрафуется
enable_nestloop	Nested Loop Join
enable_hashjoin	Hash Join
enable_mergejoin	Merge Join

Прочие операции:

Параметр	Что штрафуется
enable_sort	Явная сортировка
enable_hashagg	Hash Aggregation
enable_material	Материализация промежуточного результата

Пример использования для диагностики:

SET enable_seqscan = off;
EXPLAIN SELECT * FROM users WHERE age > 30;

Если после отключения seq scan планировщик выбрал index scan — значит, индекс существует, но планировщик считал seq scan дешевле. Сравнив cost обоих планов, можно понять, насколько велика разница и не связано ли это с устаревшей статистикой или неверным random_page_cost. Эти параметры — инструмент диагностики на уровне сессии, а не настройка для production: отключение seq scan глобально заставит планировщик избегать его даже для маленьких таблиц, где seq scan оптимален.

Практические рекомендации

Понимание работы планировщика позволяет целенаправленно влиять на качество планов.

Актуальная статистика — основа. Если autovacuum по каким-то причинам не успевает (например, слишком консервативные пороги), планировщик работает с устаревшей картиной и выбирает неоптимальные планы.

Запросы стоит писать так, чтобы планировщик мог применить статистику: условия на «голые» колонки (WHERE age > 30 вместо WHERE age * 2 > 60), минимум функций в WHERE, а для неизбежных выражений — expression index.

Настройки под железо: на SSD уменьшить random_page_cost до 1.1–1.5, чтобы планировщик не штрафовал index scan за random I/O, которое на SSD почти бесплатно. effective_cache_size установить в соответствии с доступной памятью (shared_buffers — см. буферный кеш + ожидаемый OS page cache).

Для запросов с условиями на несколько коррелированных колонок — CREATE STATISTICS для связанных колонок, чтобы планировщик знал о зависимости между ними и не считал условия независимыми. Альтернатива — composite index, который косвенно даёт планировщику информацию о совместном распределении.

Все рассмотренные механизмы — статистика, cost model, методы доступа и алгоритмы соединения — работают в рамках одной таблицы или пары таблиц. Когда запрос объединяет много таблиц, возникает отдельная задача: в каком порядке выполнять соединения, и как планировщик обрабатывает подзапросы и CTE.

Sources

• PostgreSQL Documentation (пример: v16): Planner Statistics, ANALYZE, EXPLAIN, query planning cost parameters. https://www.postgresql.org/docs/16/planner-stats.html, https://www.postgresql.org/docs/16/sql-analyze.html, https://www.postgresql.org/docs/16/using-explain.html, https://www.postgresql.org/docs/16/runtime-config-query.html

---

← SP-GiST | Порядок соединения →