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

Twitter RSS
Home SQL Server (все заметки) Оптимизатор (ч.1): Введение, Optimization: Simplification
formats

Оптимизатор (ч.1): Введение, Optimization: Simplification

Введение

В этом разделе:
— обзор;
— упрощение, исключение противоречий и лишних соединений;
— просмотр дерева логических операций;

В данной заметке рассматриваются некоторые механизмы работы оптимизатора. Она будет интересна тем, кто хочет больше узнать о процессе преобразования запроса в план запроса, который и будет передан серверу на выполнение.
Многие средства, используемые в заметке — недокументированны, по этому, ни в коем случае не рекомендуется применять их на «боевых» серверах. Также, если вы хотите выполнять приведенные в заметке запросы, то рекомендуется версия сервера для экспериментов «Microsoft SQL Server 2008 R2 (RTM) — 10.50.1600», иначе результат может отличаться.
Итак, приступим.

Процесс оптимизации состоит из следующих шагов.
1. Parsing
2. Binding
3. Optimization
3.1 Simplification
3.2 Trivial Plan Optimization
3.3 Full Optimization
3.3.1 Search 0
3.3.2 Search 1
3.3.3 Search 2
4. Execution

Parsing – на данном этапе производится разбор текста запроса, проверка синтаксиса и построение дерева логических операторов. На выходе из данного этапа оптимизатор получает parsed tree.

Binding – на этапе связывания, производится разрешение имен, проверка на существование таблиц, колонок и других объектов и сопоставление каждого объекта дерева с реальным объектом системного каталога.

Optimization: Simplification – этап упрощения дерева. Он включает в себя следующие функции:
— разворачивание подзапросов в соединения (тех, что возможно);
— удаление излишних соединений;
— фильтры из where «пропихиваются» вниз по дереву, чтобы обеспечить раннее фильтрование;
— выявляются и исключаются противоречия.
На выходе из этой стадии получается упрощенное дерево логических операторов.

Optimization: Trivial Plan Optimization – поиск тривиального плана. Если запрос может быть решен единственным или очевидно единственно лучшим способом, то значит, запрос удовлетворяет условию тривиального плана. На данном этапе не используются решения на основе статистик, стоимости и т.д. Используется только информация о схеме БД (хотя это не совсем так и мы посмотри на это позже). На каждом этапе, начиная с этого, оптимизация может быть завершена, если найден достаточно хороший план, удовлетворяющий внутренним порогам оптимизатора.

Optimization: Full Optimization: Search 0 — эту стадию также называют transaction processing – она преследует такую же цель, как и поиск тривиального плана, найти хороший план за минимальное время. На этом этапе, оптимизатор, на основе эвристик, генерирует начальные наборы возможных вариантов соединения, начиная с соединения наиболее мелких (или хорошо отфильтрованных на ранней стадии) таблиц. Этот порядок, как правило, единственный, используемый на данном этапе. Если после этой стадии достаточно хороший план не найден, то управление переходит к следующей стадии. Данная стадия может быть пропущена, и оптимизатор сразу может перейти к стадии 1, если запрос не удовлетворяет определенным условиям.

Optimization: Full Optimization: Search 1 — эта стадия так же известна как Quick Plan. На данном этапе используются дополнительные правила преобразования и некоторые возможные перестановки вариантов соединения. Если после генерации плана на этой стадии, план все еще не достаточно хорош, то данная стадия повторяется с целью поиска параллельного плана. После чего два плана сравниваются, и для оценки выбирается лучший из них. Если этот лучший план все еще не проходит внутренние пороги оптимизатора, то управление переходит к следующей стадии.

Optimization: Full Optimization: Search 2 — эта стадия известна как Full. Самая последняя стадия, а значит, на ней, план должен быть получен в любом случае, даже если он кажется оптимизатору все еще недостаточно хорошим. Эта стадия используется для сложных и очень сложных запросов.
Создадим на тестовом сервере, тестовую БД и таблицы (здесь и далее я не буду указывать схему, подразумевая, что все объекты находятся в схеме dbo).

