PA152: Efektivní využívání DB
8. Optimalizace dotazu
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2016 2
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, 2016 3
Generování plánu dotazu
 Zvážit používání:
Transformační pravidla rel. algebry
Implementace operací rel. algebry
Použití existujících indexů
Vytváření indexů a třídění podle potřeb
PA152, Vlastislav Dohnal, FI MUNI, 2016 4
Odhad ceny plánu
 Závisí na ceně provedení každé operace
 Tj. její implementaci
 Předpoklady ceny operace
 Vstup se čte z disku
 Výstup zůstává v operační paměti
 Operace na CPU
 CPU stačí počítat během čtení z disku
 často zanedbány nebo zjednodušeny
 Komunikace po síti
 Počítat u distribuovaných databází
 Ignorování vyrovnávacích pamětí mezi dotazy
 Odhad ceny operace
 = počet čtení a zápisů z disku
Odhad ceny plánu
 Příklad nastavení PostgreSQL
http://www.postgresql.org/docs/9.1/static/runtime-config-query.html#GUC-CPU-OPERATOR-COST
seq_page_cost (1.0)
random_page_cost (4.0)
cpu_tuple_cost (0.01)
cpu_index_tuple_cost (0.005)
cpu_operator_cost (0.0025)
work_mem (1MB)
 Memory available to an operation
effective_cache_size (128MB)
PA152, Vlastislav Dohnal, FI MUNI, 2016 5
PA152, Vlastislav Dohnal, FI MUNI, 2016 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, 2016 7
Operace čtení relace: table scan
 Relace je shlukovaná (clustered)
Čtení je B(R)
TwoPhase-MergeSort = 3B(R) č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(R) č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, 2016 8
Operace čtení relace: index scan
 Čtení relace s použitím indexu
 Procházíme index  čteme záznamy
 Čteme bloky indexu (<< B(R))
 Čteme záznamy relace
 Na libovolném atributu
 Max. náklady:
 (max. B(R) až T(R) čtení) + (max.
𝑚 𝐻𝑇−1
𝑚−1
)
 Where m is an index arity (LB = 𝑚 𝐻𝑇
)
 Výhoda
 Lze omezit pouze na interval záznamů
 Min. náklady: 0 čtení bloků relace + 1..HT bloků indexu
Maximální počet uzlů
m-árního stromu
PA152, Vlastislav Dohnal, FI MUNI, 2016 9
Implementace operace
 Použití konceptu iterátor
Open – inicializace operace
 příprava před vracením řádků výsledku
GetNext – vrácení dalšího řádku výsledku
Close – ukončení operace
 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, 2016 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)
 Náklady B(R)
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, 2016 11
Rušení duplicit – distinct
 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žít M-1 bloků
Testování sekvenčně je pomalé (n2 porovnání)
Použití hašování
 Omezení: B(R) < M
 Lze realizovat pomocí iterátorů?
Distinct – example
 Relation company(company_key,company_name)
PA152, Vlastislav Dohnal, FI MUNI, 2016
12
# explain analyze SELECT DISTINCT company_name FROM provider.company;
HashAggregate (cost=438.68..554.67 rows=11600 width=20) (actual time=9.347..12.133 rows=11615 loops=1)
Group Key: company_name
-> Seq Scan on company (cost=0.00..407.94 rows=12294 width=20)
(actual time=0.019..5.007 rows=12295 loops=1)
Planning time: 0.063 ms
Execution time: 12.799 ms
# explain analyze SELECT DISTINCT company_key FROM provider.company;
Unique (cost=0.29..359.43 rows=12294 width=8) (actual time=0.041..8.857 rows=12295 loops=1)
-> Index Only Scan using company_pkey on company (cost=0.29..328.69 rows=12294 width=8)
(actual time=0.039..5.686 rows=12295 loops=1)
Heap Fetches: 4726
Planning time: 0.063 ms
Execution time: 9.645 ms
# explain analyze SELECT DISTINCT company_name FROM provider.company ORDER BY company_name;
Unique (cost=1243.05..1304.52 rows=11600 width=20) (actual time=53.468..59.072 rows=11615 loops=1)
-> Sort (cost=1243.05..1273.79 rows=12294 width=20) (actual time=53.467..55.482 rows=12295 loops=1)
Sort Key: company_name
Sort Method: quicksort Memory: 1214kB
-> Seq Scan on company (cost=0.00..407.94 rows=12294 width=20)
(actual time=0.018..5.338 rows=12295 loops=1)
PA152, Vlastislav Dohnal, FI MUNI, 2016 13
Agregační funkce (GROUP BY)
 Postup zpracování
 Vytváření skupin pro group-by atributy
 Ukládání hodnot atributů pro agregační funkce
 Interní struktura
 Organizace skupin – např. hašování
 Stav agregační funkce
 MIN, MAX, COUNT, SUM – pouze jedno „číslo/hodnota“
 AVG – dvě čísla (SUM a COUNT)
 Ukládaná informace je malá: M-1 bloků bývá dostatečné
 Iterátory:
 Vše je vypočteno v Open
 Výhoda proudového zpracování mizí
