PA152: Efektivní využívání DB
8. Optimalizace dotazu
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2009 2
Poděkování
 Zdrojem materiálů tohoto předmětu jsou:
Přednášky CS245, CS345, CS345
 Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer
Widom
 Stanford University, California
PA152, Vlastislav Dohnal, FI MUNI, 2009 3
Optimalizace dotazu
 Generování a porovnávání plánů dotazu
Zvol nejlepší
Dotaz
Plány
Odhady ceny
Generování
Filtrování
Ocenění
PA152, Vlastislav Dohnal, FI MUNI, 2009 4
Generování plánu dotazu
 Zvážit používání:
Transformační pravidla rel. algebry
Implementace operátorů rel. algebry
Použití existujících indexů
Vytváření indexů a třízení podle potřeb
PA152, Vlastislav Dohnal, FI MUNI, 2009 5
Odhad ceny plánu
 Předpoklady implementace operace
Vstup se čte z disku
Výstup zůstává v operační paměti
Operace na CPU jsou zanedbány
 CPU stačí počítat během čtení z disku
Počítat komunikaci po síti
 U distribuovaných databází
Ignorování vyrovnávacích pamětí
 Odhad ceny = počet čtení / zápisů z disku
PA152, Vlastislav Dohnal, FI MUNI, 2009 6
Odhad ceny plánu
 Parametry
B(R) – velikost relace R v blocích
f(R) – max. počet záznamů relace v bloku
M – max. dostupná RAM v blocích
HT(i) – počet úrovní indexu i
LB(i) – celkový počet listových bloků indexu
PA152, Vlastislav Dohnal, FI MUNI, 2009 7
Operace čtení relace: table scan
 Relace je shlukovaná (clustered)
Čtení je B(R)
TwoPhase-MergeSort = 3B čtení a zápisů
 Finální zápis ignorujeme
 Relace není shlukovaná (non-clustered)
Čtení je až T(R) bloků!
TwoPhase-MergeSort
 T(R) + 2B čtení a zápisů
R1 R2 R3 R4 R5 R6 R7 R8 …
R1 R2 S1 S2 R3 R4 S3 S4 …
PA152, Vlastislav Dohnal, FI MUNI, 2009 8
Operace čtení relace: index scan
 Čtení relace s použitím indexu
Na libovolném atributu
Procházíme index  čteme záznamy
 Čteme bloky indexu (<< B(R))
 Čteme záznamy relace
Náklady: B(R) až T(R) čtení
Výhoda
 Lze omezit pouze na interval záznamů
PA152, Vlastislav Dohnal, FI MUNI, 2009 9
Implementace operátoru
 Použití konceptu iterátor
Open – inicializace operátoru, příprava před
vracením řádků výsledku
GetNext – vrácení dalšího řádku výsledku
Close – ukončení operátoru, uvolnění
dočasné paměti, …
 Výhody
Výsledek nemusí být vygenerován „naráz“
 Nezabírá paměť, nemusí být ukládán
Operace lze řetězit (pipelining)
PA152, Vlastislav Dohnal, FI MUNI, 2009 10
Jednoprůchodové algoritmy
 Implementace:
Čtení relace  zpracování  výstupní paměť
Zpracování záznam po záznamu
 Operace
Projekce, selekce, rušení duplicit (DISTINCT)
Agregační funkce (GROUP BY)
 Náklady B(R)
Množinové operace, kartézský součin
 Náklady B(R) + B(S)
PA152, Vlastislav Dohnal, FI MUNI, 2009 11
Rušení duplicit
 Postup zpracování
Otestuj, zda je již záznam ve výstupu
Ne, přidej na výstup
 Testování existence ve výstupu
Pamatovat si v paměti již vypsané záznamy
 Lze použití M-1 bloků
Testování sekvenčně je pomalé (n2 porovnání)
Použití hašování
Omezení B(R) < M
PA152, Vlastislav Dohnal, FI MUNI, 2009 12
Agregační funkce
 Postup zpracování
 Vytváření skupin pro group-by atributy
 Ukládání hodnot atributů pro agregační funkce
 Interní struktura
 Pro organizaci skupin – např. hašování
 Agregační funkce
 MIN, MIN, COUNT, SUM – pouze jedno „číslo“
 AVG – dvě čísla (SUM a COUNT)
 Ukládaná informace je malá, bývá dostatečné M-1 bloků
 Vše je vypočteno v Open
 Výhoda proudového zpracování mizí
