Block nested loop join: differenze tra le versioni

Versione delle 12:31, 4 gen 2019

Versione attuale delle 00:27, 15 ott 2024

(Una versione intermedia di un altro utente non mostrate)

Riga 4:

== Differenze rispetto a nested-loop join ==

Supponendo di avere due relazioni R e S, R esterna e S interna, con |R|<|S| dove |R| è il numero di tuple coinvolte in R e |S| quello di tuple coinvolte in S, nell'algoritmo NLJ S viene scansionata ogni volta per ogni [[tupla]] di R. Questa operazione è molto dispendiosa.

Con l'algoritmo BNL il miglioramento viene ottenuto scansionando S una volta sola per ogni gruppo di tuple di R. Una versione di questo algoritmo carica nella memoria, in una [[hash table]] le tuple di R, poi passa a S ed esamina l'hash table per trovare le tuple di S che corrispondono a qualsiasi tupla di R. Questo riduce il numero di scansioni di S necessarie.

Nel caso di utilizzo di hash table, questo algoritmo può esser visto come variante dell'algoritmo di [[hash join]].

== Bibliografia ==

* Paolo Ciaccia, Dario Mario, Lezioni di basi di dati, 2013, Editrice Esculapio, ISBN 978-8874887187

* [httphttps://dev.mysql.com/doc/refman/5.6/en/nested-loop-joins.html Block nested-Loop Joins] in the MySQL 5.6 Reference Manual.

{{Portale|informatica|ingegneria}}