Оптимизатор: rule-based и cost-based проходы

Между моментом, когда вы нажали Enter на SQL-запросе, и моментом, когда движок начал считать, происходит важная работа — оптимизация. SQL декларативен: вы описываете что хотите получить, но не как это вычислить. Один и тот же SELECT можно исполнить десятками способов, и разница в скорости между лучшим и худшим легко достигает сотен раз. Оптимизатор — компонент, который выбирает план исполнения.

Этот урок разбирает оптимизатор DuckDB как конвейер: что приходит на вход, какие проходы (passes) применяются, что выходит.

Trino: iterative optimizer — правила и паттерны Понимание этого конвейера — необходимая база для чтения EXPLAIN-планов и осмысленной диагностики медленных запросов в следующих уроках.

Где оптимизатор в конвейере запроса

Запрос проходит через несколько стадий, и оптимизатор — четвёртая из них.

Вход оптимизатора — дерево логических операторов (LogicalOperator): LOGICAL_GET (чтение таблицы), LOGICAL_FILTER, LOGICAL_PROJECTION, LOGICAL_JOIN, LOGICAL_AGGREGATE и другие. Это «наивный» план — прямой перевод SQL в операторы, ещё не оптимизированный. Выход — то же дерево, но переписанное: фильтры опущены ближе к источникам, join-ы переупорядочены, лишние выражения убраны. Дальше физический планировщик подбирает алгоритмы.

Rule-based и cost-based: две стратегии

Оптимизаторы делятся на два типа, и DuckDB сочетает оба.

Rule-based оптимизация применяет преобразования, которые улучшают план всегда, независимо от данных. Пример: фильтр выгоднее применить как можно раньше — это никогда не вредит. Такие правила не требуют знаний о данных, их можно применять безусловно.

Cost-based оптимизация выбирает между альтернативами, оценивая их стоимость по статистике данных. Пример: в каком порядке соединять три таблицы — зависит от того, сколько в них строк и насколько селективны условия. Здесь нет универсально правильного ответа; нужна модель стоимости и статистика.

DuckDB использует rule-based проходы для преобразований, всегда улучшающих план, и cost-based — там, где есть реальный выбор, прежде всего для порядка join-ов.

Оптимизатор как серия проходов

DuckDB-оптимизатор устроен как последовательность проходов (optimizer passes). Каждый проход берёт план, применяет один класс преобразований и отдаёт изменённый план следующему. Порядок проходов важен: ранние проходы создают условия для поздних.

Разберём ключевые проходы.

Expression Rewriter

Упрощает выражения. Сюда входит constant folding (2 + 3 -> 5 ещё до исполнения), упрощение булевых выражений (x AND TRUE -> x, x OR TRUE -> TRUE), свёртка сравнений с константами. Цель — чтобы движок не пересчитывал на каждой из миллионов строк то, что можно вычислить один раз при компиляции.

Filter Pushdown

Опускает условия WHERE максимально вниз — ближе к чтению таблиц. Чем раньше отсеяны ненужные строки, тем меньше данных проходит через дорогие операторы вроде join. В сочетании с zonemap-статистикой filter pushdown позволяет пропускать целые row group при сканировании. Этому проходу посвящён отдельный урок далее.

Join Order Optimizer

Единственный по-настоящему cost-based проход. Решает, в каком порядке соединять таблицы, опираясь на статистику кардинальности. Использует алгоритм DPccp. Подробно — в следующем уроке.

Common Subexpression Elimination (CSE)

Находит выражения, встречающиеся в запросе несколько раз, и вычисляет их однократно. Если upper(name) упоминается и в SELECT, и в WHERE, и в ORDER BY — нет смысла считать upper трижды.

Projection Pushdown

Гарантирует, что из источника читаются только реально нужные колонки. Для колоночного хранилища это огромная экономия: лишние колонки просто не загружаются с диска.

Почему порядок проходов важен

Проходы оптимизатора — не независимый набор, а конвейер с продуманным порядком. Ранний проход создаёт условия, которыми пользуется поздний; переставь их местами — и часть оптимизаций не сработает.