PA152, Vlastislav Dohnal, FI MUNI, 2009 13
Množinové operace
 Požadavek min(B(R), B(S)) < M
Menší relace se načte celá, větší se čte
postupně
 Výjimka
Multimnožinové sjednocení s duplicitami
 Obě relace se čtou postupně
 Předpoklad
R je větší relace, tj. S je celá v paměti
 Implementace
Obvykle pomocná vyhledávací struktura
 Např. hašování
PA152, Vlastislav Dohnal, FI MUNI, 2009 14
Množinové operace
 Množinové sjednocení a průnik
Pozor: Ne multimnožinové verze
Načti S, vybuduj vyhledávací strukturu
 Eliminuj duplicitní řádky
Při čtení R ověřuj přítomnost záznamu v S
Pak dej na výstup
 Sjednocení
nakonec vypiš i S
PA152, Vlastislav Dohnal, FI MUNI, 2009 15
Množinové operace
 Množinový rozdíl
 Není komutativní – R-S ≠ S-R
 R-S
 Načti S, vybuduj vyhledávací strukturu
 Při čtení R ověřuj přítomnost záznamu v S
 Pokud není, dej na výstup
 S-R
 Načti S, vybuduj vyhledávací strukturu
 Při čtení R ověřuj přítomnost záznamu v S
 Pokud je, smaž záznam z S
 Nakonec vypiš zbylý obsah S
PA152, Vlastislav Dohnal, FI MUNI, 2009 16
Multimnožinové operace
 Multimnožinový průnik RBS
Načti S, vybuduj vyhledávací strukturu
 Místo ukládání duplicitních řádků ukládej jejich
počet
Při čtení R ověřuj přítomnost záznamu v S
Záznam byl nalezen, pak dej na výstup
 A sniž počet záznamů!
 Pokud je počet již nula, pak se na výstup nic
nedává.
PA152, Vlastislav Dohnal, FI MUNI, 2009 17
Množinové operace
 Multimnožinový rozdíl S-BR
Používá stejný trik
Záznam z R byl nalezen, sniž počet záznamů
Nakonec vypiš pouze záznamy z S
 Které mají nenulový počet.
 Multimnožinový rozdíl R-BS
Stejný trik
Záznam z R nebyl v S nalezen  výstup
Záznam z R byl v S nalezen
  sniž počet
  pokud je počet nula (před snížením), dej na výstup.
PA152, Vlastislav Dohnal, FI MUNI, 2009 18
Množinové operace
 Kartézský součin
Snadné cvičení…
 Přirozené spojení
Předpoklad R(X,Y), S(Y,Z)
 X – atributy unikátní v R, Z – atributy unikátní v S
 Y – atributy společné v R a S
Načti S, vybuduj vyhledávací strukturu pro Y
Pro záznam z R, najdi v S všechny odpovídající
 Na výstup dej jejich kombinace (eliminuj opakování Y)
PA152, Vlastislav Dohnal, FI MUNI, 2009 19
Jednoprůchodové algoritmy
 Shrnutí
Unární operátory: op(R)
 B(R) ≤ M-1, 1 blok pro výstup
Binární operátory: R op S
 B(S) ≤ M-2, 1 blok pro R, 1 blok pro výstup
Cena = B(R) + B(S)
 Založeno na volné paměti M
Je známo  ok
Není známo  odhadnout
 Chyba  swapování, výměna jednoprůchodového
za dvouprůchodový algoritmus
PA152, Vlastislav Dohnal, FI MUNI, 2009 20
Algoritmy pro spojení
 Relace se nevejdou do paměti
 Základ – vnořené cykly (nested-loop join)
for each s in S do
 for each r in R do
 if r a s se shodují then output spojení r a s.
 Příklad
T(R) = 10 000 T(S) = 5 000
Náklady = 5 000(1+10 000) = 50 005 000 čtení
Čtení celé RČtení záznamu z S
PA152, Vlastislav Dohnal, FI MUNI, 2009 21
Algoritmy pro spojení
 Relace uloženy v blocích
 Blokované vnořené cykly
block-based nested-loop join
 R – vnitřní relace, S – vnější relace
 Příklad:
B(R) = 1000 B(S) = 500
Náklady = 500(1+1000) = 500 500 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2009 22
Algoritmy pro spojení
 Využití vyrovnávací paměti (M bloků)
Načti M-1 bloků relace S naráz
 Načítej relaci R po 1 bloku
 Spojuj záznamy
Náklady: B(S)/(M-1)  (M-1 + B(R)) čtení
 Příklad R S:
