Заметки Дмитрия Пилюгина о Microsoft SQL Server 

Twitter RSS
Home SQL Server (все заметки) Оптимизатор без границ (ч.1)
formats

Оптимизатор без границ (ч.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».

Алгоритм генерации альтернатив

Допустим есть запрос:

select * from t2 join t1 on t1.a = t2.b;

Соответствующее ему дерево логических операторов выглядит следующим образом:

Дерево копируется в начальное 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, что использую в примерах почти всегда.
Для удобства приведу еще раз скрипт ее генерации:

Spoiler for Create DB opt

use master;
go
if db_id('opt') is not null drop database opt;
go
create database opt;
go
use opt;
go
create table dbo.t1(a int primary key, b int not null, c int not null check (c between 1 and 50), d char(100) not null default(''));
create table dbo.t2(b int primary key, c int, d char(10));
create table dbo.t3(c int primary key);
create table dbo.t4(d int primary key);
go
insert dbo.t1(a,b,c) select number, number%100+1, number%50+1 from master..spt_values where type = 'p' and number between 1 and 1000;
insert dbo.t2(b,c) select number, number%100+1 from master..spt_values where type = 'p' and number between 1 and 1000;
insert dbo.t3(c) select number from master..spt_values where type = 'p' and number between 1 and 1000;
insert dbo.t4 values (1),(2),(3),(4),(5);
delete top(9) from t1 where t1.b = 1;
go
alter table dbo.t1 add constraint fk_t2_b foreign key (b) references dbo.t2(b);
go
create index ix_b on dbo.t1(b);
go
update statistics dbo.t1 with fullscan;
update statistics dbo.t2 with fullscan;
update statistics dbo.t3 with fullscan;
update statistics dbo.t4 with fullscan;
go
--drop table t1,t2,t3,t4

Теперь, давайте выполним следующий умозрительный запрос, для того, чтобы получить Timeout.

Примечание: Для просмотра информации я использую недокументированный флаг трассировки 8675, который выводит информацию по стадиям оптимизации. Я уже неоднократно использовал этот флаг в рассказах про оптимизатор. Например, тут Оптимизатор (ч.3): Optimization: Full Optimization: Search 0.

set showplan_xml on
go
with cte as(select t1.* from t1 join t2 on t1.a = t2.b where t1.b > 1)
select 
	t1.a, t1.b, t1.c,
	cte.b, cte2.c
from 
	t1 
	join cte on t1.a = cte.b 
	join cte cte2 on t1.c = cte2.b 
option 
(
	recompile
	,querytraceon 3604
	,querytraceon 8675
)
go
set showplan_xml off
go

В результате выполнения в SSMS, на вкладке Messages можно увидеть следующее:

А в плане:

Т.е. в данном случае, работа оптимизатора прекратилась раньше времени из-за Timeout-а.

Теперь, выполним тот же самый запрос с флагом 8780.

set showplan_xml on
go
with cte as(select t1.* from t1 join t2 on t1.a = t2.b where t1.b > 1)
select 
	t1.a, t1.b, t1.c,
	cte.b, cte2.c
from 
	t1 
	join cte on t1.a = cte.b 
	join cte cte2 on t1.c = cte2.b 
option 
(
	recompile
	,querytraceon 3604
	,querytraceon 8675
	,querytraceon 8780
)
go
set showplan_xml off
go

Посмотрим на информацию по оптимизации:

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

Посмотрим, что стало причиной прекращения оптимизации в данном случае:

Как видно из свойств плана, причиной стало то, что по мнению оптимизатора найден достаточно хороший план.

Тепрь, давайте посмотрим на сами планы.
Тут я использую Sql Sentry Plan Explorer, т.к. он, отображает планы в более компактном виде и удобнее для блога.
Итак!
Timeout plan

No timeout: Good enough plan

Как видно из планов, если оптимизация продолжается, то оптимизатор строит план с использованием Merge Join, а не Hash Join.
Если выполнить оба запроса в одном окне и посмотреть на относительную стоимость, то мы увидим:

Я думаю, многие знают, что относительные проценты по стоимости, показывают только дешевизну одного плана, в сравнении с другим. В то время как к реальному времени исполнения это может не иметь никакого отношения. Может быть так, что план потребляющий много ресурсов и имеющий большую стоимость выполнится быстрее. Но может быть что план потребляющий меньше ресурсов выполнится быстрее, потому что более эффективен.
На моей практике, эти проценты больше путают людей, чем помогают. Чтобы не путаться нужно уяснить, что у человека рассматривающего запрос и у сервера разные цели. Серверу необходимо выполнить запрос с наименьшим потреблением ресурсов. Человеку оптимизирующему запрос — наиболее быстро. Но разница в том, что сервер беспокоится не об одном конкретном запросе, а о нагрузке в целом. Иначе, можно было бы отдать все ресурсы одному запросу, а всех остальных заставить ждать, что сказалось бы негативно на производительности в целом.
По этому, давайте посмотрим на время, которое выполняется тот и другой запрос, включив сбор статистики.
Также, давайте исключим из измерения передачу на клиента, записывая результаты в переменные.
Итак, запрос:

print('-------------------------------------------------------------');
print('Timeout:');
set statistics time, io on;
go
declare @v1 int,@v2 int,@v3 int,@v4 int,@v5 int,@v6 int,@v7 int,@v8 int;
with cte as(select t1.* from t1 join t2 on t1.a = t2.b where t1.b > 1)
select 
	@v1=t1.a, @v2=t1.b, @v3=t1.c,
	@v4=cte.b, @v5=cte2.c
from 
	t1 
	join cte on t1.a = cte.b 
	join cte cte2 on t1.c = cte2.b
option (recompile);
go
set statistics time, io off;
print('-------------------------------------------------------------')
print('No timeout - Good Enough:');
go
set statistics time, io on;
go
declare @v1 int,@v2 int,@v3 int,@v4 int,@v5 int,@v6 int,@v7 int,@v8 int;
with cte as(select t1.* from t1 join t2 on t1.a = t2.b where t1.b > 1)
select 
	@v1=t1.a, @v2=t1.b, @v3=t1.c,
	@v4=cte.b, @v5=cte2.c
from 
	t1 
	join cte on t1.a = cte.b 
	join cte cte2 on t1.c = cte2.b 
option (recompile,querytraceon 8780);
go
set statistics time, io off;
go

Результаты:

Чтения: 52 против 38. Время: 7 против 6.
Выгоднее? Скорее нет чем да. Все на уровне погрешности. Повторив тест несколько раз, можно увидеть время различающееся в обратную сторону.
Если мы посмотрим на свойства плана обоих запросов, то мы увидим:

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

Есть еще один интересный вопрос. Неужели одним простым трейс флагом возможно полностью исключить таймаут, и надолго занять ресурсы сервера для оптимизации одного запроса?
Оказывается нет.

Проведя пару бессонных ночей, я нашел магическое число, которое устанавливается в качестве таймаута при включенном TF 8780. Это константа, зашитая внутри сервера — 3 072 000 преобразований. Именно такой таймаут устанавливается при включении флага трассировки 8780.
Насколько это много? На мой взгляд очень много, но зависит от того как вычисляется таймаут.
Точных сведений как он вычисляется пока к сожалению нет. Из моих эмпирических наблюдений — это зависит от кардинальности и количества соединений.
Можно ли написать запрос, который превысит максимальный, псевдо-бесконечный таймаут?
Да, и вот например:

set showplan_xml on
go
declare @v1 int,@v2 int,@v3 int,@v4 int,@v5 int,@v6 int,@v7 int,@v8 int;
with cte as(select t1.* from t1 join t2 on t1.a = t2.b where t1.b > 1)
select 
	@v1=t1.a, @v2=t1.b, @v3=t1.c,
	@v4=cte.b, @v5=cte2.c
from 
	t1 
	join cte on t1.a = cte.b 
	join cte cte2 on t1.c = cte2.b 
	join cte cte3 on t1.c = cte3.b
	join cte cte4 on t1.c = cte4.b	
	join cte cte5 on t1.c = cte5.b
	join cte cte6 on t1.c = cte6.b
	join cte cte7 on t1.c = cte7.b	
option 
(
	recompile
	,querytraceon 3604
	,querytraceon 8675
	,querytraceon 8780
	,querytraceon 8671
)
--3072000
go
set showplan_xml off
go

Результат:

Минуточку! Мне одному кажется или появился какой-то новый флаг трассировки 8671?

Да. Этот флаг трассировки отключает еще одну концепцию, которая была названа в разделе «Теория».
И я поделюсь своими наблюдениями относительно него и расскажу, что по моему мнению он делает, в следующей части! Ведь пока, «отключен» только «Timeout».

Примечание: Есть еще один флаг, 8788, он тоже «отключает» Timeout. Пока я не смог докопаться до сути, чем он отличается от 8780, единственное что смог выяснить это то, что он проверяется уже после того как проверен 8780 по этому, я буду использовать тот что проверяется первым.

Представленное здесь относится к версиям 2008R2 rtm/sp2, 2012 rtm.

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

 
Теги:, , ,

2 комментария

  1. Спасибо, обязательно поизучаю!

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Анти-спам: введите результат (цифрами) *