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, хотя используют различный синтаксис запроса - APPLY в одном случае, и JOIN - в другом:
Оба запроса описывают один и тот же результирующий набор вне зависимости от содержимого таблиц. Планы выполнения идентичны и имеют одно и то же значение QueryPlanHash.
В обоих случаях оптимизатор запросов выбирает Nested Loops Join, а не Apply - оператор соединения имеет Predicate, но не имеет Outer References:
Этот план выполняется следующим образом:
• Для каждой строки из таблицы @T2:
Начнем с формы JOIN SQL-запроса:
Видно, что входное дерево передается в оптимизатор, используя флаг трассировки 8606 (также необходимо включить флаг трассировки 3604, чтобы получить выход отладки, показанный на вкладке сообщений SSMS):
Логически это cross join двух таблиц с последующей реляционной выборкой (фильтрацией) по предикату соединения. Оптимизатор упрощает его, сводя к внутреннему соединению с помощью правила SELonJN (реляционная выборка по соединению):
Оптимизатор рассматривает возможность переписать этот логический join на логический apply во время оптимизации на основе стоимости с помощью правила исследования JoinToIndexOnTheFly. Кандидат на замену представляет собой внутренний apply вместо join и внутренний Eager Index Spool (показан вывод на выходе флага трассировки 8619):
Также рассматривается обмен входами внутреннего соединения через JoinCommute:
Имея сгенерированное множество логических альтернатив, оптимизатор переходит к реализации с помощью физических операторов. Альтернативы apply, генерируемые посредством ApplyToNL и BuildSpool, включают опции для eager spool, lazy spool и вообще без спула (no spool):
Оптимизатор также рассматривает реализацию логического join посредством физического Nested Loops Join посредством применения правила JNtoNL (join to nested loops):
Обратите внимание, что физическим оператором является PhyOp_LoopsJoin, а не PhyOp_Apply, как было ранее. Оптимизатор рассматривает оба варианта.
После оценки стоимости предложенных комбинаций типа соединения, порядка соединения, типа спула, оптимизатор решает, что вариант Nested Loops Join является самым дешевым при общей стоимости 0.00657068 единиц.
Окончательный выход оптимизатора можно увидеть с флагом трассировки 8607:
После преобразования в форму, используемую механизмом выполнения (флаг 7352):
Теперь перейдем к форме запроса с APPLY:
Входное дерево теперь представляет теперь логический apply, а не join, как мы видели раньше.
Это в точности то же самое логическое дерево, которое было получено при использовании синтаксиса с JOIN. Оптимизатор продолжит делать то же самое с тем же результатом, приводящим к Nested Loops Join в плане, несмотря на то, что мы стартовали с синтаксиса APPLY.
Мы можем модифицировать тестовый скрипт, чтобы произвести план с Apply (вне зависимости от того, какой синтаксис, с APPLY или же JOIN, используется в спецификации запроса), добавив индекс в одну из этих таблиц:
И снова эти запросы описывают один и тот же результирующий набор, а планы выполнения одинаковы для обеих форм запроса.
Теперь оптимизатор запросов выбирает Apply, а не Nested Loops Join, поэтому соединение имеет внешнюю ссылку (Outer References) и не имеет предиката (Predicate):
Этот план выполняется следующим образом:
• Для каждой строки из таблицы @T1
Важное отличие состоит в том, что текущее значение столбца c1 передается как внешняя ссылка во внутреннюю сторону соединения, поэтому Index Seek может эффективно обнаружить совпадающие строки:
Это более эффективно, чем проверять все строки в операторе соединения.
Начнем наш анализ с формы запроса APPLY:
Входное дерево содержит логический apply:
Оно, как и прежде, трансформируется к join с помощью ApplyHandler:
Во время оптимизации на основе стоимости оптимизатор учитывает те же варианты, что и прежде, включая:
Оптимизатор также рассматривает варианты lazy spool и без спула для альтернатив apply, генерируемых JoinToIndexOnTheFly, однако вариант apply, создаваемый JNtoIdxLookup, оказывается самым дешевым с итоговой стоимостью плана 0.00657038 единиц:
Скопированное дерево имеет вид:
Обратите внимание, что мы стартовали с APPLY и имели логический apply во входном дереве. Оно было трансформировано в join, а затем преобразовано в физический apply с index lookup в процессе оптимизации на основе стоимости.
Теперь перейдем к синтаксису с JOIN:
Входное дерево содержит cross join и реляционную выборку, которое упрощается к внутреннему join с помощью SELonJN:
Это в точности то же самое дерево, что и упрощенное дерево для синтаксиса APPLY после трансформации apply к join с помощью ApplyHandler. Остальной процесс оптимизации продолжается точно так же, как и прежде, с тем же физическим apply в плане, выбранном с помощью реализации правила JNtoIdxLookup.
Форма написания запроса SQL может оказать влияние на исходное логическое дерево, передаваемое в процессы компиляции и оптимизации, однако оптимизатор зачастую преобразует apply в join, и всегда может рассмотреть возможность альтернативы join в качестве apply.
Используется ли синтаксис с APPLY или JOIN в исходном запросе, это не обязательно определяет, какой оператор будет использовать план выполнения - apply (nested loops join с внешними ссылками) или обычный loops join (с предикатом, оцениваемым при соединении).
План с apply может быть более интуитивным, однако корреляции (внешние ссылки) означают лишь то, что возможная физическая реализация должна основываться на вложенных циклах. Join без корреляций может быть реализован вложенными циклами, поиском соответствий в хэше или слиянием с сортировкой. Оптимизатор исследует относительные преимущества apply и join в попытках найти разумный план выполнения за разумное время.
Оптимизатор в состоянии преобразовать 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Правило упрощения ApplyHandler преобразует это дерево в join (показан вывод из TF 8621):
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
Примененное правило: 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); -- Новый индекс
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 в попытках найти разумный план выполнения за разумное время.
Обратные ссылки
Нет обратных ссылок
Автор не разрешил комментировать эту запись
Комментарии
Показывать комментарии Как список | Древовидной структурой