Всем привет! В компании Querify Labs мы создаем компоненты СУБД, включая оптимизаторы SQL-запросов.

Любой SQL-запрос может быть выполнен множеством способов. Задача оптимизатора - найти эффективный план выполнения запроса.

В этой статье мы обсудим rule-based оптимизацию - популярную архитектуру оптимизатора, в котором планирование запроса разбито на последовательность атомарных трансформации. Мы рассмотрим особенности реализации данного подхода в Apache Calcite, Presto, и CockroachDB.

Трансформации

Задача оптимизатора - сгенерировать набор альтернативных планов, и выбрать из них оптимальный. Решение об оптимальности может быть эвристическим, либо же основанным на стоимости операторов (cost-based). Модель стоимости зависит от задачи, например: минимизация времени выполнения, минимизация денежных расходов, и т.д. Больше узнать о cost-based оптимизации можно в наших статьях: раз, два.

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

Будучи разработчиком оптимизатора, вы можете разработать десятки и сотни трансформаций. Например, вы можете переставлять операторы местами, менять порядок join-ов, переписывать подзапросы на последовательность более простых операторов, и т.д.

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

Планирование порядка join-ов с помощью динамического программирования

Другие трансформации являются более изолированными, и затрагивают лишь один или несколько соседних операторов. Например, трансформация, которая перемещает фильтр под агрегат, работает только с двумя этими операторами, и не требует глобального контекста.

Трансформация, которая меняет местами фильтр и агрегат

Правила

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

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

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

Такой подход имеет следующие преимущества по сравнению с монолитным оптимизатором:

  • Разработчик может создавать, изменять и тестировать конкретное правило независимо от других правил. Это уменьшает время разработки и повышает качество кода.

  • Правила могут быть абстрагированы от алгоритма планирования. Это позволяет разработчикам разбивать процесс оптимизации на отдельные фазы, каждая из которых может работать с собственным набором правил и алгоритмом планирования. Так, Apache Flink имеет более десяти фаз оптимизации.

С другой стороны, rule-based оптимизаторы не могут эффективно решать ряд важных задач:

  • Shanbhag et al. показали, что перебор допустимых порядков join-ов с помощью rule-based оптимизации требует больше вычислительных ресурсов, чем перебор с помощью dynamic programming.

  • Некоторые планировщики стремятся учитывать сложные зависимости между операторами. Например, для использования merge join вам может потребоваться сначала выбрать подходящие сортированные реализации для произвольного числа промежуточных дочерних операторов. Правила не могут справиться с этой задачей без полного перебора всех допустимых комбинаций операторов, число которых очень велико.

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

Рассмотрим особенности использования rule-based оптимизации в продуктах Apache Calcite, Presto, and CockroachDB.

Apache Calcite

Apache Calcite это фреймворк для построения query-движков. Одним из его ключевых компонентов является оптимизатор SQL-запросов, состоящий из двух планировщиков, и большой библиотеки правил.

HepPlanner это итеративный планировщик, который последовательно применяет правила к текущему плану до тех пор, пока существуют последующие трансформации.

VolcanoPlanner это cost-based планировщик, который аккумулирует множество эквивалентных планов в единой структуре данных MEMO, после чего выбирает наиболее дешевый план на основе стоимости отдельных операторов. В последних версиях Apache Calcite была добавлена возможность планирования с применением алгоритма Cascades.

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

class CustomRule extends RelOptRule {
    new CustomRule() {
        super(pattern_for_the_rule);
    }
    
    void onMatch(RelOptRuleCall call) {
        RelNode equivalentNode = ...;
        
        // Register the new equivalent node.
        call.transformTo(equivalentNode);
    }
}

Рассмотрим правила оптимизации порядка join-ов. Для генерации всех возможных bushy-деревьев join-ов можно использовать пару правил JoinCommuteRule и JoinAssociateRule совместно с VolcanoPlanner. Эти правила принимают на вход один и два join оператора соответственно, и генерируют по одному новому оператору. Математически доказано, что применение этих двух правил генерирует все возможные порядки join-ов, но делает это достаточно неэффективно. Такой подход к планированию join-ов применен в VoltDB, планировщик которого основан на Apache Calcite.

