Should I use NOT IN, OUTER APPLY, LEFT OUTER JOIN, EXCEPT, or NOT EXISTS?

Let's say you want to find all the patients who have never had a flu shot. Or, in AdventureWorks2012, a similar question might be, "show me all of the customers who have never placed an order." Expressed using NOT IN, a pattern I see all too often, that would look something like this (I'm using the enlarged header and detail tables from this script by Jonathan Kehayias (@SQLPoolBoy)):

SELECT CustomerID 
FROM Sales.Customer 
WHERE CustomerID NOT IN 
(
  SELECT CustomerID 
  FROM Sales.SalesOrderHeaderEnlarged
);

When I see this pattern, I cringe. But not for performance reasons – after all, it creates a decent enough plan in this case:

The main problem is that the results can be surprising if the target column is NULLable (SQL Server processes this as a left anti semi join, but can't reliably tell you if a NULL on the right side is equal to – or not equal to – the reference on the left side). Also, optimization can behave differently if the column is NULLable, even if it doesn't actually contain any NULL values (Gail Shaw talked about this back in 2010).

In this case, the target column is not nullable, but I wanted to mention those potential issues with NOT IN – I may investigate these issues more thoroughly in a future post.

TL;DR version

Instead of NOT IN, use a correlated NOT EXISTS for this query pattern. Always. Other methods may rival it in terms of performance, when all other variables are the same, but all of the other methods introduce either performance problems or other challenges.

Alternatives

So what other ways can we write this query?

OUTER APPLY

One way we can express this result is using a correlated OUTER APPLY.

SELECT c.CustomerID 
FROM Sales.Customer AS c
OUTER APPLY 
(
 SELECT CustomerID 
   FROM Sales.SalesOrderHeaderEnlarged
   WHERE CustomerID = c.CustomerID
) AS h
WHERE h.CustomerID IS NULL;

Logically, this is also a left anti semi join, but the resulting plan is missing the left anti semi join operator, and seems to be quite a bit more expensive than the NOT IN equivalent. This is because it is no longer a left anti semi join; it is actually processed in a different way: an outer join brings in all matching and non-matching rows, and *then* a filter is applied to eliminate the matches:



LEFT OUTER JOIN

A more typical alternative is LEFT OUTER JOIN where the right side is NULL. In this case the query would be:

SELECT c.CustomerID 
FROM Sales.Customer AS c
LEFT OUTER JOIN Sales.SalesOrderHeaderEnlarged AS h
ON c.CustomerID = h.CustomerID
WHERE h.CustomerID IS NULL;

This returns the same results; however, like OUTER APPLY, it uses the same technique of joining all the rows, and only then eliminating the matches:



You need to be careful, though, about what column you check for NULL. In this case CustomerID is the logical choice because it is the joining column; it also happens to be indexed. I could have picked SalesOrderID, which is the clustering key, so it is also in the index on CustomerID. But I could have picked another column that is not in (or that later gets removed from) the index used for the join, leading to a different plan. Or even a NULLable column, leading to incorrect (or at least unexpected) results, since there is no way to differentiate between a row that doesn't exist and a row that does exist but where that column is NULL. And it may not be obvious to the reader / developer / troubleshooter that this is the case. So I will also test these three WHERE clauses:

WHERE h.SalesOrderID IS NULL; -- clustered, so part of index

WHERE h.SubTotal IS NULL; -- not nullable, not part of the index

WHERE h.Comment IS NULL; -- nullable, not part of the index

The first variation produces the same plan as above. The other two choose a hash join instead of a merge join, and a narrower index in the Customer table, even though the query ultimately ends up reading the exact same number of pages and amount of data. However, while the h.SubTotal variation produces the correct results:



The h.Comment variation does not, since it includes all of the rows where h.Comment IS NULL, as well as all of the rows that did not exist for any customer. I've highlighted the subtle difference in the number of rows in the output after the filter is applied:



In addition to needing to be careful about column selection in the filter, the other problem I have with the LEFT OUTER JOIN form is that it is not self-documenting, in the same way that an inner join in the "old-style" form of FROM dbo.table_a, dbo.table_b WHERE ... is not self-documenting. By that I mean it is easy to forget the join criteria when it is pushed to the WHERE clause, or for it to get mixed in with other filter criteria. I realize this is quite subjective, but there it is.

EXCEPT

If all we are interested in is the join column (which by definition is in both tables), we can use EXCEPT – an alternative that doesn't seem to come up much in these conversations (probably because – usually – you need to extend the query in order to include columns you're not comparing):

