Index Union

[Craig_Freedman]

First published on MSDN on Oct 18, 2006

I was planning to continue writing about parallelism this week (and I will continue another time in another post), but I received an interesting question and chose to write about it instead.

Let’s begin by considering the following query:

create table T (a int, b int, c int, x char(200))

create unique clustered index Ta on T(a)

create index Tb on T(b)

create index Tc on T(c)

insert T values (1, 1, 1, 1)

insert T values (2, 2, 2, 2)

insert T values (3, 3, 3, 3)

select a from T where b = 1 or b = 3

|--Index Seek(OBJECT:([T].[Tb]), SEEK:([T].[b]=(1) OR [T].[b]=(3)) ORDERED FORWARD)

We have an index on column b and not surprisingly, the optimizer chooses to use the index and perform a seek.  Since we have two predicates on column b, we get a seek with two predicates.  First we execute the predicate “b = 1” and then we execute the predicate “b = 3”.  Note that since we only output column a and since column a is the clustering key (and is, thus, covered by all non-clustered indexes), there is no need for a bookmark lookup.  So far, there are no surprises.

Note that we could just as easily write this query as:

select a from T where b = 1

union all

select a from T where b = 3

|--Concatenation

|--Index Seek(OBJECT:([T].[Tb]), SEEK:([T].[b]=(1)) ORDERED FORWARD)

|--Index Seek(OBJECT:([T].[Tb]), SEEK:([T].[b]=(3)) ORDERED FORWARD)

The optimizer does not collapse the union all into a single index seek, but the queries and the plans are logically identical.

Now consider this query:

select a from T where b = 1 or c < 3

|--Clustered Index Scan(OBJECT:([T].[Ta]), WHERE:([T].[b]=(1) OR [T].[c]<(3)))

We have an index on both columns b and c, but we didn’t use either.  Why not?  We need all rows that satisfy either predicate.  We could use the index on column b to get rows that satisfy the predicate “b = 1”, but we may miss rows that satisfy “c < 3” but for which “b != 1”.  For example, we would miss the row with the value (2, 2, 2, 2).  The same problem would occur if we use the index on column c to satisfy the predicate “c < 3”.  (My sample data does not include a row with “b = 1” for which “c >= 3” but such a row could exist and so we must assume one does.)

Index union

So, is there a way for SQL Server to evaluate this query and use the indexes?  Yes!  First, for the optimizer to choose a plan other than the clustered index scan, we need to add enough data to the table to make the scan more expensive.  (Note that I added a char(200) column to the original table to make the rows larger.  This column makes the table occupy more pages which also makes the scan more expensive.)

truncate table T

set nocount on

declare @i int

set @i = 0

while @i < 1000

begin

insert T values(@i, @i, @i, @i)

set @i = @i + 1

end

select a from T where b = 1 or c < 3

|--Sort(DISTINCT ORDER BY:([T].[a] ASC))

|--Concatenation

|--Index Seek(OBJECT:([T].[Tb]), SEEK:([T].[b]=(1)) ORDERED FORWARD)

|--Index Seek(OBJECT:([T].[Tc]), SEEK:([T].[c] < (3)) ORDERED FORWARD)

This plan is very similar to the union all plan that we saw above.  The optimizer rewrote the query as:

select a from T where b = 1

union

select a from T where c < 3

Note, however, that since the two queries that make up the union could return duplicate rows, we must use a union (which eliminates duplicates) rather than a union all (which does not).  The concatenation operator implements union all while the sort distinct eliminates duplicates and turns the union all into a union.  We refer to this type of plan as an “index union.”

Merge union

Now let’s change the query slightly:

select a from T where b = 1 or c = 3

|--Stream Aggregate(GROUP BY:([T].[a]))

|--Merge Join(Concatenation)

|--Index Seek(OBJECT:([T].[Tb]), SEEK:([T].[b]=(1)) ORDERED FORWARD)

|--Index Seek(OBJECT:([T].[Tc]), SEEK:([T].[c]=(3)) ORDERED FORWARD)

Instead of the concatenation and sort distinct operators, we now have a merge join (concatenation) and a stream aggregate.  What happened?  The merge join (concatenation) or “merge union” is not really a join at all.  It is implemented by the same iterator as the merge join, but it really performs a union all while preserving the order of the input rows.  Finally, we use the stream aggregate to eliminate duplicates.  (See this post for more about using stream aggregate to eliminate duplicates.)  This plan is generally a better choice since the sort distinct uses memory and could spill data to disk if it runs out of memory while the stream aggregate does not use memory.

So, why didn’t we use this plan before?  Just like a merge join, the merge union requires that input data be sorted on the merge key (in this case column a).  The non-clustered index Tb covers the explicit index key b and the clustering key a.  Thus, this index returns rows in the order (b, a).  However, with an equality predicate such as “b = 1”, column b is a constant so we actually get rows ordered by column a.  The same thing happens with the index Tc and the predicate “c = 3”.  So, we have two inputs that are both ordered by column a and we can use the merge union.

In the prior example, one of the predicates was “c < 3”.  Because this predicate is an inequality, the index seek returns rows in the order (c, a).  Since the rows are not strictly sorted by a, we cannot use the merge union.

Union of three indexes

The concatenation operator directly supports more than two inputs:

select a from T where a = 1 or b = 2 or c < 3

|--Sort(DISTINCT ORDER BY:([T].[a] ASC))

|--Concatenation

|--Clustered Index Seek(OBJECT:([T].[Ta]), SEEK:([T].[a]=(1)) ORDERED FORWARD)

|--Index Seek(OBJECT:([T].[Tb]), SEEK:([T].[b]=(2)) ORDERED FORWARD)

|--Index Seek(OBJECT:([T].[Tc]), SEEK:([T].[c] < (3)) ORDERED FORWARD)

Merge union only supports two inputs, but it can be cascaded to handle more than two inputs:

select a from T where a = 1 or b = 2 or c = 3

|--Stream Aggregate(GROUP BY:([T].[a]))

|--Merge Join(Concatenation)

|--Merge Join(Concatenation)

|    |--Clustered Index Seek(OBJECT:([T].[Ta]), SEEK:([T].[a]=(1)) ORDERED FORWARD)

|    |--Index Seek(OBJECT:([T].[Tb]), SEEK:([T].[b]=(2)) ORDERED FORWARD)

|--Index Seek(OBJECT:([T].[Tc]), SEEK:([T].[c]=(3)) ORDERED FORWARD)

What columns does the union return?

A union only returns the columns that are common to all of its inputs.  In all of the above index union examples, the only column that the indexes have in common is the clustering key a.  (Recall that index Tb covers (b, a) while index Tc covers (c, a).)  Thus, the union can only return column a.  If we ask for other columns, we must perform a bookmark lookup.  This is true even if one of the indexes in the union covers the extra columns.  For example, if we ask for all three columns a, b, and c, we get a bookmark lookup even though column b is covered by Tb and column c is covered by Tc:

select a, b, c from T where b = 1 or c = 3

|--Nested Loops(Inner Join, OUTER REFERENCES:([T].[a]))

|--Stream Aggregate(GROUP BY:([T].[a]))

|    |--Merge Join(Concatenation)

|         |--Index Seek(OBJECT:([T].[Tb]), SEEK:([T].[b]=(1)) ORDERED FORWARD)

|         |--Index Seek(OBJECT:([T].[Tc]), SEEK:([T].[c]=(3)) ORDERED FORWARD)

|--Clustered Index Seek(OBJECT:([T].[Ta]), SEEK:([T].[a]=[T].[a]) LOOKUP ORDERED FORWARD)