Предыстория

Оптимизация оптимизатора — это четвертый этап обработки SQL.,Это также самый важный шаг,Сущность оптимизации оптимизатора основана на Правила оптимизациивыполнить Эквивалентное преобразование реляционной алгебры。

Эквивалентное преобразование реляционной алгебры：Это важная концепция оптимизации запросов к базе данных.,Относится к преобразованию одного выражения реляционной алгебры в другое выражение реляционной алгебры.,Хотя эти два выражения имеют разные формы,Но они имеют одинаковую семантику и вычисляют одинаковые результаты.,Производительность вычислений вновь преобразованного реляционного выражения часто выше, чем у исходного выражения. В Кальците,Эквивалентное преобразование реляционной алгебры — это эквивалентное преобразование дерева планов RelNode.。

Преобразование эквивалента дерева планов RelNode

На данный момент Calcite имеет два типа встроенных оптимизаторов:

• HepPlanner：RBO（Rule-based Optimizer) — это оптимизатор на основе правил, который строит дерево планов в виде ациклического графа, ориентированного на DAG, просматривает и выполняет Правила по порядку. оптимизации
• VolcanoPlanner：CBO（Cost-based Optimizer) оптимизатор, основанный на затратах, на основе Volcano/Cascades. Optimizer Классическая структура оптимизатора реализуется путем поддержания набора эквивалентностей с помощью Memo и использования жадного алгоритма для поиска оптимального решения. Кроме того, эффект оптимизации CBO зависит от двух ключевых факторов: модели затрат (Cost Модель) и Статистика

Тип оптимизатора

Правила оптимизации

Calcite имеет более 200 встроенных Правил оптимизации, которые можно разделить на две категории:

• TransformationRule：для логического планирования Эквивалентное преобразование реляционной алгебры,Например, постоянное складывание, предикат, обрезка столбца и т. д. Преобразование эквивалентности логического плана не гарантирует, что преобразованное дерево планов будет лучше.,его подкатегорииSubstitutionRuleПоддержан набор правил, который определенно будет работать лучше после преобразования.
• ConverterRule：Соглашение о вызовах,Реализуйте преобразование между различными соглашениями,Эквивалентно можно понимать как: реализацию преобразования логического плана в физический план.

На рисунке показано эквивалентное преобразование дерева плана на основе Правил оптимизации:

1. постоянное складывание：Вычисление значения постоянного выражения непосредственно во время оптимизации,Как показано на рисунке 2020+6=2026.,Замените постоянное выражение вычисленным постоянным значением,Уменьшите количество постоянных вычислений во время выполнения запроса.
2. предикат：состояние фильтра（предикат）Рассчитайте и примените заранее, насколько это возможно.,то есть в дереве планов,Сдвиньте оператор Filter как можно ближе к низу дерева.,Уменьшите объем ввода данных для операций верхнего уровня за счет сброса фильтра.
3. Обрезка столбца：Получите только те столбцы, которые действительно необходимы в запросе.,Удалите неиспользуемые столбцы с помощью оператора Project.,тем самым сокращая использование столбцов и обработку данных

Эффект оптимизации

Кальцит, выполняя Правила оптимизации,Реализация эквивалентного преобразования RelNode,Состоит из трёх шагов:

1. Шаблон соответствия правил：на основе RelOptRule#matches суждение Применение Условия и шаблоны правил гарантируют, что к определенному узлу дерева могут быть применены только правила, удовлетворяющие шаблону соответствия, т. е. Внедрить процесс фильтрации правил
2. Применение правил：на основеRelOptRule#onMatch→RelOptRuleCall#transformTo Выполнение правила триггера для достижения эквивалентного преобразования деревьев планов.
3. Эквивалентная конструкция узла：Преобразованное эквивалентное дерево планов сохраняется вRelOptRuleCallсередина,Оптимизатор можно настроить в зависимости от требований реализации.,Создайте соответствующий эквивалент RelNode

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

оптимизатор RBO

На рисунке ниже показан процесс выполнения RBOHepPlanner, который разделен на три этапа:

1. инициализация：ВоляRelNodeПреобразовать вDAGориентированный ациклический граф,в Каждая вершина используется HepRelVertex Представляет и поддерживает связанные дочерние узлы
2. Поиск оптимального дерева плана：ТраверсDAGТриггер последовательно Применение правил（fireRule）,Порядок обхода можно параметризовать на основе HepMatchOrder.
3. Построить оптимальное дерево плана：на основеVisitorрежим сверху вниз ТраверсDAGвершина,Получите соответствующий узел RelNode.,Постройте оптимальное дерево планов на основе конвертированного RelNode.

