Обзор внутренней структуры DuckDB

На этой странице приводится краткое описание внутренней структуры движка DuckDB.

Парсер

Парсер преобразует строку запроса в следующие токены:

• SQLStatement
• QueryNode
• TableRef
• ParsedExpression

Парсер не осведомлен о каталоге или других аспектах базы данных. Он не будет генерировать ошибки, если таблицы не существуют, и не будет разрешать никакие типы столбцов. Он только преобразует строку запроса в набор токенов, как указано.

ParsedExpression

ParsedExpression представляет выражение внутри SQL-запроса. Это может быть, например, ссылка на столбец, оператор сложения или константное значение. Тип ParsedExpression указывает, что он представляет, например, сравнение представлено как ComparisonExpression.

ParsedExpressions не имеют типов, за исключением узлов с явными типами, такими как CAST операторы. Типы для выражений разрешаются в Binder, а не в Parser.

TableRef

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

QueryNode

QueryNode представляет либо (1) SELECT оператор, либо (2) операцию над множествами (например, UNION, INTERSECT или DIFFERENCE).

SQL-оператор

SQLStatement представляет собой полный SQL-оператор. Тип SQL-оператора указывает, какой это оператор (например, StatementType::SELECT представляет SELECT оператор). Одна строка SQL может быть преобразована в несколько SQL-операторов, если исходная строка запроса содержит несколько запросов.

Binder

Binder преобразует все узлы в их связанные эквиваленты. На стадии Binder:

• Таблицы и столбцы разрешаются с использованием каталога
• Разрешаются типы
• Выделяются агрегатные/окна функции

Происходят следующие преобразования:

• SQLStatement → BoundStatement
• QueryNode → BoundQueryNode
• TableRef → BoundTableRef
• ParsedExpression → Expression

Логический планировщик

Логический планировщик создаёт узлы LogicalOperator из связанных операторов. На этом этапе создаётся фактическое логическое дерево запроса.

Оптимизатор

После того, как логический планировщик создал логическое дерево запроса, оптимизаторы выполняют над этим деревом, чтобы создать оптимизированный план запроса. Выполняются следующие оптимизаторы запросов:

• Переписыватель выражений: Упрощает выражения, выполняет свёртку констант
• Подтаскивание фильтров: Подтаскивает фильтры вниз по плану запроса и дублирует фильтры по наборам эквивалентности. Также обрезает поддеревья, которые гарантированно будут пустыми (из-за фильтров, которые статически оцениваются как ложные).
• Оптимизатор порядка соединений: Изменяет порядок соединений с помощью динамического программирования. В частности, используется алгоритм DPccp из статьи Dynamic Programming Strikes Back.
• Общие подвыражения: Извлекает общие подвыражения из узлов проекции и фильтрации, чтобы избежать ненужного дублирования выполнения.
• Переписыватель операторов IN: Переписывает большие статические операторы IN на соединение MARK или INNER JOIN.

Разрешитель связывания столбцов

Разрешитель связывания столбцов преобразует логические BoundColumnRefExpresion узлы, которые ссылаются на столбец определенной таблицы, в BoundReferenceExpression узлы, которые ссылаются на определенный индекс в DataChunks, передаваемых в движок выполнения.

Генератор физического плана

Генератор физического плана преобразует получившееся логическое дерево операторов в дерево PhysicalOperator.

Выполнение

На стадии выполнения физические операторы выполняются для получения результата запроса. DuckDB использует векторизованную модель «сверху вниз», где DataChunks передаются через дерево операторов. Более подробную информацию можно найти в докладе Push-Based Execution in DuckDB.