Block nested loop join: differenze tra le versioni

Versione delle 15:26, 19 mar 2015

Versione attuale delle 00:27, 15 ott 2024

(5 versioni intermedie di 5 utenti non mostrate)

Riga 1:

{{W|informatica|marzo 2015}}

== Block nested loop join ==

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’algoritmonell'algoritmo NLJ S viene scansionata ogni volta per ogni [[tupla]] di R. Questa operazione è molto dispendiosa.

Con l’algoritmol'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’hashl'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’algoritmodell'algoritmo di [[hash join]].

== Bibliografia ==

* Paolo Ciaccia, Dario Mario, Lezioni di basi di dati, 2013, Editrice Esculapio, ISBN-13: 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.

== Fonti ==

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

{{Reflist}}

* [http://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}}

[[Categoria:Terminologia informatica]]

[[Categoria:Teoria delle basi di dati]]