Как устроен оптимизатор запросов Trino: от реляционного дерева до cost-based планирования

Оптимизатор запросов Trino решает задачу с комбинаторным взрывом: аналитический SQL-запрос с несколькими JOIN и подзапросами может иметь миллионы альтернативных планов выполнения. В распределённых движках число вариантов растёт быстрее факториала от количества таблиц. Разница между лучшим и худшим планом измеряется не процентами, а порядками: один и тот же запрос на одних данных может выполняться секунду или час. При этом план нужно выбрать за миллисекунды, пока клиент ждёт ответа. Поэтому промышленные системы не перебирают все альтернативы, а ищут достаточно хороший вариант.

Trino — распределённый open source SQL-движок для больших данных. Изначально проект назывался Presto и создавался в Facebook как более быстрая альтернатива Hive. Trino построен на массивно-параллельной архитектуре: промежуточные результаты между узлами передаются в памяти, без записи на диск. Он подключается к десяткам источников: озёрам данных в S3-совместимых хранилищах, реляционным СУБД вроде PostgreSQL и Greenplum, Kafka. Это делает Trino федеративным движком для запросов к разнородным системам.

Федеративность усложняет работу оптимизатора. Данные хранятся во внешних системах, поэтому Trino должен заранее решить, какую работу передать источнику, а какую выполнить самостоятельно. Переспросить источник по ходу выполнения запроса нельзя: каждое лишнее чтение из озера данных или внешней СУБД увеличивает сетевые задержки и время обработки.

В статье разберём, как устроено промежуточное представление запроса в Trino, как работает основной механизм трансформаций IterativeOptimizer и как правила pushdown сокращают объём данных, получаемых из источника. Покажем, как cost-based компонент JoinEnumerator выбирает порядок соединений. Также рассмотрим, что команда CedrusData, с марта 2026 года входящая в VK Tech, добавила поверх открытого кода Trino: реализацию фреймворка Cascades для более точной расстановки операций обмена данными между узлами.

Материал переработан из статьи 2022 года. Часть архитектуры с тех пор не изменилась, но статус Cascades в CedrusData устарел. Код в тексте сверен с веткой master Trino по состоянию на сентябрь 2026 года.

Пять техник оптимизации SQL-запросов

Прежде чем разбирать конкретную реализацию, зафиксируем основные подходы к построению оптимизаторов запросов. В индустрии сложилось пять техник. Они не исключают друг друга: реальные системы, включая Trino, комбинируют их в одном пайплайне.

Visitor-обход. Единый проход по дереву плана, который нужен там, где требуется полный контекст запроса. Например, чтобы удалить неиспользуемые атрибуты, нужно знать, какие колонки потребуются на выходе. Rule-based трансформации. Правило описывает переписывание конкретного паттерна операторов. Например, Filter по ключу группировки над Aggregate можно перенести под Aggregate, чтобы отфильтровать данные раньше.

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

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

Многофазная оптимизация. Вместо одного универсального прохода оптимизатор выполняет фиксированную последовательность шагов: сначала проталкивает фильтры к источнику, затем определяет порядок соединений, подставляет материализованные представления и расставляет операции обмена. Порядок JOIN и выбор материализованных представлений по отдельности относятся к NP-полным задачам, а их совместное решение в одной фазе потребовало бы перемножать сложности. Разбиение на фазы делает задачу практически решаемой, поэтому так устроены промышленные оптимизаторы, включая Trino.

Промежуточное представление: дерево реляционных операторов

Первое архитектурное решение при разработке оптимизатора — выбрать представление запроса, с которым он будет работать. Абстрактное синтаксическое дерево, AST, напрямую отражает текст SQL: SELECT, FROM, WHERE и GROUP BY становятся узлами дерева. Такое представление проще всего получить, поскольку оно напрямую формируется парсером.

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

