Sorter-slå sammen - Sort-merge join
Den sort-flettingen delta (også kjent som fletting delta) er en delta-algoritme , og i tilknytning til iverksettelse av et relasjonsdatabasesystem .
Det grunnleggende problemet med en sammenkoblingsalgoritme er å finne settet med tupler i hver relasjon som viser den verdien for hver distinkt verdi av sammenføyningsattributtet . Hovedideen til sorteringssammenslåingsalgoritmen er å først sortere relasjonene etter attributtet join, slik at sammenflettede lineære skanninger vil møte disse settene samtidig.
I praksis er den dyreste delen av å utføre en sorteringsfusjonssamling å sørge for at begge inngangene til algoritmen presenteres i sortert rekkefølge. Dette kan oppnås via en eksplisitt sorteringsoperasjon (ofte en ekstern sortering ), eller ved å dra nytte av en eksisterende bestilling i en eller begge sammenkoblingsforholdene. Den sistnevnte tilstanden, kalt interessant rekkefølge, kan oppstå fordi en inngang til sammenføyningen kan produseres av en indeksskanning av en trebasert indeks, en annen sammenslåingsforbindelse eller en annen planoperatør som tilfeldigvis produserer utdata sortert på en passende nøkkel. Interessante bestillinger trenger ikke å være serendipitous: optimalisereren kan oppsøke denne muligheten og velge en plan som er suboptimal for en bestemt foregående operasjon hvis den gir en interessant ordre som en eller flere nedstrøms noder kan utnytte.
La oss si at vi har to forhold og og . passer inn i sideminnet og passer inn i sideminnet. Så i verste fall vil sort-merge join kjøre i I / Os. I tilfelle at og ikke er bestilt, vil tidskostnadene inneholde ytterligere vilkår for sorteringstid:, som er lik (som linearitmiske termer oppveier de lineære vilkårene, se Big O-notasjon - Ordener på vanlige funksjoner ).
Pseudokode
For enkelhets skyld er algoritmen beskrevet i tilfelle en indre sammenføyning av to relasjoner på et enkelt attributt. Generalisering til andre sammenføyningstyper, flere relasjoner og flere nøkler er grei.
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]
Enkel C # implementering
Merk at denne implementeringen forutsetter at tilknytningsattributtene er unike, dvs. at det ikke er behov for å sende ut flere tupler for en gitt verdi av nøkkelen.
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>();
}
}
