I believe the answer to this lies in the contradiction removal of the optimizer.

Consider these two queries based on the same data

SELECT  PeopleID,
Low,
High
FROM    dbo.Guesses
WHERE  High NOT IN(SELECT Value FROM dbo.Result)

go
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE  High NOT IN(SELECT Value FROM dbo.Result WHERE Value <> High)

With the Second (using Value <> High) , the execution plan contains no mention on the Result table at all.

So if we break down the 'double-negative' of the predicate, we can see that the not in condition will always be True since the only value that could cause it to be true (HIGH) is explicitly not being returned.

The rest is down to extrapolation.

Its magic... :)

Query 1 and Query 3 are actually have different meanings... In general they will not return the same data. But in this context, they will give same results. Because we deleted dual hits........ By removing dual hits, we ensured that there will not be any rows in Guesses table, where both Low and High of a row exists in results table.

In query1, the where condition is looks like this..

( Low IN(SELECT Value FROM dbo.Result) AND High NOT IN(SELECT Value FROM dbo.Result)) 
OR
(Low NOT IN (SELECT Value FROM dbo.Result) AND High IN(SELECT Value FROM dbo.Result))

But this is not required, as we deleted dual hit rows. So, the below condition enough is going to be give us the required output..

Low IN(SELECT Value FROM dbo.Result) or High IN(SELECT Value FROM dbo.Result)

In query1, the other 2 conditions are making the query engine to believe that there are dual hit rows, its performing clustered index seek for all 4 conditions. By adding the 2dummy conditions, Value <> High and Value <> Low , which makes the below conditions useless....

High NOT IN (SELECT Value FROM dbo.Result where Value <> High)
Low NOTIN (SELECT Value FROM dbo.Result where Value <> Low)

adding that 2 conditions , will makes the subquery always returns empty rows... so, the query will become like

Low IN(SELECT Value FROM dbo.Result) or High IN(SELECT Value FROM dbo.Result)

Optimizer here will understand that they are 2 dummy conditions and it will not evaluate that 2 conditions, which evaluates other 2 conditions only............... So, this query performs fast.

In summary, Initiaally, out table has data in such a way that dual hits never going to occur. But in query1, we will try to check for dual hit rows, so, it evaluate for all 4 conditions.

In query3, we gave the hint to optimizer by adding that 2 Not equal statements, inturn making them dummy, so, optimizer will evalualte 2 conditions only..

This is Magic... But if we didn't delete the dual hit rows initially, The query1 and query3 will give different results.

Now coming to question of handling nulls between Not In and Not Exists

Basic difference is "Not In" Clause will exclude nulls from Source Table, while "Not exists" will include NULLs. One disadvantage of "Not in" clause is, if the table we are checking for values contains null values, it will not return any row as output.

See this example:

create table Vals(ID int)
insert into Vals values(10),(20),(null)
create table Lookups(ID int)
insert into Lookups values (20),(30),(null)
-- First query returns No results
select * from Vals v where Id not in (select ID from Lookups)
-- Second query returns 2 records
select * from Vals v where not exists (select * from Lookups where ID = v.ID)

The Reason for this behaviour is as follows.

While evaluating "Not In " query, Engine will do the "Left Anti Semi Join", with Match predicate "SourceValue is null or DestinationValue is null or sourcevalue = destinationvalue"

Converting into algorithm,(This is not the way query executed, just for understanding)

foreach input in source table
begin
 foreach input is destination table
 begin 
  declare @Counter int = 0 
  if(source input is null or destination input is null or source input = destination input)
  begin
   set @Counter = @Counter + 1;
   break;  // Go out of the outer for loop.
  end
 end
 if(@Counter = 0)
  // add the result to output rowset. 
end

Coming to execution,

In First Iteration, 10 is compared with (20,30,null), as destination input is null, it will increases counter and go out.

as the counter is 1, 10 will not be added to output resultset.

In First Iteration, 20 is compared with (20,30,null), as 20 is matches with 20, it will increases counter and go out.

as the counter is 1, 20 will not be added to output resultset.

In First Iteration, null is compared with (20,30,null), as source input is null, it will increases counter and go out.

as the counter is 1, null will not be added to output resultset.

So, First query didn't return any results.

Now coming to second query, main difference is Match predicate is only "source value = destination value", while follows the same Left Anti Semi join

Converting into algorithm,(This is not the way query executed, just for understanding)

foreach input in source table
begin
 foreach input is destination table
 begin 
  declare @Counter int = 0 
  if(source input = destination input)
  begin
   set @Counter = @Counter + 1;
   break;  // Go out of the outer for loop.
  end
 end
 if(@Counter = 0)
  // add the result to output rowset. 