Реляционное дерево устроено иначе. Его узлы — операторы реляционной алгебры: Project, Filter, Join, Aggregate. Семантика запроса выражается непосредственно структурой дерева. Чтобы перенести фильтр, достаточно переставить два узла, а не переписывать фрагмент синтаксиса.

За это приходится платить отдельным шагом трансляции AST в реляционное дерево, но затем все фазы оптимизации работают с удобным для преобразований представлением. Поэтому большинство современных оптимизаторов, включая Trino, используют реляционные деревья.

Показательный контраст — PostgreSQL. Его планировщик оперирует деревом запроса, query tree, которое строится из синтаксического дерева на этапах анализа и переписывания правил. Это не дерево реляционных операторов в том виде, в котором оно представлено в Trino. Такой подход не делает планировщик PostgreSQL хуже, но ограничивает набор трансформаций, доступных без дополнительной перестройки представления.

Пайплайн трансляции: от парсера до реляционного дерева

До передачи запроса оптимизатору Trino проходит три этапа. Парсер на базе ANTLR и грамматики SqlBase.g4 строит AST из текста SQL. Семантический анализатор, Analyzer, проверяет логические ошибки, например обращения к несуществующим колонкам, и дополняет дерево информацией о типах и функциях. Затем RelationPlanner транслирует AST в дерево реляционных операторов, представленное узлами PlanNode. Именно это дерево проходит через дальнейшие фазы оптимизации.

Каждая фаза реализует интерфейс PlanOptimizer с простой сигнатурой: план на входе и план на выходе.

public interface PlanOptimizer
{
    PlanNode optimize(PlanNode plan, Context context);
}

Context в актуальной версии кода — record, объединяющий сессию, аллокаторы символов и идентификаторов узлов, сборщик предупреждений и статистику. В версии 2022 года эти данные передавались отдельными параметрами метода, но общий принцип не изменился.

Единый интерфейс позволяет собирать оптимизатор из десятков независимых фаз. В версии 420 их было больше 80. В ветке master на сентябрь 2026 года список PlanOptimizers создаёт более 40 экземпляров IterativeOptimizer с разными наборами правил.

Ключевые операторы на примерах

Реляционное дерево Trino строится из небольшого набора операторов:

• TableScanNode — сканирование источника: набора файлов в озере данных вместе с метаданными, топика Kafka или таблицы PostgreSQL.
• ProjectNode — преобразование атрибутов, например SELECT a, b + 10.
• FilterNode — предикат вида WHERE a > 10.
• JoinNode — объединение двух входов по условию.
• AggregationNode — агрегация вида SUM(a) GROUP BY b.
• WindowNode — оконная функция вида SUM(a) OVER (PARTITION BY b).

Возьмём запрос, который группирует заказы по статусу и суммирует стоимость:

SELECT orderstatus, SUM(totalprice)
FROM orders
GROUP BY orderstatus;

После трансляции он превращается в дерево:

OutputNode
  AggregationNode (SUM(totalprice) GROUP BY orderstatus)
    TableScanNode (orders)

Дерево читается снизу вверх: данные поступают из TableScanNode, проходят через AggregationNode и достигают корня, OutputNode. Фактический план любого запроса можно посмотреть командой EXPLAIN в Trino.

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

IterativeOptimizer: как работает rule-based оптимизация в Trino

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

Правило = паттерн + трансформация

В коде Trino правило — класс, реализующий интерфейс Rule. Оно состоит из двух обязательных частей: паттерна и логики трансформации. Паттерн описывает фрагмент реляционного дерева, который ищет правило. Если паттерн совпадает, запускается преобразование.

Пример — правило PushLimitThroughProject. Оно переносит LimitNode под ProjectNode, чтобы отсечь лишние строки до вычисления выражений в проекции. Паттерн правила в актуальном коде выглядит так:

private static final Pattern<LimitNode> PATTERN = limit()
        .with(source().matching(
                project()
                        // do not push limit through identity projection which could be there for column pruning purposes
                        .matching(projectNode -> !projectNode.isIdentity())
                        .capturedAs(CHILD)));

