ЯдроКодаподготовка к экзаменам
Подготавливаем текст, источники и редакционные примечания без изменения разметки страницы.
Автор: Казачкин Даниил Михайлович · Обновлено
Связываем устройство B-tree с cost-based planner PostgreSQL: селективность, составные индексы, EXPLAIN ANALYZE, статистика и пределы index-only scan.
Команда CREATE INDEX не является приказом планировщику. Она добавляет новый путь доступа, который PostgreSQL сравнивает с последовательным чтением таблицы и другими планами. Иногда B-tree сокращает работу на порядки, иногда индексный обход дороже Seq Scan, а иногда подходящий на вид составной индекс почти не сужает диапазон. Чтобы объяснить результат, нужно соединить две идеи: устройство упорядоченного дерева и стоимостный выбор плана.
Исходная работа Байера и МакКрейта формализовала семейство многоходовых сбалансированных деревьев для динамического индекса на внешней памяти. Работа Селинджер и соавторов описала выбор путей доступа в System R на основе оценок стоимости. Современный PostgreSQL отличается от этих систем во многих деталях, однако связка «физическая структура плюс cost-based planner» остаётся полезной моделью мышления.
У бинарного дерева в узле мало ключей и два направления. Для дискового или страничного хранилища важнее уменьшить число обращений к страницам, поэтому один узел B-tree содержит много упорядоченных ключей и указателей. Большая ветвистость делает дерево низким: поиск спускается от корня к листу через небольшое число страниц.
Классическая схема поддерживает баланс при вставках и удалениях: переполненный узел разделяется, недостаточно заполненные узлы могут перераспределять записи или объединяться. Из этого нельзя вывести точное число чтений для PostgreSQL без учёта cache, размера страниц, реализации B-tree, MVCC и распределения данных. Но модель объясняет ключевые свойства:
BETWEEN начинают сканирование с границы диапазона;В PostgreSQL B-tree является индексом по умолчанию. Официальная документация перечисляет типичные индексируемые сравнения <, <=, =, >=, >, а также эквивалентные диапазонные конструкции. B-tree может вернуть данные в порядке ключей, но это не означает, что он всегда лучший способ выполнить ORDER BY: для большой доли таблицы последовательное чтение и отдельная сортировка могут быть дешевле.
Рассмотрим журнал заказов:
CREATE TABLE orders (
id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
tenant_id bigint NOT NULL,
status text NOT NULL,
created_at timestamptz NOT NULL,
total_cents bigint NOT NULL
);
CREATE INDEX orders_tenant_created_idx
ON orders (tenant_id, created_at DESC)
INCLUDE (status, total_cents);
ANALYZE orders;
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT created_at, status, total_cents
FROM orders
WHERE tenant_id = 42
AND created_at >= timestamptz '2026-08-01 00:00:00+00'
ORDER BY created_at DESC
LIMIT 50;Порядок ключей соответствует запросу: равенство по tenant_id, затем диапазон и сортировка по created_at. Колонки в INCLUDE не участвуют в навигации; они могут позволить вернуть значения из индекса, если выполнены условия index-only scan. Даже тогда PostgreSQL иногда обращается к heap, потому что видимость версии строки определяется MVCC и не каждая страница помечена как полностью видимая.
В учебном эксперименте следует сравнивать планы на реалистичном объёме и распределении. EXPLAIN ANALYZE действительно исполняет запрос; для модифицирующих команд его запускают только с пониманием побочного эффекта, при необходимости внутри откатываемой транзакции. BUFFERS показывает работу с блоками, но один прогон после холодного старта и один прогон на прогретом cache отвечают на разные вопросы.
Если условие возвращает одну строку из десяти миллионов, B-tree часто экономит чтение. Если возвращается половина широкой таблицы, индексный план может потребовать множество разрозненных обращений к heap. Последовательный scan читает страницы подряд и способен оказаться дешевле.
Планировщик не знает будущую фактическую стоимость. Он оценивает количество строк и операции по статистике, затем складывает условные стоимости CPU и I/O. Это не измеренные миллисекунды. У плана есть startup cost, total cost, оценка rows и width. Сравнивать стоимость между разными серверами как абсолютное время нельзя, но внутри одного planning decision она помогает выбрать альтернативу.
Расхождение estimated rows и actual rows на порядки — важный диагностический сигнал. Причинами бывают устаревшая статистика, корреляция колонок, неравномерное распределение, выражение без подходящей статистики или параметр запроса. Прежде чем запрещать Seq Scan, нужно выполнить ANALYZE, проверить данные и понять ошибку оценки. Официальная документация прямо рекомендует экспериментировать на реальных данных: маленькая синтетическая таблица отвечает только за маленькую синтетическую таблицу.
Индекс (a, b, c) упорядочен сначала по a, внутри одинакового a — по b, затем по c. Наиболее предсказуемо он сужает сканирование при равенствах по ведущим колонкам и ограничении на первую следующую колонку. Запрос только по c не получает магического прямого адреса ко всем значениям c: они разбросаны по диапазонам разных a и b.
В актуальном PostgreSQL есть skip scan: при некоторых распределениях planner может выполнять повторные поиски по возможным значениям пропущенной ведущей колонки. Это уточняет старое мнемоническое правило «без левой колонки индекс не работает». Правильнее сказать: ограничения на ведущие колонки обычно определяют, какую часть B-tree придётся просмотреть; skip scan выгоден лишь тогда, когда оценённое число повторных поисков невелико.
Порядок колонок выбирают по реальным шаблонам запросов, не только по индивидуальной cardinality. Для WHERE tenant_id = ? AND created_at >= ? ведущий tenant обеспечивает локальный диапазон времени. Для глобального отчёта только по времени тот же индекс может оказаться плохим. Один широкий индекс «на всё» увеличивает место, стоимость записей и число вариантов для сопровождения.
Планировщик сопоставляет условие с индексным ключом и его operator class. Если индекс построен по created_at, условие по функции от колонки может не задавать тот же диапазон:
-- Выражение меняет форму ключа и может не использовать обычный индекс эффективно.
WHERE date(created_at) = DATE '2026-08-28'
-- Явный полуинтервал соответствует порядку created_at.
WHERE created_at >= TIMESTAMPTZ '2026-08-28 00:00:00+00'
AND created_at < TIMESTAMPTZ '2026-08-29 00:00:00+00'Альтернативой бывает expression index, если именно выражение стабильно присутствует в нагрузке. Но переписывание запроса должно сохранять семантику часового пояса и границ; производительность не оправдывает изменение результата.
Для LIKE 'prefix%' B-tree может быть применим при подходящей локали и operator class, тогда как ведущий wildcard LIKE '%fragment%' не задаёт начальную границу обычного лексикографического диапазона. Для полнотекстового поиска, массивов, геометрии и поиска похожести существуют другие типы индексов и расширения. «B-tree — быстрый поиск» не означает «B-tree — универсальный поиск».
Вторичные индексы содержат ссылку на версию строки в heap. PostgreSQL использует MVCC: разные транзакции могут видеть разные версии. Чтобы index-only scan не посещал heap, запрос должен требовать только доступные в индексе колонки, а visibility map должна подтверждать, что все строки на соответствующей heap-странице видимы всем текущим снимкам.
Поэтому добавление INCLUDE — возможность, не гарантия нулевых Heap Fetches. На активно изменяемой таблице visibility map меняется. Кроме того, покрывающий индекс становится шире: занимает больше cache, медленнее создаётся и требует работы при изменениях. Решение проверяют по полю Heap Fetches, buffers и частоте записей, а не по названию plan node.
Безопасный цикл оптимизации выглядит так:
EXPLAIN (ANALYZE, BUFFERS) на репрезентативных данных.Отключение enable_seqscan может быть диагностическим экспериментом, но не доказательством, что PostgreSQL ошибся. Принудительно полученный index scan показывает альтернативу; затем нужно понять, почему cost model её отвергла.
Статья Байера и МакКрейта не описывает точное современное устройство PostgreSQL B-tree, его concurrency control, дедупликацию, WAL или MVCC. Она даёт фундаментальную модель многоходового сбалансированного индекса, а не руководство по конкретной версии СУБД.
Алгоритм System R из работы Селинджер и соавторов не является исходным кодом нынешнего planner PostgreSQL. Из исторической работы корректно брать принцип оценки альтернативных путей, но нельзя приписывать PostgreSQL все формулы, предположения и ограничения System R.
Один EXPLAIN ANALYZE не доказывает устойчивое ускорение. Cache, конкурентная нагрузка, параметры, объём таблицы и распределение значений меняют результат. План на тысяче равномерных тестовых строк нельзя переносить на сотни миллионов коррелированных production-строк.
Наконец, наличие index scan не доказывает хороший запрос, а отсутствие index scan не доказывает ошибку planner. Цель — минимизировать измеримую стоимость пользовательского сценария с учётом записи и сопровождения, а не добиться слова Index в выводе.
Самостоятельный редакционный разбор ЯдроКода по работам Bayer и McCreight, Selinger et al. и официальной документации PostgreSQL. Текст и примеры подготовлены редакцией.
SQL-примеры, диагностический протокол и объяснительная структура созданы редакцией; исходные рисунки и таблицы не воспроизводятся.