M=101
Náklady: 5  (100 + 1000) = 5 500 čtení
Změna pořadí relací
 Náklady: 10  (100 + 500) = 6 000 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2009 23
Algoritmy pro spojení – hodnocení
 Vnořené cykly
Vždy blokovaná varianta
Do paměti načítat dávky menší relace
 Způsob uložení relace
Důležité pro výslednou cenu
 Nesouvislé  každý záznam jedno čtení
 Souvislé  každý záznam B(R)/T(R) čtení
PA152, Vlastislav Dohnal, FI MUNI, 2009 24
Dvouprůchodové algoritmy
 Implementace:
Předzpracování vstupu  uložení
Zpracování
 Způsob předzpracování
Třízení (Víceprůchodový MergeSort)
Hašování
 Operace
Rušení duplicit (DISTINCT)
Agregační funkce (GROUP BY)
Spojení relací, množinové operace
PA152, Vlastislav Dohnal, FI MUNI, 2009 25
Algoritmy pro spojení – MergeJoin
 R S R(X,Y), S(Y,Z)
R
S
...
uspořádané dávky
paměť
...
výsledek
třízení
výsledek
spojení
průchod se
spojováním
PA152, Vlastislav Dohnal, FI MUNI, 2009 26
Algoritmy pro spojení – MergeJoin
 R S R(X,Y), S(Y,Z)
 Algoritmus:
Setřiď R a S
i = 1; j = 1;
while (i ≤ T(R))  (j ≤ T(S)) do
 if R[i].Y = S[j].Y then výstup
 else if R[i].Y > S[j].Y then j = j+1
 else if R[i].Y < S[j].Y then i = i+1
PA152, Vlastislav Dohnal, FI MUNI, 2009 27
Algoritmy pro spojení – MergeJoin
 Ad výstup
Proveď nested-loop join pro řádky se stejným Y
while (R[i].Y = S[j].Y)  (i ≤ T(R)) do
 j2 = j
 while (R[i].Y = S[j2].Y)  (j2 ≤ T(S)) do
 Vypiš spojení R[i] a S[j2]
 j2 = j2 + 1
 i = i + 1
PA152, Vlastislav Dohnal, FI MUNI, 2009 28
Algoritmy pro spojení – MergeJoin
i R[i].Y S[j].Y j
1 10 5 1
2 20 20 2
3 20 20 3
4 30 30 4
5 40 30 5
50 6
52 7
PA152, Vlastislav Dohnal, FI MUNI, 2009 29
Algoritmy pro spojení – MergeJoin
 Cena
Uspořádání R a S  4(B(R) + B(S))
MergeJoin  B(R) + B(S)
 Příklad
MergeJoin
 Uspořádání: 4(1000 + 500) = 6000 čtení/zápisů
 Spojení: 1000 + 500 = 1500 čtení
 Celkem: 7500 čtení/zápisů
Původní nested-loop join
 5500 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2009 30
Algoritmy pro spojení – MergeJoin
 MergeJoin
Předzpracování je drahé
 Pokud jsou relace upořádány podle Y, lze vynechat.
 Náklady – analýza
MergeJoin – lineární
Nested-loop Join – kvadratické
 od jisté velikosti relací je MergeJoin lepší
PA152, Vlastislav Dohnal, FI MUNI, 2009 31
Algoritmy pro spojení – MergeJoin
 Jiný příklad
B(R) = 10000 B(S) = 5000
M = 101 bloků
Nested-loop Join
 (5 000/100)  (100 + 10 000) = 505 000 čtení
MergeJoin
 5(10 000 + 5 000) = 75 000 čtení a zápisů
PA152, Vlastislav Dohnal, FI MUNI, 2009 32
Algoritmy pro spojení – MergeJoin
 Paměťové nároky
Omezení na B(R) ≤ M2 a B(S) ≤ M2
 Optimální paměť
Používáme MergeSort na relaci R
 Počet dávek = B(R) / M, Délka dávky = M
 Omezení: počet dávek ≤ M-1
 B(R) / M < M  B(R) < M2  M > √B(R)
 Příklad
B(R) = 1000  M>31,62
B(S) = 500  M>22,36
PA152, Vlastislav Dohnal, FI MUNI, 2009 33
Algoritmy pro spojení – MergeJoin
 Vylepšení:
není potřeba mít relace zcela uspořádané
R
S
Přímo provést
spojení?
uspořádané dávky
PA152, Vlastislav Dohnal, FI MUNI, 2009 34
Algoritmy pro spojení – SortJoin
 Vylepšení
