SQL in the Wild

And to wrap up the miniseries on IN, EXISTS and JOIN, a look at NOT EXISTS and LEFT OUTER JOIN for finding non-matching rows.

For previous parts, see

• In vs Exists
• In vs Inner Join
• Not in vs Not Exists

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

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.

It is important, when using the LEFT OUTER JOIN … 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)

Onto the tests

The usual test tables…

CREATE TABLE BigTable (
id INT IDENTITY PRIMARY KEY,
SomeColumn char(4) NOT NULL,
Filler CHAR(100)
)

CREATE TABLE SmallerTable (
id INT IDENTITY PRIMARY KEY,
LookupColumn char(4) NOT NULL,
SomeArbDate Datetime default getdate()
)

INSERT INTO BigTable (SomeColumn)
SELECT top 250000
char(65+FLOOR(RAND(a.column_id *5645 + b.object_id)*10)) + char(65+FLOOR(RAND(b.column_id *3784 + b.object_id)*12)) +
char(65+FLOOR(RAND(b.column_id *6841 + a.object_id)*12)) + char(65+FLOOR(RAND(a.column_id *7544 + b.object_id)*8))
from master.sys.columns a cross join master.sys.columns b

INSERT INTO SmallerTable (LookupColumn)
SELECT DISTINCT SomeColumn
FROM BigTable TABLESAMPLE (25 PERCENT)
-- (3918 row(s) affected)

First without indexes

-- Query 1
SELECT BigTable.ID, SomeColumn
	FROM BigTable LEFT OUTER JOIN SmallerTable ON BigTable.SomeColumn = SmallerTable.LookupColumn
	WHERE LookupColumn IS NULL

-- Query 2
SELECT ID, SomeColumn FROM BigTable
WHERE NOT EXISTS (SELECT LookupColumn FROM SmallerTable WHERE SmallerTable.LookupColumn = BigTable.SomeColumn)

Let’s take a look at the execution plans

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?

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

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-semi join. A semi-join checks for matches, an anti-semi join does the opposite and checks for the absence of matches.

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.

That’s the major difference between these two. When using the LEFT OUTER JOIN … 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.

Technical discussion done, now how did they actually perform?

– Query 1: LEFT OUTER JOIN
Table ‘Worktable’. Scan count 0, logical reads 0, physical reads 0.
Table ‘BigTable’. Scan count 1, logical reads 3639, physical reads 0.
Table ‘SmallerTable’. Scan count 1, logical reads 15, physical reads 0.

SQL Server Execution Times:
CPU time = 157 ms,  elapsed time = 486 ms.

– Query 2: NOT EXISTS
Table ‘Worktable’. Scan count 0, logical reads 0, physical reads 0.
Table ‘BigTable’. Scan count 1, logical reads 3639, physical reads 0.
Table ‘SmallerTable’. Scan count 1, logical reads 15, physical reads 0.

SQL Server Execution Times:
CPU time = 156 ms,  elapsed time = 358 ms.

Can’t make a big deal out of that.

Now, index on the join columns

CREATE INDEX idx_BigTable_SomeColumn
ON BigTable (SomeColumn)

CREATE INDEX idx_SmallerTable_LookupColumn
ON SmallerTable (LookupColumn)

and the same queries

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.

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.

This echoes what I found when looking at IN vs Inner join. When the columns were indexed, the inner join still went for a hash join but the IN changed to a merge join. At the time, I thought it to be a fluke, I’m not so sure any longer. More tests on this are required…

The costing of the plans indicates that the optimiser believes that the LEFT OUTER JOIN form is more expensive. Do the execution stats carry the same conclusion?

– Query 1: LEFT OUTER JOIN
Table ‘Worktable’. Scan count 0, logical reads 0, physical reads 0.
Table ‘BigTable’. Scan count 1, logical reads 342, physical reads 0.
Table ‘SmallerTable’. Scan count 1, logical reads 8, physical reads 0.

SQL Server Execution Times:
CPU time = 172 ms,  elapsed time = 686 ms.

– Query 2: NOT EXISTS
Table ‘BigTable’. Scan count 1, logical reads 342, physical reads 0.
Table ‘SmallerTable’. Scan count 1, logical reads 8, physical reads 0.

SQL Server Execution Times:
CPU time = 78 ms,  elapsed time = 388 ms.

Well, yes, they do.

The reads (ignoring the existence of the worktable for the hash join) are the same. That’s to be expected, both queries executed with a single scan of each index.

The CPU time figures are not. The CPU time of the LEFT OUTER JOIN form is almost twice that of the NOT EXISTS.

In conclusion…

If you need to find rows that don’t have a match in a second table, and the columns are nullable, use NOT EXISTS. If you need to find rows that don’t have a match in a second table, and the columns are not nullable, use NOT EXISTS or NOT IN.

The LEFT OUTER JOIN … IS NULL method is slower when the columns are indexed and it’s perhaps not as clear what’s happening. It’s reasonably clear what a NOT EXISTS predicate does, with LEFT OUTER JOIN it’s not immediately clear that it’s a check for non-matching rows, especially if there are several where clause predicates.

I think that’s about that for this series. I’m going to do one more post summarising all the findings, probably in a week or two.