Почему Sql Server использует Index Seek при LIKE '%'+@Param+'%'?

#sql_server #sql_server_2008

Немного не понимаю логику:



Почему Sql Server выбрал поиск в индексе вместо того, что бы сканировать его? Хинтов
нету. 

Ведь используется оператор LIKE + еще с обоих сторон % стоят.

Если убрать параметр, то используется Index Scan, как и предполагалось => дело в
параметре.

Я изучил вот эту статью, где пишется, что когда используется параметр, то он генерит
наиболее общий план.

Неужели SQL Server не может это за ранее увидеть % и сделать оптимальный план?

Вот я весь анонимизированный запрос и план выкладываю:

Declare Variable1 Nvarchar(255)='815'
;WITH Object1 AS (SELECT Object2.Column1,Object2.Column2 from Schema1.Object3 Object2
WHERE Object2.Column3 LIKE '%' + Variable1  + '%')
SELECT Object4.Column1 AS Column4,MAX(Object4.Column1) AS Column5,MIN(Object4.Column2)
AS Column6,COUNT(Object4.Column2) AS Column7 
FROM Object1 Object4
GROUP BY Object4.Column1




Если указать хинт на FORCESCAN, то запрос выполняется шустрее 3 сек вместо 14 сек.

UPD

Если воспользоваться, то показывает такую картину set statistics io, time on:

Без FORCESCAN


  (затронуто строк: 6407) Table 'Folder'. Scan count 1, logical reads
  274975, physical reads 0, read-ahead reads 0, lob logical reads 0, lob
  physical reads 0, lob read-ahead reads 0. Table 'Worktable'. Scan
  count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob
  logical reads 0, lob physical reads 0, lob read-ahead reads 0. Table
  'Worktable'. Scan count 0, logical reads 0, physical reads 0,
  read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob
  read-ahead reads 0.
  
  SQL Server Execution Times:    CPU time = 14789 ms,  elapsed time =
  14778 ms. Warning: Null value is eliminated by an aggregate or other
  SET operation.


И с:


  (затронуто строк: 6407) Table 'Folder'. Scan count 13, logical reads
  278746, physical reads 2, read-ahead reads 2, lob logical reads 0, lob
  physical reads 0, lob read-ahead reads 0. Table 'Worktable'. Scan
  count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob
  logical reads 0, lob physical reads 0, lob read-ahead reads 0.
  
  SQL Server Execution Times:    CPU time = 28906 ms,  elapsed time =
  2837 ms. Warning: Null value is eliminated by an aggregate or other
  SET operation.


Выполнял несколько раз на с одним и тем же параметром=> данные все в кеше.
    

Ответы

Ответ 1

Почему Sql Server выбрал поиск в индексе вместо того, чтобы
  сканировать его?


Дело здесь в сочетании двух факторов:


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


Если вы уверены, что поиск по индексу вам не пригодится, то указание FORCESCAN -
одно из возможных решений, но в данном случае, вероятно, не самое лучшее. Дело в том,
что в плане запроса есть оператор Sort. И если, как вы пишете, на операторе Nested
Loops у вас


  Актуально 16 000, ожидаемо 400 000.


(оптимизатор переоценил количество строк), то скорее всего для выполнения запроса
выделяется избыточное количество памяти. Попробуйте добавить OPTION (RECOMPILE) к запросу,
тогда оптимизатор сможет использовать сканирование, плюс оценка (и выделение памяти)
станут, возможно, адекватнее.

Либо, если существующий индекс не используется для других целей, то вообще создать
вместо него

CREATE INDEX IX_Folder_Storage_id ON [Folder] ([Storage_id])
    INCLUDE ([paths], [Name]);


тогда оптимизатор будет использовать сканирование индекса, как вы и хотите, плюс
из плана запроса пропадёт сортировка.

Ниже некоторые подробности.



Возьмём из исходного запроса самое интересное

DECLARE @pattern nvarchar(255) = '815';

