По материалам статьи Craig Freedman: Merge Join

Эта статья посвящена оператору физического соединения - соединению слиянием (Merge Join или MJ). В отличие от Nested Loops Join, которое поддерживает любые предикаты соединения, соединение слиянием требует существования не менее одного предиката соединения по эквивалентности. Кроме того, получаемые соединением слиянием данные должны быть отсортированы по ключу соединения. Например, если мы имеем предикат соединения "T1.a = T2.b", таблица T1 должна быть отсортирована по T1.a, а таблица T2 должна быть сортирована по T2.b.

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

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

get first row R1 from   input 1

get first row R2 from   input 2

while not at the end   of either input

      begin

          if R1 joins with R2

              begin

                  get next row R2 from input 2

                  return (R1, R2)

              end

          else if R1 < R2

              get next row R1 from input 1

          else

              get next row R2 from input 2

    end

В отличие от Nested Loops Join, где общая стоимость может быть пропорциональна произведению числа строк получаемых на вход таблиц, в соединение слиянием каждая таблица читается только один раз, и общая стоимость пропорциональна сумме числа строк получаемых на входе таблиц. Таким образом, соединение слиянием очень часто является лучшим выбором для соединения больших наборов данных.

Сравнение соединений слиянием "один ко многим" и "многие ко многим"

Показанный выше псевдокод реализует алгоритм соединение слиянием "один ко многим". После соединения двух строк, может происходить исключении строки из R2, и последующий переход к строке из второго входного потока. Это предполагает, что никогда не будет перехода к строке из первого входного потока для соединения с исключённой строкой. Другими словами, в первом входном потоке не может быть дубликатов. С другой стороны, дубликаты вполне допустимы во втором входном потоке, поскольку текущая строка первого входного потока не исключается.

Соединение слиянием также может поддерживать слияние "многие ко многим". В этом случае, при каждом соединении двух строк нужно сохранять копию каждой строки второго входного потока. Это позволяет, при последующем обнаружении в первом входном потоке дубликатов строк, воспроизвести сохраненные строки. С другой стороны, если будет ясно, что следующая строка первого входного потока не является дубликатом, от сохраненных строк можно отказаться. Такие строки сохраняются во временно таблице базы tempdb. Размер дискового пространства, который для этого необходим, зависит от числа дубликатов во втором входном потоке.
Соединение слиянием "один ко многим" всегда будет эффективнее слияния "многие ко многим", поскольку для него не требуется временная таблица.

Для того, что бы задействовать слиянием "один ко многим", оптимизатор должен иметь возможность определить, что один из входных потоков состоит из уникальных строк. Как правило, это означает, что у такого входного потока существует уникальный индекс или в плане запроса присутствует явным образом оператор (например, сортировка при DISTINCT или группировка), который гарантирует, что строки на входе будут уникальны.

Сравнение SORT MERGE JOIN и INDEX MERGE JOIN

Существуют два пути получения отсортированных входных потоков соединения слиянием: мы можем явно отсортировать входной поток (используя оператор сортировки) или возможно чтение строк из индекса. Как правило, план запроса, использующий для сортировки индекс, будет обходиться дешевле, чем план запроса с явной сортировкой.

Предикаты соединения

Соединение слиянием поддерживает наличие нескольких предикатов соединения по эквивалентности, если входные потоки отсортированы для всех ключей соединения. Порядок сортировки не имеет значения, если оба входных потока отсортированы в одном порядке. Например, если имеется предикат соединения "T1.a = T2.a и T1.b = T2.b, " соединение слиянием будет задействовано, если оба T1 и T2 отсортированы любо по "(a, b)", либо по "(b, a)".

Кроме того, соединение слиянием поддерживает остаточные предикаты. Например, рассмотрим предикат соединения "T1.a = T2.a and T1.b > T2.b", хотя и нельзя использовать в соединении слиянием предикат неравенства, возможно частичное использование соединения по эквивалентности этого предиката, что позволяет задействовать соединение слиянием (предположительно, входные потоки отсортированы по столбцу "a"). Тогда, для каждой пары строк, которые соединяются по столбцу "a", становится возможным применение предиката неравенства. Если неравенство оценивает как истина (true), будет возвращаться соединяемая строка; в противном случае, от неё придётся отказаться.

Внешние и полусоединения

Соединение слиянием поддерживает все разновидности внешних соединений и полусоединений. Для реализации внешнего соединения, нужно проследить соединение каждой строки. Вместо того чтобы отказываться от не подлежащих соединению строк, генерируется и выдаётся на выход NULL значение. Подобным же способом реализованы полусоединения и анти-полусоединения.

При реализации полного внешнего соединения есть специальный случай, когда возможно использование соединения слиянием. В ряде случаев, соединение слиянием задействуется для полного внешнего соединения, даже если вообще нет предиката соединения по эквивалентности. Это очень похоже на соединение слиянием в варианте "многие ко многим", когда все строки от одного входного потока соединяются со всеми строками другого входного потока. Для решения этой задачи будет создана временная таблица, предназначенная для хранения и воспроизведения всех строк второго входного потока. Такой план поддерживается в качестве альтернативы полному внешнему соединению, реализованному для соединения вложенных циклов (см. мою предыдущую статью, в которой обсуждалось полное внешнее соединение).

