Sort merge join

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

Nella teoria delle basi di dati, l'algoritmo sort merge join (o anche solo merge join) si distingue dagli altri algoritmi di join perché prima di effettuare i confronti ordina (sort) le relazioni secondo l'attributo di join. Una volta ordinate le unisce (merge). Appena viene trovata una corrispondenza tra tuple provenienti da relazioni diverse, essa viene messa nel result set di output.

Pseudo-codice dell'algoritmo[modifica | modifica wikitesto]

Una possibile implementazione dell'algoritmo è la seguente:

// input: F(A,...), G(B,...)
// output: F ⋈ G on F.A = G.B
// fase di ordinamento
ordina F su F.A
ordina G su G.B  
// fase di merge
f = prima tupla di F
g = prima tupla di G
// RF indica la fine di una relazione
while f != RF && g != RF do 

    if f.A > g.B
        g = tupla successiva a g in G

    else if f.A < g.B
        f = tupla successiva a f in F

    else
        inserisci nella relazione in output f oppure g
 
        f' = tupla successiva a f in F
        while f' != RF && f'.A = g.B do
            inserisci nella relazione in output f' oppure g
            f' = tupla successiva a f' in F
        od 
      
        g' = tupla successiva a g in G
        while g' != RF && g'.B = f.A do
            inserisci nella relazione in output f oppure g'
            g' = tupla successiva a g' in G
        od

        f = tupla successiva a f in F
        g = tupla successiva a g in G

    fi

od

Utilizzi[modifica | modifica wikitesto]

Dato che l'ordinamento iniziale può essere un'operazione molto costosa, specialmente se il volume di dati coinvolti è alto, è preferibile utilizzare altri algoritmi quando ci si trova in questa condizione. Al contrario, se i dati sono già ordinati o è necessario ordinarli comunque (ad esempio è presenta la clausola order by) o la clausola di join si basa su un'ineguaglianza, è preferibile usare questo tipo di algoritmo.

Bibliografia[modifica | modifica wikitesto]