оптимизатор CBO

Примечание：ДолженCBOОписание процессана основеCalciteВерсияV1.21.0выставка,Отличия от последней версии Calcite

Процесс исполнения

На рисунке ниже показан процесс исполнения оптимизатора CBOVolcanoPlanner, разделенный на три этапа:

1. инициализация：Создайте набор эквивалентности,Пройдите через RelNode, чтобы сгенерировать соответствующий Relset/RelSubset. При регистрации RelSubset,Рассчитайте стоимость узла и добавьте правила в RuleQueue.
2. Поиск оптимального дерева плана：в соответствии сRuleQueueочередь правилсередина Всплывающее окно с условиями соответствияиз Правила Если после применения правил новое дерево планов дешевле, эквивалентное дерево планов перерегистрируется и поддерживается в пространстве поиска. Для выхода из поиска в дереве планов должно быть выполнено любое из следующих условий: (1). Правила, применимые в RuleQueue оптимизациипусто；（2）. СТОИМОСТЬ оптимального дерева плана стабильна и существенно не снижается (3); Тайм-аут поисковой оптимизации
3. Построить оптимальное дерево плана：После выхода из поиска,Пройдите через узлы оптимальной стоимости, поддерживаемые RelSubset.,Построить оптимальное дерево плана

в,оптимизатор CBOна основеRuleQueue (Очередь правил) Правила обслуживания оптимизациинабор,В отличие от правил последовательного сопоставления RBO, сопоставление правил CBO является случайным.。основнойна основеRelSubsetсерединавычислитьизВажность в обратном порядке,Чем выше COST, тем выше важность узла.,Сопоставлению правил будет отдан приоритет.

инициализация

Как показано на картинкевыставкаVolcanoPlannerинициализацияизвыполнитьпроцесс,Для инициации есть два входа исполнения:

• changeTraits изменятьRelNodeфизические свойства,Перейдите по дереву планов RelNode, чтобы зарегистрировать каждый узел.,на основеVolcanoPlanner#addRelToSet Метод генерирует соответствующие RelSet и RelSubset. Если эквивалентное дерево планов уже существует, оно добавляется к соответствующему эквивалентному набору.
• setRoot Убедитесь, что узел AbstractConverter зарегистрирован в плане RelSubset, и этот узел можно использовать для запуска последующих преобразований Соглашения.

В процессе инициализации основная обработка в основном включает в себя:

• Расчет стоимости:Как показано нижефиолетовая рамкапоказано,При регистрации RelSubset,ВоляпозвонюpropagateCostImprovements Метод вычисляет стоимость COST для всех деревьев плана в наборе эквивалентности и независимо поддерживает оптимальное дерево плана с не бесконечной стоимостью и минимальной стоимостью. Помимо расчета стоимости COST, этот процесс также запускает RelNode. Расчет важности, соответствующая важность сохраняется в RuleQueue, используемом для порядка выполнения правил сортировки.
• Правила регистрации:Как показано нижекрасная коробкапоказано,После регистрации RelSubset,на основеfireRulesотинициализацияправилонаборсерединасоответствовать, чтобы удовлетворить Долженузелизправилоребенокнабор,И добавьте подмножество правил в очередь правил RelQueue на основе важности.

Среди них Рел Сет представляет собой набор деревьев планирования, эквивалентных реляционной алгебре.,Прямо сейчасНабор эквивалентных логических деревьев планов；RelSubsetпринадлежатьRelSetребенокнабор,Представляет набор реляционных алгебраических эквивалентных деревьев планов с одинаковыми физическими свойствами.,Прямо сейчасНабор эквивалентных деревьев физического плана。

Поиск оптимального дерева

Как показано на картинкевыставкаVolcanoPlannerПоиск оптимального дерева планаизвыполнитьпроцесс：

1. На основе RuleQueue выведите соответствующий узел, соответствующий Правилам. оптимизации,Применение триггера через VolcanoRuleCall правильно сгенерировать новое эквивалентное дерево плана
2. Зарегистрируйте новое эквивалентное дерево плана на основе метода обеспеченияRegistered. Если стоимость нового дерева плана ниже оптимального дерева плана в соответствующем наборе эквивалентности RelSubset, стоимость родительского узла вычисляется рекурсивно, и дерево плана сохраняется в. пространство поиска заметок.

