Iterative optimizer: правила и паттерны

Логический план, построенный напрямую из запроса, корректен — он даёт правильный результат. Но почти никогда не оптимален. Фильтр может стоять высоко над join-ом, заставляя соединять лишние строки. Могут читаться все столбцы таблицы, хотя нужны два. Подзапрос может быть записан так, что движок выполнит его наивно. Превратить корректный план в эффективный — задача оптимизатора.

Этот урок — про iterative optimizer Trino: как он устроен, что такое правило (rule), что такое паттерн (pattern), и почему он работает многопроходно.

Идея: преобразование плана с сохранением смысла

Оптимизатор стоит на одном фундаментальном факте: для одного результата существует много разных планов. Запрос «отфильтровать customer и соединить с orders» можно выполнить, отфильтровав до join или после join. Оба плана дают одинаковый результат — но первый соединяет меньше строк и потому быстрее.

Оптимизатор берёт исходное дерево PlanNode и переписывает его, получая эквивалентное по смыслу, но более эффективное дерево. «Эквивалентное по смыслу» здесь строго: преобразование допустимо, только если оно гарантированно сохраняет результат запроса. Оптимизатор не угадывает и не рискует — он применяет лишь те трансформации, которые математически корректны: на входе у него корректное дерево PlanNode, на выходе — корректное дерево PlanNode, тот же тип представления, лучше форма.

Trino использует iterative optimizer — оптимизатор, построенный не как один монолитный алгоритм, а как набор небольших независимых правил, применяемых итеративно. Разберём, что такое правило.

Что такое правило

Правило (rule) — это одна конкретная трансформация плана. Правило устроено из двух частей:

1. Pattern (паттерн) — описание фрагмента дерева плана, к которому правило применимо. Паттерн отвечает на вопрос «где в дереве это правило вообще имеет смысл». Например, паттерн «FilterNode, у которого ребёнок — ProjectNode» или «JoinNode, оба входа которого — TableScan».

2. Трансформация — что сделать с найденным фрагментом. Если паттерн в дереве найден, правило применяет трансформацию: заменяет найденное поддерево новым.

Формула простая: правило = паттерн + трансформация. Паттерн ищет место, трансформация переписывает.

Сила такого устройства — в изоляции. Каждое правило — маленькое, отвечает за одну трансформацию, и его можно понять и протестировать отдельно от остальных. Оптимизатор Trino — это десятки таких правил. Добавить новую оптимизацию означает добавить новое правило, не трогая существующие.

Типичные трансформации правил

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

Predicate pushdown — опускание фильтра. Правило ищет паттерн «FilterNode над чем-то, что фильтр может пройти» и опускает фильтр ниже по дереву, ближе к TableScan. Чем раньше отсеяны строки, тем меньше данных проходит через дорогие операции выше.

Projection pushdown — ограничение столбцов. Правило обнаруживает, что выше по дереву используются не все столбцы таблицы, и проталкивает выбор только нужных столбцов в TableScan. Для колоночных форматов (Parquet, ORC) это означает не читать с диска ненужные столбцы вообще.

Свёртка константных выражений. Если в плане встречается выражение из одних констант — 2026 - 1 — правило вычисляет его один раз на этапе планирования и подставляет результат 2025, чтобы движок не считал это для каждой строки.

Упрощение и переписывание подзапросов. Ряд правил переписывает декоррелированные подзапросы, превращает некоторые подзапросы в join-ы, упрощает избыточные конструкции.

Важно: часть этих правил доводит план до состояния, в котором срабатывает pushdown через SPI. Когда правило опускает FilterNode к TableScan, дальше движок может спросить коннектор через applyFilter — «возьмёшь этот фильтр себе?». То есть оптимизатор и pushdown в источник работают в связке: сначала правило приводит план к удобной форме, затем коннектор забирает операцию.

Почему оптимизатор итеративный

Ключевое слово в названии — iterative. Оптимизатор не проходит по плану один раз. Он применяет правила многопроходно, пока план продолжает меняться.

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

1. Правило свёртки констант упростило выражение в предикате FilterNode.
2. После упрощения предикат стал таким, что правило predicate pushdown теперь может опустить этот FilterNode ниже.
3. После опускания фильтра правило projection pushdown видит, что выше нужно меньше столбцов, и сужает TableScan.

Если бы оптимизатор прошёл план один раз, он бы поймал только первое правило, до которого дошёл, и упустил каскад. Поэтому он работает итеративно: применяет применимые правила, смотрит, изменился ли план, и если да — заходит на новый круг. Цикл останавливается, когда очередной проход не нашёл ни одного применимого правила — план достиг фиксированной точки (fixed point), его больше нельзя улучшить имеющимися правилами.

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

Место оптимизатора в цикле

Оптимизатор — это этап, который превращает «правильный» план в «эффективный». Вход и выход у него одного типа — дерево PlanNode. Это важно: оптимизатор не меняет тип представления, он лишь улучшает его форму. Следующий этап, distributed planning, возьмёт уже оптимизированный план и разрежет его на распределённые фрагменты.

Попробуй сам

Эффект оптимизатора виден, если сравнить план до и после применения правил — это делается через EXPLAIN:

1. Выполните EXPLAIN (TYPE LOGICAL) SELECT c.name FROM tpch.sf1.customer AS c JOIN tpch.sf1.orders AS o ON c.custkey = o.custkey WHERE c.acctbal > 5000. Найдите в плане, где оказался фильтр acctbal > 5000 — обратите внимание, опущен ли он близко к чтению customer.
2. Выполните EXPLAIN (TYPE LOGICAL) SELECT custkey FROM tpch.sf1.customer. Посмотрите, какие столбцы упомянуты в TableScan — оптимизатор должен сузить чтение до нужных.
3. Выполните EXPLAIN (TYPE LOGICAL) SELECT * FROM tpch.sf1.nation WHERE nationkey = 5 + 5. Проверьте, осталось ли в плане выражение 5 + 5 или оно свёрнуто в 10.
4. Сформулируйте письменно: почему оптимизатор должен быть многопроходным, и приведите пример двух правил, где применение одного открывает применимость другого.