В этой публикации мне бы хотелось вернуться к подсказкам USE HINT, представленным впервые в SQL Server 2016 SP1. Часть из них мы уже рассмотрели в предыдущих статьях, в этой статье мы рассмотрим очередную подсказку – ASSUME_JOIN_PREDICATE_DEPENDS_ON_FILTERS, которая влияет на алгоритм оценки числа строк в соединениях.
В статье мы немного поговорим о теории оценки соединений и рассмотрим пример использования хинта. Далее, при помощи недокументированных флагов трассировки и несложной арифметики, мы посмотрим, чем отличается оценка в случае использования и не использования хинта, а также проверим вычисления на конкретном примере.
Введение
Оценка числа строк в соединении означает, что сервер должен «предсказать» сколько строк будет получено в результате соединения до его фактического выполнения. Это одна из самых сложных задач оптимизации и сложностей здесь несколько.
Во-первых, в реальном мире данные очень разнообразны и имеют разную природу. Например, разные типы, распределения, объемы и т.д. Поэтому, первая сложность заключается в том, чтобы создать математические модели таким образом, чтобы учесть максимальное число факторов реального мира.
Вторая сложность заключается в том, что данные могут соединяться по-разному. Например, столбцы соединения могут быть одного или разных типов, соединение может быть по одному, нескольким или ни одному столбцу, оператор сравнения в соединении может быть равенство, не равенство, like и т.д. Логический тип соединения также может быть разный, например, внутренний или внешний. Все это многообразие факторов порождает еще большее многообразие комбинаций этих факторов.
Третья сложность обусловлена ограничениями статистики в SQL Server, так, мы имеем всего 200 шагов гистограммы, даже если таблица очень большая и 200 шагов не могут описать распределение данных в полном объеме. В SQL Server нет многомерных гистограмм, с помощью которых можно было бы что-то сказать о корреляции данных в разных столбцах между собой. В целом, набор инструментов статистики ограничен количеством строк, векторами плотности и гистограммами.
Четвертая сложность в том, что оптимизатор имеет ограниченные ресурсы на поиск плана и, следовательно, оценку соединения.
Все эти сложности и делают проблему оценки соединения нетривиальной задачей. Вместе с тем, оценка числа строк в соединении — это очень важная задача. От правильной оценки будет зависеть правильный выбор порядка соединений, физический тип соединений, количество памяти для запроса, форма плана и производительность запроса в целом.
Ввиду многообразия описанных выше факторов, невозможно выбрать один алгоритм оценки, использовать его во всех случаях и получать при этом хорошие результаты. Поэтому, модель оценки кардинальности (Cardinality Estimation Model) включает в себя несколько алгоритмов, для разных ситуаций. Эти алгоритмы, начиная с SQL Server 2014, были выделены в отдельные классы внутри сиквел сервера, которые называются «калькуляторами селективности». Вы можете ознакомиться с публикацией Cardinality Estimation Framework 2014, описывающей как это работает.
Существует довольно много вариантов калькуляторов для соединений, которые используются в разных ситуациях, с особенностями работы некоторых из них вы можете познакомиться в статье Join Estimation Internals англоязычной версии этого блога. В данной публикации мы рассмотрим случай, когда оптимизатор должен смоделировать ситуацию, при которой соединяемая таблица или таблицы должны быть отфильтрованы, т.е. запрос имеет базовую форму:
SELECT columns FROM t1 JOIN t2 ON t1.a = t2.a WHERE t1.b = value1 AND t2.b = value2.
Часть условия фильтра выделена жирным шрифтом.
Пример
Рассмотрим вариант такого запроса на примере БД AdventureWorks2016CTP3, SQL Server 2016 SP1-CU1.
Допустим, мы хотим узнать какой сейчас в системе максимальный номер отслеживания курьера для тех заказов, которые сделаны на территории Великобритании и должны отправиться в город Лондон.
Для этого, мы написали запрос, в котором таблицу заказов (SalesOrderHeader) отфильтровали по идентификатору территории (для Великобритании это значение 10). Соединили ее с таблицей адресов по полю адреса доставки заказа и идентификатору адреса, отфильтровали адреса по городу Лондон и соединили все это с номерами отслеживания курьеров по идентификатору заказа. После этого взяли максимальный номер.
Получился следующий запрос:
select m = max(ot.CarrierTrackingNumber) from Sales.SalesOrderHeader soh join Person.Address a on soh.ShipToAddressID = a.AddressID join Sales.OrderTracking ot on soh.SalesOrderID = ot.SalesOrderID where soh.TerritoryID = 10 and a.City = 'London' option (maxdop 1);
Примечание: Я добавил подсказку MAXDOP 1, чтобы сохранить максимально простую форму плана в примерах. Забегая вперед, скажу, что, если ее убрать, оценки, о которых мы будем говорить ниже – не изменятся.
Давайте выполним его и посмотрим на план запроса.
Вы можете видеть сильную недооценку строк в соединении Hash Join, оценочное число строк равно 73.0711, реальное 756, т.е. отличие примерно в 10 раз. Из-за того, что оптимизатор ожидал небольшое число строк, он счел выгодным использовать поиск по некластерному индексу с операцией Key Lookup.
Теперь выполним этот же запрос с подсказкой ASSUME_JOIN_PREDICATE_DEPENDS_ON_FILTERS.
select m = max(ot.CarrierTrackingNumber) from Sales.SalesOrderHeader soh join Person.Address a on soh.ShipToAddressID = a.AddressID join Sales.OrderTracking ot on soh.SalesOrderID = ot.SalesOrderID where soh.TerritoryID = 10 and a.City = 'London' option (maxdop 1, use hint('ASSUME_JOIN_PREDICATE_DEPENDS_ON_FILTERS'))
Вы видите, что на этот раз план другой.
Так получилось из-за того, что соединение таблиц SalesOrderHeader и Address теперь имеет другую оценку, оценочное число строк равно 468.584, что больше предыдущего (73.0711) и ближе к реальному числу строк 756.
Если вы выполните оба запроса с включенным сбором статистики IO, то вы увидите разницу в логических чтениях.
Таблицы довольно небольшие, чтобы увидеть разницу во времени выполнения запросов, но чем больше таблицы, тем хуже может быть производительность. Более того, если этот запрос часть более сложного запроса и далее в плане будут другие операторы, то недооценка строк в первом плане может сильно исказить последующие оценки и в итоге привести к еще более худшей производительности.
Давайте разберемся, почему получилось так, что без хинта оптимизатор справился не очень хорошо, что делает этот хинт, и в каких случаях его нужно использовать.
Теория
Для объяснения необходимо немного погрузиться вглубь оптимизатора и понять, каким образом он может вычислять селективности соединений с фильтрами по независимым колонкам.
Во некоторых предыдущих статьях я уже говорил о том, что в модели оценки кардинальности используется теория вероятностей, догадки и предположения (assumptions). Оценка соединений с фильтрами не исключение. Существуют два основных предположения, на которых основывается оценка таких соединений:
Simple Containment Assumption (простое предположение о содержании) – в случае соединения по двум атрибутам A1 и А2, где D1 число различных значений в A1, а D2 число различных значений в A2, если D1 <= D2, то для каждого различного значения из A1 всегда есть совпадение в A2.
Base Containment Assumption (базовое предположение о содержании) – это простое предположение но применяемое только к базовым столбцам таблицы (т.е. до фильтрации), при этом фильтры моделируются и учитываются отдельно.
Ниже приведена упрощенная схема одного и другого подхода.
С практической точки зрения Simple Containment предполагает, что данные в столбцах фильтра и столбцах соединения зависимы и для вычисления селективности используется гистограмма, модифицированная фильтром. В случае Base Containment оптимизатор предполагает, что столбцы фильтров не зависят от столбцов соединения, т.е. данные в столбцах TerritoryID, City, ShipToAddressID и AddressID независимы.
До 2014 сервера основным предположением по умолчанию считалось Simple Containment. При этом, начиная с 2005 SP1 была возможность включить Base Containment при помощи флага трассировки 2301 (Query Processor Modelling Extensions in SQL Server 2005 SP1).
Начиная с 2014 сервера и введения нового механизма оценки кардинальности, основным стало предположение Base Containment. При этом, старое предположение можно было включить флагом трассировки 9476. Я описывал этот флаг и разницу в подходах несколько лет назад в статье Join Containment Assumption and CE Model Variation. На тот момент (май 2014) это был недокументированный флаг трассировки, однако, относительно недавно его документировали и включили в описание, так что теперь им можно пользоваться официально.
Недостаток флагов трассировки в том, что, во-первых, они обладают слабой самодокументируемостью, т.е. встретив это магическое число в коде запроса, скорее всего, придется лезть в справку и выяснять, что же оно делает, а во-вторых и требуют прав SA. Вместо флага 9476 как раз и предлагается использовать хинт ASSUME_JOIN_PREDICATE_DEPENDS_ON_FILTERS, который делает то же самое, то есть, включает «старый» алгоритм оценки с предположением Simple Containment Assumption.
Вернемся к нашей БД и запросу. Очевидно, что в нашем примере есть зависимость между TerritoryID и City, так как наибольшая вероятность, что адреса доставки совпадут, если город Лондон искать в Великобритании (TerritoryID = 10 – Великобритания), а не в Зимбабве. То есть, территория напрямую связана с городом, а условие соединения таблиц по столбцу адреса как раз создает такую зависимость между столбцами, т.е. значения в предикатах по столбцам разных таблиц влияют друг на друга. Предположение Simple Containment это учитывает, а Base Containment считает фильтры независимыми. В данном случае, Simple Containment, которое мы включили при помощи хинта ASSUME_JOIN_PREDICATE_DEPENDS_ON_FILTERS, сработало лучше, поскольку лучше отражает реальность. Число строк получилось ближе к истине, тип соединения и доступа к данным был выбран более правильно и в результате мы получили меньше логических чтений.
Подведем небольшой промежуточный итог. Подсказка ASSUME_JOIN_PREDICATE_DEPENDS_ON_FILTERS включает алгоритм оценки с предположением Simple Containment Assumption, которое использовалось по умолчанию до 2014 сервера.
Использовать данную подсказку можно, в случае если между данными в столбцах соединения и фильтров есть зависимость, либо вы хотите приблизить оценку соединения к той, что была до 2014 сервера. Однако нужно помнить, что в модели оценки произошло много других изменений, так что число строк в старой и новой модели, скорее всего, не будет совпадать полностью.
Пример вычисления
Для понимания того, как именно вычисляется селективность соединения в одном и другом случае, давайте посчитаем ее вручную. Так сказать, математическая страничка в клубе любителей SQL Server =).
Начнем с того алгоритма, что используется, начиная с 2014 сервера по умолчанию, т.е. с алгоритма с предположением Base Containment Assumption.
Base Containment Assumption
Поскольку данные всех столбцов считаются независимыми (см. картинку в части 1), нам необходимо посчитать селективность для следующих предикатов:
- Фильтр по SalesOrderHeader: TerritoryID = 10
- Фильтр по Address: City = ‘London’
- Соединение SalesOrderHeader и Address: ShipToAddressID = AddressID
После чего, согласно теории вероятностей (теорема о вероятности произведения двух независимых событий) перемножить их. После чего, для нахождения кардинальности, умножить полученную селективность на произведение кардинальности таблиц.
Селективности фильтров вычисляются по гистограммам соответствующих колонок, мы находим шаги гистограммы, в которые попадают искомые значения и, используя данные гистограммы, вычисляем селективность.
Разберем на примере фильтра по предикату City = ‘London’, у меня статистика по колонке City имеет название _WA_Sys_00000004_29572725, поэтому, я смотрю гистограмму по этой статистике этой таблице при помощи команды:
dbcc show_statistics('Person.Address', _WA_Sys_00000004_29572725) with histogram;
Далее найдем в гистограмме, куда попадает наше значение.
Это строчка со значением RANGE_HI_KEY – London. Для нее согласно данным этого шага гистограммы 434 строки, т.к. значение столбца EQ_ROWS (Equal Rows, т.е. число строк, равное значению RANGE_HI_KEY) – 434. Тогда, разделив это число на кардинальность таблицы 19614 строк, мы получим селективность 0.022127 (select 434./19614.).
Если включить недокументированный флаг трассировки 2363 (совместно с флагом 3604), который выводит информацию о селективности, то мы увидим, что оказались правы:
В свою очередь для фильтра по TerritoryID это будет селективность 0.102304, вычисляемая таким же образом, через гистограмму.
Для предиката соединения (ShipToAddressID = AddressID) все гораздо сложнее. Селективность предиката зависит от выбранного алгоритма оценки, который в свою очередь зависит от условия соединения и статистик по столбцам. Это описание заслуживает отдельной темы, которой я посвятил статью Join Estimation Internals. В данном случае используется соединение по гистограммам столбцов соединения, общий алгоритм описан в вышеприведенной статье, поэтому мы не будем здесь вдаваться в подробности.
Кроме того, после вычисления селективности предиката соединения, применяется выравнивание Overpopulated Primary Key, о котором я говорил в статье Overpopulated Primary Key and CE Model Variation. Оно также вносит свой вклад в селективность условия соединения.
Мы можем наблюдать результат этого вычисления при помощи флага трассировки, упомянутого выше, результат:
Итого у нас есть три селективности:
- Фильтр по SalesOrderHeader: TerritoryID = 10 – 102304
- Фильтр по Address: City = ‘London’ – 022127
- Соединение SalesOrderHeader и Address: ShipToAddressID = AddressID – 2304e-005
У нас есть кардинальности базовых таблиц:
- SalesOrderHeader – 31465 rows
- Address – 19614 rows
Давайте теперь перемножим все эти значения, чтобы получить оценку соединения таблиц с фильтрами по независимым столбцам.
select 0.102304 * 0.022127 * 5.2304e-005 * 31465. * 19614.
Результат:
73.0708165859043 ~ 73.071 то, что мы видели в плане выполнения (с учетом особенностей вычислений с плавающей запятой).
Таким образом, вычисляется селективность соединения, когда фильтры независимы от условия соединения.
Simple Containment Assumption
Мы переходим ко второму варианту, когда мы явно говорим оптимизатору, что данные в столбцах разных таблиц зависят друг от друга.
Для вычисления селективности предиката соединения используется тот же алгоритм, что и в предыдущем разделе, только примененный уже не к гистограммам столбцов базовых таблиц, а к гистограммам столбцов после фильтрации.
Сервер отбирает строки по предикатам City = ‘London’ и TerritoryID = 10, очевидно, что, отбирая строки по этим предикатам, он исключает строку целиком, а значит и значения этой строки для столбцов соединения ShipToAddressID и AddressID. Таким образом после фильтрации по одному атрибуту, например, City = ‘London’, из соединения исключается часть строк, которые могли бы соединиться по ShipToAddressID с AddressID. Это сервер и пытается отразить в модифицированной гистограмме, а модель называется независимый фильтр по гистограмме.
После этого сервер использует модифицированные гистограммы (не гистограммы базовых столбцов, как в первом случае) для вычисления селективности предиката соединения. Далее опять применяется компенсация OPK, и в итоге получается селективность соединения.
Далее эта селективность используется для вычисления результата, но берутся кардинальности уже не базовых таблиц, а фильтров.
Итого, у нас есть селективность соединения по модифицированным гистограммам:
- Соединение SalesOrderHeader и Address: ShipToAddressID = AddressID – 000335411
Кардинальности после фильтрации (вычисленные в предыдущем примере):
- TerritoryID = 10 – 3219 rows
- City = ‘London’ – 434 rows
Перемножаем:
select 3219 * 434 * 0.000335411
Результат:
468.584595906 ~ 468.584, что мы и видим в плане запроса.
Резюме
Мы разобрали два возможных алгоритма вычисления предполагаемого числа строк в соединениях с наличием независимых фильтров каждый из которых основан на соответствующем предположении модели:
- Simple Containment Assumption (по умолчанию до 2014)
- Base Containment Assumption (2014 и выше)
Подсказка ASSUME_JOIN_PREDICATE_DEPENDS_ON_FILTERS позволяет переключиться с нового алгоритма (основан на предположении Base Containment), на старый (основан на предположении Simple Containment). Применять подсказку стоит в случае, когда вы явно видите зависимость между столбцами соединения и столбцами фильтрации, при том, что алгоритм по умолчанию дает оценки далекие от реальности.