Соединения слиянием (merge join)

Пересказ статьи Bert Wagner. Visualizing Merge Join Internals And Understanding Their Implications

Merge Joins

Merge Joins (соединения слиянием) теоретически являются самыми быстрыми физическими операторами соединения, однако они требуют, чтобы данные обоих входов были отсортированы.

Базовый алгоритм работает следующим образом: SQL Server сравнивает первые строки обоих отсортированных входов. Затем сравнение продолжается со следующими строками второго входа до тех пор, пока значения соответствуют значению первого входа.

Если соответствий больше нет, SQL Server переходит к следующей строке того входа, который имеет меньшее значение — и затем продолжает выполнение сравнений, выводя каждую соединенную запись. (Подробней об операции merge join можно почитать в публикации Крейга Фридмана).

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

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

Что показывают нам соединения слиянием?

Знание механизма выполнения merge join позволяет нам понять, что думает оптимизатор о наших данных и восходящих потоках данных от операторов соединения. Это дает нам возможность сосредоточиться на настройке производительности.

Ниже приведены несколько сценариев, которые следует принять во внимание, когда вы встретите merge join в плане выполнения вашего запроса:

  • Оптимизатор выбирает использование merge join, когда входные данные уже отсортированы или SQL Server может выполнить сортировку данных с относительно небольшой стоимостью. Кроме того, оптимизатор весьма пессимистичен относительно вычисления стоимости merge joins, поэтому, если merge join попадает в ваши планы, это, скорее всего, говорит об их эффективности.
  • Хотя merge join может быть эффективен, всегда полезно посмотреть, почему данные, поступающие в этот оператор, уже отсортированы:
    • Если сортировка возникла благодаря тому, что merge join вытащил данные непосредственно из индекса, отсортированного по ключу соединения, то тут не о чем беспокоиться.
    • Если же оптимизатор добавил сортировку в восходящий поток данных для merge join, то полезно выяснить, не заставит ли эта предварительная сортировка SQL Server выполнять лишние сортировки . Зачастую достаточно просто переопределить включенный в индекс столбец на ключевой столбец — если вы добавляете его последним столбцом в ключ индекса, то отрицательное влияние подобного действия минимально, зато вы позволите SQL Server использовать merge join без всякой дополнительной сортировки.
  • Если ваши входы содержат много дубликатов, будет полезно проверить, действительно ли merge join наиболее эффективный оператор для выполнения соединения. Как сказано выше, соединения слиянием многие-ко-многим требуют использования tempdb, что может стать узким местом производительности.

Итак, хотя merge join обычно не являются теми узлами в плане выполнения, которые своей высокой стоимостью диагностируют проблему, всегда полезно исследовать восходящие операторы с целью поиска дополнительных возможностей улучшения производительности.


ЗАМЕЧАНИЕ. Всегда имеются исключения из правил. Merge join имеет самый быстрый алгоритм, поскольку каждую строку из входных источников данных требуется прочитать только один раз. Однако возможности оптимизации, имеющие место в других операторах соединения, могут при определенных обстоятельствах дать лучшую производительность.

Например, внешняя таблица с единственной строкой и индексированной внутренней таблице при использовании nested loops join (соединение вложенными циклами) превзойдет merge join при тех же условиях за счет оптимизации внутренних циклов:

DROP TABLE IF EXISTS T1;
GO
CREATE TABLE T1 (Id int identity PRIMARY KEY, Col1 CHAR(1000));
GO

INSERT INTO T1 VALUES('');
GO

DROP TABLE IF EXISTS T2;
GO
CREATE TABLE T2 (Id int identity PRIMARY KEY, Col1 CHAR(1000));
GO

INSERT INTO T2 VALUES('');
GO 100

-- Включите планы выполнения и проверьте фактическое число строк для T2
SELECT *
FROM T1 INNER LOOP JOIN T2 ON T1.Id = T2.Id;

SELECT *
FROM T1 INNER MERGE JOIN T2 ON T1.Id = T2.Id;

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

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

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