Ответ 1
В общем случае a NOT IN будет дороже, хотя, безусловно, возможно построить сценарии, где истинно противоположное.
Во-первых, считая, что AccountId является основным ключом для таблицы Accounts.
IN (4,6,7,9,10) потребует 5 указателей, что означает, что логическое значение IO равно 5 * глубине индекса (каждый поиск должен перемещаться от корня до промежуточных страниц и ровно к одной странице листа).
NOT IN (4,6,7,9,10) потребует полного сканирования и фильтра (pushable non sargable predicate означает, что он вставляется в сканирование, а не как отдельный оператор), что означает, что логический IO будет равен количеству страниц в листе node индекс + число нелистовых уровней.
Чтобы увидеть это
CREATE TABLE #Accounts
(
AccountID INT IDENTITY(1,1) PRIMARY KEY,
Filler CHAR(1000)
)
INSERT INTO #Accounts(Filler)
SELECT 'A'
FROM master..spt_values
SET STATISTICS IO ON
SELECT * FROM #Accounts WHERE AccountID IN (4,6,7,9,10)
/* Scan count 5, logical reads 10*/
SELECT * FROM #Accounts WHERE AccountID NOT IN (4,6,7,9,10)
/*Scan count 1, logical reads 359*/
SELECT index_depth, page_count
FROM
sys.dm_db_index_physical_stats (2,object_id('tempdb..#Accounts')
, DEFAULT,DEFAULT, 'DETAILED')
Возвращает
index_depth page_count
----------- --------------------
2 358
2 1
Глядя на патологически иной случай, когда все из строк соответствуют предложению IN, и поэтому ни один из них не имеет значения NOT IN
SET STATISTICS IO OFF
CREATE TABLE #Accounts
(
AccountID INT ,
Filler CHAR(1000)
)
CREATE CLUSTERED INDEX ix ON #Accounts(AccountID)
;WITH Top500 AS
(
SELECT TOP 500 * FROM master..spt_values
), Vals(C) AS
(
SELECT 4 UNION ALL
SELECT 6 UNION ALL
SELECT 7 UNION ALL
SELECT 9 UNION ALL
SELECT 10
)
INSERT INTO #Accounts(AccountID)
SELECT C
FROM Top500, Vals
SET STATISTICS IO ON
SELECT * FROM #Accounts WHERE AccountID IN (4,6,7,9,10)
/*Scan count 5, logical reads 378*/
SELECT * FROM #Accounts WHERE AccountID NOT IN (4,6,7,9,10)
/*Scan count 2, logical reads 295*/
SELECT index_depth,page_count
FROM
sys.dm_db_index_physical_stats (2,OBJECT_ID('tempdb..#Accounts'), DEFAULT,DEFAULT, 'DETAILED')
Возвращает
index_depth page_count
----------- --------------------
3 358
3 2
3 1
(индекс меньше, поскольку уникальный ключ добавлен в кластеризованный индексный ключ)
IN по-прежнему реализуется по мере того, как ищет 5 равенств, но на этот раз количество листовых страниц, прочитанных в каждом поиске, значительно больше, чем 1. Страницы листа расположены в связанном списке, и SQL Server продолжает перемещаться по этому пути до тех пор, пока он встречает строку, не соответствующую поиску.
NOT IN теперь реализован как 2 диапазона ищет
[1] Seek Keys[1]: END: #Accounts.AccountID < Scalar Operator((4)),
[2] Seek Keys[1]: START: #Accounts.AccountID > Scalar Operator((4))
С остаточным предикатом
WHERE ( #Accounts.AccountID < 6
OR #Accounts.AccountID > 6 )
AND ( #Accounts.AccountID < 7
OR #Accounts.AccountID > 7 )
AND ( #Accounts.AccountID < 9
OR #Accounts.AccountID > 9 )
AND ( #Accounts.AccountID < 10
OR #Accounts.AccountID > 10 )
Итак, можно заметить, что даже в этом крайнем случае лучший SQL Server может сделать это, чтобы пропустить просмотр листовых страниц только для одного из значений NOT IN. Несколько неожиданно, даже когда я перекосил распределение таким образом, что записи AccountID=7 были в 6 раз более распространенными, чем теги AccountID=4, они все же дали один и тот же план и не переписывали его, поскольку диапазон стремится к любой стороне от 7, аналогично, при уменьшении число AccountID=4 записывает в 1 план, возвращенный к кластерному сканированию индекса, поэтому кажется ограниченным рассматривать это преобразование только для первого значения в индексе.
Добавление
В первой половине моего ответа числа складываются точно так, как они ожидали от моего описания и глубины индекса.
Во второй части мой ответ не объяснил точно, почему индекс с 3 уровнями и 358 листовыми страницами должен вызывать вполне точное количество логических чтений, которые он делает, по той очень хорошей причине, что я был не совсем уверен! Однако я заполнил недостающий бит знаний.
Сначала этот запрос (только синтаксис SQL Server 2008+)
SELECT AccountID, COUNT(DISTINCT P.page_id) AS NumPages
FROM #Accounts
CROSS APPLY sys.fn_PhysLocCracker(%%physloc%%) P
GROUP BY AccountID
ORDER BY AccountID
Дает эти результаты
AccountID NumPages
----------- -----------
4 72
6 72
7 73
9 72
10 73
Добавление NumPages дает в общей сложности 362, отражающий тот факт, что некоторые листовые страницы содержат 2 разных значения AccountId. Эти страницы будут посещены дважды поисками.
SELECT COUNT(DISTINCT P.page_id) AS NumPages
FROM #Accounts
CROSS APPLY sys.fn_PhysLocCracker(%%physloc%%) P
WHERE AccountID <> 4
дает
NumPages
-----------
287
Итак,
Для версии IN:
поиск =4 посещает 1 корневую страницу, 1 промежуточную страницу и 72 листа страниц (74)
поиск =6 посещает 1 корневую страницу, 1 промежуточную страницу и 72 листа страниц (74)
поиск =7 посещает 1 корневую страницу, 1 промежуточную страницу и 73 листа страниц (75)
поиск =9 посещает 1 корневую страницу, 1 промежуточную страницу и 72 листа страниц (74)
поиск =10 посещает 1 корневую страницу, 1 промежуточную страницу и 73 листа страниц (75)
Всего: (372) (против 378, зарегистрированных в статистике IO)
И для версии NOT IN:
поиск <4 посещает 1 корневую страницу, 1 промежуточную страницу и 1 лист страницы (3)
поиск >4 посещает 1 корневую страницу, 1 промежуточную страницу и 287 листовых страниц (289)
Итого: (292) (против 295, зарегистрированных в статистике IO)
А как насчет неучтенного для IO?
Оказывается, что они связаны с механизмом read-ahead. Можно (на экземпляре разработки) использовать флаг трассировки, чтобы отключить этот механизм и убедиться, что логические чтения теперь сообщаются как ожидалось из приведенного выше описания. Это обсуждается далее в комментариях к этому сообщению в блоге.