Виды оптимизаторов: итеративный, основанный на стоимостях и эвристический

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

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

Оптимизатор, основанный на стоимостях. Такой подход состоит в генерации множества планов согласно правилам эквивалентности, просчете для каждого стоимости и выборе плана с минимальной стоимостью. Для сложных запросов число построенных планов может быть огромно. Например, для выражения r1 >< r2 >< … >< rn можно построить (2(n-1))!/(n-1)! планов. (Число перестановок из n).

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

Преобразовать все конъюнкции селекции к последовательности селекций по правилу эквивалентности 1. Этот шаг перемещает селекцию вниз по дереву.

Перенести селекцию как можно ниже по дереву, используя правила эквивалентности 2, 7 и 11.

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

Заменить все операции декартова произведения операциями селекции и соединения по правилу 4а.

Раскрыть и перенести вниз по дереву проекции. Если необходимо создать новые проекции. (Правила 3, 8 и 12).

Установить какие поддеревья могут выполняться по конвейерной обработке.