Vytvoř setříděné dávky R a S
Načti první blok z každé dávky
Zjisti minimální hodnotu Y
 Najdi odpovídající záznamy z ostatních dávek
 Proveď spojení
 Pokud je hodně řádků se stejným y
Aplikuj nested-loop join ve zbytku paměti
PA152, Vlastislav Dohnal, FI MUNI, 2009 35
Algoritmy pro spojení – SortJoin
 Náklady
Uspořádání dávek: 2(B(R) + B(S))
Provedení spojení: B(R) + B(S)
 Omezení
Délka dávek M, počet dávek M
 B(R) + B(S) ≤ M2
 Příklad
Uspořádání dávek: 2(1000 + 500)
Spojení: 1000 + 500
Celkem: 4 500 čtení/zápisů
  lepší než nested-loop join
PA152, Vlastislav Dohnal, FI MUNI, 2009 36
Algoritmy pro spojení – HashJoin
 R S R(X,Y), S(Y,Z)
...
...
M-1R
...
...
M-1S
paměť kyblíky
spojení
PA152, Vlastislav Dohnal, FI MUNI, 2009 37
Algoritmy pro spojení – HashJoin
 R S R(X,Y), S(Y,Z)
Pro atributy Y vytvoř hašovací funkci
Vytvoř hašovaný index pro R i S
 Počet kyblíků je M-1
Pro každé i  [1,M-1]
 Načti kyblík i pro R a S
 Proveď vyhledání odpovídajících si záznamů a
jejich spojení
PA152, Vlastislav Dohnal, FI MUNI, 2009 38
Algoritmy pro spojení – HashJoin
 Spojování kyblíků
Kyblík R načti celý (≤ M-1)
 Pro zrychlení si vytvoř paměťové hašování
Kyblík S čti po blocích
KyblíkyS
...
R
paměť
...
KyblíkyR
PA152, Vlastislav Dohnal, FI MUNI, 2009 39
Algoritmy pro spojení – HashJoin
 Náklady:
Vytvoření hašovaného indexu: 2(B(R)+B(S))
Provedení spojení: B(R)+B(S)
 Omezení:
Velikost každého kyblíku R (nebo S) ≤ M-1
 Odhad: min(B(R), B(S)) ≤ M2
 Příklad:
Hašování: 2(1000+500)
Spojení: 1000+500
Celkem: 4 500 čtení/zápisů
PA152, Vlastislav Dohnal, FI MUNI, 2009 40
Algoritmy pro spojení – HashJoin
 Minimální paměťové nároky
Hašování R, optimální naplnění kyblíků
 Velikost kyblíku: B(R) / M
 Musí být menší než M (kvůli spojení)  B(R) / M < M
  M > √B(R)
 Celkem potřebujeme M+1 paměťových bloků
PA152, Vlastislav Dohnal, FI MUNI, 2009 41
Algoritmy pro spojení – HashJoin
 Optimalizace
ponech některé kyblíky v paměti
Hybrid HashJoin
 Optimum počtu kyblíků pro R
√B(R)  33
Tj. 31 bloků má každý kyblík
M=101
  ponechej 2 kyblíky v paměti (62 bloků)
  zbývá 39 bloků paměti
PA152, Vlastislav Dohnal, FI MUNI, 2009 42
Alg. pro spojení – Hybrid HashJoin
 Paměť pro vytvoření hašovaného indexu R
paměť
G0
G1
in
...
31 bloků
33-2=31 kyblíků
R
Využití paměti:
G0 31 bloků
G1 31 bloků
Ostatní kyblíky 33-2 bloků
Čtení R 1 blok _
Celkem 94 bloků
6 bloků je volných!
PA152, Vlastislav Dohnal, FI MUNI, 2009 43
Alg. pro spojení – Hybrid HashJoin
 Paměť pro vytvoření hašovaného indexu S
500/33 = 16 bloků na kyblík
Záznamy hašované do kyblíku 0 a 1
 Vyřešit hned (R je v paměti)  výstup
paměť
G0
G1
in
...
16 bloků
33-2=31 kyblíků
S
PA152, Vlastislav Dohnal, FI MUNI, 2009 44
Alg. pro spojení – Hybrid HashJoin
 Spojení kyblíků
