Is a SQL 'not in' more 'expensive' than a SQL 'in'?

Question

Aside from the numbers of rows that may be in a table, would one of these sample queries be more costly than the other?

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

Generally speaking a NOT IN will be more expensive although it is certainly possible to construct scenarios where the opposite is true.

First, assuming that AccountId is the Primary Key for the Accounts table.

IN (4,6,7,9,10) will require 5 index seeks which means logical IO is 5 * the depth of the index (each seek needs to navigate from the root down through the intermediate pages and to exactly one leaf page).

NOT IN (4,6,7,9,10) will require a full scan and a filter (pushable non sargable predicate means it is pushed into the scan rather than as a separate operator) which means logical IO will equal the number of pages in the leaf node of the index + the number of non leaf levels.

To see this

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')

Returns

index_depth page_count
----------- --------------------
2           358
2           1

Looking at the pathologically different case where all of the rows meet the IN clause and thus none of them the 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')

Returns

index_depth page_count
----------- --------------------
3           358
3           2
3           1

(The index is deper as the uniquifier has been added to the clustered index key)

The IN is still implemented as 5 equality seeks but this time the number of leaf pages read on each seek is considerably more than 1. The leaf pages are arranged in a linked list and SQL Server carries on navigating along this until it encounters a row not matching the seek.

The NOT IN is now implemented as 2 range seeks

[1] Seek Keys[1]: END: #Accounts.AccountID < Scalar Operator((4)), 
[2] Seek Keys[1]: START: #Accounts.AccountID > Scalar Operator((4))  

With the residual predicate of

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 )  

So it can be seen that even in this extreme case the best SQL Server can do is to skip looking at the leaf pages for just one of the NOT IN values. Somewhat surprisingly even when I skewed the distribution such that the AccountID=7 records were 6 times more prevalent than the AccountID=4 ones it still gave the same plan, and did not rewrite it as range seeks either side of 7, similarly when reducing the number of AccountID=4 records to 1 the plan reverted to a clustered index scan so it seems limited to considering this transformation only for the first value in the index.

Addition

In the first half of my answer the numbers add up exactly as they would be expected to from my description and the index depth.

In the second part my answer didn't explain exactly why an index with 3 levels and 358 leaf pages should cause quite the exact number of logical reads that it does, for the very good reason that I wasn't quite sure myself! However I've filled in the missing bit of knowledge now.

First this query (SQL Server 2008+ syntax only)

SELECT AccountID, COUNT(DISTINCT P.page_id) AS NumPages
FROM #Accounts
CROSS APPLY sys.fn_PhysLocCracker(%%physloc%%) P
GROUP BY AccountID
ORDER BY AccountID

Gives these results

AccountID   NumPages
----------- -----------
4           72
6           72
7           73
9           72
10          73

Adding up NumPages gives a total of 362 reflecting the fact that some leaf pages contain 2 different AccountId values. These pages will be visited twice by the seeks.

SELECT COUNT(DISTINCT P.page_id) AS NumPages
FROM #Accounts
CROSS APPLY sys.fn_PhysLocCracker(%%physloc%%) P
WHERE AccountID <> 4

Gives

NumPages
-----------
287

So,

For the IN version:

the seek for =4 visits 1 root page, 1 intermediate page and 72 leaf pages (74)

the seek for =6 visits 1 root page, 1 intermediate page and 72 leaf pages (74)

the seek for =7 visits 1 root page, 1 intermediate page and 73 leaf pages (75)

the seek for =9 visits 1 root page, 1 intermediate page and 72 leaf pages (74)

the seek for =10 visits 1 root page, 1 intermediate page and 73 leaf pages (75)

Total: (372) (vs 378 reported in the IO stats)

And, for the NOT IN version:

the seek for <4 visits 1 root page, 1 intermediate page and 1 leaf pages (3)

the seek for >4 visits 1 root page, 1 intermediate page and 287 leaf pages (289)

Total: (292) (vs 295 reported in the IO stats)

So what about the unaccounted for IOs?

It turns out that these are related to the read-ahead mechanism. It is possible to (on a development instance) use a trace flag to disable this mechanism and verify that the logical reads are now reported as expected from the description above. This is discussed further in the comments to this blog post.

Answer 2

NOT IN basically means full table scan - most of the time. Exception is when you have an index and distribution of the index is poor (there are only few values in the index) and most values are in NOT IN condition.

IN also means full table scan if you do not have an index on it. With having an index on it, it will mostly be using the index. Exception again is having an index with poor distribution or few rows in the table where full table scan is faster.