How to optimize NOT IN statement

Question

Why does NOT IN performs INDEX SCAN instead of INDEX SEEK?

Here's my current index on the table,

CREATE NONCLUSTERED INDEX [idx_dmcasarms_CourseList_cDesc] 
ON [dbo].[courselist]
(
    [c_desc] ASC,
    [c_code] ASC
)

SQL Statement,

SELECT  c_code CourseCode
FROM    courselist
WHERE   c_desc = 'BACHELOR OF SCIENCE IN INFORMATION TECHNOLOGY'
GO

SELECT  c_code CourseCode
FROM    courselist
WHERE   c_desc NOT IN ('PRE SCHOOL', 'BASIC EDUCATION', 'SCIENCE HIGH SCHOOL')
GO

and Execution Plan,

Is there anyway I can optimize this?

Answer 1

You could also write the query as

SELECT  c_code CourseCode
FROM    courselist
WHERE   c_desc < 'BASIC EDUCATION'
UNION ALL
SELECT  c_code CourseCode
FROM    courselist
WHERE   c_desc > 'BASIC EDUCATION' AND c_desc < 'PRE SCHOOL'
UNION ALL
SELECT  c_code CourseCode
FROM    courselist
WHERE   c_desc > 'PRE SCHOOL' AND c_desc < 'SCIENCE HIGH SCHOOL'
UNION ALL
SELECT  c_code CourseCode
FROM    courselist
WHERE   c_desc > 'SCIENCE HIGH SCHOOL'

To get four range seeks.

Unless any of the NOT IN values are extremely common I would expect this to be worse rather than better however.

If the values are common then last time I looked at this it seemed the best SQL Server would do is skip the first indexed value and scan the rest.

A completely rigged example looking at the case where this might be better...

CREATE TABLE [dbo].[courselist](
[c_desc] VARCHAR(20),
[c_code] CHAR(880))

CREATE NONCLUSTERED INDEX [idx_dmcasarms_CourseList_cDesc] 
ON [dbo].[courselist]([c_desc] ASC,[c_code] ASC);

WITH T AS (SELECT TOP (10000) v1.number FROM  master..spt_values v1, master..spt_values v2)
INSERT INTO [dbo].[courselist]
SELECT X, number 
FROM T
CROSS JOIN (VALUES ('PRE SCHOOL'),
                   ('SCIENCE HIGH SCHOOL')) V(X)
UNION ALL                   
SELECT REPLICATE('A',20), 1    

On my machine with a warm cache the NOT IN has a full scan and 3,132 logical reads with an elapsed time of 20ms. Whereas the multiple seeks shows 28 reads and an elapsed time of 0ms.

Answer 2

It performs a scan because it has to find all values not in the one listed. Imagine looking up in a phone book and finding all last name values that aren't 'Smith'. Then you'll have to scan the entire book. If you instead had to find only those with the last name value 'Smith', then you could just seek to that section.

As for how to optimize, it would unfortunately be to rework the logic to avoid NOT IN if the scan is too costly to accept. So if you somehow can change your NOT IN to an IN or = it would be better for the database engine. Of course this can be impossible at time, and then you'll have to weigh the cost of the query vs. the cost of reworking the logic.