SELECT [Name]
FROM [Folder]
WHERE [Name] LIKE '%' + @pattern + '%';


Действительный план такого запроса выглядит следующим образом:



|--Nested Loops(Inner Join, OUTER REFERENCES:([Expr1007], [Expr1008], [Expr1009]))
   |--Compute Scalar(DEFINE:([Expr1007]=LikeRangeStart(N'%'+[@pattern]+N'%'),
   |    |                    [Expr1008]=LikeRangeEnd(N'%'+[@pattern]+N'%'),
   |    |                    [Expr1009]=LikeRangeInfo(N'%'+[@pattern]+N'%')))
   |    |--Constant Scan
   |
   |--Index Seek(OBJECT:([Simple].[dbo].[Folder].[IX_Folder_Name])
                 SEEK:([Simple].[dbo].[Folder].[Name] > [Expr1007]
                   AND [Simple].[dbo].[Folder].[Name] < [Expr1008])
                 WHERE:([Simple].[dbo].[Folder].[Name] like N'%'+[@pattern]+N'%')
                 ORDERED FORWARD)


т.е. SqlServer выполняет поиск, локализуя его в области, границы которой определяются
динамически с помощью внутренних функций LikeRangeStart и LikeRangeEnd. Поиск в индексе
по диапазону ключевых значений фактически является частичным сканированием (часто так
и говорят partial scan или range scan).

Такой шаблон является специальным. Операторы Constan Scan, Compute Scalar и Nested
Loops являются дополнительными и добавляются на этапе пост-оптимизационного преобразования
(т.н. post-optimization rewrite). Этот шаблон (и другие ему подобные) хорошо описан
здесь. К тому, что можно найти в статье по ссылке хотелось бы, применительно к данному
случаю, добавить следующее.

При использовании локальных переменных оптимизатор может прибегать к упрощённым оценкам
селективности предикатов (см. здесь, раздел Avoid use of local variables in queries).

Так, например, на тестовой таблице

CREATE TABLE [Folder] ([Name] nvarchar(260) NOT NULL, [Filler] binary(400));


содержащей 100 тыс. строк

WITH Nums(N) AS (
    SELECT TOP (100000) ROW_NUMBER() OVER (ORDER BY @@SPID)
    FROM sys.all_columns a, sys.all_columns b
)
INSERT INTO [Folder] WITH (TABLOCKX) ([Name])
SELECT
    REPLICATE(CONVERT(nvarchar(200), CAST(N AS binary(4)), 2), 25)
FROM Nums;


с индексом на столбце Name

CREATE INDEX IX_Folder_Name ON [Folder] ([Name]);


запрос вернул мне следующие метрики и оценки производительности:



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

Если посмотреть (с помощью флага трассировки 2363) источник этой оценки, то можно увидеть

Plan for computation:
  CSelCalcFixedFilter (0.09)

Selectivity: 0.09

Stats collection generated: 
  CStCollFilter(ID=2, CARD=9000)
      CStCollBaseTable(ID=1, CARD=100000 TBL: Folder)


что для расчёта селективности используется калькулятор CSelCalcFixedFilter (т.е.
оценка селективности в данном случае есть величина постоянная). Использование табличной
подсказки FORCESCAN на метод расчёта оценки не влияет, оставляя селективность постоянной
равной 9% от общего количества строк в таблице.

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



Впрочем, если бы даже оператор Index Seek в этом плане и мог быть параллельным, то
выгода от этого была бы сомнительна, т.к. с параллелизмом на внутренней (inner) стороне
Nested Loops есть определённые проблемы (см. здесь, раздел A Note about Parallel Nested
Loops).

Возьмём теперь тот же самый запрос, но предикат будет не с переменной, а с литералом:

SELECT [Name]
FROM [Folder]
WHERE [Name] LIKE '%815%';


Действительный план запроса получился такой:



|--Index Scan(OBJECT:([Simple].[dbo].[Folder].[IX_Folder_Name]),
              WHERE:([Simple].[dbo].[Folder].[Name] like N'%815%'))