Комментарий означает следующее: правило ищет LimitNode, источником которого служит ProjectNode, если проекция не тождественная. Тождественную проекцию оставляют отдельно, поскольку она нужна только для отсечения колонок, а переносить через неё LimitNode бессмысленно.

Паттерн работает как регулярное выражение, но применяется к дереву, а не к строке. Он задаёт форму, которую нужно найти, а драйвер самостоятельно обходит план и ищет совпадения.

Разница хорошо видна на простом запросе:

SELECT orderkey, totalprice * 1.2 AS price_with_vat
FROM orders
LIMIT 10;

До применения правила LimitNode находится над ProjectNode, который вычисляет price_with_vat для всех строк источника. После трансформации LimitNode перемещается ближе к источнику, поэтому выражение рассчитывается только для десяти строк, попадающих в результат.

Как IterativeOptimizer применяет правила

Все rule-based трансформации запускает единый драйвер IterativeOptimizer, который получает на вход список правил. Перед началом работы он не меняет дерево операторов напрямую. Вместо этого записывает план во внутреннюю структуру Memo и заменяет входы операторов на GroupReference — ссылки на исходные узлы.

Затем драйвер обходит дерево сверху вниз. Для каждого узла он проверяет, какие правила подходят по паттерну, и применяет их по одному. Если правило изменило узел, IterativeOptimizer повторно проверяет дочерние узлы: изменение внизу дерева может открыть новую трансформацию выше. Обход продолжается, пока план не перестанет меняться.

Работа завершается в одном из двух случаев: либо ни одно правило больше не находит подходящего паттерна, либо истекает таймаут. Таймаут нужен не для ограничения производительности, а для защиты от ошибок в правилах. Например, если одно правило переносит FilterNode под JoinNode, а второе возвращает его обратно, они могут бесконечно отменять изменения друг друга. Ограничение по времени превращает такую ситуацию в явную диагностируемую ошибку вместо зависания планировщика.

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

GroupReference: указатели вместо копий

Замена узла на GroupReference — не просто техническая деталь, а один из механизмов, который позволяет IterativeOptimizer быстро работать с большими планами. Когда правило меняет один оператор, драйвер не пересобирает дерево целиком. Он обновляет ссылку в Memo, а вышестоящие операторы продолжают ссылаться на ту же группу с уже изменённым содержимым. Это сокращает затраты CPU на планах с десятками операторов.

Похожий подход использует Apache Calcite. Его эвристический планировщик HepPlanner работает со своим аналогом GroupReference — HepRelVertex. В Calcite есть и другой, принципиально отличающийся планировщик: VolcanoPlanner, cost-based оптимизатор на основе подхода Volcano/Cascades с полноценным memo. Сравнивать его с IterativeOptimizer напрямую нельзя: это разные классы алгоритмов.

Memo в Trino тоже вводит группы эквивалентности, характерные для cost-based оптимизаторов. Однако, в отличие от классического Cascades, группа Trino хранит только один план, а не набор альтернатив.

Основные группы правил

В пакете правил Trino на сентябрь 2026 года больше 200 классов. Их можно разделить на несколько функциональных групп:

• Упрощение операторов: constant folding, удаление неиспользуемых атрибутов, выявление операторов, которые заведомо не вернут записей, замена OUTER JOIN на INNER JOIN, если это доказуемо эквивалентно.
• Перестановка операторов: перенос FilterNode под JoinNode, AggregationNode под JoinNode, LimitNode под ProjectNode.
• Декорреляция и упрощение подзапросов: преобразование коррелированных подзапросов в JOIN, которые исполнитель обрабатывает эффективнее.
• Pushdown вычислений в источники: перенос фильтров, проекций и агрегаций в коннектор.
• Планирование порядка JOIN: выбор последовательности соединения таблиц.

Pushdown отличается от остальных групп: он передаёт часть операторов на выполнение внешней системе, а не просто переставляет операторы внутри плана Trino.

