Hash Join Algorithm

A hash join algoritmus egyfajta  összekapcsolási algoritmus .

Az algoritmus bemenetként két táblát és egy összekapcsolási feltételt kap. Munkája eredménye egy táblázat a kapcsolat eredményeivel.

A két bemeneti tábla közül a kisebbik egy speciális memórián belüli adatszerkezetben van elhelyezve : egy hash táblában , amely nagyon nagy keresési sebességet biztosít. Ezután a nagyobb tábla minden sorában megkeresi azokat az értékeket, amelyek megfelelnek az összekapcsolási feltételnek. Az eredmények a kimeneti táblázatba kerülnek.

A pszeudokódban az algoritmus a következőképpen írható le:

[HashTable] = BuildHashTable([SmallerTable], [Kisebb táblázat oszlopnevek, amelyekhez csatlakozni kell]); A [LargeTable] minden egyes sorához [r] Kimenet ([r], LookInHashTable([HashTable],[LargeTable oszlopnevek, amelyeken az összekapcsolás történik]));

Előnyök

• A hash join sokkal gyorsabb, mint a beágyazott hurokcsatlakozás. A kisebb asztal viszonylag kis mérete miatt ez a leghatékonyabb csatlakozási mód.

Hátrányok

• Az összekapcsolási feltételeknek tartalmazniuk kell legalább egy ekvivalenciafeltételt (az egyező kulcsokhoz).
• Nagy memóriaigény a hash tábla felépítéséhez, ami erősen korlátozza az algoritmus skálázhatóságát a kisebb tábla méretének növekedésével.
• A hash táblát teljesen fel kell építeni, mielőtt az első eredményt az eredménytáblázatba írnánk, ami elfogadhatatlanná teszi ezt a fajta összekapcsolást, ha az eredmény első sorát szeretnénk a lehető leggyorsabban megkapni.

A valódi rendszerek a fenti példánál kifinomultabb kivonatolási sémákat használnak, főként a hash tábla felépítéséhez szükséges memóriaigény csökkentését célozva. Például mindkét tábla adatai részekre oszlanak, és csak az egyik részhez készül egy hash tábla.

Linkek

• Craig Freedman A cikk tartalma Hash Join