По материалам статьи Craig Freedman: Decorrelating Subqueries

В статье про скалярные подзапросы было несколько примеров, в которых оптимизатор мог переписать запрос с коррелированным подзапросом как запрос с соединением. Например, можно было видеть, как представленный ниже простой подзапрос с «in»:

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

select *
from T1
where T1.a in (select T2.a from T2 where T2.b = T1.b)

Мог быть переписан как левое полу-соединение:

  |--Nested Loops(Left Semi Join, WHERE:([T2].[b]=[T1].[b] AND [T1].[a]=[T2].[a]))
       |--Table Scan(OBJECT:([T1]))
       |--Table Scan(OBJECT:([T2]))

Обратите внимание, что между двумя просмотрами таблицы отсутствует какая-либо корреляция. Просмотр любой таблицы может происходить независимо и будет использоваться такой алгоритм соединения, какой наиболее удобен. Эту стратегию оптимизации мы называем декорреляцией. Невозможно удалить корреляцию для всех подзапросов. Например, как мы видели в предыдущих статьях, простая замена подзапроса «in» скалярным подзапросом «=» (при отсутствии уникального индекса) вынуждает оптимизатор добавить в план оператор Assert, и это не позволит избавиться от корреляции подзапроса. Даже когда мы можем декоррелировать подзапрос, в результате необязательно получаем лучший план, но появляется возможность проанализировать больше вариантов плана и найти из них лучший.

Декорреляция подзапросов с агрегацией

Вспомним представленный ниже запрос из предыдущей статьи:

select *
from T1
where T1.a > (select max(T2.a) from T2 where T2.b < T1.b)

  |--Filter(WHERE:([T1].[a]>[Expr1008]))
       |--Nested Loops(Inner Join, OUTER REFERENCES:([T1].[b]))
            |--Table Scan(OBJECT:([T1]))
            |--Stream Aggregate(DEFINE:([Expr1008]=MAX([T2].[a])))
                 |--Table Scan(OBJECT:([T2]), WHERE:([T2].[b]<[T1].[b]))

Мы не можем декоррелировать этот подзапрос. Теперь рассмотрим почти идентичный запрос, но заменим в предложении where подзапроса «<» на «=»:

select *
from T1
where T1.a > (select max(T2.a) from T2 where T2.b = T1.b)

Это, казалось бы, незначительное изменение позволяет нам убрать корреляцию и написать этот запрос как обычное соединение:

select T1.*
from T1, (select T2.b, max(T2.a) max_a from T2 group by T2.b) S
where T1.b = S.b and T1.a > S.max_a

Оба запроса выбирают такой план:

  |--Nested Loops(Inner Join, OUTER REFERENCES:([T2].[b], [Expr1008]))
       |--Stream Aggregate(GROUP BY:([T2].[b]) DEFINE:([Expr1008]=MAX([T2].[a])))
       |    |--Sort(ORDER BY:([T2].[b] ASC))
       |         |--Table Scan(OBJECT:([T2]))
       |--Index Spool(SEEK:([T1].[b]=[T2].[b] AND [T1].[a] > [Expr1008]))
            |--Table Scan(OBJECT:([T1]))

Исходный план выполняет подзапрос для каждой строки T1, он работает вполне эффективно за счет предварительного вычисления всех возможных результатов агрегации для подзапроса и объединения этого результата с T2. Чтобы вычислить все возможные результаты подзапроса, к подзапросу добавляется предложение «group by» и это учитывается в ключе соединения. Оператор буферизации индекса «Index Spool» создает индекс на лету, это позволяет повысить производительность соединения. Вместо соединения вложенных циклов «Nested Loops» с просмотром таблицы на внутренней стороне у нас есть соединение «Nested Loops» индекса с поиском по индексу на внутренней стороне.