end

Coming to execution,

In First Iteration, 10 is compared with (20,30,null), as No value is matches with 10, it will finish inner for loop and go out.

as the counter is 0, 10 will be added to output resultset.

In First Iteration, 20 is compared with (20,30,null), as 20 is matches with 20, it will increases counter and go out.

as the counter is 1, 20 will not be added to output resultset.

In First Iteration, null is compared with (20,30,null), as NULL is not equals to null(but remember null is null. but null is not

equals null),it will finish inner for loop and go out.

as the counter is 0, null will be added to output resultset.

So, Second query returns 2 rows. (10 and null)

Finally I will tell its our friend............ :) we are fooling it.............. (ofcourse, some times its fools us also). Friends always fool each other.. :)

How come adding the ‘not equal to filter’ made such a difference in performance for Query3 vs Query1?

The very simple answer is that Query1 and Query3 are not equivalent. It is easy to be fast if you dont need to be correct...

Query3 looks like this:

SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   (
            Low IN(SELECT Value FROM dbo.Result)
            AND 
            High NOT IN(SELECT Value FROM dbo.Result WHERE Value <> High)
        )
        OR
        (
            Low NOT IN(SELECT Value FROM dbo.Result WHERE Value <> Low)
            AND 
            High IN(SELECT Value FROM dbo.Result)
        )

This is actually eqivalent to

SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   
        Low IN(SELECT Value FROM dbo.Result)
        OR
        High IN(SELECT Value FROM dbo.Result)

which is a much easier query than Query1

The only reason Query1 and Query3 returns the same data in this case is because you have deleted "duplicate hits" from the guesses table. If you remove the deletion of duplicate hits you will see clearly that Query1 and Query3 are not equivalent. The number of returned rows will be different.

The interesting thing is that the optimizer is good enough to realize that the condition High NOT IN(SELECT Value FROM dbo.Result WHERE Value <> High) is always true and can be removed.

To see that this is the case look at the inverted condition:

High IN(SELECT Value FROM dbo.Result WHERE Value <> High)

It is obvious that High can not be present in the set of values returned from Result WHERE Value<>High, so this condition is always false.

This means that NOT High IN(SELECT Value FROM dbo.Result WHERE Value <> High) is always true.

A better question is actually why Query2 is so much more efficient than Query1. These queries are completely equivalent so ideally they should result in the same execution plan.

Query 1 and 3 are not identical, since Q1 will exclude duplicate hits whereas D3 will include duplicates, if present.

Since the two queries are not identical in terms of result set under various conditions (e.g. including duplicates) and just return the same data because of the forced removal of duplicates the difference is not caused by the ‘not equal to filter’ but rather by the easier query (no double check for duplicates).

My best guess is that when you put in the additional clause inside the inner query, the “Not IN” clause need not run as inner query will never return any value that is equal to the outer predicate. Normally, “Not In” clause is very expensive as it has to completely run the inner query and then compare with the value of the outer query to see if that specific record should be returned or not. It is not very efficient set operation to get this process run one by one record.

Explain the difference between NOT EXISTS and NOT IN regarding NULL values.

NOT EXISTS will not be affected by the existance of NULL values in the result of the inner query because NOT EXISTS cares about the existance of at least one row that satisfy the conditions (equality in this case).

On the other hand NOT IN will be affected by the existance of NULL values in the result of the inner query because NOT IN cares about assuring that none of the values that returned equal the outer value, and in case of existance of NULL value then we can't assure that, and the the result would be either false or unknown for all outer query rows, hence empty result.

We can put that under test through this example:

SELECT T1.value
  FROM (VALUES(1)) AS T1(value)
 WHERE value NOT IN(SELECT T2.value
                      FROM (VALUES(2), (NULL)) AS T2(value))

SELECT T1.value
  FROM (VALUES(1)) AS T1(value)
 WHERE NOT EXISTS(SELECT T2.value
                    FROM (VALUES(2), (NULL)) AS T2(value)
                   WHERE T2.value = T1.value)

The results confirm that the first query (NOT IN) returned empty result, while the the second query (NOT EXISTS) returned one row of value 1.

How come adding the 'not equal to filter' made such a difference in performance for Query3 vs Query1?

Adding the 'not equal to filter' to the inner query of NOT IN makes that inner query useless because it will not be possible to get a value that will affects on the result of the outer query. Even NULL value will not affects on the result. To but this under test we can modify the previous script to be:

