Push-based исполнение: от SQL к физическому плану

До сих пор в модуле мы разбирали структуры данных — Vector, DataChunk, физические типы, selection vector. Но эти структуры сами по себе не выполняют запрос. Нужно две вещи: превратить текст SQL в дерево операторов и прогнать через это дерево DataChunk-и. Этот урок — про обе. Сначала путь запроса от строки SQL до исполняемого физического плана, потом — модель исполнения, которой DuckDB прогоняет данные через план.

И здесь у DuckDB есть второе важное архитектурное решение (первое — векторизация). Классические движки тянут данные сверху вниз — pull-модель, итераторы Volcano. DuckDB толкает данные снизу вверх — push-модель.

DataFusion: Query Pipeline от SQL до RecordBatch Разберём весь конвейер: четыре стадии компиляции запроса и push-исполнение.

Путь запроса: четыре стадии

Текст SQL не исполняется напрямую. Между строкой запроса и работающими операторами — четыре стадии преобразования. Каждая берёт результат предыдущей и обогащает его.

Parser

Parser (парсер) превращает текст SQL в синтаксическое дерево по грамматике языка. Он отвечает на вопрос «синтаксически ли корректен запрос»: расставлены ли ключевые слова, сбалансированы ли скобки, на месте ли запятые.

Что важно — парсер не знает ничего о содержимом базы. Он не в курсе, существует ли таблица orders и есть ли в ней колонка amount. Парсер работает только с текстом и грамматикой. Запрос SELECT foo FROM bar пройдёт парсер успешно, даже если ни bar, ни foo не существуют — синтаксически он безупречен. Парсер DuckDB основан на грамматике PostgreSQL, поэтому DuckDB понимает Postgres-совместимый SQL.

Binder

Binder (биндер) — стадия, которая сводит запрос с реальностью базы. Биндер обращается к каталогу (catalog) — внутреннему реестру всех таблиц, колонок, типов, функций — и привязывает (binds) имена из запроса к реальным объектам.

Биндер делает две главные вещи. Первое — разрешение имён: проверяет, что таблица orders существует, что колонка amount в ней есть, что функция sum известна. Именно здесь возникают ошибки вида «table does not exist» или «column not found» — не в парсере, а в биндере. Второе — определение типов: биндер выясняет тип каждого выражения. amount это INTEGER, amount * 1.08 это DOUBLE, результат sum(amount) имеет такой-то тип. Без типов нельзя ни оптимизировать, ни исполнять запрос.

Граница «парсер не знает каталог, биндер знает» — принципиальная. Парсер — про форму, биндер — про смысл. Конструкции friendly SQL вроде COLUMNS() и GROUP BY ALL (модуль 03) разворачиваются именно на стадии биндинга: чтобы развернуть COLUMNS('regex') в список колонок, нужен каталог — а он есть только у биндера.

Logical planner

Logical Planner строит из привязанного дерева логический план — дерево LogicalOperator. Логический план описывает, ЧТО нужно сделать, в терминах реляционной алгебры: просканировать таблицу, отфильтровать, соединить, сгруппировать. Но он не говорит, КАК: «соединить две таблицы» — без указания, каким алгоритмом join.

Optimizer

Optimizer (оптимизатор) берёт логический план и переписывает его в эквивалентный, но более эффективный. Это несколько проходов (passes), каждый делает своё преобразование. Среди них: filter pushdown (продвинуть фильтры как можно ближе к сканированию, чтобы рано отсеять строки), projection pushdown (читать только нужные колонки), выбор порядка соединений (join order), упрощение выражений (например, свёртка констант). Оптимизатор подробно разбирается в отдельном модуле курса; здесь важно его место в конвейере — между логическим и физическим планом.

Physical planner

Physical Planner превращает оптимизированный логический план в физический — дерево PhysicalOperator. Здесь абстрактные операции получают конкретные алгоритмы: логический «join» становится физическим HASH JOIN, логическая «агрегация» — HASH AGGREGATE или другим конкретным алгоритмом. Физический план — это уже исполняемое дерево: именно его прогоняют DataChunk-и.

Pull против push: направление движения данных

Дерево физических операторов построено. Теперь — как через него текут данные. И здесь два принципиально разных подхода.

