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

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

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

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

Сложность

Позволять $R$ и $S$ быть отношениями, где $|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}))$ (поскольку линейные члены перевешивают линейные, см. Обозначение Big O – Порядки общих функций ).

Псевдокод

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

function Sort-Merge Join(left: Relation, right: Relation, comparator: Comparator) {
    result = new Relation()
    
    // Ensure that at least one element is present
    if (!left.hasNext() || !right.hasNext()) {
        return result
    }
    
    // Sort left and right relation with comparator
    left.sort(comparator)
    right.sort(comparator)
    
    // Start Merge Join algorithm
    leftRow = left.next()
    rightRow = right.next()
    
    outerForeverLoop:
    while (true) {
        while (comparator.compare(leftRow, rightRow) != 0) {
            if (comparator.compare(leftRow, rightRow) < 0) {
                // Left row is less than right row
                if (left.hasNext()) {
                    // Advance to next left row
                    leftRow = left.next()
                } else {
                    break outerForeverLoop
                }
            } else {
                // Left row is greater than right row
                if (right.hasNext()) {
                    // Advance to next right row
                    rightRow  = right.next()
                } else {
                    break outerForeverLoop
                }
            }
        }
        
        // Mark position of left row and keep copy of current left row
        left.mark()
        markedLeftRow = leftRow
        
        while (true) {
            while (comparator.compare(leftRow, rightRow) == 0) {
                // Left row and right row are equal
                // Add rows to result
                result = add(leftRow, rightRow)
                
                // Advance to next left row
                leftRow = left.next()
                
                // Check if left row exists
                if (!leftRow) {
                    // Continue with inner forever loop
                    break
                }
            }
            
            if (right.hasNext()) {
                // Advance to next right row
                rightRow  = right.next()
            } else {
                break outerForeverLoop
            }
            
            if (comparator.compare(markedLeftRow, rightRow) == 0) {
                // Restore left to stored mark
                left.restoreMark()
                leftRow = markedLeftRow
            } else {
                // Check if left row exists
                if (!leftRow) {
                    break outerForeverLoop
                } else {
                    // Continue with outer forever loop
                    break
                }
            }
        }
    }
    
    return result
}

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

function compare(leftRow: RelationRow, rightRow: RelationRow): number {
	// Return -1 if leftRow is less than rightRow
	// Return 0 if leftRow is equal to rightRow
	// Return 1 if leftRow is greater than rightRow
}

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

interface Relation {
    // Returns true if relation has a next row (otherwise false)
    hasNext(): boolean
    
    // Returns the next row of the relation (if any)
    next(): RelationRow
    
    // Sorts the relation with the given comparator
    sort(comparator: Comparator): void
    
    // Marks the current row index
    mark(): void
    
    // Restores the current row index to the marked row index
    restoreMark(): void
}

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

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

public class MergeJoin
{
    // Assume that left and right are already sorted
    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 Key => list[position];

    public bool Advance()
    {
        if (position == list.Count - 1 || position == ENDPOS)
        {
            position = ENDPOS;
            return false;
        }
        position++;
        return true;
    }

    public void Add(int key)
    {
        list.Add(key);
    }

    public bool IsPastEnd()
    {
        return position == ENDPOS;
    }

    public void Print()
    {
        foreach (int key in list)
            Console.WriteLine(key);
    }

    public Relation(List<int> list)
    {
        this.list = list;
    }

    public Relation()
    {
        this.list = new List<int>();
    }
}

См. также

• Хэш-соединение
• Соединение вложенного цикла

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

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