Планирование преобразования дерева

под ВолякПланирование преобразования дерева图直观извыставкаCBOПроцесс исполнения,ПримерSQL: выберите имя, число от ученика, где имя = 'добавить'

1. инициализация：changeTraitsВоляRelNodeстановитьсяRelSubset,представлять группуфизические свойстватакой жеизлогический план；setRootгарантироватьAbstractConverterРегистрация узла,Поскольку соглашение = НЕТ,В настоящее время цена COST бесконечна.
2. выполнение поиска：на основе Поиск оптимального дерева плана,Наконец, получается дерево плана с оптимальной стоимостью COST.,В настоящее время цена COST ограничена.

CBOПоиск оптимального дерева планаРеализовано на основе жадного алгоритма и нисходящего динамического программирования.,Следуйте оптимальному принципу подструктур динамического программирования.,Локальная оптимальность может в конечном итоге привести к глобальной оптимальности.。поэтому,В области поиска заметок,Вы можете выбрать дочерний узел оптимальной стоимости из RelSubset с одинаковыми физическими атрибутами сверху вниз.,Комбинация дает оптимальное дерево плана.

Процесс построения оптимального дерева плана показан на рисунке ниже: Начиная с корневого узла (Root node)

1. rel#41 Эквивалентная концентрация EnumerableProject Стоимость самая низкая, а соответствующий дочерний узел rel#58
2. rel#58 Эквивалентная концентрация EnumerableFilter Стоимость самая низкая, а соответствующий дочерний узел rel#63
3. rel#63 Эквивалентная концентрация JdbcToEnumerableConverter Стоимость самая низкая, а соответствующий дочерний узел rel#26
4. rel#26 Эквивалентная концентрация JdbcTableScan Стоимость самая низкая, а узел является конечным узлом TableScan.

Статистические метаданные

CalciteСтатистические Ниже показана метаданная система, основанная на RelNode#computeSelfCost Получите текущую цену COST узла, внедрите RelMetadataProvider на основе JaninoRelMetadataProvider Динамически генерируется. Часто используемые Статистические метаданные Обработка звонков：

• Некумулятивная цена COST для RelNode: RelMetadataQuery#getNonCumulativeCost → RelMdPercentageOriginalRows → RelMdPercentageOriginalRows#getNonCumulativeCost → RelNode#computeSelfCost
• Количество строк данных RelNode: RelMdRowCount#getRowCount → RelNode#estimateRowCount
• Максимальное количество строк RelNode: RelMdMaxRowCount#getMaxRowCount
• Статистика RelNode NDV: RelMdDistinctRowCount#getDistinctRowCount
• Сортировка данных RelNode: RelMdCollation#collations
• Тип поля RelNode: RelMdNodeTypes#getNodeTypes
• Определите, является ли поле таблицы уникальным: RelMdColumnUniqueness#areColumnsUnique.

Calling Convention

Соглашение о вызовах: реализация различных преобразований соглашений.,Завершено на этапе оптимизации CBO。Изображение нижевыставкана основеConvertRule转换правило Воляплан дереваотConvention=NONE（Цена бесконечнаinfinite）изLogicalPlanПреобразовать вConvention=ENUMERABLE（Ограниченная цена）из Исполняемый план。

Прыжок

Подвести итог

Оптимизатор запросов — это не только основной модуль проекта Calcite.,Это также основная конструкция всей системы базы данных. Хороший оптимизатор запросов,Может оптимизировать логику плана выполнения SQL.,Обеспечьте выполнение лучше и эффективнее. В этой статье описаны детали реализации модуля оптимизатора Calcite.,В основном включают в себя: Правила оптимизации、оптимизатор Принцип исполнения RBO, оптимизатор Принцип исполнения CBO, Статистические метаданныеждать。 проходить本文可к初步了解Calciteиз Дизайнерское мышление：На основе Правил оптимизации он поддерживает выполнение оптимизации в разных режимах.：RBOвыполняется последовательно,CBO выполняет оптимальный выбор на основе статистической стоимости COST.

Я участвую в последнем конкурсе эссе для специального учебного лагеря Tencent Technology Creation 2024, приходите и разделите со мной приз!