Hash Join Algorithm

Hajautusalgoritmi on eräänlainen  liitosalgoritmi . _ _

Algoritmi vastaanottaa syötteenä kaksi taulukkoa ja liitosehdon. Hänen työnsä tulos on taulukko yhteyden tuloksista.

Pienempi kahdesta syöttötaulukosta on sijoitettu erityiseen muistin sisäiseen tietorakenteeseen : hash-taulukkoon , joka tarjoaa erittäin suuren hakunopeuden. Sitten jokaiselle suuremman taulukon riville tehdään haku arvoja, jotka vastaavat liitosehtoa. Tulokset sijoitetaan tulostaulukkoon.

Pseudokoodissa algoritmi voidaan kuvata näin:

[HashTable] = BuildHashTable([Pienempitaulukko], [Pienempitaulukko-sarakkeiden nimet, joihin liitetään]); Jokaiselle riville [r] kohteesta [LargeTable] Tulos ([r], LookInHashTable([HashTable],[LargeTable-sarakkeiden nimet, joihin liitos tehdään]));

Edut

• Hash-liitos on paljon nopeampi kuin sisäkkäinen silmukkaliitos. Pienen pöydän suhteellisen pienen koon vuoksi tämä on tehokkain liitostyyppi.

Haitat

• Liittymisehdoissa on oltava vähintään yksi vastaavuusehto (vastaaville avaimille).
• Suuri muistitarve hash-taulukon rakentamiseen, mikä rajoittaa pahasti algoritmin skaalautuvuutta pienemmän taulukon koon kasvaessa.
• Hajautustaulukko on rakennettava kokonaan ennen kuin ensimmäinen tulos kirjoitetaan tulostaulukkoon, mikä tekee tällaisesta liittämisestä mahdotonta hyväksyä, jos haluat saada tuloksen ensimmäisen rivin mahdollisimman nopeasti.

Todelliset järjestelmät käyttävät yllä olevaa esimerkkiä kehittyneempiä hajautusmenetelmiä, joiden tarkoituksena on pääasiassa vähentää muistin tarvetta hash-taulukon rakentamiseen. Esimerkiksi molempien taulukoiden tiedot jaetaan osiin, ja vain yhdelle näistä osista rakennetaan hash-taulukko.

Linkit

• Craig Freedman Artikkelin sisältö Hash Join