Алгоритм соединения слиянием сортированных списков

Алгоритм соединения слиянием сортированных списков (merge join, sort merge join, sort-merge join) — разновидность алгоритма соединения.

Алгоритм получает на вход 2 таблицы и условие соединения. Результатом его работы является таблица с результатами соединения.

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

Простой пример на псевдокоде:

//нужно соеденить Таблицу 1 и Таблицу 2  
//по условию: Таблица1.Колонка1 = Таблица2.Колонка2
//Для упрощения примера будем считать, что значения в Колонке2 уникальны
Таблица1.Сортировать(Колонка1);
Таблица2.Сортировать(Колонка2);
Таблица1.ВстатьНаПервуюЗапись;
Таблица2.ВстатьНаПервуюЗапись;
Пока Таблица1.НеПоследняяЗапись и Tаблица2.НеПоследняяЗапись
{
    Пока Таблица1.Колонка1 < Taблица2.Колонка2
        Таблица1.ПерейтиКСледующейЗаписи;
    Если Таблица1.Колонка1 = Таблица2.Колонка2
    {
        Вывести (Таблица1.ТекущаяЗапись, Таблица2.ТекущаяЗапись);
        Таблица1.ПерейтиКСледующейЗаписи;
    }
    Пока Таблица1.Колонка1 > Таблица2.Колонка2
    {
        Таблица2.ПерейтиКСледующейЗаписи;
    }                   
}                       

Преимущества:

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

Недостатки:

  • Главным недостатком алгоритма является необходимость в предварительной сортировке списков. Накладные расходы на сортировку могут быть неприемлемо высокими.
  • При реализации в СУБД, соединение слиянием требует больше памяти и менее гибко, чем алгоритм соединения вложенными циклами.Многие авторы, в связи с этим, на практике рекомендуют избегать этого вида соединения. Во многих СУБД соединение слиянием по умолчанию не используется оптимизатором запросов и должно быть включено явно.
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home