COMPUTERWORLD
pod kapotou
Hašovaná spojení

Novější verze relačních databázových serverů se ve výčtu svých novinek často zmiňují o hašovaných spojeních, která mohou výrazně zlepšit provedení této časově nejnáročnější relační operace. Nejprve ale krátce o tom, jaké jiné algoritmy jsou pro spojení v relačním serveru k dispozici. Není jich mnoho. Z klasických algoritmů jsou často uváděny dva:

  • metoda vnořených cyklů,
  • metoda setřídění-slévání.

Tyto algoritmy jsou zcela nezajímavé. Budeme předpokládat, že relace, které spojujeme jsou R a S, prostor v počtu stránek potřebný pro tyto relace je pR, resp. pS. Dále budeme předpokládat, že R je menší než S, tj. pR £ pS a že ve vnitřní paměti máme k dispozici prostor velikosti M stránek.

V prvním z algoritmů se spojení řádků tabulek provádí sekvenčním prolézáním obou relací ve dvou cyklech tak, že se porovnává každý řádek s každým. To lze dělat pouze v případech, že relace ve vnějším cyklu (zde R) je dostatečně malá. Počet čtení stránek je v daném případě

pR + pS* pR

Ve druhé metodě, je nutné relace R a S nejprve setřídit. Pak se čtou sekvenčně, postupně se provádí porovnání n-tic a v positivním případě se vytváří n-tice výsledku. Neuvažuje-li se čas potřebný ke třídění, přečte se celkem

pR + pS

stránek. Oba algoritmy lze modifikovat se zlepšením časové složitosti, existují-li pro atribut A indexy.

Implementace relačních SŘBD ukázaly, že jestliže nejsou dostupné indexy k spojovacím atributům relací a jestliže výsledek spojení nemusí být setříděn podle hodnot spojovacích atributů, je nejlepší použít pro spojení hašování.

Vysvětlíme princip této metody na nejjednodušší variantě - klasickém hašování. Dále ukážeme variantu tzv. GRACE algoritmu, použitého původně v hardwarově orientované verzi spojení v japonském projektu 5. generace počítačů. Jde o případ, kdy žádnou z relací nelze hašovat celou do vnitřní paměti. Budeme předpokládat, že relace, které spojujeme jsou R a S, prostor potřebný pro tyto relace je pR, resp. pS. Dále budeme předpokládat, že R je menší než S, tj. pR £ pS a že ve vnitřní paměti máme k dispozici prostor velikosti M stránek.

Spojení klasickým hašováním

Nejjednodušší variantou spojení pomocí hašování je metoda nazývaná spojení klasickým hašováním. Ve vnitřní paměti se alokuje prostor, do kterého lze hašovat celou relaci R (viz heslo Hašování Databázové abecedy). Protože k hašování je nutné použít větší prostor než pR, budeme dále uvažovat koeficient F, který v součinu s pR vede ke skutečné velikosti potřebného prostoru. Obvykle F= 1,25, tj. relace R zabírá 80% vyhrazeného prostoru. Tedy é pR *Fù < M, kde é přiřazuje x nejbližší celé číslo větší nebo rovné x.

Algoritmus klasického hašování spočívá v tom, že po zahašování relace R do vnitřní paměti se sekvenčně čte relace S, hašuje se hodnota s.A pro každý prvek s z S, a k ní se nachází přímým přístupem odpovídající n-tice r z R uložené ve vnitřní paměti. Je-li splněna podmínka spojení, např. s.A = r.A, generuje se odpovídající n-tice výsledku.

Je zřejmé, že tento algoritmus vyžaduje (bez ukládání výsledku)

pR + pS

operací čtení stránek. Je tedy lepší než metoda setřídění-slévání, protože nevyžaduje čas potřebný ke třídění. Pro realizaci algoritmu stačí é pR *Fù + 1 stránek na čtení, 1 stránka pro vytváření výsledku.

V obecném případě, kdy se relace R (a tedy ani S) nevejde do vnitřní paměti, rozdělují se relace R a S na vhodné disjunktní podmnožiny (kapsy) a spojují se pouze korespondující podmnožiny. Toto rozdělení nemusí být jednoduché, protože je navíc nutné, aby dané podmnožiny měly rozumnou specifikovanou velikost v závislosti na dostupné vnitřní paměti.

Algoritmy s rozdělováním relací mají dvě fáze. V první se provádí rozdělení R a S. V druhé fázi se část R (resp. části R) hašuje do vnitřní paměti, čtou se n-tice s z odpovídající části S, hašováním hodnoty s.A se najdou eventuální odpovídající n-tice r a generují se spojené n-tice do výsledku.

GRACE algoritmus - zjednodušená verze