у меня он не параллельный, т.к. строк в таблице не много, но в данном случае всё
примитивно и никаких препятствий для параллелизма нет. Интереснее, впрочем, оценочное
количество строк



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

Если посмотреть источник этой оценки, то можно увидеть

Plan for computation:
  CSelCalcTrieBased
      Column: QCOL: [Simple].[dbo].[Folder].Name

Selectivity: 0.000107411

Stats collection generated: 
  CStCollFilter(ID=2, CARD=10.7411)
      CStCollBaseTable(ID=1, CARD=100000 TBL: Folder)


что она не фиксированная, а рассчитана с помощью CSelCalcTrieBased (калькулятор селективности
на основе префиксного дерева).

Представленные выше результаты получены на SqlServer 2014. В SqlServer 2008 оценка
для предиката LIKE с литералом получилась (после UPDATE STATISTICS ... WITH FULLSCAN)
идентичной



А оценка для предиката с переменной получилась похожей



но всё же несколько отличающейся, что ожидаемо, т.к. Cardinality Estimator в SqlServer
2014 претерпел изменения (отличия могут быть даже в минорных версиях одного релиза).

Флаг трассировки 2363 появился лишь в SqlServer 2014, поэтому в SqlServer 2008 нет
возможности так же легко посмотреть источники оценок селективности. Некоторую информацию,
впрочем, можно добыть с помощью отладчика.

Судя по стеку вызовов, в SqlServer 2008 для оценки селективности фильтра LIKE с литералом
так же используется префиксное дерево (CTrieInMem):

(call-stack)
sqlservr!OptimizerUtil::ProbLikeGuess
sqlservr!CTrieInMemCore::UlCountLikeStrings
sqlservr!CTrieInMemCore::FFilterLike+0x2af
sqlservr!CTrieInMem::FFilterLike+0x2e
sqlservr!CInMemHistogram::FFilterLike+0x5d
sqlservr!CScaOp_Intrinsic::FCalcSelectivity+0x47c0
sqlservr!CalculateFilter+0x72
sqlservr!CSelContext::CalculateSelectivity+0x37e
sqlservr!GroupCard+0x736
sqlservr!CLogOp_Select::DeriveCardinality+0x587
...


а для для оценки селективности фильтра LIKE с переменной используется какое-то предположение
(ProbLikeGuess)

(call-stack)
sqlservr!OptimizerUtil::ProbLikeGuess
sqlservr!CScaOp_Intrinsic::FCalcSelectivity+0x6023
sqlservr!CalculateFilter+0x72
sqlservr!CSelContext::CalculateSelectivity+0x37e
sqlservr!GroupCard+0x736
sqlservr!CLogOp_Select::DeriveCardinality+0x587
...


по-видимому на основе вектора плотности

(call-tree)
sqlservr!CLogOp_Select::DeriveCardinality+0x587
sqlservr!GroupCard+0x736
sqlservr!CSelContext::CalculateSelectivity+0x37e
sqlservr!CalculateFilter+0x72
  sqlservr!CScaOp_Intrinsic::FCalcSelectivity+0x34b
    sqlservr!CScaOp_Identifier::FCalcSelectivity+0x44a
      sqlservr!CInMemHistogram::CardGetStepTotal
    sqlservr!CScaOp_Identifier::FCalcSelectivity+0x47a
      sqlservr!CDensityGroup::FFindDensityByPvr
...




Резмируем вышесказанное. Неадекватные оценки могут быть причиной генерации неоптимального
плана запроса, медленного его выполнения и/или избыточного выделения ресурсов. Если
производительность запроса не устраивает, и причина низкой производительности именно
в неадекватности оценок, то (в общем случае) можно попытаться это исправить следующими
способами:


обновить статистики на таблицах, участвующих в запросе
добавить к запросу OPTION (RECOMPILE) (на тяжёлых запросах с
несложным планом чаще всего это приемлемый компромисс)
материализовать часть запроса в #-таблицу