SELECT T1.value
  FROM (VALUES(1)) AS T1(value)
 WHERE value NOT IN(SELECT T2.value
                      FROM (VALUES(2), (NULL)) AS T2(value)
                     WHERE T2.value <> T1.value)

The results confirm that adding the 'not equal to filter' changed the result from an empty result to one row result of 1 value (same result of NOT EXISTS) because NOT IN was removed by the optimizer.

So as you said SQL Server Query Optimizer is a truly amazing piece of software.

Question #2 (In answer screen): Explain the difference between NOT EXISTS and NOT IN regarding NULL values.

Answering this first becuase the answer is shorter.

NOT IN evaluates its correlation on the single column of the SELECT clause and additional optional coluns in its WHERE clause. NOT EXISTS evaluates correlation only in the subquery's WHERE clause and the SELECT clause is completely ignored. NULLs being spewed in the NOT IN()'s SELECT are evaluated as <>, and NULLs fail the check. With NOT EXISTS(), it don't matter what gets spewed in the SELECT because it its ignored, but the correlation in the WHERE will still be affected by NULLs (comparing with them yields 'UNKNOWN' which is not 'TRUE' or 'FALSE' that = or <> expects)

Question #1 (Question details screen): How come adding the ‘not equal to filter’ made such a difference in performance for Query3 vs Query1?

Query # 1 activated a short-cut code branch in the optimizer. It caused it to jumpto conclusions when it saw the valid use of a fully covering (clustered) fully distinct (primary key) index. This is actually a bad decision in this scenario. The code semantics in Query #3 spoiled that short-cut so the optimizer went into full optimization with that query and produced a better plan.

Proof of the amount of effort spent in optimization can be obtained by running this and looking at the 'SQL Server parse and compile time' output above the '(## row(s) affected)'. Query #3's parse and compile time is triple that of Query #1.

SET STATISTICS TIME ON

DBCC FREEPROCCACHE
GO

--Query 1
SELECT PeopleID, Low, High
FROM dbo.Guesses
WHERE
    (
        Low IN(SELECT Value FROM dbo.Result)
        AND High NOT IN(SELECT Value FROM dbo.Result)
    )
    OR (
        Low NOT IN(SELECT Value FROM dbo.Result)
        AND High IN(SELECT Value FROM dbo.Result)
    )
OPTION (MAXDOP 1)

DBCC FREEPROCCACHE
GO
--Query 3
SELECT PeopleID, Low, High
FROM dbo.Guesses
WHERE
    (
        Low IN(SELECT Value FROM dbo.Result)
        AND High NOT IN(SELECT Value FROM dbo.Result WHERE Value <> High)
    )
    OR
    (
        Low NOT IN(SELECT Value FROM dbo.Result WHERE Value <> Low)
        AND High IN(SELECT Value FROM dbo.Result)
    )
OPTION (MAXDOP 1)

I added another version of the query and ran 5 of them first without adding extra indexes:

set statistics io on
--Query 1
SELECT  PeopleID,
Low,
High
FROM    dbo.Guesses
WHERE   (
Low IN(SELECT Value FROM dbo.Result)
AND High NOT IN(SELECT Value FROM dbo.Result)
)
OR
(
Low NOT IN(SELECT Value FROM dbo.Result)
AND High IN(SELECT Value FROM dbo.Result)
)
print 'Number of records Query1: ' + cast(@@Rowcount as varchar(20))
--Query2
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   Low IN(SELECT Value FROM dbo.Result)
AND High NOT IN(SELECT Value FROM dbo.Result)

UNION

SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   Low NOT IN(SELECT Value FROM dbo.Result)
AND High IN(SELECT Value FROM dbo.Result)
print 'Number of records Query2: ' + cast(@@Rowcount as varchar(20))
--Query3
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   (
            Low IN(SELECT Value FROM dbo.Result)
AND High NOT IN(SELECT Value FROM dbo.Result WHERE Value <> High)
)
OR
(
            Low NOT IN(SELECT Value FROM dbo.Result WHERE Value <> Low)
AND High IN(SELECT Value FROM dbo.Result)
)
print 'Number of records Query3: ' + cast(@@Rowcount as varchar(20))
--Query 4
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   Low IN(SELECT Value FROM dbo.Result WHERE Value <> High)
OR High IN(SELECT Value FROM dbo.Result WHERE Value <> Low)
print 'Number of records Query4: ' + cast(@@Rowcount as varchar(20))
-- Naomi's versions
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses G
inner Join dbo.Result R
on G.Low = R.Value and not exists (select 1 from dbo.Result R1 where G.High = R1.Value) 
UNION ALL 
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses G
inner Join dbo.Result R
on G.High = R.Value and not exists (select 1 from dbo.Result R1 where G.Low = R1.Value)