create database opt;
go
use opt;
go
create table t1(a int primary key, b int not null, c int check (c between 1 and 50));
create table t2(b int primary key, c int, d char(10));
create table t3(c int primary key);
go
insert into 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 into t2(b,c) select number, number%100+1 from master..spt_values where type = 'p' and number between 1 and 1000;
insert into t3(c) select number from master..spt_values where type = 'p' and number between 1 and 1000;
go
alter table t1 add constraint fk_t2_b foreign key (b) references t2(b);

Теперь, давайте рассмотрим каждую стадию Optimization более подробно. По мере того, как мы будем узнавать новые средства исследования, мы будем возвращаться к запросам предыдущей стадии для подтверждения выводов.
Итак, приступим!

Optimization: Simplification

Посмотрим на эту фазу более детально. Включим опцию Include Actual Plan и выполним следующий запрос:

select
	t1.b,
	t1.c
from
	t1
	join t2 on t1.b = t2.b
	outer apply (select c from t3 where c = 1) t3
where
	t1.a = 200 and
	t1.c between 1 and 50
option (recompile)

Что мы можем ожидать в плане, если рассуждать логически. Во-первых, соединение таблиц t1 и t2, по условию равенства столбцов t1.b = t2.b, во-вторых, для полученного результата выполнение подзапроса с outer apply для каждой строки, после чего фильтрацию по предикатам t1.a = 200 и t1.c between 1 and 50.
Но вместо этого мы видим:

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

Начнем с соединения таблицы t2. Если мы посмотрим на запрос, то нигде не увидим, чтобы в результатах требовалась хоть одна колонка из t2. Но гипотетически таблица t2 все еще может влиять на результат запроса, например, уменьшив или увеличив число строк, за счет условия соединения. Однако, вспомним, как мы определили таблицу t1, столбец b там определен как b int not null, т.е. в нем обязательно должно содержаться какое-то значение, а, следовательно, при соединении по нему, результирующее число строк не может уменьшиться (если нет дополнительных фильтров в where, конечно, но у нас их нет). Но может быть оно может увеличиться? Но вспомним, что столбец t2.b определен как primary key, который содержит только уникальные значения. Так же вспомним, что за счет ограничения внешнего ключа fk_t2_b, в таблице t1 в столбце b не могут появляться никакие другие значения, кроме как из таблицы t2. Что мы получаем в итоге, в результирующем запросе столбцов из t2 нет, в условии соединения таблица t2 ни на что не влияет, т.к. не может ни добавить, ни удалить строк, а значит, можно ее исключить!

Теперь разберемся с apply. Т.к. мы используем outer apply, а не cross apply, то количество строк не может уменьшиться, даже если подзапрос select c from t3 where c = 1 не найдет ни одной строки для условия c = 1. Могут ли строки быть добавлены, если подзапрос вернет более одного значения? Нет, т.к. у нас условие строгого равенства, а по полю t3.c у нас есть первичный ключ, а значит, будет выбрана максимум одна строка. Итак, мы получаем похожу ситуацию, ссылок на колонки таблицы t3 в итоговом выражении select нет, операция apply не влияет на количество строк в результирующем наборе, а значит можно ее исключить вовсе!

Теперь переходим к секции where. Посмотрим на предикат t1.c between 1 and 50. Почему мы не видим этого сравнения в плане? Дело в том, что если вспомнить, то мы при определении таблицы t1 задали ограничение c int check (c between 1 and 50), исходя из него, в этом столбце вообще не могут содержаться другие значения, так зачем же еще раз это проверять? По этому, это условие исключается из плана. Более того, если вы измените в запросе условие, например, на t1.c between 100 and 150, то у вас план примет и вовсе такой вид:

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

Перейдем к следующему условию, t1.a = 200, почему мы не видим оператор Filter? Здесь, дело в том, что оптимизатор как бы «пропихивает» этот предикат, на более раннюю стадию (до выполнения соединения), на стадию выбора строк из таблицы t1. Действительно, зачем соединять все строки, а затем фильтровать, если можно сразу выбрать для соединения только нужные, при помощи индекса. Этот прием известен как predicate pushdown.

Что в итоге. В итоге остается единственная операция, выполнить поиск нужных данных в кластерном индексе, причем, это единственная самая лучшая стратегия применимая в данном случае, а значит, план удовлетворяет условиям trivial plan, и оптимизация на этом заканчивается.

К этапу поиск тривиального плана мы вернемся чуть позже, а пока взглянем на другой запрос.