Pushdown вычислений в источники данных

Trino не хранит данные самостоятельно: он получает их из внешних систем. Чаще всего это озёра данных, то есть файлы в объектных хранилищах, реляционные СУБД вроде PostgreSQL и Greenplum, а также Kafka.

Поэтому pushdown относится к самым выгодным категориям оптимизаций. Разница между подходами «прочитать всё и отфильтровать в Trino» и «запросить у источника только подходящие данные» может измеряться порядками по объёму передаваемых данных.

Без pushdown Trino извлекает из источника все колонки и строки, а фильтрацию и агрегацию выполняет самостоятельно. С pushdown движок сообщает источнику, какие строки и колонки ему нужны, и передаёт ему часть вычислений.

Filter pushdown в Trino реализован как разновидность rule-based трансформации. Правило ищет паттерн «оператор над TableScanNode» и передаёт информацию о нём коннектору. Коннектор решает, может ли выполнить операцию самостоятельно, и сообщает ядру, какую часть работы он взял на себя, а какую должен выполнить Trino.

Пример: partition pruning для таблицы sales

Пусть таблица sales в озере данных партиционирована по колонке s_date:

SELECT s_date, SUM(s_amount)
FROM sales
WHERE s_date = DATE '2026-07-22'
GROUP BY s_date;

Без pushdown Trino прочитал бы все колонки и все партиции таблицы, а затем отбросил бы всё, кроме s_date, s_amount и одной нужной партиции. За перенос предиката отвечает правило PushPredicateIntoTableScan. Оно вызывает у коннектора метод ConnectorMetadata.applyFilter.

Для озера данных предикат по s_date превращается в partition pruning и row group pruning: коннектор не читает файлы и фрагменты файлов, которые заведомо не содержат подходящих записей.

В результате план сканирует две колонки в одной партиции вместо полного перебора файлов таблицы.

Что Trino умеет передавать в источник

Коннекторный SPI Trino поддерживает несколько видов pushdown:

• Предикаты: applyFilter превращает условие WHERE в partition pruning и row group pruning на стороне источника.
• Проекции: applyProjection заставляет источник возвращать только нужные колонки. Для колоночных форматов вроде Parquet и ORC это напрямую сокращает объём чтения.
• Агрегации: applyAggregation позволяет выполнить SUM, COUNT и похожие функции силами внешней СУБД, не передавая в Trino все исходные строки.
• JOIN: applyJoin позволяет выполнить соединение внутри внешней СУБД, если обе стороны JOIN находятся в одном источнике.
• Limit: applyLimit сообщает источнику, что нужно вернуть не больше N строк, после чего он может завершить чтение раньше.

Конкретный коннектор сам решает, возьмёт ли он операцию на себя. SPI задаёт возможность pushdown, но не гарантирует его для каждого источника. Проверить результат можно через EXPLAIN: если операция ушла в источник, в плане вместо отдельного FilterNode или AggregationNode появится сканирование со встроенным условием или ограничением.

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

Cost-based оптимизация: как ReorderJoins выбирает порядок Join

Порядок JOIN — одна из самых важных оптимизаций в аналитическом движке. Неверное решение может увеличить время выполнения запроса на порядки.

Рассмотрим запрос к таблицам TPC-H:

SELECT o.orderkey, l.extendedprice
FROM orders o
JOIN lineitem l ON o.orderkey = l.orderkey
JOIN customer c ON o.custkey = c.custkey
JOIN nation n ON c.nationkey = n.nationkey
WHERE n.name = 'RUSSIA';

После фильтра n.name = 'RUSSIA' от таблицы nation остаётся одна строка. Выгодно сначала соединить её с customer, затем с orders. Тогда большая часть заказов отсеется до тяжёлого JOIN с lineitem.

Если же сначала объединить orders и lineitem, движок построит полный JOIN двух крупнейших таблиц схемы и только затем отфильтрует результат по стране.

