Why is a scan faster than seek for this predicate?
Why is there a large difference in CPU time for these two queries?


The scan plan evaluates the following pushed non-sargable (residual) predicate for each row:

[two_col_key_test].[ID1]&lt;&gt;N'1' 
AND [two_col_key_test].[ID1]&lt;&gt;N'10' 
AND [two_col_key_test].[ID1]&lt;&gt;N'11' 
AND [two_col_key_test].[ID1]&lt;&gt;N'12' 
AND [two_col_key_test].[ID1]&lt;&gt;N'13' 
AND [two_col_key_test].[ID1]&lt;&gt;N'14' 
AND [two_col_key_test].[ID1]&lt;&gt;N'15' 
AND [two_col_key_test].[ID1]&lt;&gt;N'16' 
AND [two_col_key_test].[ID1]&lt;&gt;N'17' 
AND [two_col_key_test].[ID1]&lt;&gt;N'18' 
AND [two_col_key_test].[ID1]&lt;&gt;N'19' 
AND [two_col_key_test].[ID1]&lt;&gt;N'2' 
AND [two_col_key_test].[ID1]&lt;&gt;N'20' 
AND [two_col_key_test].[ID1]&lt;&gt;N'3' 
AND [two_col_key_test].[ID1]&lt;&gt;N'4' 
AND [two_col_key_test].[ID1]&lt;&gt;N'5' 
AND [two_col_key_test].[ID1]&lt;&gt;N'6' 
AND [two_col_key_test].[ID1]&lt;&gt;N'7' 
AND [two_col_key_test].[ID1]&lt;&gt;N'8' 
AND [two_col_key_test].[ID1]&lt;&gt;N'9' 
AND 
(
    [two_col_key_test].[ID1]=N'FILLER TEXT' 
    AND [two_col_key_test].[ID2]&gt;=N'' 
    OR [two_col_key_test].[ID1]&gt;N'FILLER TEXT'
)




The seek plan does two seeking operations:

Seek Keys[1]: 
    Prefix: 
    [two_col_key_test].ID1 = Scalar Operator(N'FILLER TEXT'), 
        Start: [two_col_key_test].ID2 &gt;= Scalar Operator(N'')
Seek Keys[1]: 
    Start: [two_col_key_test].ID1 &gt; Scalar Operator(N'FILLER TEXT')


...to match this part of the predicate:

(ID1 = N'FILLER TEXT' AND ID2 &gt;= N'' OR (ID1 &gt; N'FILLER TEXT'))


A residual predicate is applied to rows that pass the seek conditions above (all rows in your example). 

However, each inequality is replaced by two separate tests for less than OR greater than:

([two_col_key_test].[ID1]&lt;N'1' OR [two_col_key_test].[ID1]&gt;N'1') 
AND ([two_col_key_test].[ID1]&lt;N'10' OR [two_col_key_test].[ID1]&gt;N'10') 
AND ([two_col_key_test].[ID1]&lt;N'11' OR [two_col_key_test].[ID1]&gt;N'11') 
AND ([two_col_key_test].[ID1]&lt;N'12' OR [two_col_key_test].[ID1]&gt;N'12') 
AND ([two_col_key_test].[ID1]&lt;N'13' OR [two_col_key_test].[ID1]&gt;N'13') 
AND ([two_col_key_test].[ID1]&lt;N'14' OR [two_col_key_test].[ID1]&gt;N'14') 
AND ([two_col_key_test].[ID1]&lt;N'15' OR [two_col_key_test].[ID1]&gt;N'15') 
AND ([two_col_key_test].[ID1]&lt;N'16' OR [two_col_key_test].[ID1]&gt;N'16') 
AND ([two_col_key_test].[ID1]&lt;N'17' OR [two_col_key_test].[ID1]&gt;N'17') 
AND ([two_col_key_test].[ID1]&lt;N'18' OR [two_col_key_test].[ID1]&gt;N'18') 
AND ([two_col_key_test].[ID1]&lt;N'19' OR [two_col_key_test].[ID1]&gt;N'19') 
AND ([two_col_key_test].[ID1]&lt;N'2' OR [two_col_key_test].[ID1]&gt;N'2') 
AND ([two_col_key_test].[ID1]&lt;N'20' OR [two_col_key_test].[ID1]&gt;N'20') 
AND ([two_col_key_test].[ID1]&lt;N'3' OR [two_col_key_test].[ID1]&gt;N'3') 
AND ([two_col_key_test].[ID1]&lt;N'4' OR [two_col_key_test].[ID1]&gt;N'4') 
AND ([two_col_key_test].[ID1]&lt;N'5' OR [two_col_key_test].[ID1]&gt;N'5') 
AND ([two_col_key_test].[ID1]&lt;N'6' OR [two_col_key_test].[ID1]&gt;N'6') 
AND ([two_col_key_test].[ID1]&lt;N'7' OR [two_col_key_test].[ID1]&gt;N'7') 
AND ([two_col_key_test].[ID1]&lt;N'8' OR [two_col_key_test].[ID1]&gt;N'8') 
AND ([two_col_key_test].[ID1]&lt;N'9' OR [two_col_key_test].[ID1]&gt;N'9')




Rewriting each inequality e.g.:

[ID1] &lt;&gt; N'1'  -&gt;  [ID1]&lt;N'1' OR [ID1]&gt;N'1'


...is counterproductive here. Collation-aware string comparisons are expensive. Doubling the number of comparisons explains most of the difference in CPU time you see.

You can see this more clearly by disabling the pushing of non-sargable predicates with undocumented trace flag 9130. That will show the residual as a separate Filter, with performance information you can inspect separately:





This will also highlight the slight cardinality misestimate on the seek, which explains why the optimizer chose the seek over the scan in the first place (it expected the seeking portion to eliminate some rows).

While the inequality rewrite may make (possibly filtered) index matching possible (to make the best use of the seeking ability of b-tree indexes), it would be better to subsequently revert this expansion if both halves end up in the residual. You could suggest this as an improvement on the SQL Server feedback site.

Note also that the original ("legacy") cardinality estimation model happens to select a scan by default for this query.