Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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,

enter image description here

Is there anyway I can optimize this?

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
+1 clever. but i could hardly use this solution as the number of values are dynamic. I choose this as the accepted answer since there are some queries that needs only two values. thanks! –  Rossana Oct 22 '13 at 8:18
add comment

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.

share|improve this answer
    
Smith is quite a common surname though so once you have found the first "Smith" you might decide to seek ahead to the first name after Smith rather than read all the names with Smith. –  Martin Smith Oct 22 '13 at 7:27
    
yes I'll go on reworking the logic. thank you. –  Rossana Oct 22 '13 at 8:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.