Dec 272012
 

A pattern I see quite a bit, and wish that I didn't, is NOT IN. 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 (note that I'm using the enlarged header and detail tables from this script by Jonathan Kehayias (blog | @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:

loj_1

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:

    loj_5

    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:

    loj_2

    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:

    loj_3

    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:

    loj_4

    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:

    loj_1

    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, but simply to clarify intent: this subquery does not 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:

    loj_1

    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:

    loj_6

    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:

    LOJ_perf1

    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)

    loj_NOTIN_noindex

    OUTER APPLY

    loj_APPLY_noindex

    LEFT OUTER JOIN (all three were identical)

    loj_LOJ_noindex

    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:

    LOJ_perf2

    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.

  15 Responses to “Should I use NOT IN, OUTER APPLY, LEFT OUTER JOIN, EXCEPT, or NOT EXISTS?”

  1. Great article Aaron. I use the LEFT OUTER JOIN almost exclusively. My assumption was that the NOT EXISTS was creating a more cursor-like row-by-row comparison. I'll definitely be putting this to good use.

  2. Aaron,
    Extremely well-documented post. Even a n00b like me can 'get it'. I ran into just this sort of an issue last week where NOT IN produced a bad record set, probably based on NULLS, but I was time-pressed to fix the problem and never went back to see what the root cause was. I fixed it using EXCEPT as it was a little less wordy to code. Nice to know the performance implications around all of these methods. I will definitely use this in the future. Thanks for the article.

  3. Just curious..Why est rows for left join are 1?

    • The bad estimate in the LOJ case is coming from the filter. I think this happens for the same black box reasons that a UDF will estimate the row count at 1 – the optimizer can't see how many rows won't match the join because of the filter, so makes a swag. It makes a swag in the other direction, but a little farther off, with the non-outer join methods.

  4. Very clear explanation of the scenarios, thank you.

  5. the picture is beautiful, like Performance Results, how can u do it? what tools u use i want to know,thanks!

  6. The full ANSI/ISO Standard SQL has EXCEPT [ALL], INTERSECTION [ALL], as well as UNION [ALL]. As usual, MS is behind by a decade :)

    • Yes, Joe, it's true – SQL Server has not implemented the full standard. And – gasp – instead they have implemented a lot of features that customers have asked for but that the standard fails to provide. Let us all know when a major vendor provides an RDBMS that implements the standard, the whole standard, and nothing but the standard. :-)

    • Joe Celko
      The open source community is 2 decades behind MS and losing ground. The latest is "Eventually Concurrent" since MSSQL server is the only true ACID compliant database.

  7. Very well put and confirms my experience as well. Testing where the Outer Table is wide and the target column is not indexed makes a far more dramatic result.

  8. One of my "favorites" that I've actually seen used by developers in my company:

    SELECT CustomerID 
    FROM Sales.Customer AS c 
    WHERE (SELECT COUNT(*) FROM Sales.SalesOrderHeaderEnlarged 
    WHERE CustomerID = c.CustomerID) = 0;

    I rant and I rave every time I see this, but because the optimizer will sometimes process this as a NOT EXISTS, people think I'm exaggerating the issue.

  9. [...] I like to think that my skills are good but last week I read Aaron Bertrand’s (b | t) great post about the performance of outer joins versus other options such as not exists and I have decided [...]

  10. Most of the variants shown in this post should be collapsed by the optimizer into the best one. NOT-IN is a common requirement for a query, and many different clever and not so clever variants of this are being written every day. They should just all result in the same, optimal plan.

    • Yes, *should* is the key word there. Sadly we have to deal with an imperfect optimizer and understand its limitations.

 Leave a Reply

(required)

(required)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" cssfile="">