По материалам статьи Craig Freedman: Nested Loops Join
SQL Server поддерживает три физические оператора соединений: соединение вложенных циклов, соединение слиянием и хэш-соединение. В этой статье я опишу соединение вложенных циклов - Nested Loops Join (или NL-соединение, для краткости).
Основной алгоритм
В упрощённом виде, Nested Loops Join (далее будем называть его соединением вложенных циклов) сравнивает каждую строку одной таблицы (называемой внешней таблицей) с каждой строке другой таблицы (называемой внутренней таблицей), ища те строки, которые удовлетворяют предикату соединения. Обратите внимание, что термины "внутренняя" и "внешняя" многозначны; их понимание зависит от контекста. "Внутренняя таблица" и "внешняя таблица" относится к потребляемым соединением строкам. "Внутреннее соединение" и "внешнее соединение" относятся к логическим операциям.
Этот алгоритм в псевдокоде можно представить таким образом:
for each row R1 in the outer table
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)Эти вложенные циклы представляют тот самый алгоритм, который дал название соединению вложенных циклов.
Все строки должны подвергнуться сравнению, и, таким образом, стоимость этого алгоритма пропорциональна размеру внешней таблицы, умноженному на размер внутренней таблицы. Поскольку при увеличении размеров соединяемых таблиц стоимость растет очень сильно, на практике её уменьшают путём сокращения выборки из внутренней таблицы, строки которой обрабатываются для каждой строки внешней таблицы.
Для последующих примеров давайте использовать ту же самую схему, которая была в моей предшествующей статье:
create table Customers (Cust_Id int, Cust_Name varchar(10))
insert Customers values (1, 'Craig')
insert Customers values (2, 'John Doe')
insert Customers values (3, 'Jane Doe')
create table Sales (Cust_Id int, Item varchar(10))
insert Sales values (2, 'Camera')
insert Sales values (3, 'Computer')
insert Sales values (3, 'Monitor')
insert Sales values (4, 'Printer')Рассмотрим такой запрос:
select *
from Sales S inner join Customers C
on S.Cust_Id = C.Cust_Id
option(loop join)Я использовал подсказку оптимизатору "loop join" для того, чтобы явно задать соединение вложенных циклов. В результате, будет получен показанный ниже план исполнения запроса, который был получен при выполнении с установкой "set statistics profile on":
В этом плане исполнения внешней является таблица Customers, в то время как внутренней таблицей является Sales. Таким образом, всё начинается с просмотра таблицы Customers, откуда выбираются клиенты (по одному) и, для каждого из них просматривается таблица Sales. Поскольку у нас в таблице 3 клиента, просмотр таблицы Sales выполняется 3 раза. Каждый просмотр таблицы Sales возвращает 4 строки. Мы сравниваем каждую продажу с текущим клиентом и оцениваем, одинаковый ли у пары строк Cust_Id. Если это так, возвращаем эту пару строк. У нас имеется 3 клиента и 4 продажи, так что это сравнение исполняется всего 3*4 = 12 раз. Только три из этих сравнений соответствию заданным требованиям.
Теперь посмотрим, что случается, если создать индекс для таблицы Sales:
create clustered index CI on Sales(Cust_Id)Теперь мы получаем такой план:
На этот раз, вместо просмотра таблицы Sales выполняется поиск по индексу. Поиск по индексу все еще делается три раза, по разу для каждого клиента, но каждый поиск по индексу возвращает только те строки, которые ссылаются на C.Cust_Id и квалифированы предикатом соединения. Таким образом, поиск возвращает только 3 строки по сравнению с 12 строками, возвращаемыми при просмотре таблицы.
Обратите внимание, что поиск по индексу зависит от C.CustId, который получается из внешней таблицы соединения, путём просмотра таблицы Customers. Каждый раз, когда выполняется поиск по индексу (как Вы помните, он выполняется три раза - по одному для каждого клиента), C.CustId будет иметь разные значения. Обратите внимание, что C.CustId, по сути, является "коррелированным параметром". Если соединение вложенных циклов использует коррелированные параметры, они будут показаны в плане исполнения, как внешние ссылки "OUTER REFERENCES". Соединения вложенных циклов часто встречаются там, где имеется поиск по индексу, который зависит от коррелированного параметра, и эта зависимость носит характер соединения индекса "index join". Это распространённый сценарий.
Какие типы предикатов соединения поддерживает соединение вложенных циклов?
Соединение вложенных циклов поддерживает все предикаты соединения, включая предикаты эквивалентности (равенство) и предикаты неравенства.
Какие логические операторы соединения поддерживает соединение вложенных циклов?
Соединение вложенных циклов поддерживает следующие логические операторы соединения:
Внутреннее соединение
Левое внешнее соединение
Перекрестное соединение
CROSS APPLY и OUTER APPLY
Левое полусоединение и левое анти-полусоединение
Соединение вложенных циклов не поддерживает следующие логические операторы соединения:
Правое и полное внешние соединения
Правое полусоединение и правое анти-полусоединение
Почему соединение вложенных циклов поддерживает только левые соединения?
Алгоритм соединения вложенных циклов легко поддаётся расширению, позволяющему поддерживать левое внешнее и полусоединение. В качестве примера, ниже показан псевдокод для левого внешнего соединения. Можно написать подобный псевдокод для левого полусоединения и левого анти-полусоединения.
for each row R1 in the outer table
begin
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)
if R1 did not join
return (R1, NULL)
endЭтот алгоритм отслеживает соединение каждой строки внешней таблицы, и, если после просмотра всех строк внутренней таблицы не удалось найти для соединения строку во внутренней таблице, создаёт дополнительные строки с NULL значениями.
Теперь давайте посмотрим, какие возможности существуют для поддержки правого внешнего соединения. В этом случае, нужно возвратить пары (R1, R2) для удовлетворяющих условию соединения строк, и пары (NULL, R2) для строк внутренней таблицы, которые не удовлетворяют условие соединения. Проблема состоит в том, что просмотр внутренней таблицы выполняется несколько раз, по одному разу для каждой строки внешнего соединения. В результате этих нескольких сканирований, могут быть получены те же самые строки внутренней таблицы. При этом неизвестно, как определить, что конкретная строка внутренней таблицы не удовлетворяет или не будет удовлетворять условию соединения? Кроме того, если мы используем соединение индекса, некоторые строками внутренней таблицы могут вообще оказаться пропущенными, хотя они должны быть возвращены для внешнего соединения.
К счастью, поскольку правое внешнее соединение легко переписать как левое внешнее соединение, а правое полусоединение переписывается левым полусоединение, остаётся возможность использовать соединение вложенных циклов для правого внешнего и полусоединения. Однако, хотя такие преобразования и допустимы, они могут повлиять на производительность. Например, соединение "Customer left outer join Sales" применённое на указанной выше схеме с кластеризованным индексом по Sales, может использовать поиск по индексу Sales по аналогии с тем, как это делается в примере по внутренним соединениям. С другой стороны, соединение "Customer right outer join Sales" можно преобразовать в "Sales left outer join Customer", но теперь понадобится индекс по Customer.
Почему не поддерживаются полные внешние соединения?
Соединение вложенных циклов не поддерживает полное внешнее соединение. Однако, всегда можно преобразовать "T1 full outer join T2" в "T1 left outer join T2 UNION T2 left anti-semi-join T1". В основе подобного преобразования лежит преобразование полного внешнего соединения в левое внешнее соединение, которое включает все подлежащие соединению пары строк из T1 и T2, и все строки T1, который не подлежат соединению, после чего, с помощью анти-полусоединения, добавляются строки T2, которые также не подлежат соединению. Вот так это может выглядеть:
select *
from Customers C full outer join Sales S
on C.Cust_Id = S.Cust_Id
Конкатенация тут представляет собой объединение красных строк (2-4) - левое внешнее соединение, и зеленых строк (5-9) - полусоединение, что позволяет реализовать полное внешнее соединение. Compute Scalar - это просто вычисление константы NULL для столбцов Customer, которое необходимо потому, что само по себе полусоединение не может генерировать выходные значения для внутренней таблицы (в этом случае имеется ввиду таблица Customer). Получается, что полусоединение только проверяет существование; т.е. то, что нет фактического соответствия никакой строке. TOP применяется в целях дополнительной (не обязательной) оптимизации, это позволяет прекратить просмотр таблицы при создании более чем одной строки. Ещё раз подчеркну, полусоединение только выполняет проверку на существование, поэтому единственное соответствие - это всё, что нам тут нужно. Говоря: "не обязательной", я имел ввиду то, что полусоединение остановилось бы после первого соответствия даже без TOP.
Обратите внимание, что в последнем примере, оптимизатор выбирает просмотр внутреннего кластеризованного индекса даже при том, что вполне можно было использовать поиск. Это обусловлено стоимостью решения. Таблица настолько маленькая (помещается на одной странице), что нет никакой разницы между просмотром и поиском.
NL-соединение - это хорошо или плохо?
Это некорректный вопрос. Не бывает "лучшего" алгоритма соединений, и никакой алгоритм соединения не может считаться хорошим или плохим. Каждый алгоритм соединения хорошо работает в определённых условиях и может плохо работать в других условиях. Поскольку эффективность соединения вложенных циклов зависит от размера внешних данных, умножаемых на размер внутренних данных, это соединение лучше всего использовать для относительно маленьких наборов входных данных. Внутренний набор данных не обязательно должен быть маленьким, но, если он большой, может помочь создание индекса по ключу соединения с хорошей селективностью.
В некоторых случаях, соединение вложенных циклов может оказаться единственным алгоритмом соединения, который SQL Server сможет использовать. SQL Server должен использовать соединение вложенных циклов в случае перекрестных соединений, а так же при некоторых сложных CROSS APPLY и OUTER APPLY. Кроме того, с одним исключением (для полного внешнего соединения), соединение вложенных циклов является единственным доступным алгоритмом соединения, который SQL Server может использовать без предикатов соединения по эквивалентности.
Комментариев нет:
Отправить комментарий