MultiJoinNode и JoinEnumerator: top-down перебор с мемоизацией

За выбор порядка JOIN в Trino отвечает правило ReorderJoins. Оно работает в три этапа.

Сначала текущий JoinNode и все расположенные ниже JoinNode, ProjectNode и FilterNode сворачиваются в один MultiJoinNode. В нём собирается информация о соединениях, фильтрах и атрибутах.

Затем вложенный класс JoinEnumerator выбирает порядок JOIN. Он использует cost-based top-down перебор с мемоизацией: управление идёт от корня, в отличие от классического bottom-up перебора System R.

Для трёх таблиц a JOIN b JOIN c это работает так. Корневая группа [abc] разбивается на все пары непустых подмножеств: [ab][c], [ac][b], [bc][a]. Рекурсия спускается до отдельных таблиц [a], [b] и [c], стоимость которых равна стоимости сканирования. Затем управление возвращается вверх: для группы [ab] сравниваются варианты a JOIN b и b JOIN a по статистике и эвристическим формулам стоимости. В корне выбирается лучший порядок из лучших планов подгрупп.

Одни и те же группы многократно встречаются в процессе перебора, поэтому результаты кэшируются в словаре вида «группа → самый дешёвый порядок JOIN».

После выбора порядка MultiJoinNode снова разворачивается в дерево JoinNode, ProjectNode и FilterNode.

Где заканчивается cost-based в upstream Trino

Авторы Presto в 2019 году писали, что движок уже поддерживает две cost-based оптимизации на основе статистики таблиц и столбцов: выбор стратегии JOIN и переупорядочивание JOIN. Следующим шагом они называли «более полное исследование пространства планов с cost-based оценкой на основе техник фреймворка Cascades».

Спустя годы cost-based подход в upstream Trino применяется точечно: в ReorderJoins и при выборе стратегии JOIN. IterativeOptimizer не хранит альтернативные планы в группах Memo. Полноценного Cascades-оптимизатора в upstream Trino на релизе 483, выпущенном в июле 2026 года, нет.

Операторы Exchange расставляет отдельная фаза AddExchanges. Она выбирает оптимальное перераспределение данных в окрестности конкретного оператора, а не ищет глобально лучший вариант для всего плана.

Динамические фильтры: pushdown во время выполнения

Как работает динамический фильтр

Статический predicate pushdown знает предикат уже на этапе планирования, например WHERE s_date = .... Динамический фильтр формируется во время выполнения из данных одной стороны JOIN и передаётся второй стороне.

Build side — обычно правая и меньшая сторона JOIN, например таблица-справочник. Probe side — левая и более крупная сторона. Сначала выполняется build side: из неё собираются значения ключей JOIN, формируется фильтр и передаётся в скан probe side. Скан отбрасывает строки, которые заведомо не попадут в результат JOIN. Коннектор озера данных может отбросить и целые партиции — это называется dynamic partition pruning.

В документации Trino по dynamic filtering приведён пример для Hive. Поддерживаются INNER JOIN и RIGHT JOIN с условиями =, <, <=, >, >=, IS NOT DISTINCT FROM, а также semi-join с IN.

SELECT o.orderkey, o.totalprice
FROM orders o
JOIN customer c ON o.custkey = c.custkey
WHERE c.nationkey = 22;

Build side — customer с фильтром по nationkey — даёт небольшой набор значений custkey. Из него строится динамический фильтр, который передаётся в скан orders и отсекает лишние строки ещё до JOIN.

Основная логика реализована visitor PredicatePushDown. Это хороший пример оптимизации, которую неудобно представлять набором изолированных правил: ей нужен доступ ко всему плану, а не только к локальному фрагменту дерева.

Статический и динамический pushdown

CedrusData: Cascades поверх Trino

Что такое Cascades и чем он отличается от IterativeOptimizer

