Classificar-mesclar junção - Sort-merge join
A junção sort-merge (também conhecida como junção de mesclagem) é um algoritmo de junção e é usada na implementação de um sistema de gerenciamento de banco de dados relacional .
O problema básico de um algoritmo de junção é encontrar, para cada valor distinto do atributo de junção, o conjunto de tuplas em cada relação que exibe esse valor. A ideia principal do algoritmo de ordenação e mesclagem é primeiro ordenar as relações pelo atributo de junção, de forma que varreduras lineares intercaladas encontrem esses conjuntos ao mesmo tempo.
Na prática, a parte mais cara de realizar uma junção de classificação e mesclagem é organizar para que ambas as entradas para o algoritmo sejam apresentadas em ordem classificada. Isso pode ser obtido por meio de uma operação de classificação explícita (geralmente uma classificação externa ) ou aproveitando uma ordenação pré-existente em uma ou ambas as relações de junção. A última condição, chamada de ordem interessante, pode ocorrer porque uma entrada para a junção pode ser produzida por uma varredura de índice de um índice baseado em árvore, outra junção de mesclagem ou algum outro operador de plano que produza a saída classificada em uma chave apropriada. Ordens interessantes não precisam ser fortuitas: o otimizador pode buscar essa possibilidade e escolher um plano que não seja o ideal para uma operação anterior específica, se produzir uma ordem interessante que um ou mais nós downstream possam explorar.
Digamos que temos duas relações e e . cabe na memória de páginas e cabe na memória de páginas. Portanto, no pior caso , a junção sort-merge será executada em I / Os. No caso em que e não são ordenados a pior custo de tempo caso irá conter termos adicionais de triagem tempo: que é igual (como linearithmic termos superam os termos lineares, consulte Big O notação - Ordens de funções comuns ).
Pseudo-código
Para simplificar, o algoritmo é descrito no caso de uma junção interna de duas relações em um único atributo. A generalização para outros tipos de junção, mais relações e mais chaves é direta.
function sortMerge(relation left, relation right, attribute a)
var relation output
var list left_sorted := sort(left, a) // Relation left sorted on attribute a
var list right_sorted := sort(right, a)
var attribute left_key, right_key
var set left_subset, right_subset // These sets discarded except where join predicate is satisfied
advance(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 // Join predicate satisfied
add cartesian product of left_subset and right_subset to output
advance(left_subset, left_sorted, left_key, a)
advance(right_subset, right_sorted, right_key, a)
else if left_key < right_key
advance(left_subset, left_sorted, left_key, a)
else // left_key > right_key
advance(right_subset, right_sorted, right_key, a)
return output
// Remove tuples from sorted to subset until the sorted[1].a value changes
function advance(subset out, sorted inout, key out, a in)
key := sorted[1].a
subset := emptySet
while not empty(sorted) and sorted[1].a = key
insert sorted[1] into subset
remove sorted[1]
Implementação simples de C #
Observe que esta implementação assume que os atributos de junção são únicos, ou seja, não há necessidade de gerar múltiplas tuplas para um determinado valor da chave.
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
{
get { return position; }
}
public int Key
{
get { return 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>();
}
}