Планирование порядка join-ов с помощью commute и associate трансформаций

Альтернативно, в Apache Calcite есть набор правил, которые превращают подграф бинарных join-ов в один N-арный join. Так же, существует правило, которое использует эвристики для выбора одного перспективного порядка соединения таблиц для заданного N-арного join-а. Данные правила можно использовать совместно с HepPlanner для итеративного планирования. Такой подход применен в Apache Flink и Dremio, планировщики которых так же основаны на Apache Calcite.

Планирование порядка join-ов с помощью N-арного join оператора

Эти два примера демонстрируют, как rule-based оптимизация может быть использована как для cost-based, так и для эвристического итеративного планирования.

Presto

Presto это распределенный SQL-движок для больших данных. Presto применяет rule-based подход для планирования запросов. В отличие от Apache Calcite, Presto имеет только итеративный, но не cost-based планировщик. Таким образом, Presto не может рассматривать несколько планов запросов одновременно, что серьезно ограничивает пространство поиска. 

interface Rule {
    Pattern getPattern();
    Result apply(T node, ...);
}

Однако, Presto имеет ряд правил, которые оценивают стоимость операторов. Например, правило ReorderJoins генерирует допустимые графы join-ов с помощью dynamic programming, и оценивает их кардинальность для выбора перспективного порядка join-ов.

Следует отметить, что оценка стоимости операторов внутри конкретного правила не эквивалентна полноценной cost-based оптимизации. Тем не менее по утверждению инженеров Starburst (слайд 25), этот подход позволил радикально сократить время исполнения TPC-DS запросов в Presto по сравнению классическим итеративным планированием.

Больше деталей о планировщике Presto можно узнать в нашем блоге.

CockroachDB

CockroachDB это географически распределенная cloud-native реляционная СУБД.

CockroachDB использует cost-based оптимизатор на основе алгоритма Cascades, который использует правила трансформации.

В отличие от Apache Calcite и Presto, CockroachDB не имеет общего интерфейс для правил с многочисленными имплементациями. Вместо этого, был разработан DSL, который описывает паттерн и логику трансформации. Специальный модуль анализирует правила, и генерирует два монолитных планировщика в момент компиляции проекта.

Первый планировщик является итеративным. Его задача - нормализовать план для упрощения последующей cost-based оптимизации. Соответствующие правила называются normalization rules. Примером является NormalizeNestedAnds, которое приводит произвольную последовательность конъюнкций к left-deep форме.

Второй планировщик является cost-based. По аналогии с Apache Calcite, он использует мемоизацию для компактного хранения большого количества альтернативных планов. Соответствующие правила называются exploration rules.

Ниже приведен пример правила, которое генерирует оператор потоковой агрегации. Тело правила ссылается на конкретные методы, которые будут вызваны в процессе работы правила. Это делает DSL достаточно компактным.

[GenerateStreamingGroupBy, Explore]
(GroupBy | DistinctOn | EnsureDistinctOn | UpsertDistinctOn
        | EnsureUpsertDistinctOn
    $input:*
    $aggs:*
    $private:* & (IsCanonicalGroupBy $private)
)
=>
(GenerateStreamingGroupBy (OpName) $input $aggs $private)

Выводы

Rule-based оптимизация является распространенным паттерном, который используют многие современные SQL-оптимизаторы.

Rule-based оптимизация позволяет разбить код планировщика на независимые правила, а так же отделить алгоритмы планирования (итеративные, cost-based) от трансформаций, что значительно облегчает разработку и эволюцию продукта.

Вместе с тем rule-based оптимизация не позволяет эффективно решать ряд важных задач, таких как планирование порядка join-oв, или учет свойств операторов для выбора более эффективных имплементаций. Поэтому практические оптимизаторы комбинируют rule-based оптимизацию с другими подходами, такими как dynamic programming или Cascades.

Подписывайтесь на наш блог, где мы рассказываем про устройство СУБД и распределенных систем. А если вы хотите создавать новые СУБД вместе с нами, не забывайте откликаться на наши вакансии.