Классическая модель — pull (тянущая), она же итераторная модель Volcano. Управление идёт сверху вниз. Корневой оператор говорит дочернему «дай мне данные», тот говорит своему дочернему «дай мне данные», запрос-«дай» спускается до самого листа-сканирования. Затем данные поднимаются обратно вверх как ответы на эти запросы. Каждый оператор — итератор с методом «верни следующее». Инициатива у верхнего оператора, он вытягивает данные.

DuckDB использует push (толкающую) модель. Управление идёт снизу вверх. Источник данных (сканирование таблицы) сам берёт инициативу: он читает DataChunk и толкает (pushes) его вверх — передаёт следующему оператору. Тот обрабатывает чанк и толкает результат ещё выше. DataChunk-и движутся снизу вверх по дереву, проталкиваемые источником, а не вытягиваемые корнем.

Почему push лучше для DuckDB

Push-модель выбрана не случайно — у неё есть конкретные преимущества для аналитического векторизованного движка.

Первое — параллелизм. В pull-модели управление переплетено по всему дереву: каждый оператор активно дёргает дочерние. Распараллелить такое дерево трудно — синхронизация нужна повсюду. В push-модели поток данных однонаправленный — снизу вверх. Это сильно упрощает параллельное исполнение: разные DataChunk-и можно толкать через дерево независимо, разными потоками. Параллельной осведомлённости требуют в основном только концы конвейера — источник и приёмник, — а промежуточные операторы просто обрабатывают то, что в них толкнули. На этой модели строится morsel-driven параллелизм DuckDB (отдельный модуль курса).

Второе — естественность для конвейера операторов. Push-модель ложится на понятие pipeline — линейной цепочки операторов от источника до приёмника. Чанк проталкивается через всю цепочку, потом следующий. Меньше накладных расходов на «протокол запросов» между операторами: нет постоянного обмена «дай — на» вверх-вниз, есть однонаправленный поток.

Третье — управление потоком и буферизация. Когда данные толкаются вверх, оператору-приёмнику проще контролировать темп и буферизовать; конвейер естественно делится на стадии в местах, где данные нужно накопить (например, построить хеш-таблицу для join).

Push-модель и векторизация работают в паре. Векторизация определяет, ЧТО движется по дереву — DataChunk-и примерно по 2048 строк. Push-модель определяет, КАК они движутся — проталкиваются снизу вверх источником. Вместе они дают аналитический движок, который и эффективно использует процессор (плотные векторные циклы), и легко масштабируется на много ядер (однонаправленный параллелизуемый поток).

Итог урока. Запрос проходит четыре стадии: Parser (текст в синтаксическое дерево, только синтаксис, без каталога), Binder (разрешение имён по каталогу и определение типов, здесь ловятся ошибки несуществующих таблиц), Logical Planner плюс Optimizer (дерево логических операторов и его переписывание — pushdown, порядок join), Physical Planner (конкретные алгоритмы, исполняемое дерево). По готовому физическому плану DataChunk-и движутся в push-модели — источник толкает их снизу вверх, в отличие от pull-модели Volcano, где корень тянет данные сверху. Push выбран ради параллелизма, естественности конвейера и низких накладных расходов.

Попробуй сам

Задания на наблюдение через EXPLAIN.

1. Выполните EXPLAIN SELECT region, sum(amount) FROM sales GROUP BY region (создав сначала таблицу sales). В выводе вы увидите физический план — дерево физических операторов. Найдите оператор сканирования и оператор агрегации.
2. Сравните EXPLAIN (логический и физический план) и EXPLAIN ANALYZE (с реальными счётчиками выполнения) на одном запросе. Какой из них показывает, сколько строк реально прошло через каждый оператор?
3. Намеренно напишите запрос с несуществующей таблицей (SELECT * FROM no_such_table). На какой из четырёх стадий возникнет ошибка — на парсере или на биндере? Объясните почему.
4. Намеренно напишите синтаксически сломанный запрос (SELECT FROM WHERE). На какой стадии возникнет ошибка? Чем эта ошибка отличается от ошибки из задания 3?
5. Объясните своими словами, почему push-модель проще распараллелить, чем pull-модель Volcano.