Microsoft SQL Server. Работа с оптимизатором запросов (часть 1)
На недавнем мероприятии SQL Saturday 178, мне задали вопрос, можно ли сделать так, чтобы оптимизатор не прекращал оптимизацию, когда посчитает что уже нашел хороший план или наступит таймаут, а исследовал все альтернативы. Я ответил, что документированных средств нет, либо я о таких не знаю. И это действительно так, однако, возможно есть какие-то недокументированные флаги трассировки, которыми можно влиять на этот процесс. Я решил провести небольшое исследование и в этой заметке расскажу о его результатах.
Забегая вперед, сразу сообщу об итогах исследования, для тех кому не важны технические подробности, а важны выводы. Оказывается, действительно можно сделать так, чтобы оптимизатор продолжал поиски «до упора», но вероятность, что он действительно найдет гораздо более удачный план невелика. Это логично, иначе, если бы оптимизатор очень часто «недооптимизировал» запросы, прекращая поиски раньше положенного, то следовало бы поменять механизм определения того самого момента, когда считается, что искать план дальше не имеет смысла. Между тем, оптимизатор довольно неплохо справляется со своей задачей, а когда не справляется, причина очень часто кроется не в самом оптимизаторе, а в том с чем ему приходится работать (неактуальная статистика, плохо написанный код и т.д.). Хотя, ради справедливости, стоит сказать, что бывают случаи, когда причина в самом оптимизаторе.
Далее, я расскажу о том, как заставить оптимизатор отбросить ограничения и продолжать оптимизацию до конца.
Теория
Основные понятия
Дерево логических операторов — дерево объектов, в котором каждым узлом является логический оператор, соответствующий той или иной операции в запросе. Это дерево — результат того, во что был превращен запрос после того как он попал на сервер и прошел некоторые стадии упрощения и преобразования. Короче говоря, это то с чем начинает работать оптимизатор.
Transformation Rule — правило преобразования. Это объект который содержит в себе методы по преобразованию одних логических операторов в другие логические (или физические) операторы.
Optimization Task — дословно, задача оптимизации, это операция предпринимаемая оптимизатором в процессе поиска плана. Это может быть например, применение правила преобразования к узлу дерева операторов.
Memo — структура в памяти сервера, которая используется для хранения и анализа получаемых в результате преобразований деревьев операторов.
Group — группа эквивалентности, часть структуры Memo, в которой хранятся эквивалентные выражения (операторы), например — Group 1: (A join B) , (B join A).
Group Expression — выражение в группе эквивалентности, например — Group 1: (A join B) , (B join A). (A join B) — одно из выражений группы Group 1.
Timeout — определенное количество задач оптимизации (Optimization Task), которое отводит себе оптимизатор перед тем, как начинает оптимизировать запрос («Я угадаю эту мелодию с 5 нот»!), т.е. некий бюджет на количество преобразований. По мере выполнения преобразований оптимизатор смотрит на этот счетчик, и как только потратил всё отведенное количество — прекращает оптимизацию и выдает тот план, который у него есть на данный момент. При этом, если в SSMS посмотреть на полученный план, выбрать корневой оператор SELECT и посмотреть свойства, то можно увидеть «Reason For Early Termination: Time Out».
Good Enough Plan — достаточно хороший план, это еще одно условие при котором оптимизация прекращается. Происходит это в том случае, если запас преобразований еще есть, но найденный на данном этапе план уже удовлетворяет внутреннему порогу оптимизатора. Это условие, также можно увидеть в свойствах плана в SSMS — «Reason For Early Termination: Good Enough Plan Found».
Алгоритм генерации альтернатив
Допустим есть запрос:
Соответствующее ему дерево логических операторов выглядит следующим образом:
Дерево копируется в начальное Memo (Copy In):
Теперь, на этом этапе, начинается процесс оптимизации. Начинают применяться правила, генерироваться альтернативы, оцениваться стоимость, достаточно хороший план и таймаут. Укрупнено, алгоритм работы по поиску плана можно представить так:
Optimize Group
- На входе: группа, верхняя граница, требуемые свойства
- Сохранение лучшего плана в memo
Explore Group
- Итеративное исследование каждого выражения
Explore Expression
- Применение правил
- Генерирование альтернативных выражений
- Работа с memo, чтобы избежать повторов (e.g. JoinCommute)
- Битовая карта pattern memory определяет уже примененные правила
Apply Rule
- Предшественник – Потомок
- Привязка предшественников к правилам
- Применение правила
- Сохранение в memo (в том числе новых групп)
- Запуск следующего задания в зависимости от типа потомка
- Логический – Explore Expression
- Физический – Optimize Inputs
Optimize Inputs
- Подсчет наилучшего плана
- Форсирование физических свойств
- Отброс неэффективных ветвей
Все начинается с того, что на вход алгоритму, поступает корневая группа, на вход также поступают требуемые физические свойства, верхняя граница, выше которой (если стоимость превысит порог) не имеет смысла искать план. Поскольку план должен содержать физические операторы, то группа должна содержать физические операторы. Рекурсивно вызывается оптимизация дочерних групп. В процессе оптимизации каждой из групп происходит исследование группы (Explore Group), если группа содержит несколько выражений, то исследование группы заключается в итеративном вызове (Explore Expression). На этапе Explore Expression определяются правила, которые могут быть применены к этому выражению, ведется учет повторов, чтобы избежать одних и тех же преобразований, идет применение правил (Apply Rule). Важный момент: правила применяются не все подряд. А только те, что соответствуют некоторому шаблону для конкретного выражения группы (оператора). Правило применяется к выражению (предшественник) и генерирует новое выражение (потомок). В зависимости от потомка, запускается либо задача Explore Expression, если потомок логический оператор. Либо Optimize Inputs, если потомок физический оператор. Либо Optimize Group, если применение правила породило потомка, который не входит ни в какую существующую группу, а образует новую. Этап Optimize Inputs в свою очередь обеспечивает стратегию отброса (Discarding) неэффективных ветвей плана (Cost Based Pruning Factor), подсчет наилучшего плана и форсирование физических свойств (например, если у нас есть Merge join, который требует отсортированного входа, то будет форсирована операция сортировки).
В результате всего этого, в Memo сохраняются физические операторы, реализующие наиболее эффективный план.
После этого наиболее эффективный план копируется из Memo (Copy Out):
На протяжении всего этого процесса активно применяются две следующие концепции: Timeout, Cost Based Pruning Factor, Discarding. Именно они влияют на то, как будет выбран план, и именно на них можно повлиять флагами трассировки.
Практика
Перейдем от теории к практике.
Отключаем Timeout
Первый флаг трассировки: 8780. Он позволяет «отключить» Timeout.
Для демонстрации, я буду использовать ту же простую БД opt, что использую в примерах почти всегда. Для удобства приведу еще раз скрипт ее генерации:
Теперь, давайте выполним следующий умозрительный запрос, для того, чтобы получить Timeout.
Примечание: Для просмотра информации я использую недокументированный флаг трассировки 8675, который выводит информацию по стадиям оптимизации. Я уже неоднократно использовал этот флаг в рассказах про оптимизатор. Например, тут Оптимизатор (ч.3): Optimization: Full Optimization: Search 0.