print 'Number of records Naomi''s version: ' + cast(@@Rowcount as varchar(20))

And I got these results:

Table 'Result'. Scan count 0, logical reads 2994632, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Guesses'. Scan count 9, logical reads 1574, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Number of records Query1: 1986
Table 'Result'. Scan count 4, logical reads 8, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Guesses'. Scan count 18, logical reads 3148, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Number of records Query2: 1986
Table 'Result'. Scan count 2, logical reads 4, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Guesses'. Scan count 18, logical reads 3094, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Number of records Query3: 1987
Table 'Result'. Scan count 2, logical reads 4, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Guesses'. Scan count 18, logical reads 3094, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Number of records Query4: 1987
Table 'Result'. Scan count 4, logical reads 8, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Guesses'. Scan count 18, logical reads 3148, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Number of records Naomi's version: 1986

As you see from the above, query 3 and 4 returned wrong number of records (I commented out the dual hits removal), so they should not be even considered - they are not equivalent of the original query. So, I eliminated queries 3 and 4 from the consideration (as not valid) and ran another test:

set statistics io on
--Query 1

SELECT  PeopleID,
Low,
High
FROM    dbo.Guesses
WHERE   (
Low IN(SELECT Value FROM dbo.Result)
AND High NOT IN(SELECT Value FROM dbo.Result)
)
OR
(
Low NOT IN(SELECT Value FROM dbo.Result)
AND High IN(SELECT Value FROM dbo.Result)
)
print 'Number of records Query1: ' + cast(@@Rowcount as varchar(20))
--Query2
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   Low IN(SELECT Value FROM dbo.Result)
AND High NOT IN(SELECT Value FROM dbo.Result)

UNION

SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   Low NOT IN(SELECT Value FROM dbo.Result)
AND High IN(SELECT Value FROM dbo.Result)
print 'Number of records Query2: ' + cast(@@Rowcount as varchar(20))
/*
--Query3
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   (
            Low IN(SELECT Value FROM dbo.Result)
AND High NOT IN(SELECT Value FROM dbo.Result WHERE Value <> High)
)
OR
(
            Low NOT IN(SELECT Value FROM dbo.Result WHERE Value <> Low)
AND High IN(SELECT Value FROM dbo.Result)
)
print 'Number of records Query3: ' + cast(@@Rowcount as varchar(20))
--Query 4
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   Low IN(SELECT Value FROM dbo.Result WHERE Value <> High)
OR High IN(SELECT Value FROM dbo.Result WHERE Value <> Low)
print 'Number of records Query4: ' + cast(@@Rowcount as varchar(20))
*/
-- Naomi's versions
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses G
inner Join dbo.Result R
on G.Low = R.Value and not exists (select 1 from dbo.Result R1 where G.High = R1.Value) 
UNION ALL 
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses G
inner Join dbo.Result R
on G.High = R.Value and not exists (select 1 from dbo.Result R1 where G.Low = R1.Value)
print 'Number of records Naomi''s version: ' + cast(@@Rowcount as varchar(20))

And I got the following results.

Table 'Result'. Scan count 0, logical reads 2994632, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Guesses'. Scan count 9, logical reads 1574, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Number of records Query1: 1986
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Guesses'. Scan count 40, logical reads 126, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Result'. Scan count 4, logical reads 8, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Number of records Query2: 1986
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Guesses'. Scan count 40, logical reads 126, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Result'. Scan count 4, logical reads 8, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Number of records Naomi's version: 1986

As we see, the original query still performed very poor, but the other 2 queries benefited from the new indexes greatly.

To get the idea which version (version 2 or my new version) performed better, I ran only last 2 queries: and got 55% vs. 45% result (so my query performed slightly better).

Finally, there is no need to use UNION since we can use UNION ALL in the second query. I re-wrote the query to use UNION ALL and also added an exists version and now I got identical results for all 3 queries:

--Query 1

SELECT  PeopleID,
Low,
High
FROM    dbo.Guesses
WHERE   (
Low IN(SELECT Value FROM dbo.Result)
AND High NOT IN(SELECT Value FROM dbo.Result)
)
OR
(
Low NOT IN(SELECT Value FROM dbo.Result)
AND High IN(SELECT Value FROM dbo.Result)
)
print 'Number of records Query1: ' + cast(@@Rowcount as varchar(20))
--Query2
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   Low IN(SELECT Value FROM dbo.Result)
AND High NOT IN(SELECT Value FROM dbo.Result)