Конкретный пример. Expression Rewriter идёт раньше Filter Pushdown — и не случайно. Рассмотрим условие WHERE TRUE AND amount > 5 * 2. Если бы filter pushdown сработал первым, он опустил бы в скан условие в исходном, «грязном» виде: TRUE AND amount > 5 * 2. Движок на каждой строке вычислял бы 5 * 2 и TRUE AND .... Но Expression Rewriter идёт раньше: он сворачивает условие в amount > 10, и уже это упрощённое условие filter pushdown опускает в скан. Поздний проход получает результат раннего в лучшей форме.

Другой пример взаимодействия. Filter Pushdown идёт раньше Join Order Optimizer. Опущенные фильтры урезают входы таблиц, и оценки кардинальности, на которые опирается join order, становятся точнее: оптимизатор видит не «в таблице 10 млн строк», а «после фильтра останется примерно 50 тысяч». Cost-based проход работает лучше, потому что rule-based проход до него уже подготовил почву.

Видим оптимизатор в работе

EXPLAIN показывает физический план — результат всех проходов. Сравним наивный смысл запроса с тем, что получилось.

EXPLAIN
SELECT o.order_id, c.name
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE c.country = 'DE' AND 1 = 1 AND o.amount > 0 + 0;

┌───────────────────────────┐
│         PROJECTION        │
│        order_id, name     │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         HASH_JOIN         │
│      customer_id = id     │
└──────┬─────────────┬──────┘
┌──────┴──────┐ ┌────┴───────────┐
│   SEQ_SCAN  │ │    SEQ_SCAN    │
│   orders    │ │   customers    │
│ Filters:    │ │ Filters:       │
│ amount > 0  │ │ country = 'DE' │
└─────────────┘ └────────────────┘

Что сделал оптимизатор:

• 1 = 1 исчезло целиком — Expression Rewriter свернул тождественно истинное условие.
• 0 + 0 свернулось в 0, и условие стало amount > 0 — constant folding.
• Оба фильтра — country = 'DE' и amount > 0 — опущены прямо в SEQ_SCAN соответствующих таблиц, а не выполняются после join. Это filter pushdown.
• Фильтр country = 'DE' поехал именно к customers, потому что колонка country принадлежит ей; оптимизатор понимает, к какой таблице относится каждое условие.

Наивный план фильтровал бы после join, прогоняя через него все строки. Оптимизированный отсекает лишнее до join.

Когда оптимизатор ошибается

Cost-based решения опираются на статистику, а статистика — это оценка. Если она искажена (например, у внешнего файла нет точных данных о кардинальности, или фильтр коррелирует с распределением необычным образом), оптимизатор может выбрать неудачный план.

Симптом: EXPLAIN ANALYZE показывает оператор, где оценочное число строк сильно расходится с фактическим — оптимизатор «думал», что строк будет 1000, а пришёл 1 миллион. Такое расхождение объясняет, почему был выбран, скажем, неудачный порядок join.

Оптимизатор можно временно отключить целиком для диагностики:

PRAGMA disable_optimizer;
-- теперь запросы исполняются по наивному плану
EXPLAIN SELECT ... ;  -- видно план без оптимизаций

PRAGMA enable_optimizer;  -- вернуть обратно

Это диагностический инструмент, а не режим работы: сравнив план с оптимизатором и без, вы понимаете, что именно дал каждый проход и не сделал ли он хуже. В нормальной эксплуатации оптимизатор всегда включён.

Попробуй сам

1. Создай таблицы products(id, name, price) и sales(id, product_id, qty), наполни каждую несколькими тысячами строк через range.
2. Выполни EXPLAIN для запроса с заведомо «грязными» выражениями: SELECT * FROM sales s JOIN products p ON s.product_id = p.id WHERE TRUE AND p.price > 10 * 1 AND s.qty <> 0 + 0; Найди в плане следы Expression Rewriter (что стало с TRUE AND, 10 * 1, 0 + 0) и filter pushdown (куда уехали фильтры).
3. Выполни PRAGMA disable_optimizer; и повтори тот же EXPLAIN. Сравни два плана: какие фильтры теперь НЕ опущены к сканам, остались ли тождественные условия. Верни PRAGMA enable_optimizer;.
4. Сделай EXPLAIN ANALYZE оптимизированного запроса и найди для каждого SEQ_SCAN фактическое число строк после фильтра. Совпадает ли оно с твоей интуицией о селективности условий?