Давайте рассмотрим, когда этот новый план будет лучше изначального. Если в T2.b хранится всего несколько уникальных значений и, следовательно, будет всего несколько групп для вычисления, а также если в T1 будет много строк, новый план может оказаться очень эффективным. С другой стороны, если в T2.b много уникальных значений, а в T1 всего несколько строк, может оказаться выгоднее вычислять только те агрегаты, которые нужны:

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

select *
from T1
where T1.a > (select max(T2.a) from T2 where T2.b = T1.b)

   |--Filter(WHERE:([T1].[a]>[Expr1008]))
       |--Stream Aggregate(GROUP BY:([Bmk1000]) DEFINE:([Expr1008]=MAX([T2].[a]), [T1].[a]=ANY([T1].[a]), [T1].[b]=ANY([T1].[b])))
            |--Nested Loops(Inner Join, WHERE:([T1].[b]=[T2].[b]))
                 |--Table Scan(OBJECT:([T1]))
                 |--Table Scan(OBJECT:([T2]))

Этот план в основном такой же, как и исходный (с корреляцией), за исключением того, что агрегация делается после соединения.

Обратите внимание, что результаты агрегации после соединения мы группируем по [Bmk1000]. Это уникальный реляционный ключ для T1. Вы можете убедиться в том, что [Bmk1000] является ключом для T1, исследовав столбец для этих значений в результатах выполнения showplan_all. Группировка по ключу T1 необходима, так как одна строка T1 может соединяться с несколькими строками T2, но запрос предполагает вычисление MAX(T2.a) значений для каждой строки T1.

Нет необходимости в сортировке потока после агрегации, поскольку соединение «Nested Loops» выбирает все строки T2, которые подлежат соединению со строкой из T1, прежде чем перейти к следующей строке T1. Другими словами, результаты соединения уже «сгруппированы» по T1, даже если они и не отсортированы по T1.

Если у T1 есть кластерный или любой уникальный индекс, мы будем использовать этот ключ вместо столбца закладки [Bmk1000]. На самом деле, если мы создадим уникальный ключ для T1, мы можем переписать запрос иначе:

create unique clustered index T1a on T1(a)

select T1.a, min(T1.b) as T1b
from T1 join T2 on T1.b = T2.b
group by T1.a
having T1.a > max(T2.a)

План в принципе тот же:

 |--Filter(WHERE:([T1].[a]>[Expr1007]))
    |--Stream Aggregate(GROUP BY:([T1].[a]) DEFINE:([Expr1007]=MAX([T2].[a]), [Expr1008]=MIN([T1].[b])])))
        |--Nested Loops(Inner Join, WHERE:([T2].[b]=[T1].[b]))
           |--Clustered Index Scan(OBJECT:([T1].[T1a]))
           |--Table Scan(OBJECT:([T2]))

Теперь давайте рассмотрим вариант, когда в обеих таблицах много строк, размер соединения увеличивается, и оптимизатор может выбрать еще один вариант плана:

set nocount on
declare @i int
set @i = 0
while @i < 10000
  begin
    insert T1 values(@i, @i)
    set @i = @i + 1
  end
  
select *
from T1
where T1.a > (select max(T2.a) from T2 where T2.b = T1.b)

   |--Hash Match(Inner Join, HASH:([T1].[b])=([T2].[b]), RESIDUAL:([T1].[b]=[T2].[b] AND [T1].[a]>[Expr1007]))
       |--Clustered Index Scan(OBJECT:([T1].[T1a]))
       |--Hash Match(Aggregate, HASH:([T2].[b]), RESIDUAL:([T2].[b] = [T2].[b]) DEFINE:([Expr1007]=MAX([T2].[a])))
            |--Table Scan(OBJECT:([T2]))

Этот план по сути такой же, как исходный декоррелированный план, за исключением того, что вместо потоковой агрегации и соединения «Nested Loops» используется хэш-агрегация и хеш-соединение.

Как видите, декорреляция подзапроса может открыть возможность получения множества альтернативных планов.