Interesting TSQL query plan for NOT IN vs. NOT EXISTS

Ran across this one the other day.

I was searching for something the other day on Google!, can’t remember what right now, and happened upon an old post [1] (old for the internet – 1998) entitled The EXISTS Flaw.  This referenced a C.J. Date from September, 1989 and his postulate on a flaw with the EXISTS syntax of the structured query language.  I’ve been using SQL and TSQL now for about 15 years and I never heard of it…glad I learn something new every day, right?.  So I look at this posting and right off determined that the author 1) isn’t comparing apples-to-apples in his two queries, and 2) is actually witnessing how each operator – IN and EXISTS – is supposed to work, by definition.  That is beside the point, because this particular blog posting is not to engage anyone in a debate (I might save that one for another occasion) but to instead look into the behavior of why NOT IN works as it does.

While checking this out I discovered something interesting when you use NOT IN that I wanted to share. Run the following to create the table and insert the rows which he has done.

DROP TABLE sp
go
CREATE TABLE sp
(sno char(2)
,pno char(2)
,qty int
)
GO

INSERT sp VALUES ('S1', 'P1', NULL)
INSERT sp VALUES ('S2', 'P1', 200)
INSERT sp VALUES ('S3', 'P1', 1000) 
 

The question here is: “Find supplier numbers for suppliers who are known to supply part P1, but not in a quantity of 1,000”. 

SELECT DISTINCT spx.sno
FROM sp spx
WHERE spx.pno = 'P1'
AND 1000 NOT IN
    ( SELECT spy.qty
    FROM   sp spy
    WHERE spy.sno = spx.sno
    AND      spy.pno = 'P1');
 
SELECT DISTINCT spx.sno
FROM sp spx
WHERE spx.pno = 'P1'
AND NOT EXISTS
    ( SELECT spy.qty
    FROM sp spy
    WHERE spy.sno = spx.sno
    AND spy.pno = 'P1'
    AND spy.qty = 1000);

Now, look at the result set.  You will notice that a S2 returns for the first query, but that suppliers S1 and S2 return in the second query. What’s up with this?  The author states that EXISTS does not return the correct result set.  Let us ask now, does NULL not equal 1000?  Without question yes, NULL does not equal 1000, and in fact NULL equals nothing, not even NULL.  So in this light you could make a case that in fact the first query is incorrect because our question wants to know who carries part P1 in a quantity other than 1000, and NULL is not a quantity equal to 1000.

What I find interesting here, however, is to understand why the first query returns only S2 and not why the second returns both S1 and S2, and we do this with none other than a query execution plan.  Let’s look at them both:

Figure 1. Execution Plan (est) for query 1

Figure 2. Execution Plan (est) for query 2

For Figure 2, notice how for the predicates we find that qty=1000 and pno=’P1’ as expected. Now look at the same plan in Figure 1 and check out the differences – NOT IN also includes pno=’P1’ , but it’s interesting that it includes the compound predicate AND (qty IS NULL OR qty = 1000).  I am quite certain here that in my statement I have nothing that tells NOT IN to disregard NULLs.  This I cannot explain.  Why does NOT IN handle this as such?  Why is NOT IN doing me a favor and checking for (and throwing out of the recordset) the NULL? 

Additionally, it would seem that the IN and NOT IN work differently.  If you remember, IN actually flattens out a TSQL statement to a series of ORs (Figure 3), but a NULL won’t be handled as it appears to be under the NOT IN scenario because nothing can equal NULL. If you were to add “, NULL” to the SELECT list you would not get sno equal to 1.

Figure 3.  IN flattens out to OR

SELECT * FROM sp
WHERE qty IN (200, 1000)

Notice when comparing Figure 1 to Figure 3 the vast difference in behavior for an IN and NOT IN. Wouldn’t one expect that IN would also include the following, since NOT IN adds this caveat?  Makes sense to me…

OR [Test].[dbo].[sp].[qty] IS NOT NULL

Try some of these experiments with IN and NOT IN, and NOT EXISTS and see what you can come up with.  I find that geeking with these peculiarities is a lot of fun.

Thanks for reading!

Lee

------------------------

“I haven't felt this awful since we saw that Ronald Reagan film.”

[1]  FFE Software (1998). The Exists Flaw. Retrieved 4/2/10 from http://firstsql.com/iexist2.htm