Sort merge join
Da Wikipedia, l'enciclopedia libera
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
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
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
- Sort Merge Joins in the MySQL 5.6 Reference Manual.
- https://www.dcs.ed.ac.uk/
Wikiwand - on
Seamless Wikipedia browsing. On steroids.