По материалам статьи Craig Freedman: Semi-join Transformation

В предыдущих статьях я приводил примеры полу-соединений (semi-joins). Вспомним, что полу-соединение возвращает строку из таблицы, если для этой строки есть хотя бы одна совпадающая строка во второй таблице. Вот простой пример:

create table T1 (a int, b int)
create table T2 (a int, b int)

set nocount on
declare @i int
set @i = 0
while @i < 10000
  begin
    insert T1 values(@i, @i)
    set @i = @i + 1
  end

set nocount on

declare @i int
set @i = 0
while @i < 100
  begin
    insert T2 values(@i, @i)
    set @i = @i + 1
  end

select * from T1
where exists (select * from T2 where T2.a = T1.a)

Rows	Executes
100	1	^{\|--Hash Match(Right Semi Join, HASH:([T2].[a])=([T1].[a]), RESIDUAL:([T2].[a]=[T1].[a]))}
100	1	^{\|--Table Scan(OBJECT:([T2]))}
10000	1	^{\|--Table Scan(OBJECT:([T1]))}

Обратите внимание, что для этого запроса оптимизатор выбрал хэш-соединение и вполне логично строит хэш-таблицу по маленькой таблице Т2, которая имеет всего 100 строк, и потом выбирает соответствующие им строки из большой таблицы T1, которая имеет 10000 строк.

Трансформация

Предположим, что мы хотим создать индекс, который позволит ускорить исполнение запроса. Для этого нам мог бы подойти план, который использовал бы новый индекс и оператор соединения вложенных циклов (nested loops join). Определимся на какой из таблиц Т1 и Т2 нужно создать индекс. Для этого вспомним, что соединение вложенных циклов поддерживает только левое полу-соединение, и не поддерживает правое. Таким образом, в плане с вложенными циклами и полу-соединением, таблица Т1 должна быть внешней, а Т2 внутренней. Значит нам нужно попытаться создать индекс на таблице Т2:

create clustered index T2a on T2(a)

К сожалению, создание индекса план исполнения нашего запроса не изменило. Оптимизатор решил, что с этим индексом выйдет 10000 обращений к данным (по одному для каждой строки в T1), что дороже, чем хэш-соединение. К счастью, у нас есть еще один менее очевидный вариант. Мы можем создать индекс на большой таблице T1:

create clustered index T1a on T1(a)

select * from T1
where exists (select * from T2 where T2.a = T1.a)

Теперь мы получаем соединение вложенных циклов по индексу:

Rows	Executes
100	1	^{\|--Nested Loops(Inner Join, OUTER REFERENCES:([T2].[a], [Expr1009]) WITH UNORDERED PREFETCH)}
100	1	^{\|--Stream Aggregate(GROUP BY:([T2].[a]))}
100	1	^{\| \|--Clustered Index Scan(OBJECT:([T2].[T2a]), ORDERED FORWARD)}
100	100	^{\|--Clustered Index Seek(OBJECT:([T1].[T1a]), SEEK:([T1].[a]=[T2].[a]) ORDERED FORWARD)}

Но подождите минуту! Этот план имеет внутреннее соединение. Что случилось с полу-соединением? Помните, что полу-соединение просто возвращает для каждой строки из T1 как минимум одну соответствующую строку из T2. Внутреннее соединение может использоваться для выбора соответствующих условию строк, если нет необходимости возвращать дубликаты строк из Т1. В этом плане, мы используем сканирование упорядоченного кластеризованного индекса Т2 и оператор «Stream Aggregate», чтобы устранить возможные дубликаты значений Т2.а. В процессе соединения строки из Т2 со строками в Т1 подразумевается, что соответствие каждой строке Т1 будет установлено только однажды. Обратите внимание, что в отличие от оригинального хэш-соединения, план которого затронул все 10000 строк T1, этот план выполняет только 100 неповторяющихся поисковых запросов к индексу Т1.

Когда подобная трансформация полезна?

Трансформация, или лучше сказать, преобразование полу-соединения во внутреннее соединение помогает тогда, когда, как в данном примере, мы имеем большое количество строк на “увесистой” стороне соединения (таблица Т1 в примере), и после преобразования у нас появляется возможность использования оператора поиска по индексу, что иначе было невозможно.

Трансформация также имеет смысл, если количество строк на той стороне соединения, где работает поиск по индексу, очень большое, но большинство этих строк дублируется. Поскольку полу-соединение не зависит от дубликатов, мы можем их устранить. Например, удалим индекс на таблице Т1 и создадим новую таблицу Т3, у которой будет 10000 строк, и все они будут дубликаты:

drop index T1.T1a
create table T3 (a int, b int)
set nocount on
declare @i int

set @i = 0
while @i < 10000
  begin
    insert T3 values(0, @i)
    set @i = @i + 1
  end

select * from T1
where exists (select * from T3 where T3.a = T1.a)

Rows	Executes
1	1	^{\|--Hash Match(Inner Join, HASH:([T3].[a])=([T1].[a]), RESIDUAL:([T3].[a]=[T1].[a]))}
1	1	^{\|--Hash Match(Aggregate, HASH:([T3].[a]), RESIDUAL:([T3].[a] = [T3].[a]))}
10000	1	^{\| \|--Table Scan(OBJECT:([T3]))}
10000	1	^{\|--Table Scan(OBJECT:([T1]))}

Обратите внимание, что даже без индексов в плане используется хэш-соединение, и тут тоже полу-соединение превращается во внутреннее соединение. На этот раз, поскольку индекса нет, используется хэш-агрегирование, что позволяет исключить повторяющиеся значения из Т3.а. Без трансформации, хэш-соединение построило бы хэш-таблицу для всех 10000 строк из Т3. С использованием трансформации построена хэш-таблица для одной строки.

Уникальный индекс

Если добавить уникальный индекс, после чего существование повторяющиеся значений в Т2.a будет невозможно, оптимизатору не потребуется устранять дубликаты и он тогда сможет выполнить подобное преобразование ещё проще. Пример:

create unique clustered index T2a on T2(a) with (drop_existing = on)

select * from T1
where exists (select * from T2 where T2.a = T1.a)

Rows	Executes
100	1	^{\|--Hash Match(Inner Join, HASH:([T2].[a])=([T1].[a]), RESIDUAL:([T2].[a]=[T1].[a]))}
100	1	^{\|--Clustered Index Scan(OBJECT:([T2].[T2a]))}
10000	1	^{\|--Table Scan(OBJECT:([T1]))}

Поскольку мы удалили индекс на Т1 (см. выше), мы снова получаем хэш-соединение. Однако, в отличие от первоначального плана с правым полу-соединением, теперь мы получаем внутреннее соединение. Нет необходимости в полу-соединении, потому что оптимизатор знает, что в Т2 дубликатов быть не может и что планы с полу-соединением и внутренним соединением эквивалентны.