Microsoft SQL Server

На недавньому заході 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.