The use of NOT logic in relation to indexes 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?
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.