Block nested loop join: differenze tra le versioni

Versione delle 03:58, 21 mar 2015

Versione attuale delle 00:27, 15 ott 2024

(3 versioni intermedie di 3 utenti non mostrate)

Riga 1:

{{W|informatica|marzo 2015}}

L'algoritmo diIl '''block nested loop join''' (BNL) è unaun [[algoritmo]], variante di quello di ''[[simple nested loop join]]'', che [[Buffer|bufferizza]] le righe lette nel ciclo esterno per ridurre il numero di volte che la tabella nel ciclo interno deve essere letta. Per esempio, se in un buffer vengono memorizzate 10 righe e questo viene passato al ciclo interno, ogni riga del ciclo interno può essere confrontata con tutte le 10 nel buffer, riducendo di un ordine di grandezza il numero di accessi alla tabella interna.

=== 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}}