Can you explain this execution plan?

I was researching something else when I came across this thing. I was generating test tables with some data in it and running different queries to find out how different ways to write queries affects execution plan. Here is the script that I used to generate random test data:

IF  EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID('t') AND type in (N'U'))
DROP TABLE t
GO

CREATE TABLE t 
(
 c1 int IDENTITY(1,1) NOT NULL 
,c2 int NULL
) 
GO

insert into t
select top 1000000 a from
(select t1.number*2048 + t2.number a, newid() b
from [master]..spt_values t1 
cross join  [master]..spt_values t2
where t1.[type] = 'P' and t2.[type] = 'P') a
order by b
GO

update t set c2 = null
where c2 < 2048 * 2048 / 10
GO

CREATE CLUSTERED INDEX pk ON [t] (c1)
GO

CREATE NONCLUSTERED INDEX i ON t (c2)
GO

Now, given this data, I invoked the following query:

select * 
from t 
where 
      c2 < 1048576 
   or c2 is null
;

To my great surprise, the execution plan that was generated for this query, was this. (Sorry for the external link, it's too large to fit here).

Can someone explain to me what's up with all these "Constant Scans" and "Compute Scalars"? What's happening?

```
|--Nested Loops(Inner Join, OUTER REFERENCES:([Expr1010], [Expr1011], [Expr1012]))
|--Merge Interval
| |--Sort(TOP 2, ORDER BY:([Expr1013] DESC, [Expr1014] ASC, [Expr1010] ASC, [Expr1015] DESC))
| |--Compute Scalar(DEFINE:([Expr1013]=((4)&[Expr1012]) = (4) AND NULL = [Expr1010], [Expr1014]=(4)&[Expr1012], [Expr1015]=(16)&[Expr1012]))
| |--Concatenation
| |--Compute Scalar(DEFINE:([Expr1005]=NULL, [Expr1006]=NULL, [Expr1004]=(60)))
| | |--Constant Scan
| |--Compute Scalar(DEFINE:([Expr1008]=NULL, [Expr1009]=(1048576), [Expr1007]=(10)))
| |--Constant Scan
|--Index Seek(OBJECT:([t].[i]), SEEK:([t].[c2] > [Expr1010] AND [t].

The constant scans each produce a single in-memory row with no columns. The top compute scalar outputs a single row with 3 columns

Expr1005    Expr1006    Expr1004
----------- ----------- -----------
NULL        NULL        60

The bottom compute scalar outputs a single row with 3 columns

Expr1008    Expr1009    Expr1007
----------- ----------- -----------
NULL        1048576        10

The concatenation operator Unions these 2 rows together and outputs the 3 columns but they are now renamed

Expr1010    Expr1011    Expr1012
----------- ----------- -----------
NULL        NULL        60
NULL        1048576     10

The Expr1012 column is a set of flags used internally to define certain seek properties for the Storage Engine.

The next compute scalar along outputs 2 rows

Expr1010    Expr1011    Expr1012    Expr1013    Expr1014    Expr1015
----------- ----------- ----------- ----------- ----------- -----------
NULL        NULL        60          True        4           16            
NULL        1048576     10          False       0           0

The last three columns are defined as follows and are just used for sorting purposes prior to presenting to the Merge Interval Operator

[Expr1013] = Scalar Operator(((4)&[Expr1012]) = (4) AND NULL = [Expr1010]), 
[Expr1014] = Scalar Operator((4)&[Expr1012]), 
[Expr1015] = Scalar Operator((16)&[Expr1012])

Expr1014 and Expr1015 just test whether certain bits are on in the flag.
Expr1013 appears to return a boolean column true if both the bit for 4 is on and Expr1010 is NULL.

From trying other comparison operators in the query I get these results

+----------+----------+----------+-------------+----+----+---+---+---+---+
| Operator | Expr1010 | Expr1011 | Flags (Dec) |       Flags (Bin)       |
|          |          |          |             | 32 | 16 | 8 | 4 | 2 | 1 |
+----------+----------+----------+-------------+----+----+---+---+---+---+
| >        | 1048576  | NULL     |           6 |  0 |  0 | 0 | 1 | 1 | 0 |
| >=       | 1048576  | NULL     |          22 |  0 |  1 | 0 | 1 | 1 | 0 |
| <=       | NULL     | 1048576  |          42 |  1 |  0 | 1 | 0 | 1 | 0 |
| <        | NULL     | 1048576  |          10 |  0 |  0 | 1 | 0 | 1 | 0 |
| =        | 1048576  | 1048576  |          62 |  1 |  1 | 1 | 1 | 1 | 0 |
| IS NULL  | NULL     | NULL     |          60 |  1 |  1 | 1 | 1 | 0 | 0 |
+----------+----------+----------+-------------+----+----+---+---+---+---+

From which I infer that Bit 4 means "Has start of range" (as opposed to being unbounded) and Bit 16 means the start of the range is inclusive.

This 6 column result set is emitted from the SORT operator sorted by
Expr1013 DESC, Expr1014 ASC, Expr1010 ASC, Expr1015 DESC. Assuming True is represented by 1 and False by 0 the previously represented resultset is already in that order.

Based on my previous assumptions the net effect of this sort is to present the ranges to the merge interval in the following order

ORDER BY 
          HasStartOfRangeAndItIsNullFirst,
          HasUnboundedStartOfRangeFirst,
          StartOfRange,
          StartOfRangeIsInclusiveFirst

The merge interval operator outputs 2 rows

Expr1010    Expr1011    Expr1012
----------- ----------- -----------
NULL        NULL        60
NULL        1048576     10

For each row emitted a range seek is performed

Seek Keys[1]: Start:[dbo].[t].c2 > Scalar Operator([Expr1010]), 
               End: [dbo].[t].c2 < Scalar Operator([Expr1011])

So it would appear as though two seeks are performed. One apparently > NULL AND NULL AND = and <= rather than just the straightforward equality seek you get for the query c2 = 0 OR c2 = 1048576.

StackExchange Database Administrators Q#14789, answer score: 29