Hash připojit - Hash join

Hash je uveden příklad spojit algoritmus a používá se při provádění relační databázový systém . Všechny varianty algoritmů hash join zahrnují vytváření hašovacích tabulek z n-tic jedné nebo obou spojených relací a následné prozkoumávání těchto tabulek, takže je třeba porovnávat pouze n-tice se stejným hash kódem pro rovnost v equijoins.

Spojení hash jsou obvykle efektivnější než spojení vnořených smyček, kromě případů, kdy je strana spojení spojení velmi malá. Vyžadují equijoin predikát (a predikát srovnávající záznamy z jedné tabulky s údaji z druhé tabulky pomocí kombinací různých operátorů rovnosti ‚=‘ na jeden nebo více sloupců).

Klasický hash join

Klasický algoritmus hash join pro vnitřní spojení dvou vztahů probíhá následovně:

  • Nejprve připravte hashovací tabulku pomocí obsahu jedné relace, ideálně podle toho, která z nich je menší po použití místních predikátů. Tato relace se nazývá stránka sestavení spojení. Položky tabulky hash jsou mapování z hodnoty (složeného) atributu join na zbývající atributy daného řádku (podle toho, které z nich jsou potřeba).
  • Jakmile je hashovací tabulka vytvořena, naskenujte druhý vztah (strana sondy). Pro každý řádek relace sondy vyhledejte příslušné řádky z relace sestavení pohledem do hash tabulky .

První fáze se obvykle nazývá fáze "sestavení" , zatímco druhá fáze se nazývá fáze "sondy" . Podobně se relace spojení, na které je vytvořena hashovací tabulka, nazývá vstup „sestavení“, zatímco druhý vstup se nazývá vstup „sonda“.

Tento algoritmus je jednoduchý, ale vyžaduje, aby se vztah menšího spojení hodil do paměti, což někdy není pravda. Jednoduchý přístup k řešení této situace probíhá následovně:

  1. Pro každou n-tici ve vstupu sestavení
    1. Přidejte do tabulky hash v paměti
    2. Pokud se velikost tabulky hash rovná maximální velikosti v paměti:
      1. Naskenujte vstup sondy a do výstupní relace přidejte odpovídající spojovací n-tice
      2. Resetujte hashovací tabulku a pokračujte ve skenování vstupu sestavení
  2. Proveďte finální skenování vstupu sondy a přidejte výsledné spojovací n-tice do výstupního vztahu

To je v podstatě stejné jako u algoritmu blokování vnořené smyčky . Tento algoritmus skenuje nakonec vícekrát, než je nutné.

Grace hash připojit

Lepší přístup je známý jako „grace hash join“ po databázovém stroji GRACE, pro který byl poprvé implementován.

Tento algoritmus zabrání opětovnému prohledání celé relace tak, že nejprve rozdělíte obě oddíly a pomocí hashovací funkce a zapíšete tyto oddíly na disk. Algoritmus poté načte páry oddílů do paměti, vytvoří hašovací tabulku pro menší rozdělenou relaci a prozkoumá druhou relaci pro shody s aktuální hashovací tabulkou. Protože oddíly byly vytvořeny hašováním na klíči spojení, musí to být tak, že všechny výstupní n-tice spojení musí patřit do stejného oddílu.

Je možné, že se jeden nebo více oddílů stále nevejde do dostupné paměti, v takovém případě se algoritmus použije rekurzivně: je vybrána další ortogonální hashovací funkce k hašování velkého oddílu do dílčích oddílů, které jsou poté zpracovány jako před. Vzhledem k tomu, že je to nákladné, pokusí se algoritmus snížit pravděpodobnost, že k tomu dojde vytvořením nejmenších možných oddílů během počáteční fáze rozdělení.

Hybridní hash join

Hybridní algoritmus hash join je zdokonalením grace hash join, která využívá více dostupné paměti. Během fáze rozdělení používá hybridní hash join dostupnou paměť pro dva účely:

  1. Pro uložení aktuální stránky výstupní paměti pro každý z oddílů
  2. K uložení celého oddílu v paměti, známého jako „oddíl 0“

Protože oddíl 0 se nikdy nezapisuje ani nečte z disku, hybridní hash join obvykle provádí méně I / O operací než milostný hash join. Všimněte si, že tento algoritmus je citlivý na paměť, protože existují dva konkurenční požadavky na paměť (hash tabulka pro oddíl 0 a výstupní vyrovnávací paměti pro zbývající oddíly). Výběr příliš velké tabulky hash může způsobit opakování algoritmu, protože jeden z nenulových oddílů je příliš velký, aby se vešel do paměti.

Protipřipojte se hash

Spojení hash lze také vyhodnotit pro predikát anti-spojení (predikát, který vybírá hodnoty z jedné tabulky, pokud v druhé nejsou nalezeny žádné související hodnoty). V závislosti na velikostech tabulek lze použít různé algoritmy:

Hash vlevo anti-join

  • Připravte hashovací tabulku pro stranu NOT IN spojení.
  • Naskenujte druhou tabulku a vyberte všechny řádky, kde atribut join hashuje na prázdný záznam v hash tabulce.

To je efektivnější, když tabulka NOT IN je menší než tabulka FROM

Hash pravý anti-join

  • Připravte hashovací tabulku pro FROM stranu spojení.
  • Naskenujte tabulku NOT IN a odeberte odpovídající záznamy z hash tabulky při každém zásahu hash
  • Vraťte vše, co zbylo v hašovací tabulce

To je efektivnější, když tabulka NOT IN je větší než tabulka FROM

Hash semi-join

Hash semi-join se používá k vrácení záznamů nalezených v druhé tabulce. Na rozdíl od obyčejného spojení vrátí každý odpovídající záznam z hlavní tabulky pouze jednou, bez ohledu na to, kolik shod existuje v IN tabulce.

Stejně jako u anti-join, semi-join může být také vlevo a vpravo:

Hašujte levé spojení

  • Připravte hashovací tabulku pro IN stranu spojení.
  • Naskenujte druhou tabulku a vraťte všechny řádky, které vytvářejí hash.

Záznamy jsou vráceny hned poté, co vygenerovaly zásah. Skutečné záznamy z hash tabulky jsou ignorovány.

To je efektivnější, když je tabulka IN menší než tabulka FROM

Hash vpravo semi-join

  • Připravte hashovací tabulku pro FROM stranu spojení.
  • Naskenujte IN tabulku, vraťte odpovídající záznamy z hash tabulky a odeberte je

S tímto algoritmem lze každý záznam z hash tabulky (tj. FROM tabulky) vrátit pouze jednou, protože je po vrácení odstraněn.

To je efektivnější, když je tabulka IN větší než tabulka FROM

Viz také

Reference

  1. ^ DeWitt, DJ; Katz, R .; Olken, F .; Shapiro, L .; Stonebraker, M .; Wood, D. (červen 1984). "Implementační techniky pro hlavní paměťové databázové systémy". Proc. Konfig . ACM SIGMOD 14 (4): 1–8. doi : 10,1145 / 971697,602261 .

externí odkazy