По материалам статьи Craig Freedman: Index Union. Перевод Ирины Наумовой.

Ранее я планировал продолжить писать о параллелизме (и сделаю это в следующий раз в другой статье), но получил интересный вопрос и решил написать об индексных объединениях.

Начнем:

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:([ Т ].[ Тb ]), SEEK:([ Т ]. [ b ]=(1) OR [ Т ]. [ b ]=(3)) ORDERED FORWARD)}

У нас имеется индекс на поле "b", и, как и ожидалось, оптимизатор выбирает поиск по индексу. Поскольку мы имеем два предиката для поля "b", мы получим поиск с двумя предикатами. Вначале выполнится предикат "b=1", а зетем "b=3". Обратите внимание, что поскольку мы выводим столбец "a", а он является кластеризованным (и таким образом покрывает все некластеризованные индексы), не возникает необходимости в операции BOOKMARK LOOKUP (поиск закладок). Пока нет никаких неожиданностей.

Обратите внимание, что мы могли записать этот запрос в ином виде:

select a from T where b = 1   
union all   
select a from   T where b = 3

^{|--Concatenation
|--Index Seek(OBJECT:([ Т ].[ Тb ]), SEEK:([ Т ]. [ b ]=(1)) ORDERED FORWARD)
|--Index Seek(OBJECT:([ Т ].[ Тb ]), SEEK:([ Т ]. [ b ]=(3)) ORDERED FORWARD)}

Оптимизатор не объединяет эти операции в одну операцию INDEX SEEK (поиска по индексу), но запросы и планы логически идентичны.

Рассмотрим следующий запрос:

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

^{|--Clustered Index Scan(OBJECT:([Т].[Тa]), WHERE:([ Т ]. [ b ]=(1) OR [Т]. [ c ]<(3)))}

У нас имеются индексы на столбцах "b" и "c", но оптимизатор их не использовал. Почему? Нам нужны все строки, удовлетворяющие любому из предикатов. Мы могли бы использовать индекс на столбце "b", чтобы получить строки, удовлетворяющие предикату "b=1", но при этом мы можем пропустить строки, которые удовлетворяют предикату "с<3", и для которых "b!=1". Например, мы пропустили бы строку со значением (2,2,2,2). Та же самая проблема возникает при использовании индекса на столбце "с", чтобы удовлетворить предикату "c<3". (В моем примере данные не включают строк со значением "b=1", для которых выполняется предикат "с>3", но такая строка могла бы существовать, поэтому мы должны предусмотреть и такой вариант).

Индексные объединения

И так, давайте разберёмся, будет ли SQL Server так выполнять декомпозицию запроса, чтобы использовать два индекса? Да! Сначала для того чтобы оптимизатор выбрал другой план, в котором не будет сканирования кластерного индекса, мы должны добавить достаточно большое количество данных в таблицу, чтобы сделать операцию сканирования кластерного индекса более дорогостоящей.

Обратите внимание, что к используемой ранее таблице я добавил столбец типа char(200), чтобы строки стали больше. Добавление этого столбца приведет к тому, что таблица будет занимать больше страниц, что также сделает операцию просмотра более дорогостоящей.

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]. [ а ]ASC))
     |--Concatenation
        |--Index Seek(OBJECT:([T].[Tb]), SEEK:([T]. [ b ]=(1)) ORDERED FORWARD)
        |--Index Seek(OBJECT:([T].[Tc]), SEEK:([T]. [ c ] < (3)) ORDERED FORWARD)}

Этот план очень похож на приведенный выше план с оператором UNION ALL. Оптимизатор выполнил декомпозицию таким образом, что запрос стал выглядеть так:

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

Однако, стоит обратить внимание на то, что два объединяемых запроса могут возвратить дубликаты строк, поэтому нужно использовать оператор UNION (который устраняет дубликаты), а не UNION ALL (который этого не делает). Оператор CONCATENATION реализует конструкцию UNION ALL, а SORT DISTINCT устраняет дубликаты, превращая UNION ALL в UNION. Такой тип плана исполнения запроса можно считать индексным объединением.

Merge Join

Давайте немного изменим запрос:

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

^{|--Stream Aggregate(GROUP BY:([Т]. [ a ]))
     |--Merge Join(Concatenation)
        |--Index Seek(OBJECT:([ Т ].[ Тb ]), SEEK:([ Т ]. [ b ]=(1)) ORDERED FORWARD)
        |--Index Seek(OBJECT:([Т].[Тc]), SEEK:([Т]. [ c ]=(3)) ORDERED FORWARD)}

