Block nested loop join
Il block nested loop join (BNL) è un algoritmo, variante di quello di simple nested loop join, che 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 modifica
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 modifica
- Paolo Ciaccia, Dario Mario, Lezioni di basi di dati, 2013, Editrice Esculapio, ISBN 978-8874887187
- Block nested-Loop Joins in the MySQL 5.6 Reference Manual.
