Sort merge join

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.

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

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 è presente la clausola order by) o la clausola di join si basa su un'ineguaglianza, è preferibile usare questo tipo di algoritmo.

• Sort Merge Joins in the MySQL 5.6 Reference Manual.
• https://www.dcs.ed.ac.uk/

Portale Informatica

Portale Ingegneria