Теперь, вместо операторов CONCATENATION и SORT DISTINCT мы имеем MERGE JOIN (Concatenation) и STREAM AGGREGATE. Что же произошло? MERGE JOIN (Concatenation) или "MERGE UNION" в действительности ничего не соединяют. Это осуществляется также, как с помощью итератора MERGE UNION, но в действительности выполняется операция UNION ALL с сохранением порядка входных строк. После этого используется STREAM AGGREGATE, который устраняет дубликаты (для получения более подробной информации, изучите статью "Агрегат потока (Stream Aggregate)", в которой написано об использовании STREAM AGGREGATE для устранения дубликатов). Такой план исполнения запроса будет работать лучше, потому что не будет использовать SORT DISTINCT, который использует память и может стать причиной сброса страницы данных на диск, если действие выполняется за пределами памяти. В этом плане исполнения запроса используется STREAM AGGREGATE, который память не использует.

Тогда почему же мы не использовали этот план с самого начала? Точно так же как MERGE JOIN, MERGE UNION требует, чтобы входные данные были отсортированы по ключу слияния (в нашем случае это столбец "a"). Некластеризованный индекс "Tb" покрывает ключ индекса "b" и ключ кластеризованного индекса "a". Таким образом, этот индекс возвращает строки в порядке (b, a). Однако, это эквивалентно предикату "b = 1", столбец "b" - константа, этим мы фактически упорядочиваем строки по столбцу "a". То же самое случается с индексом Tc и предикатом "c = 3". Таким образом, у нас имеется два входных потока, которые оба упорядочены по столбцу "а", и мы можем использовать MERGE UNION.

В предшествующем примере, одним из предикатов был "c 3". Поскольку этот предикат - неравенство, INDEX SEEK возвращает строки в порядке (c, a). И так как строки не отсортированы по столбцу "a", мы не сможем использовать MERGE UNION.

Объединение трех индексов

Оператор CONCATENATION может поддерживать больше двух входных потоков:

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

^{|--Sort(DISTINCT ORDER BY:([Т]. [ а ]ASC))
     |--Concatenation
        |--Clustered Index Seek(OBJECT:([Т].[Тa]), SEEK:([Т]. [ a ]=(1)) ORDERED FORWARD)
        |--Index Seek(OBJECT:([ Т ].[ Тb ]), SEEK:([ Т ]. [ b ]=(2)) ORDERED FORWARD)
        |--Index Seek(OBJECT:([Т].[Тc]), SEEK:([Т].[с] < (3)) ORDERED FORWARD)}

MERGE UNION поддерживает только два входных потока, но входные потоки можно объединять каскадом, чтобы позволяет в итоге объединить больше двух входных потоков:

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

^{|--Stream Aggregate(GROUP BY:([Т]. [ a ]))
     |--Merge Join(Concatenation)
        |--Merge Join(Concatenation)
        |   |--Clustered Index Seek(OBJECT:([Т].[Тa]), SEEK:([Т]. [ a ]=(1)) ORDERED FORWARD)
        |   |--Index Seek(OBJECT:([ Т ].[ Тb ]), SEEK:([ Т ]. [ b ]=(2)) ORDERED FORWARD)
        |--Index Seek(OBJECT:([Т].[Тc]), SEEK:([Т]. [ c ]=(3)) ORDERED FORWARD)}

Какие столбцы возвращает объединение?

Объединение возвращает только те столбцы, которые являются общими для всех его входных потоков. Во всех приведенных выше примерах индексных объединений, единственным столбцом, который у индексов был общим, являлся ключ кластеризованного индекса - колонка "a" (это как если бы индекс Tb состоял из столбцов "b, a", а индекс Tc состоял из "c, a"). Таким образом, наше объединение может вернуть только столбец "a". Если будут запрошены и другие столбцы, будет использоваться BOOKMARK LOOKUP. Так будет даже в том случае, если один из индексов в объединении будет покрывающим ещё для каких-либо столбцов. Например, если мы запросим все три столбца "a", "b" и "c", в плане исполнения будет BOOKMARK LOOKUP, несмотря на то, что столбец "b" будет покрываться индексом Тb, а столбец "c" будет покрываться индексом Тc:

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

^{|--Nested Loops(Inner Join, OUTER REFERENCES:([Т]. [ a ]))
     |--Stream Aggregate(GROUP BY:([Т]. [ a ]))
        |   |--Merge Join(Concatenation)
        |      |--Index Seek(OBJECT:([ Т ].[ Тb ]), SEEK:([T]. [ b ]=(1)) ORDERED FORWARD)
        |      |--Index Seek(OBJECT:([Т].[Тc]), SEEK:([Т]. [ c ]=(3)) ORDERED FORWARD)
        |--Clustered Index Seek(OBJECT:([Т].[Тa]), SEEK:([Т]. [ a ]=[Т]. [ a ]) LOOKUP ORDERED FORWARD)}

Индексные объединения (Index Union)