Apply или соединение вложенными циклами?

Пересказ статьи Paul White. Apply versus Nested Loops Join

SQL является декларативным языком. Мы используем SQL, чтобы написать логическую спецификацию запроса, описывающую результат, который мы хотим получить. Например, мы могли бы написать запрос с использование либо APPLY, либо JOIN, которые логически описывают в точности одни и те же результаты.

Теперь оптимизатору предстоит найти эффективную физическую реализацию этих логических требований. SQL Server волен выбирать любой план, если он гарантирует те же результаты, которые сформулированы в оригинальном SQL.

Оптимизатор в состоянии преобразовать apply в join и наоборот. Он обычно пытается переписать apply в join на стадии начальной компиляции, чтобы максимизировать пространство поисковых планов при оптимизации на базе стоимости. Преобразовав apply в join на раннем этапе, он также может позже рассмотреть обратное преобразование в форму с apply, чтобы оценить преимущества, например, соединения вложенными циклами по столбцу, имеющему индекс.

Физические операторы

В выводе оптимизатора могут присутствовать обе физических операции — как apply, так и nested loops join. Обе показываются в планах выполнения как оператор Nested Loops Join, но они имеют различные свойства:

Apply

Оператор Nested Loops Join имеет Outer References (внешние ссылки). Они описывают значения параметра, переданного с внешней (верхней) стороны соединения в операторы на внутренней (нижней) стороне соединения. Значение каждого параметра может изменяться на каждой итерации цикла. Предикат соединения оценивается (при заданных текущих значениях параметров) одним или большим числом операторов на внутренней стороне соединения. Предикат соединения не оценивается самим соединением.

Join

Оператор Nested Loops Join имеет предикат (если это не cross join). Он не имеет никаких внешних ссылок. Предикат соединения всегда оценивается оператором соединения.

Пример Nested Loops Join

Следующая пара запросов производят один и тот же план с Nested Loops Join, хотя используют различный синтаксис запроса — APPLY в одном случае, и JOIN — в другом:

DECLARE @T1 TABLE (c1 INTEGER NULL);
DECLARE @T2 TABLE (c2 INTEGER NULL);
 
INSERT @T1 (c1)
VALUES (1), (2), (3);
 
INSERT @T2 (c2)
VALUES (1), (2), (3);
 
-- синтаксис с Join
SELECT
    T1.c1,
    T2.c2
FROM @T1 AS T1
JOIN @T2 AS T2
    ON T2.c2 > T1.c1;
 
-- Синтаксис с Apply
SELECT 
    T1.c1, 
    CA.c2 
FROM @T1 AS T1
CROSS APPLY 
(
    SELECT T2.c2
    FROM @T2 AS T2
    WHERE T2.c2 > T1.c1
) AS CA;

Оба запроса описывают один и тот же результирующий набор вне зависимости от содержимого таблиц. Планы выполнения идентичны и имеют одно и то же значение QueryPlanHash.

В обоих случаях оптимизатор запросов выбирает Nested Loops Join, а не Apply — оператор соединения имеет Predicate, но не имеет Outer References:


Этот план выполняется следующим образом:

• Для каждой строки из таблицы @T2:

• Для каждой строки из таблицы @T1:

• Проверить предикат T2.c2 > T1.c1 при соединении.

Оптимизация синтаксиса Join

Начнем с формы JOIN SQL-запроса:

-- синтаксис Join
SELECT
    T1.c1,
    T2.c2
FROM @T1 AS T1
JOIN @T2 AS T2
    ON T2.c2 > T1.c1;

Видно, что входное дерево передается в оптимизатор, используя флаг трассировки 8606 (также необходимо включить флаг трассировки 3604, чтобы получить выход отладки, показанный на вкладке сообщений SSMS):

*** Входное дерево: ***
LogOp_Project QCOL: [T1].c1 QCOL: [T2].c2
    LogOp_Select
    LogOp_Join
        LogOp_Get TBL: @T1
        LogOp_Get TBL: @T2
        ScaOp_Const TI(bit,ML=1) XVAR(bit,Value=1)
    ScaOp_Comp x_cmpGt
        ScaOp_Identifier QCOL: [T2].c2
        ScaOp_Identifier QCOL: [T1].c1
    AncOp_PrjList 

