Сортировка-слияние соединения

Соединение сортировкой -слиянием (также известное как соединение слиянием) представляет собой алгоритм соединения и используется при реализации системы управления реляционными базами данных .

Основная проблема алгоритма соединения заключается в том, чтобы найти для каждого отдельного значения атрибута соединения набор кортежей в каждом отношении, которые отображают это значение. Ключевая идея алгоритма сортировки-слияния заключается в том, чтобы сначала отсортировать отношения по атрибуту соединения, так что чередующиеся линейные сканирования будут сталкиваться с этими наборами одновременно.

На практике наиболее затратной частью выполнения сортировки-слияния является организация обоих входов алгоритма, которые будут представлены в отсортированном порядке. Это может быть достигнуто с помощью явной операции сортировки (часто внешней сортировки ) или путем использования уже существующего порядка в одном или обоих отношениях соединения. ^[1] Последнее условие, называемое интересным порядком, может возникнуть, поскольку вход для соединения может быть получен путем сканирования индекса древовидного индекса, другого слияния или некоторого другого оператора плана, который случайно производит вывод, отсортированный по соответствующему ключу. Интересные порядки не обязательно должны быть случайными: оптимизатор может искать эту возможность и выбирать план, который является субоптимальным для определенной предыдущей операции, если он дает интересный порядок, который может использовать один или несколько нижестоящих узлов.

Сложность

Пусть и будут отношениями, где . помещается в памяти страниц и помещается в памяти страниц. В худшем случае соединение сортировки-слияния будет выполняться в операциях ввода-вывода. В случае, если и не упорядочены, временные затраты в худшем случае будут содержать дополнительные члены времени сортировки: , что равно (поскольку линейные члены перевешивают линейные члены, см. нотацию Big O – Порядки общих функций ). $R$ $S$ $|Р|<|С|$ $R$ $P_{r}$ $S$ $P_{s}$ $O(P_{r}+P_{s})$ $R$ $S$ $O(P_{r}+P_{s}+P_{r}\log(P_{r})+P_{s}\log(P_{s}))$ $O(P_{r}\log(P_{r})+P_{s}\log(P_{s}))$

Псевдокод

Для простоты алгоритм описан для случая внутреннего соединения двух отношений left и right . Обобщение на другие типы соединений простое. Выходные данные алгоритма будут содержать только строки, содержащиеся в левом и правом отношении, а дубликаты образуют декартово произведение .

function Sort - Merge Join ( left : Relation , right : Relation , comparator : Comparator ) { result = new Relation () // Гарантируем, что присутствует хотя бы один элемент if ( ! left.hasNext () || ! right.hasNext ( )) { return result } // Сортируем левое и правое отношение с помощью компаратора left.sort ( comparator ) right.sort ( comparator ) // Запускаем алгоритм Merge Join leftRow = left.next () rightRow = right.next ( ) outerForeverLoop : while ( true ) { while ( comparator.compar ( leftRow , rightRow ) ! = 0 ) { if ( comparator.compar ( leftRow , rightRow ) < 0 ) { // Левая строка меньше правой строки if ( left.hasNext ( )) { // Переход к следующей левой строке leftRow = left.next ( ) ) next () } else { break outerForeverLoop } } else { // Левая строка больше правой if ( right . hasNext ()) { // Переход к следующей правой строке rightRow = right . next () } else { break outerForeverLoop } } } // Отметить позицию левой строки и сохранить копию текущей левой строки left . mark () markedLeftRow = leftRow while ( true ) { while (                                                                                                comparator.comparate ( leftRow , rightRow ) == 0 ) { // Левая и правая строки равны // Добавить строки к результату result = add ( leftRow , rightRow ) // Перейти к следующей левой строке leftRow = left.next ( ) // Проверить, существует ли левая строка if ( ! leftRow ) { // Продолжить с внутренним вечным циклом break } } if ( right.hasNext ()) { // Перейти к следующей правой строке rightRow = right.next () } else { break outerForeverLoop } if ( comparator.comparate ( markedLeftRow , rightRow ) == 0 ) { // Восстановить слева сохранённую метку left.restoreMark () leftRow = markedLeftRow } else { // Проверить , существует ли левая строка if ( ! leftRow ) { break outerForeverLoop } else { // Продолжить с внешним вечным циклом break } } } } return result }

Поскольку логика сравнения не является центральным аспектом этого алгоритма, она скрыта за общим компаратором и может также состоять из нескольких критериев сравнения (например, нескольких столбцов). Функция сравнения должна возвращать, если строка меньше (-1) , равна (0) или больше (1) , чем другая строка:

функция сравнения ( leftRow : RelationRow , rightRow : RelationRow ) : number { // Возвращает -1, если leftRow меньше rightRow // Возвращает 0, если leftRow равен rightRow // Возвращает 1, если leftRow больше rightRow }

Обратите внимание, что отношение в терминах этого псевдокода поддерживает некоторые базовые операции:

interface Relation { // Возвращает true, если у relation есть следующая строка (иначе false) hasNext () : boolean // Возвращает следующую строку relation (если есть) next () : RelationRow // Сортирует relation с заданным компаратором sort ( comparator : Comparator ) : void // Отмечает текущий индекс строки mark () : void // Восстанавливает текущий индекс строки до отмеченного индекса строки restoreMark () : void }

Простая реализация на C#

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

public class MergeJoin { // Предположим , что left и right уже отсортированы public static Relation Merge ( Relation left , Relation right ) { Relation output = new Relation ( ); while ( ! left.IsPastEnd && ! right.IsPastEnd ) { if ( left.Key == right.Key ) { output.Add ( left.Key ) ; left.Advance ( ) ; right.Advance ( ) ; } else if ( left.Key < right.Key ) left.Advance ( ) ; else // if ( left.Key > right.Key ) right.Advance ( ) ; } return output ; } } public class Relation { private List < int > list ; public const int ENDPOS = - 1 ;                                                        public int position = 0 ; public int Position => position ;          public int Ключ => список [ позиция ];     public bool IsPastEnd => position == ENDPOS ;       public bool Advance ( ) { if ( position == list.Count - 1 || position == ENDPOS ) { position = ENDPOS ; return false ; } position ++ ; return true ; }                         public void Добавить ( int key ) { список . Добавить ( key ); }       public void Print ( ) { foreach ( int key in list ) Console.WriteLine ( key ) ; }           публичная связь ( список <int> список ) { this.list = list ; }        public Relation ( ) { this.list = new List <int> ( ) ; } }

Смотрите также

Ссылки

^ "Sort-Merge Joins". www.dcs.ed.ac.uk . Получено 2022-11-02 .

Внешние ссылки

Реализации различных алгоритмов соединения на языке C#