Since it is a longstanding production SQL Server I can't easily suggest to upgrade versions
The anti semi join cardinality estimation bug is reproducible on all versions of SQL Server from 2005 to 2012 inclusive. All require trace flag 4199 to enable the fix, so upgrading would not solve your problem without activating 4199 (though there are many other good reasons to upgrade from 2005, of course).
...as such I cannot force the traceflag 4199 hint on this specific query.
If it is just one particular query that is affected, you can use OPTION (QUERYTRACEON 4199) to enable the trace flag for just that query. This query hint is documented and supported for use with 4199, and applies from SQL Server 2005 Service Pack 2 onward.
This hint effectively runs DBCC TRACEON (4199) and DBCC TRACEOFF (4199) around the query, and requires sysadmin permission as a result. If that is a problem, add the hint using a plan guide.
You should also look at testing your whole system with 4199 enabled instance-wide. Plan regressions are possible, but overall you may find that the various optimizer fixes enabled by this flag are well worth it. All future plan-affecting query processor fixes require this flag to activate.
All that said...
As mentioned in ypercube's answer, the bug requires two or more join columns to manifest (among many details). The redundancy in your NOT IN clause causes the optimizer to see two column comparisons (though logically there is only one), thereby exposing the bug.
Removing this redundancy will 'solve' the problem for this particular query, though other queries that really do have more than one join predicate will still be vulnerable.
Example
To illustrate, here is an example based on the CSS blog post linked in the question (but with a complete script!):
CREATE TABLE dbo.tst_TAB1
(
c1 integer NOT NULL,
c2 integer NOT NULL,
c3 integer NOT NULL
);
CREATE TABLE dbo.tst_TAB2
(
c1 integer NOT NULL,
c2 integer NOT NULL,
c3 integer NOT NULL
);
CREATE INDEX i ON dbo.tst_TAB1 (c1, c2);
CREATE INDEX i ON dbo.tst_TAB2 (c1, c2);
Sample data:
INSERT dbo.tst_TAB1
(c1, c2, c3)
SELECT
number, number, number
FROM master.dbo.spt_values
WHERE
[type] = N'P'
AND number BETWEEN 1 AND 2047;
INSERT dbo.tst_TAB2 (c1, c2, c3)
VALUES (1, 1, 1);
Test query using NOT IN with redundant predicate:
SELECT
T1.c1
FROM tst_TAB1 AS t1
WHERE
t1.c1 NOT IN
(
SELECT
t2.c1
FROM tst_TAB2 AS t2
-- This is redundant!
WHERE
t2.c1 = t1.c1
);
The estimated execution plan shows an estimate of 1 row after the anti semi join:
Side note: In fact this is an example of another (rare) bug. Writing the WHERE clause as t1.c1 = t2.c1 instead of t2.c1 = t1.c1 allows the optimizer to see that the two join predicates are in fact the same, and the bug does not manifest.
The same query with OPTION (QUERYTRACEON 4199):
SELECT
T1.c1
FROM tst_TAB1 AS t1
WHERE
t1.c1 NOT IN
(
SELECT
t2.c1
FROM tst_TAB2 AS t2
WHERE
t2.c1 = t1.c1
)
OPTION (QUERYTRACEON 4199);
The estimated execution plan now shows an estimate of 2046 rows, which is exactly right:
We can also remove the redundant predicate:
SELECT
T1.c1
FROM tst_TAB1 AS t1
WHERE
t1.c1 NOT IN
(
SELECT
t2.c1
FROM tst_TAB2 AS t2
);
The execution plan happens to use an additional unrelated optimization (the Stream Aggregate), but the important point is that the post-join estimate is correct without having to enable 4199:
Multiple anti semi join columns
It is possible to express an anti semi join over multiple columns using NOT IN syntax. These cases will require 4199. For example, the next query joins on c1 and c2:
SELECT
T1.c1
FROM tst_TAB1 AS t1
WHERE
t1.c1 NOT IN
(
SELECT
t2.c1
FROM tst_TAB2 AS t2
WHERE
t2.c2 = t1.c2
);
The execution plan shows the erroneous 1-row estimate:
With 4199, the issue is resolved:
SELECT
T1.c1
FROM tst_TAB1 AS t1
WHERE
t1.c1 NOT IN
(
SELECT
t2.c1
FROM tst_TAB2 AS t2
WHERE
t2.c2 = t1.c2
)
OPTION (QUERYTRACEON 4199);
Other syntaxes
Using NOT IN in this way is best avoided, not least for the reasons mentioned in Books Online:
That issue with NOT IN and NULLs has been written about many times. There are many alternative syntaxes available, of which NOT EXISTS is my personal preference. Note that changing syntax will not avoid the cardinality estimation bug:
SELECT
T1.c1
FROM dbo.tst_TAB1 AS t1
WHERE
NOT EXISTS
(
SELECT 1
FROM dbo.tst_TAB2 AS t2
WHERE
t2.c1 = t1.c1
AND t2.c2 = t1.c2
);
That two column anti semi join produces the 1-row estimate, and requires 4199 to fix it. The execution plans are exactly the same as seen previously, so I will not repeat them. The NOT EXISTS syntax does avoid the NULLs issue with NOT IN.
Other observations
I agree with ypercube's other observations.
Sprinkling NOLOCK hints over every table in a query is a bad code smell. If the query can truly tolerate READ UNCOMMITTED transaction semantics, set the isolation level explicitly.
TOP without ORDER BY is another sign of poor code. TOP requires an ORDER BY clause to define what TOP means. Never rely on observed behaviour, use an explicit top-level ORDER BY to obtain a guarantee.
INNER LOOP JOIN and join hints in general, imply a FORCE ORDER query hint. This severely limits the optimizer's freedom, and is usually misunderstood and misapplied. Never use hints that you don't fully understand.