Логически это cross join двух таблиц с последующей реляционной выборкой (фильтрацией) по предикату соединения. Оптимизатор упрощает его, сводя к внутреннему соединению с помощью правила SELonJN (реляционная выборка по соединению):

*** Упрощенное дерево: ***
LogOp_Join
    LogOp_Get TBL: @T1
    LogOp_Get TBL: @T2
    ScaOp_Comp x_cmpGt
    ScaOp_Identifier QCOL: [T2].c2
    ScaOp_Identifier QCOL: [T1].c1

Оптимизатор рассматривает возможность переписать этот логический join на логический apply во время оптимизации на основе стоимости с помощью правила исследования JoinToIndexOnTheFly. Кандидат на замену представляет собой внутренний apply вместо join и внутренний Eager Index Spool (показан вывод на выходе флага трассировки 8619):

LogOp_Apply (x_jtInner)
    Leaf-Op 3
    LogOp_Spool Index on fly Eager
        Leaf-Op 4
        ScaOp_Comp x_cmpGt
            ScaOp_Identifier QCOL: [T2].c2
            ScaOp_Identifier QCOL: [T1].c1

Также рассматривается обмен входами внутреннего соединения через JoinCommute:

Apply Rule: JoinCommute - A JOIN B -> B JOIN A

LogOp_Join
    Leaf-Op 4
    Leaf-Op 3
    Leaf-Op 2

Имея сгенерированное множество логических альтернатив, оптимизатор переходит к реализации с помощью физических операторов. Альтернативы apply, генерируемые посредством ApplyToNL и BuildSpool, включают опции для eager spool, lazy spool и вообще без спула (no spool):

-- Eager spool
PhyOp_Spool Index-on-fly EAGER
      Leaf-Op 4
      Leaf-Op 2

-- Logical Lazy spool
PhyOp_Apply (x_jtInner)
    Leaf-Op 3
    LogOp_Spool Lazy
        Leaf-Op 6
        
-- Physical Lazy spool
PhyOp_Spool LAZY
    Leaf-Op 6

-- No spool
PhyOp_Apply (x_jtInner)
    Leaf-Op 3
    Leaf-Op 6

Оптимизатор также рассматривает реализацию логического join посредством физического Nested Loops Join посредством применения правила JNtoNL (join to nested loops):

PhyOp_LoopsJoin x_jtInner 
    Leaf-Op 3
    Leaf-Op 4
    ScaOp_Comp x_cmpGt
        ScaOp_Identifier QCOL: [T2].c2
        ScaOp_Identifier QCOL: [T1].c1

Обратите внимание, что физическим оператором является PhyOp_LoopsJoin, а не PhyOp_Apply, как было ранее. Оптимизатор рассматривает оба варианта.

После оценки стоимости предложенных комбинаций типа соединения, порядка соединения, типа спула, оптимизатор решает, что вариант Nested Loops Join является самым дешевым при общей стоимости 0.00657068 единиц.

Окончательный выход оптимизатора можно увидеть с флагом трассировки 8607:

*** Output Tree: ***
PhyOp_LoopsJoin x_jtInner
    PhyOp_Range TBL: @T2
    PhyOp_Range TBL: @T1
    ScaOp_Comp x_cmpGt
    ScaOp_Identifier QCOL: [T2].c2
    ScaOp_Identifier QCOL: [T1].c1

После преобразования в форму, используемую механизмом выполнения (флаг 7352):

Inner Join Nested Loops (0) 
    [QCOL: [T1].c1 TI(int,Null,ML=4)]
    [QCOL: [T2].c2 TI(int,Null,ML=4)]
  Table Scan Table Scan (1) 
        [QCOL: [T2].c2 TI(int,Null,ML=4)]
  Table Scan Table Scan (2) 
        [QCOL: [T1].c1 TI(int,Null,ML=4)]

Оптимизация синтаксиса Apply

Теперь перейдем к форме запроса с APPLY:

SELECT 
    T1.c1, 
    CA.c2 
FROM @T1 AS T1
CROSS APPLY 
(
    SELECT T2.c2
    FROM @T2 AS T2
    WHERE T2.c2 > T1.c1
) AS CA;

Входное дерево теперь представляет теперь логический apply, а не join, как мы видели раньше.

