Sort Merge Join¶

Sort Merge Join — это алгоритм соединения (join) двух реляционных таблиц, основанный на предварительной сортировке обеих таблиц по ключу соединения и последующем однопроходном слиянии отсортированных наборов данных. Относится к классу алгоритмов соединения, используемых в системах управления базами данных (СУБД) и системах обработки больших данных (например, Apache Hadoop, Spark). В отличие от вложенного цикла (Nested Loop Join), Sort Merge Join эффективен при соединении больших объёмов данных, особенно когда обе таблицы уже отсортированы по ключу соединения или когда требуется полное соединение (full outer join).

¶Принцип работы

Алгоритм Sort Merge Join состоит из двух основных фаз: фазы сортировки и фазы слияния.

¶Фаза сортировки

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

¶Фаза слияния

После сортировки обе таблицы сканируются параллельно. Для каждой строки из первой таблицы (левой) алгоритм ищет совпадающие строки во второй таблице (правой). Поскольку обе таблицы отсортированы, поиск выполняется не путём полного перебора, а последовательным продвижением указателей. Если ключи совпадают, строки объединяются в результирующий набор. Если ключ из левой таблицы меньше ключа из правой, указатель левой таблицы сдвигается вперёд; если больше — сдвигается указатель правой таблицы. При обнаружении совпадения может потребоваться возврат указателя в правой таблице, если в ней есть несколько строк с одинаковым ключом (дубликаты).

¶Сложность и производительность

Временная сложность алгоритма в общем случае составляет O(N log N + M log M + N + M), где N и M — количество строк в левой и правой таблицах соответственно. Первые два слагаемых соответствуют сортировке, последние — слиянию. Если обе таблицы уже отсортированы, сложность снижается до O(N + M).

Основные факторы, влияющие на производительность:

• Размер таблиц: алгоритм хорошо масштабируется на большие объёмы данных.
• Наличие дубликатов: при большом количестве строк с одинаковыми ключами в одной из таблиц может потребоваться возврат указателя, что увеличивает время слияния.
• Доступная память: недостаток памяти приводит к использованию внешней сортировки, что значительно замедляет выполнение.
• Тип соединения: для внутреннего соединения (INNER JOIN) алгоритм работает эффективно; для внешних соединений (LEFT, RIGHT, FULL OUTER JOIN) требуется дополнительная обработка строк, не имеющих совпадений.

¶Сравнение с другими алгоритмами соединения

¶Sort Merge Join vs Nested Loop Join

• Nested Loop Join эффективен для малых таблиц (особенно если одна из них помещается в память) и для соединений по неравенству. При больших таблицах его сложность составляет **O(N * M)**, что делает его неприемлемым.
• Sort Merge Join предпочтительнее для больших таблиц, особенно если обе таблицы уже отсортированы или требуется полное соединение.

¶Sort Merge Join vs Hash Join

• Hash Join обычно быстрее, когда обе таблицы большие, но не отсортированы, и соединение выполняется по равенству. Он требует построения хеш-таблицы для одной из таблиц.
• Sort Merge Join может быть быстрее, если таблицы уже отсортированы, или если требуется сортировка результата по ключу соединения (например, для последующей обработки). Также он эффективнее при соединениях по неравенству (например, a.key < b.key), хотя такие случаи редки.

¶Применение

Sort Merge Join широко используется в:

• Реляционных СУБД: PostgreSQL, Oracle, MySQL (в некоторых версиях), Microsoft SQL Server. В PostgreSQL, например, этот алгоритм применяется, когда обе таблицы большие и не помещаются в память, или когда требуется сортировка результата.
• Системах обработки больших данных: Apache Hadoop (MapReduce), Apache Spark, Apache Hive. В этих системах Sort Merge Join является одним из основных алгоритмов для соединения больших наборов данных, распределённых по кластеру.
• Системах потоковой обработки: в некоторых случаях, когда данные поступают в отсортированном виде.

¶Пример работы

Рассмотрим две таблицы: Таблица А (столбцы: id, name) и Таблица Б (столбцы: id, value). Соединение выполняется по столбцу id.

Таблица А (после сортировки):

Таблица Б (после сортировки):

Фаза слияния:

1. Указатели на первых строках: (1, A) и (1, X). Ключи совпадают → формируется строка (1, A, X). Указатель в таблице Б сдвигается на (2, Y).
2. Указатели: (1, A) и (2, Y). Ключ левой (1) меньше ключа правой (2) → указатель левой сдвигается на (2, B).
3. Указатели: (2, B) и (2, Y). Ключи совпадают → формируется строка (2, B, Y). Указатель в таблице Б сдвигается на (2, Z).
4. Указатели: (2, B) и (2, Z). Ключи совпадают → формируется строка (2, B, Z). Указатель в таблице Б сдвигается на (4, W).
5. Указатели: (2, B) и (4, W). Ключ левой (2) меньше ключа правой (4) → указатель левой сдвигается на (3, C).
6. Указатели: (3, C) и (4, W). Ключ левой (3) меньше ключа правой (4) → указатель левой сдвигается на конец (нет строк).
7. Строка (4, W) из таблицы Б не имеет совпадений (для INNER JOIN она не включается).

Результат (INNER JOIN):

¶Интересные факты

• Sort Merge Join является одним из трёх классических алгоритмов соединения, наряду с Nested Loop Join и Hash Join. В современных СУБД оптимизатор запросов выбирает между ними на основе статистики по таблицам и доступных индексов.
• В распределённых системах, таких как Apache Spark, Sort Merge Join часто реализуется в два этапа: сначала данные перераспределяются (shuffle) по ключам, затем сортируются и сливаются в рамках каждого раздела.
• Алгоритм естественным образом поддерживает соединения по неравенству (например, a.key < b.key), но в таких случаях фаза слияния усложняется, так как для каждой строки из левой таблицы может потребоваться сканирование нескольких строк из правой.

¶Источники

• Гарсиа-Молина, Г., Ульман, Дж., Уидом, Дж. «Системы баз данных. Полный курс». — М.: Вильямс, 2004.
• Ramakrishnan, R., Gehrke, J. «Database Management Systems». — McGraw-Hill, 2003.
• Документация PostgreSQL: «Chapter 11. Performance Tips» (раздел о методах соединения).
• Apache Spark Documentation: «Spark SQL Guide» (раздел о join-стратегиях).