Cascades — фреймворк cost-based оптимизации, который Гётц Графе, Goetz Graefe, описал в 1995 году. Его ключевое отличие от IterativeOptimizer состоит в том, что группа эквивалентности в Memo хранит не один, а множество альтернативных планов подвыражения. Правила добавляют новые варианты, стоимость каждого рассчитывается по статистике, а итоговый план выбирается по минимальной суммарной стоимости.

Подход используют SQL Server и Greenplum. В Apache Calcite его реализует VolcanoPlanner, который не следует путать с rule-based планировщиком HepPlanner.

Cascades особенно полезен для расстановки Exchange. Во время распределённого запроса многим операторам требуется предварительно перераспределить данные. Для GROUP BY a, b все строки с одинаковой парой [a, b] должны попасть на один узел. Аналогичные требования есть у JOIN, Window и Sort.

Правило AddExchanges ищет оптимальный вариант рядом с конкретным оператором, но не строит глобально оптимальный план с учётом требований всех операторов одновременно.

Что мы реализовали в CedrusData 417-1

В CedrusData в релиз 417-1, вышедший в мае 2023 года на основе Trino 417, добавили новое cost-based правило расстановки Exchange на базе Cascades. Оно одновременно рассматривает сотни и тысячи вариантов перераспределения данных, генерирует их через Cascades и мемоизацию, а затем выбирает вариант по cost-модели и статистике. Такой подход позволяет находить нестандартные планы, которые сокращают объём сетевых передач.

Режим включался параметром в config.properties:

cedrusdata.optimizer.cascades-enabled=true

Это параметр релиза 417-1. Настройки для конкретной версии CedrusData Engine нужно проверять в актуальной документации.

Показательный пример — запрос q39 из TPC-DS. В нём несколько операторов JOIN и Aggregation, причём у каждого свои требования к распределению данных. Trino выполняет такой запрос через несколько последовательных перераспределений: сначала Exchange по атрибутам [a1, a2, a3, a4], затем ещё один по [a1, a2]. Оптимизатор CedrusData видит, что нескольким операторам подходит партиционирование по общему атрибуту a1, и выполняет одно перераспределение на ранней стадии вместо нескольких.

На бенчмарке релиза CedrusData 417-1 использовался кластер из четырёх узлов по 32 CPU и 96 ГБ RAM, а тесты выполнялись на TPC-DS со scale factor 1000. Сравнивались пять запросов: q2, q8, q39, q49 и q70. Все пять выполнялись быстрее с включённым Cascades-оптимизатором, а максимальный выигрыш показал q39.

Это выборка из пяти запросов, а не полный прогон всех 99 запросов TPC-DS. Точные значения времени вне графика релиза не приводятся. Следующим шагом в релизе заявлялась интеграция Cascades с другими правилами, включая планирование порядка JOIN.

Другие отличия CedrusData Engine от open source Trino не ограничиваются оптимизатором.

Что это значит для пользователей

Запросы с большим числом JOIN, Aggregation и Window могут выполняться быстрее без изменений в SQL. План перераспределения данных между узлами MPP-кластера выбирает оптимизатор.

Заключение

Оптимизатор запросов Trino — многофазная система, в которой реляционное дерево служит общим представлением для всех этапов. Правила IterativeOptimizer работают локально и эвристически, а cost-based подход применяется точечно — прежде всего в ReorderJoins при выборе порядка JOIN. Динамические фильтры переносят часть pushdown из этапа планирования в runtime и сокращают объём данных на probe side ещё до JOIN.

Cascades-оптимизатор, добавленный CedrusData поверх Trino в релизе 417-1, закрывает пробел в расстановке Exchange. Вместо локального выбора для отдельного оператора он ищет план, учитывающий требования к распределению данных сразу у нескольких операторов.

Инженеру, который оптимизирует SQL-запросы, полезно воспринимать план выполнения не как чёрный ящик, а как последовательность объяснимых решений. Разделение оптимизации на этапы становится рабочей моделью для анализа планов, статистики и узких мест запроса.