PA152, Vlastislav Dohnal, FI MUNI, 2016 14
Množinové operace
 Požadavek min(B(R), B(S)) < M-2
Menší relace se načte celá
Větší se čte postupně
Množinové sjednocení a množinový rozdíl
 Paměť může být větší: B(R)+B(S) < M-2
 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, 2016
15
Množinové sjednocení
Pozor: Ne multimnožinová verze,
tj. bez ALL v SQL
 Načti S, vybuduj vyhledávací strukturu
Eliminuj duplicitní řádky
Unikátní řádky, hned vypisuj
 Při čtení R ověřuj přítomnost záznamu v S
Je, pak nic.
Není, pak vypiš a přidej do struktury
 Omezení
B(R)+B(S) < M-2
PA152, Vlastislav Dohnal, FI MUNI, 2016
16
Množinový průnik
Pozor: Ne multimnožinová verze,
tj. bez ALL v SQL
 Načti S, vybuduj vyhledávací strukturu
Eliminuj duplicitní řádky
 Při čtení R ověřuj přítomnost záznamu v S
Je, pak vypiš a smaž z interní struktury.
Není, pak nic.
 Omezení
min(B(R), B(S)) < M-2
PA152, Vlastislav Dohnal, FI MUNI, 2016 17
Množinové operace
 Množinový rozdíl (R–S ≠ S–R)
 R–S
 Načti S, vybuduj vyhledávací strukturu
 Eliminuj případné duplicity v S
 Při čtení R ověřuj přítomnost záznamu v S
 Pokud není, dej na výstup
 také přidej do interní struktury
 S–R
 Načti S, vybuduj vyhledávací strukturu
 Eliminuj duplicity
 Při čtení R ověřuj přítomnost záznamu v S
 Pokud je, smaž záznam z S
 Nakonec vypiš zbylý obsah S
Zde pozor, omezení
je B(R)+B(S) < M-2
PA152, Vlastislav Dohnal, FI MUNI, 2016 18
Multimnožinové operace
 Multimnožinové sjednocení RBS
Snadné cvičení…
 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 zruš z interní struktury.
Záznam nebyl nalezen, pak nic
PA152, Vlastislav Dohnal, FI MUNI, 2016 19
Multimnož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í kladný počet.
 Multimnožinový rozdíl R–BS
Analogicky…
Záznam z R nebyl v S nalezen  výstup
Záznam z R byl v S nalezen
  pokud je počet nula, dej na výstup.
  jinak sniž počet a nic
PA152, Vlastislav Dohnal, FI MUNI, 2016 20
Operace spojení
 Kartézský součin
Snadné cvičení…
 Přirozené spojení (NATURAL JOIN v SQL)
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, 2016 21
Jednoprůchodové algoritmy
 Shrnutí
Unární operace: op(R)
 B(R) ≤ M-1, 1 blok pro výstup
