The use of NOT logic in relation to indexes

• 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.