Use More Than Density to Cost a Scan on the Inner Side of a Nested Loop with TOP
Consider a simple query of the following form:
FROM dbo.OUTER o
WHERE NOT EXISTS
FROM dbo.INNER i
WHERE o.ID = i.ID
Sometimes the query optimizer will implement the join as a left anti semi nested loop join
with a TOP operator applied to the scan on the dbo.INNER table. The row goal introduced
by TOP aggressively reduces the cost of the repeated scan on the dbo.INNER table.
The density of the table is used in the calculation to reduce the cost of the scan.
Using the density means that the query optimizer assumes that a matching row will
always be found and that the scan can always terminate early.
This can lead to performance issues when there are rows in the dbo.OUTER table that
do not have a matching row in the dbo.INNER table.
I run into this problem in my environment quite often and it can be incredibly difficult to explain to my developers why a seemingly simple query runs so slow.