Binární operace: R op S
 B(S) ≤ M-2, 1 blok pro R, 1 blok pro výstup
 U některých B(R)+B(S) ≤ M-2
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, 2016 22
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 M=2
Náklady = 5 000(1+10 000) = 50 005 000 čtení
Čtení celé RČtení záznamu z S
PA152, Vlastislav Dohnal, FI MUNI, 2016 23
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 M=3
Náklady = 500(1+1000) = 500 500 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2016 24
Algoritmy pro spojení
 Využití vyrovnávací paměti (M bloků)
Cached Block-based Nested-loop Join
Načti M-2 bloků relace S naráz
 Načítej relaci R po 1 bloku
 Spojuj záznamy
Náklady: B(S)/(M-2)  (M-2 + B(R)) čtení
 Příklad RS:
M=102
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, 2016 25
Algoritmy pro spojení – hodnocení
 Vnořené cykly
Vždy blokovaná varianta
Do paměti načítat dávky menší relace (pro M>3)
 Způsob uložení relace
Důležité pro výslednou cenu
 Nesouvislé (non-clustered)  každý záznam jedno čtení
 Souvislé  každý záznam B(R)/T(R) čtení
 Využitelné pro libovolnou podmínku spojení
tzv. theta-joins
PA152, Vlastislav Dohnal, FI MUNI, 2016
26
Dvouprůchodové algoritmy
 Princip:
Předzpracování vstupu  uložení
 Třídění (vícecestný MergeSort)
 Hašování
Zpracování
 Operace:
Spojení relací
Rušení duplicit (DISTINCT)
Agregační funkce (GROUP BY)
Množinové operace
PA152, Vlastislav Dohnal, FI MUNI, 2016 27
paměť
R
S
...
uspořádané dávky
...
R
S
uspořádané relace
...
výsledek
spojení
průchod se
spojováním
Algoritmy pro spojení – MergeJoin
 R S R(X,Y), S(Y,Z)
disk
PA152, Vlastislav Dohnal, FI MUNI, 2016 28
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 doJoin()
 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, 2016 29
Algoritmy pro spojení – MergeJoin
 Funkce doJoin():
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
j = j2
PA152, Vlastislav Dohnal, FI MUNI, 2016 30
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, 2016 31
Algoritmy pro spojení – MergeJoin
 Cena
MergeSort R a S  4(B(R) + B(S))
MergeJoin  B(R) + B(S)
 Příklad (M=102)
MergeJoin
 Uspořádání: 4(1000 + 500) = 6000 čtení/zápisů
 Spojení: 1000 + 500 = 1500 čtení
 Celkem: 7500 čtení/zápisů
Původní cached block-based nested-loop join
 5500 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2016 32
Algoritmy pro spojení – MergeJoin
 Jiný příklad
B(R) = 10 000 B(S) = 5 000
M = 102 bloků
Cached Block-based Nested-loop Join
 (5 000/100)  (100 + 10 000) = 505 000 čtení
MergeJoin
 5(10 000 + 5 000) = 75 000 čtení a zápisů
10x větší relace!!!
PA152, Vlastislav Dohnal, FI MUNI, 2016 33
Algoritmy pro spojení – MergeJoin
 MergeJoin
Předzpracování je drahé
 Pokud jsou relace uspořádány podle Y, lze vynechat.
 Náklady – analýza
MergeJoin
 lineární složitost
Cached Block-based Nested-loop Join
 kvadratická složitost
 od jisté velikosti relací je MergeJoin lepší
PA152, Vlastislav Dohnal, FI MUNI, 2016 34
Algoritmy pro spojení – MergeJoin
 Paměťové nároky
Omezení na max 𝐵 𝑅 , 𝐵 𝑆 < 𝑀2
 Optimální paměť
Používáme MergeSort na relaci R
 Počet dávek = 𝐵 𝑅 𝑀, Délka dávky = 𝑀
 Omezení: počet dávek ≤ 𝑀 − 1
 𝐵 𝑅 𝑀 < 𝑀  𝐵 𝑅 < 𝑀2  𝑀 > 𝐵 𝑅
 Příklad
