На написание этой заметки меня подвиг доклад Алексея Эксаревского на 24 hours of PASS про наиболее часты причины ошибок в оценке кардинальности. Те, кто не видел этот доклад могут ознакомиться с ним на techdays.
Алексей рассказывает о возможных причинах неправильных оценок кардинальности (или количества строк), из-за чего оптимизатор выбирает неудачный план запроса. Наиболее интересным и нетривиальным мне показался один из последних рассмотренных случаев, когда на эти оценки влияет механизм RowGoal.
Я уже касался вкратце этого механизма, когда описывал вывод недокументированных флагов трассировки тут. Но на всякий случай повторюсь, чтобы было понятно, о чем речь.
RowGoal – это механизм оптимизатора, который позволяет основываясь на заранее известном числе строк, которые необходимо получить (например в запросе есть предложение Top N), ограничить число строк для обработки в более ранних операторах. Казалось бы, если мы заранее знаем число строк, то это позволит выбрать лучший план. И, как правило, это так, однако, при некотором особенном распределении данных, этот механизм может мешать.
Рассмотрим механику более подробно.
Для начала, создадим таблицу для демонстрации. Данные в ней будут распределены следующим образом: «первые» 150 000 строк имеют случайные значения от 0 до 99 999. «Последние» 5000 строк имеют значение 100 000.Мы создадим таблицу с возрастающим, статичным (не меняющимся) уникальным кластерным индексом, который будет, в данном случае и первичным ключом, поэтому «первые» строки будут располагаться на первых страницах индекса, последние 5000 строк на последних. Здесь имеется ввиду логический порядок страниц, в порядке следования ключа индекса, а не физическое размещение страниц.
Схематично это выглядит так.
Кроме того, создадим индекс по этому полю. Обновим всю статистику по всей таблице с полным сканированием и попросим сервер записать данные на диск.
use tempdb; go create table t(a int identity primary key, b int, filler char(500) not null default ''); -- 150 000 with values random insert t(b) select top (150000) abs(checksum(newid()))%100000 from master..spt_values v1,master..spt_values v2; -- 5000 ordinary with value 100000 insert t(b) select top (5000) 100000 from master..spt_values v1,master..spt_values v2; go --creating index create index ix_b on t(b); --updating all the stats update statistics t with fullscan; --saving checkpoint; go
Чем вообще отличается RowGoal, от Cardinality Estimation? Тем, что оценка кардинальности вычисляется снизу вверх, а RowGoal, заранее зная количество строк которые необходимо получить (благодаря спецификации запроса, например ключевым словам TOP, EXISTS и т.д.), ограничивает оценку сверху.
Рассмотрим запрос:
select top(10) * from t where b = 100000 order by a
Оценка кардинальности, происходит примерно так:
Кардинальность вычисляется, начиная с нижнего базового оператора, используя статистическую информацию. Поднимаясь вверх по дереву операторов, оценка претерпевает изменения. В частности, например, при вычислении кардинальности операции фильтра происходит вычисление селективности скалярных операторов. Селективность скалярных операторов зависит от контекста реляционного оператора, в котором она вычисляется. Например, селективность предиката a=b в соединении будет зависеть от контекста, и будет разной, например, для inner join и semi join. После этого селективность применяется к входной кардинальности, и мы получаем выходную кардинальность. Прочая статистическая информация так же модифицируется.
Когда в дело вступает RowGoal, оценка ограничивается сверху:
Т.е. оптимизатор заранее знает нужный результат и модифицирует план в соответствии с нуждами.
И в этом моменте, вступает в игру еще одна особенность математической модели оптимизатора, а именно предположения. Одно из предположений – предположение равномерности.
У нас в таблице 155000 строк. Из них, согласно статистике значение 100000 имеют 5000 строк. Допустим, что данные у нас распределены равномерно. Тогда сколько строк в среднем нам необходимо будет просканировать, чтобы получить 1 строку с искомым значением 100000, очевидно это общее количество строк, разделенное на количество строк с искомым значением. 155000/5000 = 31. Итого 31 строка. Чтобы получить 10 строк, очевидно 31 нужно умножить на 10. Итак, оптимизатор, руководствуясь предположением о равномерности, оценил, что будет необходимо просканировать 310 строк.
Кстати, если мы выполним запрос, и посмотрим на план:
select top(10) * from t where b = 100000 order by a option(recompile);
То увидим оценку в 10 строк. Хитрый оптимизатор нас немного обманывает, скрывая оператор фильтр. А точнее объединяя его со сканом. Ну, а мы давайте в свою очередь его тоже обманем и выполним тот же самый запрос, но с недокументированным флагом трассировки 9130. (Disclaimer: помните, все недокументированные флаги, нужно использовать для исследовательских целей).
select top(10) * from t where b = 100000 order by a option(recompile, querytraceon 9130);
Чтобы быть уверенным, откуда взялась эта оценка, можно также выполнить запрос с двумя другими недокументированными флагами, которые позволяют просматривать выходное дерево физических операторов и включать туда аргументы из memo. О них я рассказывал в предыдущей заметке.
Выполните запрос, и переключитесь на вкладку Messages.
select top(10) * from t where b = 100000 order by a option(recompile, querytraceon 3604,querytraceon 8607,querytraceon 8612);
Я убрал вывод некоторых аргументов, которые нас не интересуют, для краткости. Вот что мы увидим:
*** Output Tree: *** PhyOp_Top Columns : QCOL: [tempdb].[dbo].[t].a Ascending, NoTies [ Card=10 Cost(RowGoal 0) ] PhyOp_Filter [ Card=5000 Cost(RowGoal 10)] PhyOp_Range TBL: t(1) ASC Bmk ( QCOL: [tempdb].[dbo].[t].a) [ Card=155000 Cost(RowGoal 310) ] ScaOp_Comp x_cmpEq ScaOp_Identifier QCOL: [tempdb].[dbo].[t].b ScaOp_Const TI(int,ML=4) XVAR(int,Not Owned,Value=100000) ScaOp_Const TI(bigint,Null,ML=8) XVAR(bigint,Not Owned,Value=10)
Как мы видим, в операторе сканирования кардинальность имеет значение 155000, а RowGoal как раз 310.
Ради чего весь сыр бор.
Как вы уже, наверное, догадались, оптимизатор, сделав оценку в 310 строк, сильно недооценил, какое же реально количество строк ему будет необходимо просканировать, т.к. не имел сведений о том, где эти строки располагаются.
А если мы посмотрим в план, на два параметра скана:
То мы увидим, что, во-первых, он упорядоченный (Ordered=true), во-вторых, имеет направление вперед (Scan Direction=FORWARD).
Поэтому, ситуацию можно представить так:
Теперь, когда механика понятна. Перейдем к конкретным замерам.
Этот эффект хорошо проявляется на больших таблицах, и сложных запросах. Но т.к. у нас таблица относительно небольшая и простейший запрос, для демонстрации эффекта просто будем выполнять тесты на холодном кэше.
Итак, давайте очистим кэш, включим статистику и попробуем выполнить запрос:
dbcc dropcleanbuffers with no_infomsgs; go set statistics time, io on; go select top(10) * from t where b = 100000 order by a; go set statistics time, io off; go
результат:
(10 row(s) affected)
Table ‘t’. Scan count 1, logical reads 10041, physical reads 45, read-ahead reads 10368, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 62 ms, elapsed time = 1163 ms.
Выполнение заняло больше секунды. Насколько это быстро или медленно?
Чтобы это понять, нужно, чтобы было с чем сравнивать.
В данном случае, решением может быть вообще отказаться от сканирования и вместо этого заставить оптимизатор использовать поиск, при помощи подсказки forceseek.
Также, в качестве «Proof of concept», мы выполним запрос, где сканирование будет идти в обратную сторону (Scan Direction=BACKWARD) , указав другой порядок сортировки. Это будет уже другой запрос, потому что вернет другие результаты, но он хорошо подходит, для демонстрации отличий в скорости одного и того же оператора сканирования при разном распределении данных и RowGoal.
Итак:
set nocount on go print(' --------------------------------- Problem non-uniform data(Scan Direction - FORWARD): '); dbcc dropcleanbuffers with no_infomsgs; go set statistics time, io on; go select top(10) * from t where b = 100000 order by a; go set statistics time, io off; go dbcc dropcleanbuffers with no_infomsgs; go print(' --------------------------------- Proof of concept distribution dependent (Scan Direction - BACKWARD): '); set statistics time, io on; go select top(10) * from t where b = 100000 order by a desc; go set statistics time, io off; go print(' --------------------------------- Workaround (Seek Forced): '); dbcc dropcleanbuffers with no_infomsgs; go set statistics time, io on; go select top(10) * from t with(forceseek) where b = 100000 order by a; go set statistics time, io off;
Результаты:
———————————
Problem non-uniform data(Scan Direction — FORWARD):
Table ‘t’. Scan count 1, logical reads 10041, physical reads 45, read-ahead reads 10368, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.SQL Server Execution Times:
CPU time = 47 ms, elapsed time = 1239 ms.———————————
Proof of concept distribution dependent (Scan Direction — BACKWARD):
Table ‘t’. Scan count 1, logical reads 14, physical reads 11, read-ahead reads 1503, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 99 ms.———————————
Workaround (Seek Forced):
Table ‘t’. Scan count 1, logical reads 505, physical reads 3, read-ahead reads 24, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 83 ms.
Как вы видите, производительность, время и количество чтений отличается значительно, более чем в 10 раз.
Может показаться, что данный пример притянут за уши, но он хорош для демонстрации. Примеры, более приближенные к реальным, на больших таблицах, приведены в докладе, на который я ссылался в начале заметки, и по словам докладчика, такие проблемы у клиентов не редкость. В завершение, хотелось бы еще раз поблагодарить Алексея, за то, что он подкинул интересный случай для изучения.