Pouze pro kyblíky s id 2-32
Načti jeden kyblík celý do paměti, druhý
procházej po blocích
paměť
Hi
výstupní
...16
33-2=31
výsledek
...
31
33-2=31
Kyblíky S Kyblíky R
jeden
kyblík S
jeden blok
kyblíku R
PA152, Vlastislav Dohnal, FI MUNI, 2009 45
Alg. pro spojení – Hybrid HashJoin
 Náklady:
Hašování R: 1000 + 3131 = 1961 čtení/zápisů
Hašování S: 500 + 3116 = 996 čtení/zápisů
 Pouze 31 kyblíků!
Spojení: 3131 + 3116 = 1457 čtení
 2 kyblík jsou již zpracovány
Celkem: 4414 čtení/zápisů
PA152, Vlastislav Dohnal, FI MUNI, 2009 46
Algoritmy pro spojení
 Hybrid HashJoin
Kolik kyblíků ponechat v paměti?
Empiricky: 1 kyblík
 Jiné zlepšení
Hašování ne záznamů, ale ukazatelů
 Do kyblíků ukládej dvojice [hodnota, ukazatel]
Spojování
 Při shodě hodnot si musíme záznam načíst
PA152, Vlastislav Dohnal, FI MUNI, 2009 47
Alg. pro spojení – jiné zlepšení
 Příklad
Do bloku se vejde 100 dvojic hodnota-klíč
Odhadovaný výsledek je 100 záznamů
Náklady:
 Hašování S do paměti
 5000 záznamů  5000/100 bloků = 50 bloků
 Spojení – čti R a spojuj
 Při shodě načti záznam S  100 čtení
 Celkem: 500 + 1000 + 100 = 1600 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2009 48
Algoritmy pro spojení – IndexJoin
 R S R(X,Y), S(Y,Z)
 Předpoklad: R má index nad atributy Y
 Postup:
Pro každý záznam s  S
Prohledej index na shodu  záznamy A
 Pro každý záznam r  A
 Vypiš kombinaci r a s
PA152, Vlastislav Dohnal, FI MUNI, 2009 49
Algoritmy pro spojení – IndexJoin
 Příklad
Předpoklady
 Index na Y pro relaci R: HT=2, LB=200
 Situace 1
Index se vejde do paměti
Náklady:
 Průchod S: 500 čtení
 Prohledání indexu: zdarma
 Pokud shoda, načti záznam R – 1 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2009 50
Algoritmy pro spojení – IndexJoin
 Náklady
Závisí na počtu shod v indexu
Případy:
 A) Y je v R primární klíč, v S je cizí klíč  1 záznam
Výsledek: 500 + 500011 = 5500 čtení
 B) V(R,Y) = 5000 T(R) = 10 000
rovnoměrné rozložení  2 záznamy
Výsledek: 500 + 500021 = 10500 čtení
 C) DOM(R,Y)=1 000 000 T(R) = 10 000
 10k/1m = 1/100 záznamu
Výsledek: 500 + 5000(1/100)1 = 550 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2009 51
Algoritmy pro spojení – IndexJoin
 Situace 2
Index se nevejde do paměti
Index na Y pro R má 201 bloků
 V paměti udržuj kořen a 99 listů
Náklady pro vyhledání
 0(99/200) + 1(101/200) = 0.5 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2009 52
Algoritmy pro spojení – IndexJoin
 Situace 2
Náklady
 B(S) + T(S)(prohledání indexu + čtení záznamů)
Případy:
 A)  1 záznam
Výsledek: 500 + 5000(0,5+1) = 8000 čtení
 B)  2 záznamy
Výsledek: 500 + 5000(0,5+2) = 13000 čtení
 C)  1/100 záznamu
Výsledek: 500 + 5000(0,5+1/100) = 3050 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2009 53
Algoritmy pro spojení – shrnutí
Nested-loop Join 5500
Merge Join 1500
Sort Merge Join 7500
Index Join
R.Y index 5500  550
Hash Join 4500
Hybrid verze 4414
Ukazatele 1600
PA152, Vlastislav Dohnal, FI MUNI, 2009 54
Algoritmy pro spojení – doporučení
 Nested-loop Join
 Vhodné pro malé relace (vzhledem k paměti)
 Pro spojení na rovnost (equi-join)
 Relace nejsou uspořádané a nejsou indexy 
HashJoin
 SortMergeJoin
 Vhodný pro spojení s nerovností (non-equi-join)
 Např. R.Y > S.Y
 MergeJoin
 Pokud jsou relace již uspořádané
 IndexJoin
 Pokud jsou indexy, může být vhodná volba
 Závisí na velikosti odpovědi