Obě relace jsou hašovány na atributu A pomocí hašovací funkce h. Pro jednotlivé hodnoty z A jsou pro relaci R, resp. S vytvářeny kapsy ukazatelů na n-tice z R, resp. S. Každá kapsa HRi odpovídá těm n-ticím z R, jejichž hodnota atributu A se hašuje na hodnotu i (kolize se soustřeďují do jedné kapsy). Tedy h zobrazuje atribut A do množiny {0,1,...,m-1}, tj. i je z této množiny. Podobně uvažujeme i pro relaci S, kde kapsy označujeme HS i.

Kapsy lze je realizovat jako datové struktury ve vnitřní paměti. Sekvenčním čtením obou relací se kapsy naplní ukazateli na n-tice, tj. přesněji řečeno ukazatelem na stránku, kde se n-tice nalézá (+ event. relativní číslo n-tice). Je zřejmé, že pro potencionální spojení přicházejí v úvahu pouze n-tice z odpovídajících si kapes, tj. z HRi a HSi. Díky tomu, že hašovací funkce není prostá, mohou ale existovat v daných kapsách n-tice r, resp. s tak, že r.A ¹ s.A.

Situaci lze ukázat na obr. 1. Vytváření kapes vlastně odpovídá rozdělení relace R, resp. S na m podrelací. Pak se převede problém spojení na realizaci spojení pro dvojice odpovídajících si podrelací. Pro odpovídající kapsy odpovídají žluté čtverce těm dvojicím, které jdou potencionálně spojit.

   

HS0

HS1

...

HSm-1

   

s0 s1

s5 s6 s7 s8

...

sk sk+1 ... snS

r1

   

 

HR0

r2

       
 

r3

       

r4

       
 

r5

       

HR1

r6

       

.

         

.

         

.

         

         
           

HRm-1

rnR-1

       
 

rnR

       

Obr. 1 Adepti na spojení v korespondujících si kapsách

Hašované spojení s rozdělováním relací je vhodné vytvářet tehdy, když se n-tice odpovídající jedné kapse vejdou do vnitřní paměti. Pak je složitost spojení, které se v algoritmu realizuje např. pomocí hnízděných cyklů, lineární v počtu řádků obou relací. Počet stránek čtený ve fázi rozdělování relací je pR + pS, v další fázi činí nR + nS, tj. musíme přečíst stránku pro každou uvažovanou n-tici. Celkový počet čtení je tedy

pR + pS + nR + nS

což se zatím nezdá příliš výhodné.

Pro vlastní spojení lze opět využít hašování. Podrelaci Ri se při načítání do vnitřní paměti hašuje přes atribut A do odpovídajícího adresového prostoru. Pak při čtení Si pro 1 stránce hašujeme s.A, vstupujeme k n-ticím R a provádíme či neprovádíme spojení. Velikost M souvisí s m. Zřejmě musí platit

(pR/m) * F + 1 < M

Úspěch metody patrně závisí i na tom, zdali se podaří vytvořit všechny kapsy (zhruba) stejně velké.

GRACE algoritmus s ukládáním rozdělených relací

Tato verze bude realističtější. Nevyužívají se kapsy, ale relace se dokomponují na části a ty se ukládají na disk. Pro obě fáze se použije Ö (pR*F) stránek vnitřní paměti. Zbytek (do M stránek) je možné využít pro ukládání částí rozdělených relací. Pro i-tou část disponujeme v prostoru M stránek jednou stránkou (bufferi). Algoritmus probíhá v následujících krocích:

(1) Zvol hašovací funkci h tak, že relaci R lze rozdělit do m = Ö (pR *F) částí přibližně stejné délky.

(2) Čti relaci R a hašuj ji do (výstupních) vyrovnávacích pamětí. Kdykoli se bufferi, 0£ i£ m-1, naplní, zapiš ho na disk. Po přečtení celé relace R zapiš všechny bufferi na disk.

(3) Čti relaci S a zpracuj ji stejně jako relaci R.

Pro 0 £ i £ m-1 proveď kroky (4) a (5).

(4) Čti Ri a hašuj ji do paměti velikosti Ö (pR *F). Zdůvodnění: protože všechny Ri jsou přibližně stejně velké, jejich velikost je srovnatelná s pR /m = pR / Ö (pR *F) = Ö (pR /F) stránkami. Vyžadují tedy prostor F* Ö (pR /F) = Ö (pR *F) stránek.

(5) Čti n-tice z Si a hašuj je na hodnotě atributu A. Existují-li odpovídající n-tice relace Ri, generuj výsledek.

Výhodné je, že části relace S mohou být libovolné velikosti. Potřebujeme pro ně pouze 1 stránku paměti. Počet I/O operací (neuvažujeme-li zápis výsledku) činí

3(pR + pR)

Uvážíme-li, že existují servery, jejichž kapacita vnitřní paměti je několik Gbyte, pak i alternativa spojení s klasickým hašováním je zcela postačující, neboť je velmi pravděpodobné, že celá relace R (ne-li dokonce obě) se vejde do vnitřní paměti.



<seznam dílů seriálu>   <COMPUTERWORLD>