B(R) = 1000  M>31,62
B(S) = 500  M>22,36
PA152, Vlastislav Dohnal, FI MUNI, 2016 35
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
(1. fáze MergeSort)
PA152, Vlastislav Dohnal, FI MUNI, 2016 36
Algoritmy pro spojení – SortJoin
 Vylepšení
Vytvoř setříděné dávky R a S
Načti první blok z každé dávky (R i S)
Zjisti minimální hodnotu v Y
 Najdi odpovídající záznamy z ostatních dávek
 Proveď spojení
 Pokud je hodně řádků se stejným Y
Aplikuj block-nested-loop join ve zbytku
paměti
PA152, Vlastislav Dohnal, FI MUNI, 2016 37
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 (M=102)
Uspořádání dávek: 2(1000 + 500)
Spojení: 1000 + 500
Celkem: 4 500 čtení/zápisů
  lepší než cached block-based nested-loop join
PA152, Vlastislav Dohnal, FI MUNI, 2016 38
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, 2016 39
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, 2016 40
Algoritmy pro spojení – HashJoin
 Spojování kyblíků
Kyblík R načti celý (≤ M-2)
 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, 2016 41
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-2
 Odhad: 𝑚𝑖𝑛 𝐵 𝑅 , 𝐵 𝑆 < 𝑀 − 1 . (𝑀 − 2)
 Příklad:
Hašování: 2(1000+500)
Spojení: 1000+500
Celkem: 4 500 čtení/zápisů
PA152, Vlastislav Dohnal, FI MUNI, 2016 42
Algoritmy pro spojení – HashJoin
 Minimální paměťové nároky
Hašování R, optimální naplnění kyblíků
 Celkem máme M paměťových bloků
 Velikost kyblíku
 B(R) / (M-1)
 Musí být menší než M (kvůli spojení)
  B(R) / (M-1) < M-2
  𝑀 − 2 > 𝐵 𝑅
PA152, Vlastislav Dohnal, FI MUNI, 2016 43
Algoritmy pro spojení – HashJoin
 Optimalizace
ponech některé kyblíky v paměti
Hybrid HashJoin
 Optimum počtu kyblíků pro R
 𝐵 𝑅  33
Tj. 31 bloků má každý kyblík
M=102
  ponechej 2 kyblíky v paměti (62 bloků)
  zbývá 40 bloků paměti
PA152, Vlastislav Dohnal, FI MUNI, 2016 44
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 (M=102):
G0 31 bloků
G1 31 bloků
Ostatní kyblíky 33-2 bloků
Čtení R 1 blok _
Celkem 94 bloků
8 bloků je volných!
...
PA152, Vlastislav Dohnal, FI MUNI, 2016 45
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, 2016 46
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, 2016 47
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íky jsou již zpracovány
Celkem: 4414 čtení/zápisů
PA152, Vlastislav Dohnal, FI MUNI, 2016 48
Algoritmy pro spojení
 Hybrid HashJoin