select
	t1.b,
	t1.c,
	d = (select min(c) from t3 where t1.c = t3.c)
from
	t1
option (recompile)

Что бы мы могли ожидать в этом случае? В этом случае можно было бы ожидать просмотр таблицы t1, после чего, для каждой найденной строки выполнение подзапроса к таблице t3 с агрегацией. Что мы видим в итоге:

В итоге, мы видим, что было выполнено сканирование всей таблицы t3, причем обратите внимание, сделано это всего 1 раз. После чего результаты для обоих таблиц были объединены. Т.е. оптимизатор сообразил, что не нужно выполнять одно и то же 1000 раз, можно заранее вычислить результат и соединить с таблицей t1, т.е. он «раскрыл» наш подзапрос (unnest sub query).

Теперь, добавим всего одно слово, которое не изменит результат и логику, и снова взглянем на план

select
	t1.b,
	t1.c,
	d = (select top(1) min(c) from t3 where t1.c = t3.c)
from
	t1
option (recompile)

Тут мы видим, что план кардинальным образом поменялся. Теперь, действительно выполняется просмотр таблицы t3 и для каждой полученной строки (в данном случае у нас 1000 строк) выполняется поиск по индексу в таблице t3, после чего агрегирование и выбор одной строки. Все это происходит 1000 раз. Т.е. запрос, не был развернут, а остался подзапросом. Почему так?

Дело в том, что оптимизатор не склонен выполнять операцию unnest для подзапросов с top. Об этой особенности знают и используют ее при написании t-sql кода, об этом использовании также знают и разработчики сиквел сервера, по этому, пока не спешат ее менять, но в будущих версиях от таких изменений никто не застрахован.
Напоследок, маленькая ремарка по производительности. Я думаю, вы уже догадались, но все же, приведу количество чтений и сравнительную стоимость планов для обоих запросов.

И количество чтений соответственно

(1000 row(s) affected)
Table 't1'. Scan count 1, logical reads 5, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 't3'. Scan count 1, logical reads 3, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
(1 row(s) affected)

(1000 row(s) affected)
Table 't3'. Scan count 0, logical reads 2000, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 't1'. Scan count 1, logical reads 5, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
(1 row(s) affected)

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

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

select
	t1.b,
	t1.c
from
	t1
	join t2 on t1.b = t2.b
	outer apply (select c from t3 where c = 1) t3
where
	t1.a = 200 and
	t1.c between 1 and 50
option (recompile, querytraceon 3604, querytraceon 8606)

Далее переключимся на вкладку Messages и мы увидим очень интересную картину. Для удобства я разбил вывод служебной информации на три картинки с пояснениями, а некоторую часть опустил.
Итак, вот что мы увидим:

Следующая фаза, упрощенное дерево:

На этом этапе мы видим, что был полностью исключен оператор apply и обращение к таблице t3, а так же предикат t1.c between 1 and 50. Но появился новый логически оператор, который проверяет, что значения в колонке c не равны null. Почему? Потому, что мы определили для колонки диапазон от 1 до 50, но сама колонка у нас nullable, и следовательно, хоть и не имеет смысла проверять диапазон, т.к. он обеспечивается ограничением check (c between 1 and 50), но этот предикат все еще может повлиять на результирующий набор исключив строки со значением null в колонке c. Если бы мы вначале определили бы c как not null – эта ветка бы также исчезла полностью. Вы можете это сами проверить, переопределив эту колонку как not null.
На этом этапе по-прежнему осталось «лишнее» соединение с таблицей t2.

Переходим к следующему этапу Join-Collapse, исключению лишних соединений.

 

На этом этапе мы избавились и от таблицы t2. Теперь, все что у нас осталось в дереве логических операторов, это получение данных из таблицы t1, сравнение с константной 200 и проверка колонки c на not null.

На этом, в нашем примере, этап упрощения завершается.
Ок, мы многое увидели, но вопросы еще остались, первое — как именно оптимизатор «догадался» применить все эти преобразования, и второе – все-таки, execution engine оперирует не логическим деревом, а значит, это не конечный этап и дальше тоже что-то происходит, где, когда и как происходит преобразование логического дерева в физические операторы. Ответы на эти вопросы, я постараюсь дать в следующих разделах посвященных дальнейшей оптимизации.

 

 

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

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

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