Skip to content

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 в реальном мире.

Trackbacks

No Trackbacks

Comments

Display comments as Linear | Threaded

No comments

The author does not allow comments to this entry

Add Comment

Enclosing asterisks marks text as bold (*word*), underscore are made via _word_.
Standard emoticons like :-) and ;-) are converted to images.

To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA

Form options

Submitted comments will be subject to moderation before being displayed.