Соединение сортировка-слияние (также известное как соединение слиянием) представляет собой алгоритм объединения и используется при реализации системы управления реляционными базами данных .
Основная проблема алгоритма соединения состоит в том, чтобы найти для каждого отдельного значения атрибута соединения набор кортежей в каждом отношении, которые отображают это значение. Ключевая идея алгоритма сортировки-слияния состоит в том, чтобы сначала отсортировать отношения по атрибуту соединения, чтобы при чередующемся линейном сканировании эти наборы одновременно встречались.
На практике самая дорогостоящая часть выполнения соединения сортировка-слияние - это организация представления обоих входных данных алгоритма в отсортированном порядке. Это может быть достигнуто с помощью явной операции сортировки (часто внешней сортировки ) или использования преимуществ уже существующего порядка в одном или обоих отношениях соединения. Последнее условие, называемое интересным порядком, может возникнуть из-за того, что вход в соединение может быть произведен сканированием индекса древовидного индекса, другого соединения слиянием или какого-либо другого оператора плана, который производит вывод, отсортированный по соответствующему ключу. Интересные заказы не обязательно должны быть случайными: оптимизатор может найти эту возможность и выбрать план, который является неоптимальным для конкретной предыдущей операции, если он дает интересный порядок, который может использовать один или несколько нижестоящих узлов.
Допустим, у нас есть два отношения а также а также . вписывается в память страниц и вписывается в страницы памяти. Итак, в худшем случае соединение сортировки и слияния будет выполнятьсяВвод / вывод. В случае, если а также не упорядочены; в худшем случае временные затраты будут содержать дополнительные сроки сортировки: , что равно (как linearithmic термины , перевешивают линейные члены, см Big O обозначение - Заказы общих функций ).
Псевдокод
Для простоты алгоритм описан в случае внутреннего соединения двух отношений по одному атрибуту. Обобщение для других типов соединений, большего количества отношений и большего количества ключей просто.
function sortMerge ( отношение слева, отношение справа, атрибут a) var отношение output var list left_sorted: = sort (left, a) // Отношение, отсортированное слева по атрибуту a var list right_sorted: = sort (right, a) var attribute left_key, right_key var set left_subset, right_subset // Эти наборы отброшены, за исключением случаев, когда выполняется предикат соединения продвижение (left_subset, left_sorted, left_key, a) advance (right_subset, right_sorted, right_key, a) while not empty (left_subset) and not empty (right_subset) if left_key = right_key // Предикат соединения удовлетворен добавить декартово произведение left_subset и right_subset для вывода продвижение (left_subset, left_sorted, left_key, a) advance (right_subset, right_sorted, right_key, a) иначе, если left_keyпродвижение (left_subset, left_sorted, left_key, a) иначе // левая_ключ> правая_ключ advance (right_subset, right_sorted, right_key, a) возвратный вывод
// Удаляем кортежи из сортированного в подмножество до тех пор, пока значение sorted [1] .a не изменится function advance (subset out , sorted inout , key out , a in ) ключ: = отсортировано [1] .a подмножество: = emptySet, пока не пусто (отсортировано) и отсортировано [1] .a = ключ вставить отсортированный [1] в подмножество удалить отсортированный [1]
Простая реализация на C #
Обратите внимание, что эта реализация предполагает, что атрибуты соединения уникальны, т. Е. Нет необходимости выводить несколько кортежей для данного значения ключа.
public class MergeJoin { // Предположим, что левая и правая стороны уже отсортированы public static Relation Merge ( Relation left , Relation right ) { Relation output = new Relation (); while (! left . IsPastEnd () && ! right . IsPastEnd ()) { if ( left . Key == right . Key ) { output . Добавить ( влево . Key ); слева . Advance (); правильно . Advance (); } else if ( left . Key < right . Key ) left . Advance (); else // если (left.Key> right.Key) right . Advance (); } вернуть вывод ; } } общедоступный класс Relation { частный список < int > список ; общественный Const ИНТ ENDPOS = - 1 ; public int position = 0 ; public int Position { get { return position ; } } общедоступный int Key { получить { список возврата [ позиция ]; } } общественного BOOL Advance () { если ( позиция == список . Count - 1 || позиция == ENDPOS ) { позиция = ENDPOS ; вернуть ложь ; } позиция ++; вернуть истину ; } public void Add ( int key ) { list . Добавить ( ключ ); } public bool IsPastEnd () { позиция возврата == ENDPOS ; } public void Print () { foreach ( ключ int в списке ) Консоль . WriteLine ( ключ ); } общедоступные отношения ( список < int > list ) { this . список = список ; } public Relation () { this . список = новый Список < int > (); } }