Algoritmul Hash Join

Algoritmul hash join este un  fel de algoritm de join .

Algoritmul primește două tabele și o condiție de unire ca intrare. Rezultatul muncii sale este un tabel cu rezultatele conexiunii.

Cel mai mic dintre cele două tabele de intrare este plasat într-o structură specială de date în memorie : o tabelă hash , care oferă o viteză foarte mare de căutare. Apoi, pentru fiecare rând din tabelul mai mare, se face o căutare a valorilor care se potrivesc cu condiția de îmbinare. Rezultatele sunt plasate în tabelul de rezultate.

În pseudocod , algoritmul poate fi descris cam așa:

[HashTable] = BuildHashTable([SmallerTable], [Nume de coloane SmallTable la care să se alăture]); Pentru fiecare rând [r] din [LargeTable] Ieșire ([r], LookInHashTable([HashTable],[LargeTable coloana nume pe care se face îmbinarea]));

Beneficii

• Unirea hash este mult mai rapidă decât îmbinarea buclei imbricate. Având în vedere dimensiunea relativ mică a mesei mai mici, acesta este cel mai eficient tip de unire.

Dezavantaje

• Condițiile de îmbinare trebuie să aibă cel puțin o condiție de echivalență (pentru chei de potrivire).
• O cerință mare de memorie pentru construirea unui tabel hash, care limitează sever scalabilitatea algoritmului pe măsură ce dimensiunea tabelului mai mic crește.
• Tabelul hash trebuie construit complet înainte ca primul rezultat să fie scris în tabelul cu rezultate, ceea ce face ca acest tip de îmbinare să fie inacceptabil dacă doriți să obțineți primul rând al rezultatului cât mai repede posibil.

Sistemele reale folosesc scheme de hashing mai sofisticate decât exemplul de mai sus, având ca scop reducerea necesarului de memorie pentru construirea unui tabel hash. De exemplu, datele ambelor tabele sunt împărțite în părți și un tabel hash este construit doar pentru una dintre aceste părți.

Link -uri

• Craig Freedman Conținutul articolului Hash Join