Hash join
Algoritmul de asociere hash este un anumit algoritm de asociere care folosește un tabel hash pentru a stoca date.
Alăturare clasică hash
Primul pas în algoritmul clasic de asociere hash este pregătirea pentru cea mai mică relație a unui tabel hash care conține atributul de asociere și rândul său. Deoarece tabelul hash este accesat prin aplicarea unei funcții hash pe atributul join, va fi mult mai rapid să găsiți rândul care se potrivește în acest fel. Odată ce acest tabel este construit, cealaltă relație este scanată pentru a se potrivi rândurilor sale prin tabelul hash.
Algoritmul necesită să existe suficient spațiu în memorie pentru a putea fi salvată cea mai mică relație.
Dați două relații R și S cu | R | <| S | unde | R | este numărul de tupluri implicate în R și | S | cel al tuplurilor implicate în S, pașii algoritmului sunt după cum urmează:
- Pentru fiecare tupl r de R.
- Adăugați r la masă
- Dacă dimensiunea tabelului este egală cu capacitatea maximă de memorie:
- scanează S și adaugă tupluri potrivite la ieșire
- Resetați masa
- Efectuați o scanare finală a lui S adăugând tuplurile rezultate la ieșire
Grace hash se alătură
Această versiune a algoritmului de asociere hash evită nevoia de a scana din nou întreaga relație S prin partiționarea R și S printr-o funcție hash și stocarea acestor partiții pe disc. Algoritmul încarcă apoi perechi de partiții în memorie, construiește un tabel hash pentru cea mai mică dintre relațiile partiționate și examinează cealaltă relație pentru a căuta potriviri cu tabelul hash curent.
Dacă nu există suficient spațiu pentru una sau mai multe partiții, algoritmul este reaplicat recursiv: se aplică o funcție de hash suplimentară pentru a împărți partițiile în altele mai mici, care vor fi apoi procesate cu aceeași procedură. Deoarece recursivitatea este foarte costisitoare, algoritmul de la început încearcă să reducă șansele ca aceasta să apară formând cât mai multe partiții posibil în timpul fazei inițiale.
Hibrid hash join
Algoritmul de asociere hash hibrid diferă de cel al asocierii hash Grace prin faptul că folosește memoria disponibilă diferit. În timpul fazei de partiționare, acest algoritm folosește memoria disponibilă pentru a deține atât o partiție întreagă, numită partiție 0 , cât și bufferul de ieșire pentru fiecare dintre k partiții.
Prin urmare, există două cereri diferite de memorie (una pentru tabelul hash al partiției 0 și cealaltă pentru bufferele de ieșire ale celorlalte partiții), deci este necesar să alegeți o tabelă hash care nu este prea mare pentru a evita recursivitatea algoritmului cauzată de dimensiuni mari de partiții diferite de zero, ceea ce ar risca deci să nu aibă suficient spațiu în memorie. Deoarece partiția 0 nu este niciodată citită sau scrisă de pe disc, algoritmul de asociere hash hibrid efectuează mai puține operațiuni I / O decât asocierea hash Grace.
Bibliografie
- Hash se alătură în Manualul de referință MySQL 5.6.