Kolik kyblíků ponechat v paměti?
 Empiricky: 1 kyblík
 Hašování ukazatelů
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, 2016 49
Alg. pro spojení – Hašování ukazatelů
 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, 2016 50
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, 2016 51
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í (B(S)=500, T(S)=5000)
 Prohledání indexu: zdarma
 Pokud shoda, načti záznam R  1 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2016 52
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, 2016 53
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.505 čtení
PA152, Vlastislav Dohnal, FI MUNI, 2016 54
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, 2016 55
Algoritmy pro spojení – shrnutí
R  S
B(R) = 1000
B(S) = 500
Algorithm Costs
Cached Block-based Nested-loop Join 5500
Merge Join (w/o sorting) 1500
Merge Join (with sorting) 7500
Sort Join 4500
Index Join (R.Y index) 8000  550
Hash Join 4500
Hybrid 4414
Pointers 1600
PA152, Vlastislav Dohnal, FI MUNI, 2016 56
Algoritmy pro spojení – shrnutí
R  S Assume B(S) < B(R), Y are common attributes
Algorithm Costs Limits
Block-based Nested-loop Join B(S)  (1+B(R)) M=3
Cached version B(S)/(M-2)  (M-2 + B(R)) M3
Merge Join (w/o sorting) B(R) + B(S) M=3
Merge Join (with sorting) 5  (B(R) + B(S)) 𝑀 = 𝐵 𝑅
Sort Join 3  (B(R) + B(S)) 𝑀 = 𝐵 𝑅 + 𝐵 𝑆 + 1
Index Join (R.Y index) (max costs) B(S) + T(S)  (HT + )
e.g.  = T(R)/V(R,Y)
min. M=4
Hash Join 3  (B(R) + B(S)) 𝑀 = 2 + 𝐵 𝑆
max. M-1 buckets
Hybrid
Pointers B(S)+B(R)+T(R)  
e.g.  = T(S)/V(S,Y)
M=B(hash on S) + 3
PA152, Vlastislav Dohnal, FI MUNI, 2016 57
Algoritmy pro spojení – doporučení
 Cached Block-based Nested-loop Join
 Vhodné pro malé relace (vzhledem k paměti)
 HashJoin
 Pro spojení na rovnost (equi-join)
 Relace nejsou uspořádané a nejsou indexy
 SortJoin
 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, 2016 58
Dvouprůchodové algoritmy
 Pomocí třídění
Rušení duplicit
Agregační funkce (GROUP BY)
Množinové operace
PA152, Vlastislav Dohnal, FI MUNI, 2016 59
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 ≥ 𝐵 𝑅
PA152, Vlastislav Dohnal, FI MUNI, 2016 60
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 ≥ 𝐵 𝑅
PA152, Vlastislav Dohnal, FI MUNI, 2016 61
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í: 𝐵 𝑅 + 𝐵 𝑆 ≤ 𝑀
PA152, Vlastislav Dohnal, FI MUNI, 2016 62
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, 2016 63
Množinový průnik a rozdíl
 Ad výpis
RS: vypiš t,
 pokud #R > 0  #S > 0
RBS: vypiš t min(#R,#S)-krát
R-S: vypiš t,
 pokud #R > 0  #S = 0
R-BS: vypiš t max(#R - #S,0)-krát
 Vlastnosti
Náklady: 3(B(R) + B(S))
Omezení: 𝐵 𝑅 + 𝐵 𝑆 ≤ 𝑀
PA152, Vlastislav Dohnal, FI MUNI, 2016 64
Dvouprůchodové algoritmy
 Pomocí hašování
Rušení duplicit
Agregační funkce (GROUP BY)
Množinové operace
PA152, Vlastislav Dohnal, FI MUNI, 2016 65
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 a zruš duplicity, dále zbytek na
výstup
 velikost kyblíku je pak max. M-1
 Vlastnosti
Náklady: 3B(R)
Omezení: B(R) ≤ (M-1)2
PA152, Vlastislav Dohnal, FI MUNI, 2016 66
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 (velikost kyblíku max. M-1)
 Vytvoř skupiny a spočítej agregační funkce
 Vypiš výsledky na výstup
 Vlastnosti
Náklady: 3B(R)
Omezení: B(R) ≤ (M-1)2
PA152, Vlastislav Dohnal, FI MUNI, 2016 67
Množinové sjednocení, průnik, rozdíl
 Postup
Proveď hašování pro R a S (stejnou haš. funkcí!)
 Vždy M-1 kyblíků
Zpracuj vždy dvojici kyblíků Ri a Si
 Jeden z kyblíků načti do paměti
 velikost kyblíku max. M-2
 Druhý zpracuj postupně
 Vlastnosti
Náklady: 3(B(R) + B(S))
Omezení: min(B(R), B(S)) ≤ (M-2)2
Summary
 Operations
 distinct, group by, set operations, joins
 Algorithm type
 one-pass, two-pass
 Implementation
 Sorting
 Hashing
 Exploiting indexes
 Costs
 blocks to read/write
 memory footprint
PA152, Vlastislav Dohnal, FI MUNI, 2016 68