![]() |
![]() | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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:
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 é xù 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.
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> |