Hash join
L'algoritmo di hash join è un particolare algoritmo di join che usa una Hash table per memorizzare i dati.
Classic hash join[modifica | modifica wikitesto]
Il primo passo nell'algoritmo di hash join classico è la preparazione per la relazione più piccola di una hash table contenente l'attributo di join e la sua riga. Dato che alla hash table si accede applicando una funzione hash sull'attributo di join, sarà molto più rapido trovare la riga corrispondente in questo modo. Una volta costruita questa tabella, si scandisce l'altra relazione per trovare corrispondenze nelle sue righe attraverso la hash table.
L'algoritmo richiede che ci sia spazio sufficiente in memoria affinché la relazione più piccola possa essere salvata.
Date due relazioni R e S con |R|<|S| dove |R| è il numero di tuple coinvolte in R e |S| quello di tuple coinvolte in S, i passi dell'algoritmo sono i seguenti:
- Per ogni tupla r di R
- Aggiungere r nella tabella
- Se la dimensione della tabella uguaglia la capacità di memoria massima:
- scandire S e aggiungere all'output le tuple che hanno corrispondenza
- Resettare la tabella
- Eseguire una scansione finale di S aggiungendo le risultanti tuple all'output
Grace hash join[modifica | modifica wikitesto]
Questa versione dell'algoritmo di hash join evita di dover scandire nuovamente l'intera relazione S, partizionando R e S tramite una funzione hash e memorizzando queste partizioni nel disco. L'algoritmo carica poi coppie di partizioni in memoria, costruisce una hash table per la più piccola delle relazioni partizionate ed esamina l'altra relazione per ricercare corrispondenze tramite la hash table corrente.
Nel caso in cui non ci sia abbastanza spazio per una o più partizioni l'algoritmo viene riapplicato in modo ricorsivo: viene applicata un ulteriore funzione hash per suddividere le partizioni in altre più piccole, che verranno poi elaborate con la stessa procedura. Dato che la ricorsione risulta molto costosa, l'algoritmo fin dal principio cerca di ridurre le probabilità che si verifichi formando il maggior numero possibile di partizioni durante la fase iniziale.
Hybrid hash join[modifica | modifica wikitesto]
L'algoritmo hybrid hash join si differenzia da quello di Grace hash join in quanto sfrutta in modo diverso la memoria disponibile. Durante la fase di ripartizione questo algoritmo utilizza la memoria disponibile per contenere sia un'intera partizione, denominata partizione 0, sia il buffer di uscita per ciascuna delle k partizioni.
Ci sono dunque due richieste diverse per la memoria (una per la hash table della partizione 0 e l'altra per i buffer di output delle altre partizioni) quindi è necessario scegliere una hash table non troppo grande per evitare la ricorsione dell'algoritmo causata dalla dimensione troppo grande delle partizioni non-zero, che rischierebbero quindi di non avere abbastanza spazio in memoria. Dato che la partizione 0 non viene mai né letta né scritta dal disco, l'algoritmo di hybrid hash join esegue meno operazioni di I/O di quello di Grace hash join.
Bibliografia[modifica | modifica wikitesto]
- Hash Joins in the MySQL 5.6 Reference Manual.