SELECT CustomerID 
FROM Sales.Customer AS c 
EXCEPT
SELECT CustomerID
FROM Sales.SalesOrderHeaderEnlarged;

This comes up with the exact same plan as the NOT IN variation above:



One thing to keep in mind is that EXCEPT includes an implicit DISTINCT – so if you have cases where you want multiple rows having the same value in the "left" table, this form will eliminate those duplicates. Not an issue in this specific case, just something to keep in mind – just like UNION versus UNION ALL.

NOT EXISTS

My preference for this pattern is definitely NOT EXISTS:

SELECT CustomerID 
FROM Sales.Customer AS c 
WHERE NOT EXISTS 
(
  SELECT 1 
    FROM Sales.SalesOrderHeaderEnlarged 
    WHERE CustomerID = c.CustomerID
);

(And yes, I use SELECT 1 instead of SELECT * … not for performance reasons, since SQL Server doesn't care what column(s) you use inside EXISTS and optimizes them away, but simply to clarify intent: this reminds me that this "subquery" does not actually return any data.)

Its performance is similar to NOT IN and EXCEPT, and it produces an identical plan, but is not prone to the potential issues caused by NULLs or duplicates:



Performance Tests

I ran a multitude of tests, with both a cold and warm cache, to validate that my long-standing perception about NOT EXISTS being the right choice remained true. The typical output looked like this:



I'll take the incorrect result out of the mix when showing the average performance of 20 runs on a graph (I only included it to demonstrate how wrong the results are), and I did execute the queries in different order across tests to make sure that one query was not consistently benefitting from the work of a previous query. Focusing on duration, here are the results:



If we look at duration and ignore reads, NOT EXISTS is your winner, but not by much. EXCEPT and NOT IN aren’t far behind, but again you need to look at more than performance to determine whether these options are valid, and test in your scenario.

What if there is no supporting index?

The queries above benefit, of course, from the index on Sales.SalesOrderHeaderEnlarged.CustomerID. How do these results change if we drop this index? I ran the same set of tests again, after dropping the index:

DROP INDEX [IX_SalesOrderHeaderEnlarged_CustomerID] 
ON [Sales].[SalesOrderHeaderEnlarged];

This time there was much less deviation in terms of performance between the different methods. First I'll show the plans for each method (most of which, not surprisingly, indicate the usefulness of the missing index we just dropped). Then I'll show a new graph depicting the performance profile both with a cold cache and a warm cache.

NOT IN, EXCEPT, NOT EXISTS (all three were identical)



OUTER APPLY



LEFT OUTER JOIN (all three were identical except for the number of rows)



Performance Results

We can immediately see how useful the index is when we look at these new results. In all but one case (the left outer join that goes outside the index anyway), the results are clearly worse when we've dropped the index:



So we can see that, while there is less noticeable impact, NOT EXISTS is still your marginal winner in terms of duration. And in situations where the other approaches are susceptible to schema volatility, it is your safest choice, too.

Conclusion

This was just a really long-winded way of telling you that, for the pattern of finding all rows in table A where some condition does not exist in table B, NOT EXISTS is typically going to be your best choice. But, as always, you need to test these patterns in your own environment, using your schema, data and hardware, and mixed in with your own workloads.