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

Twitter RSS
Home SQL Server (все заметки) USE HINT и ASSUME_MIN_SELECTIVITY_FOR_FILTER_ESTIMATES
formats

USE HINT и ASSUME_MIN_SELECTIVITY_FOR_FILTER_ESTIMATES

В одной из предыдущих заметок мы говорили о таком механизме как Cardinality Estimator.

Cardinality Estimation, СЕ (оценка кардинальности) – это оценка предполагаемого числа строк, которое будет обработано тем или иным оператором запроса. Оценка – один из ключевых факторов при построении плана запроса. Оценку числа строк осуществляет компонент Cardinality Estimator.

Хинт ASSUME_MIN_SELECTIVITY_FOR_FILTER_ESTIMATES контролирует один из аспектов поведения этого компонента, а именно, оценку комплексных предикатов. На сегодняшний день SQL Server имеет три алгоритма оценки подобных предикатов:

  • оценка по предположению независимости
  • оценка по минимальной селективности
  • оценка по алгоритму exponential backoff

Удобнее всего будет разобрать их на примере.

Допустим, у нас есть таблица для некоторого учета автомобилей, которая содержит атрибуты ID, Марка, Модель и Цвет. В таблице две марки Ford и BMW, для каждой марки есть пять моделей этой марки, каждый автомобиль может быть одного из трех цветов красный, черный или серебристый. Всего в таблице 300 записей. Таблица имеет кластерный индекс по полю ИД и некластерный по полю Brand, они нам не нужны для демонстрации оценок, но позволят избежать тривиальных планов и простой параметризации.

use tempdb;
go
set nocount on;
drop table if exists dbo.Cars;

create table dbo.Cars(CarID int identity primary key, Brand varchar(50), Model varchar(50), Color varchar(50), index ix nonclustered(Brand));
go
insert dbo.Cars (Brand, Model, Color)
select 
	Brand, Model, Color
from
(
	values
		('Ford', 'Focus'),
		('Ford', 'Fiesta'),
		('Ford', 'Explorer'),
		('Ford', 'Transit'),
		('Ford', 'Kuga'),
		('BMW', '1'),
		('BMW', '3'),
		('BMW', '5'),
		('BMW', 'X3'),
		('BMW', 'X5')
) v1 (Brand, Model) cross join(values ('Red'),('Black'), ('Silver')) v2(Color);
go 10

Оценка по предположению независимости

Пусть есть задача, выбрать все форды черного цвета, это комплексный предикат, состоящий из двух простых: Brand = ‘Ford’ и Color = ‘Black’. Оптимизатору, перед выполнением запроса требуется оценить число строк. Он может воспользоваться алгоритмом оценки по предположению независимости. Всего у нас две марки BMW и FORD, какова вероятность, что при выборе одной из них — это будет Ford? Вероятность 50%, т.е. 0.5. Та же логика с цветом три цвета, вероятность 33.3%, т.е. 0.33(3).

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

Тогда, согласно теории вероятностей, вероятность одновременного наступления двух независимых событий равна произведению вероятностей этих событий («Теорема умножения вероятностей для независимых событий»).

Это 0.5*0.33(3). Теперь, чтобы получить оценочное число строк нужно умножить результат на общее число строк в таблице 0.33(3)*0.5*300 ~ 50 строк.

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

select count_big(*) from dbo.Cars where Brand = 'Ford' and Color = 'Black'
option(use hint('FORCE_LEGACY_CARDINALITY_ESTIMATION'));

План запроса:

Как мы видим из плана, наши расчеты оказались верны, более того, они совпадают с реальным числом строк (Actual Number of Rows = Estimated Number of Rows). Конечно, в реальности распределение данных не идеальное и точные совпадения бывают редко, но если значения в колонках действительно независимы, то предположение независимости будет работать приемлемо.

Оценка по минимальной селективности

Теперь, давайте выберем все машины Форд Фокус. Это значит Brand = ‘Ford’ и Model = ‘Focus’. Если мы применим такую же логику, как и в прошлый раз мы получим. Селективность по колонке Brand также 0.5. По колонке Model 0.1, т.к. у нас всего 10 разных моделей, вероятность, что одна из 10 будет Фокус, равна 10%. Если мы перемножим вероятности и умножим на число строк мы получим 0.5*0.1*300 = 15 строк. Давайте проверим.