Примеры

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

create table   T1 (a int, b int,   x char(200))
create table   T2 (a int, b int,   x char(200))

set nocount   on
declare @i int
set @i = 0
while @i < 1000
  begin
    insert T1 values   (@i * 2, @i * 5, @i)
    insert T2 values   (@i * 3, @i * 7, @i)
    set @i = @i + 1
  end

Давайте начнём с простого примера:

select *
from T1 join   T2 on T1.a = T2.a
option (merge   join)

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

Хотя строки во входных таблицах в действительности уникальны, оптимизатор не знает этого, и не может на это полагаться, почему и создаёт соединение "многие ко многим", что видно по ключевому слову MANY-TO-MANY.

Обратите внимание, что, как писалось выше, каждый просмотр таблицы выполнялся только один раз, независимо от числа обработанных строк. Также, обратите внимание, что сортировка T2 возвратила только 668 из 1000 строк. Что же случилось? После обработки 668 строк в T2, соединение слиянием столкнулось с такой строкой T2, которая больше любой строки в T1. Поэтому, с этого места, соединение слиянием начало читать все оставшиеся строки в T1. Как только был достигнут конец T1, соединение слиянием завершилось, даже притом, что не были прочитаны все строки в T2.

Теперь посмотрим, что случается, если создать индекс для T1:

create unique   clustered index   T1ab on T1(a, b)

И снова выполнить тот же самый запрос:

Это практически такой же план за исключением того, что сортировка теперь нужна только для T2, так как для получения нужного порядка сортировки можно использовать индекс по T1. Обратите внимание, что, даже имея уникальный индекс для T1, все еще получается соединение "многие ко многим". Почему так? Потому что индекс гарантирует уникальность по "(a, b)", а не только по столбцу "a". У столбца "a" допустимы дубликаты и, таким образом, пока соединение выполняется только по "a", будет задействовано соединение "многие ко многим".

Теперь давайте попробуем добавить индекс по T2:

create unique   clustered index   T2a on T2(a)

С двумя индексами больше не нужна подсказка оптимизатору для выбора соединения слиянием:

select *
from T1 join   T2 on T1.a = T2.a

^{Rows    Executes}      

^{334     1         |--Merge Join(Inner Join,MERGE:([T2].[a])=([T1].[a]),RESIDUAL:([T2].[a]=[T1].[a]))}

^{668     1              |--Clustered Index Scan(OBJECT:([T2].[T2a]), ORDERED FORWARD)}

^{1000    1              |--Clustered Index Scan(OBJECT:([T1].[T1ab]), ORDERED FORWARD)}

Заметьте, что при двух индексах в сортировке необходимости нет. Кроме того, уникальный индекс по T2 гарантирует уникальность значений столбца "a", вследствие чего становится возможным соединение "один ко многим". Обратите внимание, что ключевое слово MANY-TO-MANY исчезло из этого примера (в текстовом плане исполнения появились несколько вхождений ключевого слова ONE-TO-MANY).

Примечательно и то, что оптимизатор поменял порядок входных потоков, поместив уникальный T2 в начало, что позволило ему задействовать соединение "один ко многим".

Далее, давайте попробуем соединить по двум столбцам:

select *
from T1 join   T2 on T1.a = T2.a and   T1.b = T2.b

Обратите внимание, что теперь соединение осуществляется по двум ключам. Ещё интересней то, что при этом для упорядочивания используются индексы, включая индекс по одиночному столбцу T2. Как же индекс по единственному столбцу "a" может обеспечить порядок для двух столбцов "(a, b)"? Вспомним, что индекс по T2 - уникальный индекс. Можно добавить в конец ключа уникального индекса любой набор столбцов, и все равно получить тот же порядок. Это работает, потому что для каждого уникального значения ключа существует только одна строка. Строки будет автоматически отсортированы по любым дополнительным столбцам, которые добавляются в конец ключа.

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

select *
from T1 join   T2 on T1.a = T2.a and   T1.b > T2.b

А вот пример полного внешнего соединения:

select *
from T1 full   outer join   T2 on T1.a = T2.a

Обратите внимание, что теперь обрабатываются все 1000 строк из обеих таблиц; соединение больше не заканчивается после обработки первых 668 строк T2. Из-за внешнего соединения, должны быть прочитаны все строки T2, а NULL значения заменят те, которые не подлежат соединению.

И, наконец, давайте рассмотрим пример полного внешнего соединения без предиката соединения по эквивалентности (предупреждение: этот пример исполняется намного дольше, чем предыдущие примеры).

select *
from T1 full   outer join   T2 on T1.a < T2.a

Стоит заметить, что тут нет ключей слияния; только остаточный предикат.

Далее…

В следующей статье, я опишу хэш-соединение, третий и последний из физических операторов соединений.