Сортировка-слияние - Sort-merge join

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

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

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

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

Псевдокод

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

функция sortMerge (связь оставили, связь верно, атрибут а) отношение var выход список переменных left_sorted: = sort (слева, a) // Отношение отсортировано слева по атрибуту a    список переменных right_sorted: = sort (справа, a) атрибут var left_key, right_key набор переменных left_subset, right_subset // Эти наборы отбрасываются, кроме случаев, когда выполняется предикат соединения    advance (left_subset, left_sorted, left_key, a) advance (right_subset, right_sorted, right_key, a) в то время как не пустой (left_subset) и нет пустой (right_subset) если left_key = right_key // Предикат соединения выполнен            добавить декартово произведение left_subset и right_subset для вывода advance (left_subset, left_sorted, left_key, a) advance (right_subset, right_sorted, right_key, a) иначе если left_key еще // left_key> right_key            advance (right_subset, right_sorted, right_key, a) возвращаться выход

// Удаляем кортежи из sorted to subset, пока значение sorted [1] .a не изменитсяфункция продвижение (подмножество из, отсортировано inout, ключ из, а в) ключ: = отсортировано [1]. подмножество: = пустой набор    в то время как не пустой (отсортированный) и sorted [1] .a = ключ вставить отсортировано [1] в подмножество удалить отсортировано [1]

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

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

общественный учебный класс MergeJoin{    // Предположим, что левый и правый уже отсортированы    общественный статический Связь Объединить(Связь оставили, Связь верно)    {        Связь выход = новый Связь();        пока (!оставили.IsPastEnd() && !верно.IsPastEnd())        {            если (оставили.Ключ == верно.Ключ)            {                выход.Добавлять(оставили.Ключ);                оставили.Продвигать();                верно.Продвигать();            }            еще если (оставили.Ключ < верно.Ключ)                оставили.Продвигать();            еще // если (left.Key> right.Key)                верно.Продвигать();        }        возвращаться выход;    }} общественный учебный класс Связь{    частный Список<int> список;    общественный const int ENDPOS = -1;    общественный int позиция = 0;    общественный int Позиция    {        получать { возвращаться позиция; }    }    общественный int Ключ    {        получать { возвращаться список[позиция]; }    }    общественный bool Продвигать()    {        если (позиция == список.Считать - 1 || позиция == ENDPOS)        {            позиция = ENDPOS;            возвращаться ложный;        }        позиция++;        возвращаться истинный;    }    общественный пустота Добавлять(int ключ)    {        список.Добавлять(ключ);    }    общественный bool IsPastEnd()    {        возвращаться позиция == ENDPOS;    }    общественный пустота Распечатать()    {        для каждого (int ключ в список)            Консоль.WriteLine(ключ);    }    общественный Связь(Список<int> список)    {        это.список = список;    }    общественный Связь()    {        это.список = новый Список<int>();    }}

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

внешняя ссылка

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