Алгоритм соединения слиянием сортированных списков: различия между версиями

Интерактивная навигация по истории

(Показать все непатрулированные изменения)

[непроверенная версия]

← Предыдущая правка

Содержимое удалено Содержимое добавлено

ВизуальныйВики-текст

Линейный

Текущая версия от 11:23, 19 октября 2024

Алгоритм соединения слиянием сортированных списков (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

@@ Строка 1: / Строка 1: @@
 '''Алгоритм соединения слиянием сортированных списков''' (merge join, sort merge join, sort-merge join) — разновидность [[алгоритм соединения (СУБД)|алгоритма соединения]].
-Алгоритм получает на вход 2 таблицы и условие соединения. Результатом его работы является таблица с результатами соединения.
+Алгоритм получает на&nbsp;вход две таблицы и&nbsp;условие соединения. Результатом его работы является таблица с&nbsp;результатами соединения.
-Входные таблицы должны быть отсортированы по столбцам, участвующим в условии соединения. Соединение осуществляется за одно сканирование (проход по) каждой из входных таблиц. То есть одна и таже строка считывается только одина раз, что даёт ему преимущество перед [[алгоритм соединения вложенными циклами|соединением вложенными циклами]].
+Входные таблицы должны быть отсортированы по&nbsp;столбцам, участвующим в&nbsp;условии соединения. Соединение осуществляется за&nbsp;одно сканирование (проход&nbsp;по) каждой из&nbsp;входных таблиц. То есть одна и&nbsp;та&nbsp;же строка считывается только один раз, что даёт преимущество перед [[алгоритм соединения вложенными циклами|соединением вложенными циклами]].
-Простой пример на псевдокоде:
+Простой пример на&nbsp;[[Псевдокод (язык описания алгоритмов)|псевдокоде]]:
+<pre>
- //нужно соеденить Таблицу 1 и Таблицу 2
+ //нужно соединить Таблицу 1 и&nbsp;Таблицу 2
- //по условию: Таблица1.Колонка1 = Таблица2.Колонка2
+ //по&nbsp;условию: Таблица1.Колонка1 = Таблица2.Колонка2
- //Для упрощения примера будем считать, что значения в Колонке2 уникальны
+ //Для упрощения примера будем считать, что значения в&nbsp;Колонке2 уникальны
  Таблица1.Сортировать(Колонка1);
  Таблица2.Сортировать(Колонка2);
- Таблица1.СтатьНаПервуюЗапись;
+ Таблица1.ВстатьНаПервуюЗапись;
- Таблица2.СтатьНаПервуюЗапись;
+ Таблица2.ВстатьНаПервуюЗапись;
- Пока Таблица1.НеПоследняяЗапись и Tаблица2.НеПоследняяЗапись
+ Пока Таблица1.НеПоследняяЗапись и&nbsp;Таблица2.НеПоследняяЗапись
  {
-     Пока Таблица1.Колонка1 < Taблица2.Колонка2
+     Если Таблица1.Колонка1 < Таблица2.Колонка2
+     {
          Таблица1.ПерейтиКСледующейЗаписи;
+     }
-     Если Таблица1.Колонка1 = Таблица2.Колонка2
+     Иначе Если Таблица1.Колонка1 = Таблица2.Колонка2
      {
          Вывести (Таблица1.ТекущаяЗапись, Таблица2.ТекущаяЗапись);
          Таблица1.ПерейтиКСледующейЗаписи;
+         Таблица2.ПерейтиКСледующейЗаписи;
      }
+     Иначе Если Таблица1.Колонка1 > Таблица2.Колонка2
-     Пока Таблица1.Колонка1 > Таблица2.Колонка2
      {
          Таблица2.ПерейтиКСледующейЗаписи;
      }
  }
+</pre>
+== Преимущества ==
+* Соединение слиянием эффективнее, чем&nbsp;[[алгоритм соединения вложенными циклами]], при&nbsp;условии, что&nbsp;списки изначально были отсортированы. В&nbsp;принципе, накладные расходы на&nbsp;сортировку могут быть распределены между несколькими операциями соединения.
+* Соединение слиянием в&nbsp;отличие от&nbsp;[[алгоритм соединения хешированием|соединения с&nbsp;использованием хеширования]] может использоваться при&nbsp;больших размерах соединяемых таблиц.
+== Недостатки ==
+* Главным недостатком алгоритма является необходимость в&nbsp;предварительной сортировке списков. Накладные расходы на&nbsp;сортировку могут быть неприемлемо высокими.
+* При&nbsp;реализации в&nbsp;[[СУБД]], соединение слиянием требует больше памяти и&nbsp;менее гибко, чем [[алгоритм соединения вложенными циклами]]. В&nbsp;связи с&nbsp;этим на&nbsp;практике рекомендуют избегать этого вида соединения. Во&nbsp;многих СУБД соединение слиянием по&nbsp;умолчанию не&nbsp;используется оптимизатором запросов и&nbsp;должно быть включено явно.
+* Соединение слиянием, как и [[алгоритм соединения хешированием]], требует в условиях наличия не менее одного условия равенства.
+== Ссылки ==
-Преимущества:
+* [http://www.sql.ru/articles/mssql/2007/051102mergejoin.shtml#20 Craig Freedman: Материалы статьи Merge Join]
-* Соединение слиянием эффективнее, чем [[алгоритм соединения вложенными циклами]], при условии, что списки изначально были отсортированы. В принципе, накладные расходы на сортировку могут быть распределены между несколькими операциями соединения.
-* Соединение слиянием в отличие от [[алгоритм соединения хэшированием|соединения с использование хэширования]] может использоваться при больших размерах соединяемых таблиц.
-* Соединение слиянием может использоваться для соединений с условиями отличными от равенства, чего не позволяет [[алгоритм соединения хэшированием]]. Однако допустимы не любые условия соединения.
+{{Нет источников |дата=2024-10-19}}
-Недостатки:
-* Главным недостатком алгоритма является необходимость в предварительной сортировке списков. Накладные расходы на сортировку могут быть неприемлемо высокими.
-* При реализации в [[СУБД]], соединение слиянием требует больше памяти и менее гибко, чем [[алгоритм соединения вложенными циклами]].Многие авторы, в связи с этим, на практике рекомендуют избегать этого вида соединения. Во многих СУБД соединение слиянием по умолчанию не используется оптимизатором запросов и должно быть включено явно.
 [[Категория:СУБД]]
-[[Категория:Алгоритмы]]
+[[Категория:Алгоритмы баз данных]]

Алгоритм соединения слиянием сортированных списков: различия между версиями

Текущая версия от 11:23, 19 октября 2024

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

Недостатки

Ссылки

Навигация

Поиск