Алгоритм соединения слиянием сортированных списков (merge join, sort merge join, sort-merge join) — разновидность алгоритма соединения.
Алгоритм получает на вход две таблицы и условие соединения. Результатом его работы является таблица с результатами соединения.
Входные таблицы должны быть отсортированы по столбцам, участвующим в условии соединения. Соединение осуществляется за одно сканирование (проход по) каждой из входных таблиц. То есть одна и та же строка считывается только один раз, что даёт преимущество перед соединением вложенными циклами.
Простой пример на псевдокоде:
//нужно соединить Таблицу 1 и Таблицу 2 //по условию: Таблица1.Колонка1 = Таблица2.Колонка2 //Для упрощения примера будем считать, что значения в Колонке2 уникальны
Таблица1.Сортировать(Колонка1); Таблица2.Сортировать(Колонка2); Таблица1.ВстатьНаПервуюЗапись; Таблица2.ВстатьНаПервуюЗапись; Пока Таблица1.НеПоследняяЗапись и Таблица2.НеПоследняяЗапись { Если Таблица1.Колонка1 < Таблица2.Колонка2
Таблица1.ПерейтиКСледующейЗаписи;
Иначе Если Таблица1.Колонка1 = Таблица2.Колонка2
Вывести (Таблица1.ТекущаяЗапись, Таблица2.ТекущаяЗапись); Таблица1.ПерейтиКСледующейЗаписи; Таблица2.ПерейтиКСледующейЗаписи;
Иначе Если Таблица1.Колонка1 > Таблица2.Колонка2
Таблица2.ПерейтиКСледующейЗаписи;
Преимущества Соединение слиянием эффективнее, чем алгоритм соединения вложенными циклами, при условии, что списки изначально были отсортированы. В принципе, накладные расходы на сортировку могут быть распределены между несколькими операциями соединения. Соединение слиянием в отличие от соединения с использованием хеширования может использоваться при больших размерах соединяемых таблиц.
Недостатки Главным недостатком алгоритма является необходимость в предварительной сортировке списков. Накладные расходы на сортировку могут быть неприемлемо высокими. При реализации в СУБД, соединение слиянием требует больше памяти и менее гибко, чем алгоритм соединения вложенными циклами. В связи с этим на практике рекомендуют избегать этого вида соединения. Во многих СУБД соединение слиянием по умолчанию не используется оптимизатором запросов и должно быть включено явно. Соединение слиянием, как и алгоритм соединения хешированием, требует в условиях наличия не менее одного условия равенства.
Ссылки Craig Freedman: Материалы статьи Merge Join
Категория:СУБД Категория:Алгоритмы баз данных