PA152, Vlastislav Dohnal, FI MUNI, 2009 55
Dvouprůchodové algoritmy
 Třízení
Rušení duplicit
Agregační funkce (GROUP BY)
Množinové operace
PA152, Vlastislav Dohnal, FI MUNI, 2009 56
Rušení duplicit
 Postup zpracování
Proveď první fázi MergeSort
  uspořádané dávky na disku
Z každé dávky načítej postupně bloky
 Vezmi nejmenší záznam a dej na výstup
 Přeskoč všechny duplicitní záznamy
 Vlastnosti
Náklady: 3B(R)
Omezení: B(R) ≤ M2
 Optimální M≥√B(R)
PA152, Vlastislav Dohnal, FI MUNI, 2009 57
Agregační funkce
 Postup (podobný předchozímu)
Uspořádej dávky R (podle group-by atributů)
Z každé dávky načítej postupně bloky
 Vezmi nejmenší záznam  nová skupina
 Počítej agregační funkce pro všechny stejné záznamy
 Žádný další není  vypiš výsledky na výstup
 Vlastnosti
Náklady: 3B(R)
Omezení: B(R) ≤ M2
 Optimální M≥√B(R)
PA152, Vlastislav Dohnal, FI MUNI, 2009 58
Množinové sjednocení
 Pro multimnožiny není třeba dvou průchodů
 Množinové sjednocení
Proveď první fázi MergeSort pro R a S
  uspořádané dávky na disku
Z každé dávky (R i S) načítej postupně bloky
 Vezmi nejmenší záznam a dej na výstup
 Přeskoč všechny duplicitní záznamy (z R i S)
 Vlastnosti
Náklady: 3(B(R) + B(S))
Omezení: B(R) + B(S) ≤ M
PA152, Vlastislav Dohnal, FI MUNI, 2009 59
Množinový průnik a rozdíl
 RS, R-S, RBS, R-BS
 Postup
Proveď první fázi MergeSort pro R a S
Z každé dávky (R i S) načítej postupně bloky
 Vezmi nejmenší záznam t
 Spočítej jeho všechny výskyty v R a S (odděleně)
 #R, #S
 Vypiš na výstup (respektuj danou operaci)
PA152, Vlastislav Dohnal, FI MUNI, 2009 60
Množinový průnik a rozdíl
 Ad výpis
Množinový průnik: vypiš t, pokud #R > 0  #S > 0
Multimnož. průnik: vypiš t min(#R,#S)-krát
Množinový rozdíl: vypiš t, pokud #R > 0  #S = 0
Multimnož. rozdíl: vypiš t max(#R - #S,0)-krát
 Vlastnosti
Náklady: 3(B(R) + B(S))
Omezení: B(R) + B(S) ≤ M
PA152, Vlastislav Dohnal, FI MUNI, 2009 61
Dvouprůchodové algoritmy
 Hašování
Rušení duplicit
Agregační funkce (GROUP BY)
Množinové operace
PA152, Vlastislav Dohnal, FI MUNI, 2009 62
Rušení duplicit
 Postup zpracování
Proveď hašování R do M-1 kyblíků
  kyblíky ulož na disk
Pro každý kyblík
 Načti do paměti
 Zruš duplicity  zbytek na výstup
 Vlastnosti
Náklady: 3B(R)
Omezení: B(R) ≤ M2
PA152, Vlastislav Dohnal, FI MUNI, 2009 63
Agregační funkce
 Postup (podobný předchozímu)
Proveď hašování R do M-1 kyblíků
 podle group-by atributů
Pro každý kyblík
 Načti do paměti
 Vytvoř skupiny a spočítej agregační funkce
 Vypiš výsledky na výstup
 Vlastnosti
Náklady: 3B(R)
Omezení: B(R) ≤ M2
PA152, Vlastislav Dohnal, FI MUNI, 2009 64
Množinové sjednocení, průnik, rozdíl
 Postup
Proveď hašování pro R a S (stejnou haš. funkcí!)
Zpracuj vždy dvojici kyblíků Ri a Si
 Jeden z kyblíků načti do paměti
 Druhý zpracuj postupně
 Vlastnosti
Náklady: 3(B(R) + B(S))
Omezení: min(B(R), B(S)) ≤ M2
PA152, Vlastislav Dohnal, FI MUNI, 2009 65
Shrnutí
 Seznam operací a jejich nákladů a omezení
Viz slides08-optimalizace-dotazu-shrnuti.pdf