Логическое планирование: Plan IR и PlanNode

После семантического анализа у движка есть Analysis — структура запроса с разрешёнными именами и типами. Но Analysis всё ещё близок к SQL: он описывает, что пользователь написал. Чтобы запрос исполнить, нужно описать, что движок будет делать — в терминах операций над данными. Этот переход и есть логическое планирование.

Этот урок — про Plan IR (intermediate representation, промежуточное представление) и его строительный блок — PlanNode. Понять Plan IR критично: это центральное представление запроса, на котором работают оптимизатор и которое затем превращается в распределённый план.

Зачем нужно ещё одно представление

У нас уже было два представления: AST и Analysis. Зачем третье?

AST и Analysis организованы вокруг синтаксиса SQL: у них есть узлы Select, From, Where — потому что так устроен текст запроса. Но синтаксис SQL и порядок операций над данными — не одно и то же. В SQL SELECT пишется первым, а логически выбор столбцов происходит почти последним — после чтения таблицы и фильтрации. SQL декларативен: он описывает результат, а не шаги.

Чтобы исполнить запрос, нужно представление, организованное вокруг операций над данными: прочитать таблицу, отфильтровать строки, соединить с другой таблицей, сгруппировать, посчитать агрегаты. Это представление и есть Plan IR.

Слово «intermediate» — ключевое. Plan IR это промежуточная форма: уже не SQL, ещё не исполнение. Она существует ради того, чтобы её удобно было анализировать и преобразовывать. Именно над Plan IR работает оптимизатор, переписывая план в более эффективный. AST для этого не годится — он завязан на синтаксис; исполнимая форма не годится — она слишком низкоуровневая и распределённая. Plan IR — золотая середина.

PlanNode: строительный блок плана

Логический план — это дерево узлов PlanNode. Каждый PlanNode описывает одну логическую операцию над данными. Узел получает на вход поток строк от своих дочерних узлов и производит выходной поток строк для своего родителя.

Основные виды узлов:

Узлы соединяются в дерево по принципу «потомок поставляет данные родителю». Листья дерева — всегда TableScan (или другие источники строк): данные откуда-то должны начаться. Корень — OutputNode: результат куда-то должен прийти. Между ними — операции, и данные текут снизу вверх, от листьев к корню.

Обратите внимание на порядок снизу вверх. Сначала TableScan читает таблицу, затем FilterNode отсеивает строки, затем ProjectNode оставляет нужные столбцы, затем OutputNode отдаёт результат. Это логический порядок исполнения — и он отличается от порядка слов в SQL, где SELECT пишется первым.

Как SQL отображается в дерево узлов

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

SELECT name
FROM tpch.sf1.customer
WHERE acctbal > 1000

Каждая синтаксическая часть запроса превращается в свой узел:

• FROM tpch.sf1.customer -> TableScan для таблицы customer. Это лист, отсюда начинаются данные.
• WHERE acctbal > 1000 -> FilterNode с предикатом acctbal > 1000. Стоит над TableScan: фильтрует то, что прочитано.
• SELECT name -> ProjectNode, оставляющий столбец name. Стоит над фильтром.
• Отдача результата -> OutputNode — корень.

Дерево читается снизу вверх как программа: «прочитай customer; отбрось строки с acctbal не больше 1000; оставь столбец name; верни результат». Декларативный SQL стал явной последовательностью операций.

Запрос с join даёт дерево с ветвлением. У JoinNode два дочерних узла — по одному на каждый входной поток:

SELECT c.name, o.orderkey
FROM tpch.sf1.customer AS c
JOIN tpch.sf1.orders AS o ON c.custkey = o.custkey

Дерево перестало быть линейной цепочкой — JoinNode свёл две ветви в одну. Так древовидная структура естественно выражает запросы любой сложности: несколько join-ов дают несколько JoinNode, подзапросы дают вложенные поддеревья.

Plan IR как материал для оптимизатора

Главная причина существования Plan IR — это удобный материал для преобразований. Дерево PlanNode легко переписывать: можно заменить поддерево другим поддеревом, переставить узлы местами, удалить лишнее, добавить новое. И при этом смысл запроса (какой результат он даёт) сохраняется, если преобразование корректно.

Именно так работает оптимизатор, которому посвящён следующий урок. Он берёт исходное дерево PlanNode и применяет к нему правила-трансформации, получая эквивалентное, но более эффективное дерево. Например, начальный план может содержать FilterNode высоко над JoinNode — оптимизатор опустит фильтр ниже, ближе к TableScan, чтобы отсеять строки раньше и меньше данных подавать в join. План до и после разный по форме, но даёт тот же результат — это и есть смысл существования отдельного представления Plan IR: его удобно переписывать.

Это объясняет, почему этап логического планирования настолько важен. Plan IR — не просто промежуточный артефакт, а та единственная форма, на которой движок умеет рассуждать об эффективности запроса. Всё, что делает оптимизатор и cost-based optimizer, делается над деревом PlanNode.

Место логического планирования в цикле

Логическое планирование — это переход от «что написал пользователь» к «какие операции над данными выполнить». Декларативный SQL стал деревом операций. Дальше это дерево будет оптимизироваться, а затем разрезаться на распределённые фрагменты — но всё это преобразования одного и того же Plan IR.

Попробуй сам

Логический план виден через EXPLAIN (TYPE LOGICAL). На кластере Trino:

1. Выполните EXPLAIN (TYPE LOGICAL) SELECT name FROM tpch.sf1.customer WHERE acctbal > 1000. В выводе найдите узлы, соответствующие чтению таблицы, фильтру и выбору столбца. Обратите внимание на отступы — они показывают древовидную структуру.
2. Выполните EXPLAIN (TYPE LOGICAL) для запроса с join двух таблиц tpch. Найдите узел join и убедитесь, что у него две входные ветви.
3. Добавьте в запрос GROUP BY и снова посмотрите логический план — найдите узел агрегации.
4. Сформулируйте письменно: чем порядок узлов в дереве плана (снизу вверх) отличается от порядка ключевых слов в тексте SQL, и почему.