Введение
Алгоритм, используемый в реляционных базах данных. Сортировка слиянием (также известная как merge join) — это алгоритм соединения, используемый в реализации реляционной системы управления базами данных. Основная задача алгоритма соединения заключается в том, чтобы для каждого уникального значения атрибута соединения найти множество кортежей в каждом отношении, содержащих это значение. Ключевая идея алгоритма сортировки слиянием состоит в предварительной сортировке отношений по атрибуту соединения, чтобы при последовательном просмотре они встречались одновременно. На практике, наиболее затратной частью выполнения сортировки слиянием является обеспечение подачи обоих входных наборов данных в отсортированном порядке. Этого можно достичь с помощью явной операции сортировки (часто внешней сортировки) или за счет использования существующего порядка в одном или обоих соединяемых отношениях. Последнее условие, называемое "удобным порядком", может возникнуть, если входные данные для соединения получены в результате сканирования индекса на основе дерева, другого соединения или другого оператора плана, который случайно выдает результат, отсортированный по соответствующему ключу. "Удобный порядок" не обязательно должен быть случайным: оптимизатор может специально искать такую возможность и выбирать план, который неоптимален для конкретной предшествующей операции, если он обеспечивает "удобный порядок", который могут использовать один или несколько последующих узлов.
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.
Сложность
Пусть R и S – отношения, где R помещается в K страниц памяти, а S – в L страниц памяти. В худшем случае, алгоритм сортировочного слияния потребует I/O операций. Если R и S не упорядочены, то в худшем случае временная сложность будет включать дополнительные компоненты времени сортировки: K*log(K) + L*log(L), что эквивалентно O(K*log(K) + L*log(L)) (поскольку линейно-логарифмические члены преобладают над линейными членами, см. нотацию «Большое О» – порядок распространенных функций).