UNION ALL

SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   Low NOT IN(SELECT Value FROM dbo.Result)
AND High IN(SELECT Value FROM dbo.Result)
print 'Number of records Query2: ' + cast(@@Rowcount as varchar(20))
/*
--Query3
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   (
            Low IN(SELECT Value FROM dbo.Result)
AND High NOT IN(SELECT Value FROM dbo.Result WHERE Value <> High)
)
OR
(
            Low NOT IN(SELECT Value FROM dbo.Result WHERE Value <> Low)
AND High IN(SELECT Value FROM dbo.Result)
)
print 'Number of records Query3: ' + cast(@@Rowcount as varchar(20))
--Query 4
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   Low IN(SELECT Value FROM dbo.Result WHERE Value <> High)
OR High IN(SELECT Value FROM dbo.Result WHERE Value <> Low)
print 'Number of records Query4: ' + cast(@@Rowcount as varchar(20))
*/
-- Naomi's versions
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses G
inner Join dbo.Result R
on G.Low = R.Value and not exists (select 1 from dbo.Result R1 where G.High = R1.Value) 
UNION ALL 
SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses G
inner Join dbo.Result R
on G.High = R.Value and not exists (select 1 from dbo.Result R1 where G.Low = R1.Value)
print 'Number of records Naomi''s version: ' + cast(@@Rowcount as varchar(20))


SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   exists (select 1 FROM dbo.Result where Value = Guesses.Low)
AND not exists(SELECT 1 FROM dbo.Result where Value = Guesses.High )

UNION ALL

SELECT  PeopleID,
        Low,
        High
FROM    dbo.Guesses
WHERE   exists (select 1 FROM dbo.Result where Value = Guesses.High)
AND not exists(SELECT 1 FROM dbo.Result where Value = Guesses.Low )
print 'Number of records Query5: ' + cast(@@Rowcount as varchar(20))

So, the important lesson we learned from this exercise - always analyze results, always try different variations of the query, always compare the resulting output and verify number of records. Finally, don't use OR with NOT IN as it doesn't perform good.

Explain the difference between NOT EXISTS and NOT IN regarding NULL values.

Quoting Books Online:

Any null values returned by subquery or expression that are compared to test_expression using IN or NOT IN return UNKNOWN. Using null values in together with IN or NOT IN can produce unexpected results.

In contrast, NOT EXISTS will return TRUE when evaluating NULL. Consider the following queries:

select 1 where exists(select null)
select 1 where not exists(select null)

The first returns a result (as EXISTS evaluates to TRUE) whereas the second does not (for the same reason). You could almost go so far as to say that they behave exactly as exact opposites as it relates to the handling of NULL.

How come adding the ‘not equal to filter’ made such a difference in performance for Query3 vs Query1?

From where I sit, it's not the fact of the 'not equal to filter' that makes the difference in Query3; rather, it’s that the evaluating values come from the outer query - making this a correlated subquery. By definition, this means that it is "evaluated by executing the subquery once and substituting the resulting value or values into the WHERE clause of the outer query" (Books Online). In the execution plan, this manifests itself as a single table scan of Guesses followed by a hash match with the Results table (it actually does this twice, once each for high and low respectively). By comparison, Query1 performs an index seek on Guesses followed by a nested loop . . . each executing ~500K times (and it does this 4 times over in the entirety of the plan). The cost of these operators executing this number of times ends up being about 52X more expensive than the table scans of Query3.

Very Interesting Question. SQL Server Query Optimizer it really helps us in performance tuning. I do agree to the fact that it’s an excellent tool.

NOT EXISTS vs NOT IN regarding NULL values

• "NOT IN" Clause will exclude NULLs from Source Table, in contrast to it "Not exists" will include NULLs.
• If the source table we are checking for values contains null values, "NOT IN " will not return any rows as output. This need to be understood while working with null values and NOT IN.
• NOT EXISTS will return TRUE when dealing with NULL values

How come adding the ‘not equal to filter’ made such a difference in performance for Query3 vs Query1?

It is not due to adding 'not equal to filter' that makes the performance difference in Query3. The values that come from the outer query made this as correlated sub query. Hence In the execution plan, it has as a single table scan with the Results table. The cost of the operators executing in Query1 (as per Query Execution Plan assessment) is more expensive than the table scans of Query3. This is due to Query1 performs an index seek on query estimation that is taking more time to execute.

I can conclude that it’s our friend. We need to understand our friend and go into his shoes. If you do not understand or communicate your friend or partner it becomes a foe.