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

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

На моей машине следующий запрос выполняет сканирование кластерного индекса и занимает около 6,8 секунд процессорного времени:

SELECT ID1, ID2
FROM two_col_key_test WITH (FORCESCAN)
WHERE ID1 NOT IN
(
N'1', N'2',N'3', N'4', N'5',
N'6', N'7', N'8', N'9', N'10',
N'11', N'12',N'13', N'14', N'15',
N'16', N'17', N'18', N'19', N'20'
)
AND (ID1 = N'FILLER TEXT' AND ID2 >= N'' OR (ID1 > N'FILLER TEXT'))
ORDER BY ID1, ID2 OFFSET 12000000 ROWS FETCH FIRST 1 ROW ONLY
OPTION (MAXDOP 1);

Следующий запрос выполняет поиск в кластеризованном индексе (единственная разница заключается в удалении FORCESCANподсказки), но занимает около 18,2 секунды процессорного времени:

SELECT ID1, ID2
FROM two_col_key_test
WHERE ID1 NOT IN
(
N'1', N'2',N'3', N'4', N'5',
N'6', N'7', N'8', N'9', N'10',
N'11', N'12',N'13', N'14', N'15',
N'16', N'17', N'18', N'19', N'20'
)
AND (ID1 = N'FILLER TEXT' AND ID2 >= N'' OR (ID1 > N'FILLER TEXT'))
ORDER BY ID1, ID2 OFFSET 12000000 ROWS FETCH FIRST 1 ROW ONLY
OPTION (MAXDOP 1);

Планы запросов очень похожи. Для обоих запросов из кластерного индекса читается 120000001 строк:

Я нахожусь на SQL Server 2017 CU 10. Вот код для создания и заполнения two_col_key_testтаблицы:

drop table if exists dbo.two_col_key_test;

CREATE TABLE dbo.two_col_key_test (
    ID1 NVARCHAR(50) NOT NULL,
    ID2 NVARCHAR(50) NOT NULL,
    FILLER NVARCHAR(50),
    PRIMARY KEY (ID1, ID2)
);

DROP TABLE IF EXISTS #t;

SELECT TOP (4000) 0 ID INTO #t
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);


INSERT INTO dbo.two_col_key_test WITH (TABLOCK)
SELECT N'FILLER TEXT' + CASE WHEN ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) > 8000000 THEN N' 2' ELSE N'' END
, ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
, NULL
FROM #t t1
CROSS JOIN #t t2;

Я надеюсь на ответ, который делает больше, чем просто создание отчетов о вызовах. Например, я вижу, что sqlmin!TCValSSInRowExprFilter<231,0,0>::GetDataXпри медленном запросе требуется значительно больше циклов ЦП по сравнению с быстрым:

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

Почему существует большая разница во времени процессора для этих двух запросов?

Почему существует большая разница во времени процессора для этих двух запросов?

План сканирования оценивает следующий выдвинутый несаржируемый (остаточный) предикат для каждой строки:

[two_col_key_test].[ID1]<>N'1' 
AND [two_col_key_test].[ID1]<>N'10' 
AND [two_col_key_test].[ID1]<>N'11' 
AND [two_col_key_test].[ID1]<>N'12' 
AND [two_col_key_test].[ID1]<>N'13' 
AND [two_col_key_test].[ID1]<>N'14' 
AND [two_col_key_test].[ID1]<>N'15' 
AND [two_col_key_test].[ID1]<>N'16' 
AND [two_col_key_test].[ID1]<>N'17' 
AND [two_col_key_test].[ID1]<>N'18' 
AND [two_col_key_test].[ID1]<>N'19' 
AND [two_col_key_test].[ID1]<>N'2' 
AND [two_col_key_test].[ID1]<>N'20' 
AND [two_col_key_test].[ID1]<>N'3' 
AND [two_col_key_test].[ID1]<>N'4' 
AND [two_col_key_test].[ID1]<>N'5' 
AND [two_col_key_test].[ID1]<>N'6' 
AND [two_col_key_test].[ID1]<>N'7' 
AND [two_col_key_test].[ID1]<>N'8' 
AND [two_col_key_test].[ID1]<>N'9' 
AND 
(
    [two_col_key_test].[ID1]=N'FILLER TEXT' 
    AND [two_col_key_test].[ID2]>=N'' 
    OR [two_col_key_test].[ID1]>N'FILLER TEXT'
)

