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