I’m looking at NOT EXISTS and LEFT OUTER JOIN, as opposed to NOT IN and LEFT OUTER JOIN, because, as shown in the previous part<\/a> of this series, NOT IN behaves badly in the presence of NULLs. Specifically, if there are any NULLs in the result set, NOT IN returns 0 matches.<\/p>\n The LEFT OUTER JOIN, like the NOT EXISTS can handle NULLs in the second result set without automatically returning no matches. It behaves the same regardless of whether the join columns are nullable or not. Seeing as NULL does not equal anything, any rows in the second result set that have NULL for the join column are eliminated by the join and have no further effect on the query.<\/p>\n It is important, when using the LEFT OUTER JOIN \u2026 IS NULL, to carefully pick the column used for the IS NULL check. It should either be a non-nullable column (the primary key is a somewhat classical choice) or the join column (as nulls in that will be eliminated by the join)<\/p>\n Onto the tests<\/p>\n The usual test tables\u2026<\/p>\n First without indexes<\/p>\n Let’s take a look at the execution plans<\/p>\n <\/p>\n The plans are almost the same. There’s an extra filter in the JOIN and the logical join types are different. Why the different joins?<\/p>\n If we look at the execution plan for the NOT EXISTS, the join type is Right Anti-Semi join (a bit of a mouthful). This is a special join type used by the NOT EXISTS and NOT IN and it’s the opposite of the semi-join that I discussed back when I looked at IN and INNER JOIN<\/a><\/p>\n An anti-semi join is a partial join. It does not actually join rows in from the second table, it simply checks for, in this case, the absence of matches. That’s why it’s an anti<\/strong>-semi join. A semi-join checks for matches, an anti-semi join does the opposite and checks for the absence of matches.<\/p>\n The extra filter in the LEFT OUTER JOIN query is because the join in that execution plan is a complete right join, i.e. it’s returned matching rows (and possibly duplicates) from the second table. The filter operator is doing the IS NULL filter.<\/p>\n That’s the major difference between these two. When using the LEFT OUTER JOIN \u2026 IS NULL technique, SQL can’t tell that you’re only doing a check for nonexistance. Optimiser’s not smart enough (yet). Hence it does the complete join and then filters. The NOT EXISTS filters as part of the join.<\/p>\n Technical discussion done, now how did they actually perform?<\/p>\n — Query 1: LEFT OUTER JOIN SQL Server Execution Times: — Query 2: NOT EXISTS SQL Server Execution Times: Can’t make a big deal out of that.<\/p>\n Now, index on the join columns<\/p>\n and the same queries<\/p>\n With indexes added, the execution plans are even more different. The LEFT OUTER JOIN is still doing the complete outer join with a filter afterwards. It’s interesting to note that it’s still a hash join, even though both inputs are sorted in the order of the join keys.<\/p>\n The Not Exists now has a stream aggregate (because duplicate values are irrelevant for an EXISTS\/NOT EXISTS) and an anti-semi join. The join here is no longer hash, it’s now a merge join.<\/p>\n\nCREATE TABLE BigTable (\nid INT IDENTITY PRIMARY KEY,\nSomeColumn char(4) NOT NULL,\nFiller CHAR(100)\n)\n\nCREATE TABLE SmallerTable (\nid INT IDENTITY PRIMARY KEY,\nLookupColumn char(4) NOT NULL,\nSomeArbDate Datetime default getdate()\n)\n\nINSERT INTO BigTable (SomeColumn)\nSELECT top 250000\nchar(65+FLOOR(RAND(a.column_id *5645 + b.object_id)*10)) + char(65+FLOOR(RAND(b.column_id *3784 + b.object_id)*12)) +\nchar(65+FLOOR(RAND(b.column_id *6841 + a.object_id)*12)) + char(65+FLOOR(RAND(a.column_id *7544 + b.object_id)*8))\nfrom master.sys.columns a cross join master.sys.columns b\n\nINSERT INTO SmallerTable (LookupColumn)\nSELECT DISTINCT SomeColumn\nFROM BigTable TABLESAMPLE (25 PERCENT)\n-- (3918 row(s) affected)\n<\/pre>\n
-- Query 1\nSELECT BigTable.ID, SomeColumn\n\tFROM BigTable LEFT OUTER JOIN SmallerTable ON BigTable.SomeColumn = SmallerTable.LookupColumn\n\tWHERE LookupColumn IS NULL\n\n-- Query 2\nSELECT ID, SomeColumn FROM BigTable\nWHERE NOT EXISTS (SELECT LookupColumn FROM SmallerTable WHERE SmallerTable.LookupColumn = BigTable.SomeColumn)\n<\/pre>\n
![\"LeftOuterJoinNotIN_NotIndexed\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2010\/03\/LeftOuterJoinNotIN_NotIndexed_thumb.png\" "\\"LeftOuterJoinNotIN_NotIndexed\\"")
<\/a><\/p>\n
\nTable ‘Worktable’. Scan count 0, logical reads 0, physical reads 0.
\nTable ‘BigTable’. Scan count 1, logical reads 3639, physical reads 0.
\nTable ‘SmallerTable’. Scan count 1, logical reads 15, physical reads 0.<\/p>\n
\nCPU time = 157 ms,\u00a0 elapsed time = 486 ms.<\/p>\n
\nTable ‘Worktable’. Scan count 0, logical reads 0, physical reads 0.
\nTable ‘BigTable’. Scan count 1, logical reads 3639, physical reads 0.
\nTable ‘SmallerTable’. Scan count 1, logical reads 15, physical reads 0.<\/p>\n
\nCPU time = 156 ms,\u00a0 elapsed time = 358 ms.<\/p><\/blockquote>\nCREATE INDEX idx_BigTable_SomeColumn\nON BigTable (SomeColumn)\n\nCREATE INDEX idx_SmallerTable_LookupColumn\nON SmallerTable (LookupColumn)<\/pre>\n
![\"LeftOuterJoinNotIN_Indexed\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2010\/03\/LeftOuterJoinNotIN_Indexed_thumb.png\" "\\"LeftOuterJoinNotIN_Indexed\\"")
<\/a><\/p>\n