Algoritmus pro připojení hash

Algoritmus spojení hash je druh  algoritmu spojení .

Algoritmus přijímá jako vstup dvě tabulky a podmínku spojení. Výsledkem jeho práce je tabulka s výsledky spojení.

Menší ze dvou vstupních tabulek je umístěna ve speciální datové struktuře v paměti : hash table , která poskytuje velmi vysokou rychlost vyhledávání. Poté se pro každý řádek z větší tabulky vyhledá hodnoty, které odpovídají podmínce spojení. Výsledky jsou umístěny ve výstupní tabulce.

V pseudokódu lze algoritmus popsat nějak takto:

[HashTable] = BuildHashTable([SmallerTable], [Názvy sloupců Menší tabulky, ke kterým se mají připojit]); Pro každý řádek [r] z [LargeTable] Výstup ([r], LookInHashTable([HashTable],[Názvy sloupců Velké tabulky, na kterých je spojení provedeno]));

Výhody

• Hash spojení je mnohem rychlejší než spojení vnořené smyčky. Vzhledem k relativně malé velikosti menšího stolu se jedná o nejefektivnější způsob spojení.

Nevýhody

• Podmínky připojení musí mít alespoň jednu podmínku ekvivalence (pro odpovídající klíče).
• Velké požadavky na paměť pro vytvoření hash tabulky, což vážně omezuje škálovatelnost algoritmu, protože velikost menší tabulky se zvětšuje.
• Hašovací tabulka musí být kompletně sestavena před zapsáním prvního výsledku do výsledné tabulky, což činí tento druh spojení nepřijatelným, pokud chcete získat první řádek výsledku co nejrychleji.

Reálné systémy používají sofistikovanější hashovací schémata než výše uvedený příklad, zaměřené především na snížení požadavků na paměť pro vytvoření hashovací tabulky. Například data obou tabulek jsou rozdělena na části a hashovací tabulka je sestavena pouze pro jednu z těchto částí.

Odkazy

• Craig Freedman Obsah článku Hash Join