LogOp_Project QCOL: [T1].c1 QCOL: [T2].c2
    LogOp_Apply (x_jtInner)
    LogOp_Get TBL: @T1
    LogOp_Project
        LogOp_Select
            LogOp_Get TBL: @T2
            ScaOp_Comp x_cmpGt
                ScaOp_Identifier QCOL: [T2].c2
                ScaOp_Identifier QCOL: [T1].c1
        AncOp_PrjList 
    AncOp_PrjList 

Правило упрощения ApplyHandler преобразует это дерево в join (показан вывод из TF 8621):

Примененное правило: APPLY stack -> Join stack

*** Simplified Tree: ***
LogOp_Join
    LogOp_Get TBL: @T1
    LogOp_Get TBL: @T2
    ScaOp_Comp x_cmpGt
    ScaOp_Identifier QCOL: [T2].c2
    ScaOp_Identifier QCOL: [T1].c1

Это в точности то же самое логическое дерево, которое было получено при использовании синтаксиса с JOIN. Оптимизатор продолжит делать то же самое с тем же результатом, приводящим к Nested Loops Join в плане, несмотря на то, что мы стартовали с синтаксиса APPLY.

Пример Apply

Мы можем модифицировать тестовый скрипт, чтобы произвести план с Apply (вне зависимости от того, какой синтаксис, с APPLY или же JOIN, используется в спецификации запроса), добавив индекс в одну из этих таблиц:

DECLARE @T1 TABLE (c1 INTEGER NULL);
DECLARE @T2 TABLE (c2 INTEGER NULL INDEX i); -- New index
 
INSERT @T1 (c1)
VALUES (1), (2), (3);
 
INSERT @T2 (c2)
VALUES (1), (2), (3);
 
-- синтаксис Apply
SELECT T1.c1, CA.c2 
FROM @T1 AS T1
CROSS APPLY 
(
    SELECT * 
    FROM @T2 AS T2
    WHERE T2.c2 > T1.c1
) AS CA;
 
-- синтаксис Join
SELECT
    T1.c1,
    T2.c2
FROM @T1 AS T1
JOIN @T2 AS T2
    ON T2.c2 > T1.c1;

И снова эти запросы описывают один и тот же результирующий набор, а планы выполнения одинаковы для обеих форм запроса.

Теперь оптимизатор запросов выбирает Apply, а не Nested Loops Join, поэтому соединение имеет внешнюю ссылку (Outer References) и не имеет предиката (Predicate):


Этот план выполняется следующим образом:

• Для каждой строки из таблицы @T1

• Вернуть каждую строку из таблицы @T2, которая удовлетворяет предикату N2.c2 > T1.c1. Этот предикат оценивается оператором Index Seek, а не соединением.

Важное отличие состоит в том, что текущее значение столбца c1 передается как внешняя ссылка во внутреннюю сторону соединения, поэтому Index Seek может эффективно обнаружить совпадающие строки:


Это более эффективно, чем проверять все строки в операторе соединения.

Оптимизация синтаксиса Apply

Начнем наш анализ с формы запроса APPLY:

SELECT T1.c1, CA.c2 
FROM @T1 AS T1
CROSS APPLY 
(
    SELECT * 
    FROM @T2 AS T2
    WHERE T2.c2 > T1.c1
) AS CA;

Входное дерево содержит логический apply:

*** Входное дерево: ***
LogOp_Project QCOL: [T1].c1 QCOL: [T2].c2
    LogOp_Apply (x_jtInner)
    LogOp_Get TBL: @T1
    LogOp_Project
        LogOp_Select
            LogOp_Get TBL: @T2
            ScaOp_Comp x_cmpGt
                ScaOp_Identifier QCOL: [T2].c2
                ScaOp_Identifier QCOL: [T1].c1
        AncOp_PrjList 
    AncOp_PrjList 

Оно, как и прежде, трансформируется к join с помощью ApplyHandler:

Применено правило: APPLY stack -> Join stack

*** Упрощенное дерево: ***
LogOp_Join
    LogOp_Get TBL: @T1
    LogOp_Get TBL: @T2
    ScaOp_Comp x_cmpGt
    ScaOp_Identifier QCOL: [T2].c2
    ScaOp_Identifier QCOL: [T1].c1

Во время оптимизации на основе стоимости оптимизатор учитывает те же варианты, что и прежде, включая:

  • JoinCommute, чтобы поменять порядок входов соединения.
  • JoinToIndexOnTheFly для преобразования join в apply c внутренним eager index spool.

    Измененная схема (новый индекс на таблице @T2) означает, что теперь дереву оптимизации соответствует новое правило JNtoIdxLookup. Как говорит его имя, это новое правило исследования генерирует логически эквивалентное поддерево путем замены join на apply плюс внутренний поиск закладки в индексе (index lookup):