select count_big(*) from dbo.Cars where Brand = 'Ford' and Model = 'Focus'
option(use hint('FORCE_LEGACY_CARDINALITY_ESTIMATION'));

 

План запроса:

Мы видим, что расчеты по формуле совпали с тем, что рассчитал сервер – 15 строк, но это в два раза отличается от действительного числа строк – 30.

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

Если же в условии участвует три предиката и более, то часто бывает, что простое перемножение их вероятностей дает настолько малую величину, что оптимизатор округляет оценку до 1 строки, тогда как в реальности строк больше на несколько порядков. В таком случае план получается очень не оптимальным, выбирается неправильный тип (как правило, Nested Loops) и порядок соединений (как правило, с большим сканированием на внутренней стороне) поэтому все работает медленно.

В данном случае, ошибка оценки в том, что предположение независимости применять было нельзя, поскольку данные в столбцах Модель и Марка зависимы (определенные модели бывают только у определённой марки). Мы считали, что у нас 10 разных моделей, в то время как для марки Форд, всего 5 разных моделей. Не существует модели Ford X5 или Ford X3, т.е. если мы ограничили по марке нам не нужно учитывать все модели.

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

У нас есть селективность по марке 0.5 и селективность по модели 0.1, выбираем минимальную, т.е. 0.1 и умножаем на количество строк в таблице, т.е. 300, получаем 0.1*300 = 30 строк. Это и есть тот алгоритм, который форсирует хинт ASSUME_MIN_SELECTIVITY_FOR_FILTER_ESTIMATES и в данном случае, это полностью совпадет с реальностью. Давайте проверим.

select count_big(*) from dbo.Cars where Brand = 'Ford' and Model = 'Focus'
option(use hint('ASSUME_MIN_SELECTIVITY_FOR_FILTER_ESTIMATES'));

План запроса:

Мы видим, что в нашем тестовом примере оценки полностью совпали с реальным числом строк.

Оценка по алгоритму Exponential Backoff

Теперь выполним первый и последний запросы без хинтов и посмотрим на их оценки (выполнение идет под уровнем совместимости 130, SQL Server 2016).

select count_big(*) from dbo.Cars where Brand = 'Ford' and Color = 'Black';
select count_big(*) from dbo.Cars where Brand = 'Ford' and Model = 'Focus';

Планы выполнения:

Вы видите, что в первом случае, оценка чуть-чуть больше 50 реальных строк, во втором чуть меньше реальных 30 строк. Дело в том, что, начиная с 2014 сервера, по умолчанию используется алгоритм Exponential Backoff. Этот алгоритм нечто среднее между первыми двумя. С одной стороны, он не отбрасывает селективности других предикатов, как это делает алгоритм минимальной селективности, с другой не умножает вероятности других предикатов напрямую, а учитывает только их некоторый «вклад». Иными словами, алгоритм исключает как полную зависимость, так и полную независимость и считает, что данные могут быть зависимы в некоторой степени. Эта степень выражается формулой:

S = S0 × S1^(1⁄2) × S2^(1⁄4) × S3^(1⁄8) 

Где S – это общая селективность комплексного предиката, а S0 – S3 селективности отдельных предикатов, начиная с наименьшей из них. Для получения кардинальности, как и ранее, умножаем общую селективность на кардинальность таблицы.

Мы можем проверить эту формулу на наших данных:

select 0.3333333333*sqrt(0.5)*300 -- 70.7106781115837 ~ 70.7107
select 0.1*sqrt(0.5)*300 -- 21.2132034355964 ~ 21.2132

Альтернативные способы изменения алгоритма оценки

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

  SQL Server 2008 — 2012 SQL Server 2014 — 2016
Предположение независимости по умолчанию 9472
Минимальная селективность 4137 9471
Exponential Backoff Н/Д по умолчанию

Заключение

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

Спасибо за чтение. В следующей заметке мы поговорим о другой ситуации в процессе оценки и о хинте ASSUME_JOIN_PREDICATE_DEPENDS_ON_FILTERS.

 

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

  1. Сергей

    Каждый Ваш пост — это небольшое откровение. Спасибо большое за информацию 🙂

  2. Спасибо, Сергей.

  3. Батор

    1. S4 не бывает?
    2. S3^(1⁄8) == sqrt(sqrt(sqrt(S3))) ?

  4. 1. Нет, селективность комплексных предикатов ограничена 4-мя аргументами.
    2. Совершенно верно.

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

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

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