План поиска выполняет две операции поиска:

Seek Keys[1]: 
    Prefix: 
    [two_col_key_test].ID1 = Scalar Operator(N'FILLER TEXT'), 
        Start: [two_col_key_test].ID2 >= Scalar Operator(N'')
Seek Keys[1]: 
    Start: [two_col_key_test].ID1 > Scalar Operator(N'FILLER TEXT')

... чтобы соответствовать этой части предиката:

(ID1 = N'FILLER TEXT' AND ID2 >= N'' OR (ID1 > N'FILLER TEXT'))

Остаточный предикат применяется к строкам, которые передают условия поиска выше (все строки в вашем примере).

Однако каждое неравенство заменяется двумя отдельными тестами для значений меньше OR чем :

([two_col_key_test].[ID1]<N'1' OR [two_col_key_test].[ID1]>N'1') 
AND ([two_col_key_test].[ID1]<N'10' OR [two_col_key_test].[ID1]>N'10') 
AND ([two_col_key_test].[ID1]<N'11' OR [two_col_key_test].[ID1]>N'11') 
AND ([two_col_key_test].[ID1]<N'12' OR [two_col_key_test].[ID1]>N'12') 
AND ([two_col_key_test].[ID1]<N'13' OR [two_col_key_test].[ID1]>N'13') 
AND ([two_col_key_test].[ID1]<N'14' OR [two_col_key_test].[ID1]>N'14') 
AND ([two_col_key_test].[ID1]<N'15' OR [two_col_key_test].[ID1]>N'15') 
AND ([two_col_key_test].[ID1]<N'16' OR [two_col_key_test].[ID1]>N'16') 
AND ([two_col_key_test].[ID1]<N'17' OR [two_col_key_test].[ID1]>N'17') 
AND ([two_col_key_test].[ID1]<N'18' OR [two_col_key_test].[ID1]>N'18') 
AND ([two_col_key_test].[ID1]<N'19' OR [two_col_key_test].[ID1]>N'19') 
AND ([two_col_key_test].[ID1]<N'2' OR [two_col_key_test].[ID1]>N'2') 
AND ([two_col_key_test].[ID1]<N'20' OR [two_col_key_test].[ID1]>N'20') 
AND ([two_col_key_test].[ID1]<N'3' OR [two_col_key_test].[ID1]>N'3') 
AND ([two_col_key_test].[ID1]<N'4' OR [two_col_key_test].[ID1]>N'4') 
AND ([two_col_key_test].[ID1]<N'5' OR [two_col_key_test].[ID1]>N'5') 
AND ([two_col_key_test].[ID1]<N'6' OR [two_col_key_test].[ID1]>N'6') 
AND ([two_col_key_test].[ID1]<N'7' OR [two_col_key_test].[ID1]>N'7') 
AND ([two_col_key_test].[ID1]<N'8' OR [two_col_key_test].[ID1]>N'8') 
AND ([two_col_key_test].[ID1]<N'9' OR [two_col_key_test].[ID1]>N'9')

Переписать каждое неравенство, например:

[ID1] <> N'1'  ->  [ID1]<N'1' OR [ID1]>N'1'

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

Вы можете увидеть это более четко, отключив отправку невысказанных предикатов с недокументированным флагом трассировки 9130. Это будет отображать остаток в виде отдельного фильтра с информацией о производительности, которую вы можете проверить отдельно:

Это также высветит небольшую погрешность кардинальности при поиске, что объясняет, почему оптимизатор в первую очередь выбрал поиск вместо сканирования (он ожидал, что часть поиска устранит некоторые строки).

Хотя перезапись неравенства может сделать (возможно, отфильтрованным) сопоставление индексов возможным (чтобы наилучшим образом использовать способность поиска индексов b-дерева), было бы лучше впоследствии отменить это расширение, если обе половины окажутся в остатке. Вы можете предложить это как улучшение сайта обратной связи по SQL Server .

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