sql - SQL 'not in' 比 SQL 'expensive' 多 'in' 吗？

Question

除了表中可能存在的行数之外，这些示例查询中的一个是否比另一个成本更高？

SELECT * FROM dbo.Accounts WHERE AccountID IN (4,6,7,9,10) 

SELECT * FROM dbo.Accounts WHERE AccountID NOT IN (4,6,7,9,10)

Answer 1

一般来说NOT IN尽管可以构建相反的场景，但成本会更高。
首先，假设AccountId是 Accounts 的主键 table 。IN (4,6,7,9,10)将需要 5 次索引查找，这意味着逻辑 IO 是 5 * 索引的深度(每次查找都需要从根向下导航到中间页并精确到一个叶页)。NOT IN (4,6,7,9,10)将需要一个完整的扫描和一个过滤器(pushable non sargable predicate 意味着它被插入扫描而不是作为一个单独的操作符)这意味着逻辑 IO 将等于索引的叶节点中的页面数 + 非叶节点的数量水平。
看到这个

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

(由于 uniquifier 已添加到聚集索引键中，因此索引更深) 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 时有点令人惊讶。记录比 AccountID=4 流行 6 倍那些它仍然给出了相同的计划，并且没有重写它作为范围寻找 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 个，反射(reflect)了某些叶页包含 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) (与 IO 统计中报告的 378 相比)
而且，对于 NOT IN版本:
寻求 <4访问 1 个根页面、1 个中间页面和 1 个叶页面 (3)
寻求 >4访问 1 个根页面、1 个中间页面和 287 个叶页面 (289)
总计: (292) (与 IO 统计中报告的 295 相比)
那么那些下落不明的 IO 呢？
原来这些都与 read-ahead有关。机制。可以(在开发实例上)使用跟踪标志来禁用此机制并验证逻辑读取现在是否按上述描述的预期报告。 This is discussed further in the comments to this blog post.