Правило Apply: JNtoIdxLookup - JN -> IDX LOOKUP

PhyOp_Apply lookup TBL: @T2 (1) (x_jtInner)
    Leaf-Op 3
    LogOp_SelectIdx(1)
        LogOp_GetIdx TBL: @T2 index 1
        ScaOp_Comp x_cmpGt
            ScaOp_Identifier QCOL: [T2].c2
            ScaOp_Identifier QCOL: [T1].c1

Оптимизатор также рассматривает варианты lazy spool и без спула для альтернатив apply, генерируемых JoinToIndexOnTheFly, однако вариант apply, создаваемый JNtoIdxLookup, оказывается самым дешевым с итоговой стоимостью плана 0.00657038 единиц:

*** Выходное дерево: ***
PhyOp_Apply lookup TBL: @T2 (1) (x_jtInner)
    PhyOp_Range TBL: @T1
    PhyOp_Range TBL: @T2
    ScaOp_Comp x_cmpGt
        ScaOp_Identifier QCOL: [T2].c2
        ScaOp_Identifier QCOL: [T1].c1

Скопированное дерево имеет вид:

Inner Join Nested Loops (0) 
    [QCOL: [T1].c1 TI(int,Null,ML=4)]
    [QCOL: [T2].c2 TI(int,Null,ML=4)]
  Table Scan Table Scan (1) 
        [QCOL: [T1].c1 TI(int,Null,ML=4)]
  Index Seek Index Seek (2)  CP 
        [QCOL: [T2].c2 TI(int,Null,ML=4)]

Обратите внимание, что мы стартовали с APPLY и имели логический apply во входном дереве. Оно было трансформировано в join, а затем преобразовано в физический apply с index lookup в процессе оптимизации на основе стоимости.

Оптимизация синтаксиса Join

Теперь перейдем к синтаксису с JOIN:

SELECT
    T1.c1,
    T2.c2
FROM @T1 AS T1
JOIN @T2 AS T2
    ON T2.c2 > T1.c1;

Входное дерево содержит cross join и реляционную выборку, которое упрощается к внутреннему join с помощью SELonJN:

*** Входное дерево: ***
LogOp_Project QCOL: [T1].c1 QCOL: [T2].c2
    LogOp_Select
    LogOp_Join
        LogOp_Get TBL: @T1
        LogOp_Get TBL: @T2
        ScaOp_Const TI(bit,ML=1) XVAR(bit,Value=1)
    ScaOp_Comp x_cmpGt
        ScaOp_Identifier QCOL: [T2].c2
        ScaOp_Identifier QCOL: [T1].c1
    AncOp_PrjList 

Примененное правило: SEL JN -> JN

*** Упрощенное дерево: ***
LogOp_Join
    LogOp_Get TBL: @T1
    LogOp_Get TBL: @T2
    ScaOp_Comp x_cmpGt
    ScaOp_Identifier QCOL: [T2].c2
    ScaOp_Identifier QCOL: [T1].c1

Это в точности то же самое дерево, что и упрощенное дерево для синтаксиса APPLY после трансформации apply к join с помощью ApplyHandler. Остальной процесс оптимизации продолжается точно так же, как и прежде, с тем же физическим apply в плане, выбранном с помощью реализации правила JNtoIdxLookup.

Заключение

Форма написания запроса SQL может оказать влияние на исходное логическое дерево, передаваемое в процессы компиляции и оптимизации, однако оптимизатор зачастую преобразует apply в join, и всегда может рассмотреть возможность альтернативы join в качестве apply.

Используется ли синтаксис с APPLY или JOIN в исходном запросе, это не обязательно определяет, какой оператор будет использовать план выполнения — apply (nested loops join с внешними ссылками) или обычный loops join (с предикатом, оцениваемым при соединении).

План с apply может быть более интуитивным, однако корреляции (внешние ссылки) означают лишь то, что возможная физическая реализация должна основываться на вложенных циклах. Join без корреляций может быть реализован вложенными циклами, поиском соответствий в хэше или слиянием с сортировкой. Оптимизатор исследует относительные преимущества apply и join в попытках найти разумный план выполнения за разумное время.

Добавить комментарий