The use of NOT logic in relation to indexes

Question

According to Microsoft's book on database development Exam 70-433: Microsoft SQL Server 2008 Database Development:

Neither leading wildcard characters not NOT logic allow the query optimizer to use indexes to optimize the search. For optimal performance, you should avoid using the NOT keyword and leading wildcard symbols.

So I took that to be NOT IN, NOT EXISTS etc

Now with regards to this SO question, I thought that the chosen solution by @GBN would violate the statement given above.

Apparently, it does not.

So my question is: Why?

Answer 1

• NOT IN (SELECT ...) and NOT EXISTS (SELECT .. WHERE correlation..) are "Anti Semi Joins". That is, recognised set based operations

• WHERE NOT (MyColumn = 1) is a filter that requires all rows to be looked at

For more info, see:

• Craig Freedman's "Introduction to Joins"
• Wikipedia "Relational algebra, Antijoins"

Edit: for completeness

LEFT JOINs often perform worse. See http://explainextended.com/2009/09/15/not-in-vs-not-exists-vs-left-join-is-null-sql-server

This same site notes that in MySQL, NOT EXISTS isn't optimised like other RDBMS and LEFT JOIN is better

In SQL Server, I know from experience that LEFT JOIN doesn't run as well as NOT EXISTS. You also often need DISTINCT to get the same results which another processing step.

Answer 2

I use a sub-select for this:

SELECT m* from Main AS m 
    WHERE m.id NOT IN 
        (SELECT m2.id FROM Main AS m2 
           WHERE m2.id IN (...possibly null/empty list goes here...));

Of course if your table is big, you'll want to analyze this to check the performance. If you've got additional clauses filtering the results in the main query, you may need to duplicate them in the sub-select. But regardless, the sub-select has an "IN" vs a "NOT IN" and hence can have different size results and, usually, query performance matters, so analyze this approach when using with a big table.