Sort-merge join (original) (raw)
Nella teoria delle basi di dati, l'algoritmo sort merge join (o anche solo merge join) si distingue dagli altri algoritmi di join perché prima di effettuare i confronti ordina (sort) le relazioni secondo l'attributo di join. Una volta ordinate le unisce (merge). Appena viene trovata una corrispondenza tra tuple provenienti da relazioni diverse, essa viene messa nel result set di output.
| Property | Value |
|---|---|
| dbo:abstract | The sort-merge join (also known as merge join) is a join algorithm and is used in the implementation of a relational database management system. The basic problem of a join algorithm is to find, for each distinct value of the join attribute, the set of tuples in each relation which display that value. The key idea of the sort-merge algorithm is to first sort the relations by the join attribute, so that interleaved linear scans will encounter these sets at the same time. In practice, the most expensive part of performing a sort-merge join is arranging for both inputs to the algorithm to be presented in sorted order. This can be achieved via an explicit sort operation (often an external sort), or by taking advantage of a pre-existing ordering in one or both of the join relations. The latter condition, called interesting order, can occur because an input to the join might be produced by an index scan of a tree-based index, another merge join, or some other plan operator that happens to produce output sorted on an appropriate key. Interesting orders need not be serendipitous: the optimizer may seek out this possibility and choose a plan that is suboptimal for a specific preceding operation if it yields an interesting order that one or more downstream nodes can exploit. Let's say that we have two relations and and . fits in pages memory and fits in pages memory. So, in the worst case sort-merge join will run in I/Os. In the case that and are not ordered the worst case time cost will contain additional terms of sorting time: , which equals (as linearithmic terms outweigh the linear terms, see Big O notation – Orders of common functions). (en) Nella teoria delle basi di dati, l'algoritmo sort merge join (o anche solo merge join) si distingue dagli altri algoritmi di join perché prima di effettuare i confronti ordina (sort) le relazioni secondo l'attributo di join. Una volta ordinate le unisce (merge). Appena viene trovata una corrispondenza tra tuple provenienti da relazioni diverse, essa viene messa nel result set di output. (it) Алгоритм соединения слиянием сортированных списков (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.ПерейтиКСледующейЗаписи; } } (ru) |
| dbo:wikiPageExternalLink | http://www.necessaryandsufficient.net/2010/02/join-algorithms-illustrated/ |
| dbo:wikiPageID | 1227155 (xsd:integer) |
| dbo:wikiPageLength | 6101 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119761034 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Articles_with_example_pseudocode dbr:Tuple dbr:Hash_join dbr:Join_(SQL) dbr:Database_management_system dbc:Articles_with_example_C_Sharp_code dbr:Relational_database dbr:Big_O_notation dbc:Join_algorithms dbr:Nested_loop_join dbr:Linearithmic_time dbr:Join_algorithm dbr:External_sort |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Articles_with_example_pseudocode dbc:Articles_with_example_C_Sharp_code dbc:Join_algorithms |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatJoinAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | Nella teoria delle basi di dati, l'algoritmo sort merge join (o anche solo merge join) si distingue dagli altri algoritmi di join perché prima di effettuare i confronti ordina (sort) le relazioni secondo l'attributo di join. Una volta ordinate le unisce (merge). Appena viene trovata una corrispondenza tra tuple provenienti da relazioni diverse, essa viene messa nel result set di output. (it) The sort-merge join (also known as merge join) is a join algorithm and is used in the implementation of a relational database management system. The basic problem of a join algorithm is to find, for each distinct value of the join attribute, the set of tuples in each relation which display that value. The key idea of the sort-merge algorithm is to first sort the relations by the join attribute, so that interleaved linear scans will encounter these sets at the same time. (en) Алгоритм соединения слиянием сортированных списков (merge join, sort merge join, sort-merge join) — разновидность алгоритма соединения. Алгоритм получает на вход две таблицы и условие соединения. Результатом его работы является таблица с результатами соединения. Входные таблицы должны быть отсортированы по столбцам, участвующим в условии соединения. Соединение осуществляется за одно сканирование (проход по) каждой из входных таблиц. То есть одна и та же строка считывается только один раз, что даёт преимущество перед соединением вложенными циклами. Простой пример на псевдокоде: (ru) |
| rdfs:label | Sort merge join (it) Sort-merge join (en) Алгоритм соединения слиянием сортированных списков (ru) |
| owl:sameAs | freebase:Sort-merge join yago-res:Sort-merge join wikidata:Sort-merge join dbpedia-it:Sort-merge join dbpedia-ru:Sort-merge join https://global.dbpedia.org/id/3m2J8 |
| prov:wasDerivedFrom | wikipedia-en:Sort-merge_join?oldid=1119761034&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Sort-merge_join |
| is dbo:wikiPageRedirects of | dbr:Merge_join dbr:Merge_scan_join dbr:Sort-Merge_Join |
| is dbo:wikiPageWikiLink of | dbr:Data_stream_management_system dbr:Hash_join dbr:Join_(SQL) dbr:Merge_join dbr:Merge_scan_join dbr:Nested_loop_join dbr:Sort-Merge_Join |
| is foaf:primaryTopic of | wikipedia-en:Sort-merge_join |