PA152: Efektivní využívání DB 8. Optimalizace dotazu Vlastislav Dohnal PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 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 operace ◼ Příklad nastavení PostgreSQL http://www.postgresql.org/docs/9.6/static/runtime-config-query.html#GUC-CPU-OPERATOR-COST https://www.postgresql.org/docs/9.6/static/runtime-config-resource.html  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)  shared_buffers (32MB) – ¼ RAM  effective_cache_size (4GB) – ½ RAM  work_mem (8MB) ◼ Memory available to an operation PA152, Vlastislav Dohnal, FI MUNI, 2019 5 PA152, Vlastislav Dohnal, FI MUNI, 2019 6 Odhad ceny operace ◼ 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 (work_mem) HT(i) – počet úrovní indexu i LB(i) – celkový počet listových bloků indexu PA152, Vlastislav Dohnal, FI MUNI, 2019 7 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, 2019 8 Operace čtení relace: table scan ◼ Relace není prokládaná Čtení je B(R) TwoPhase-MergeSort = 3B(R) čtení a zápisů ◼ Finální zápis ignorujeme ◼ Relace je prokládaná Č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, 2019 9 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í) + (až 𝑚 𝐻𝑇+1 − 1)  Where m is an index arity (LB = 𝑚 𝐻𝑇 )  Min. náklady: ◼ 0 čtení bloků relace + 1..HT bloků indexu ◼ Výhoda  Lze omezit pouze na interval záznamů  „Covering“ index nevyžaduje čtení záznamů Maximální počet uzlů m-árního stromu PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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-2 bloků Testování sekvenčně je pomalé (n2 porovnání) Použití hašování ◼ Omezení: B(R) < M-1 ◼ Lze realizovat pomocí iterátorů? Distinct – example ◼ Relation company(company_key,company_name) PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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í Output blok není nutný PA152, Vlastislav Dohnal, FI MUNI, 2019 14 Množinové operace ◼ Požadavek min(B(R), B(S)) < M-1 Menší relace se načte celá Větší se čte postupně Množinové sjednocení (i množinový rozdíl) ◼ Paměť může být větší: B(R)+B(S) < M-1 ◼ 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, 2019 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-1 PA152, Vlastislav Dohnal, FI MUNI, 2019 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-1 PA152, Vlastislav Dohnal, FI MUNI, 2019 17 Množinový rozdíl ◼ 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  B(S) + B(R) < M-1 (nejhorší případ; pipelining) ◼ Nebo předzpracuji R, pak max(B(R),B(S)) < M-1, ale ne pipel. ◼ 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 interní struktury  Nakonec vypiš zbylý obsah S (tj. pipelining není)  B(S) < M PA152, Vlastislav Dohnal, FI MUNI, 2019 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 min(B(R), B(S)) < M-1 PA152, Vlastislav Dohnal, FI MUNI, 2019 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 ty 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, 2019 20 Operace spojení - jednoprůchodově ◼ 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) ◼ Vnější spojení ? PA152, Vlastislav Dohnal, FI MUNI, 2019 21 Jednoprůchodové algoritmy ◼ Shrnutí Unární operace: op(R) ◼ B(R) ≤ M-1, 1 blok pro výstup; někdy i 1 pro vstup 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 nebo max(B(R),B(S))3) ◼ Způsob uložení relace Důležité pro výslednou cenu ◼ Prokládané → každý záznam jedno čtení ◼ Neprokládané → každý záznam B(R)/T(R) čtení ◼ Využitelné pro libovolnou podmínku spojení tzv. theta-joins PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 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, 2019 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 V/V operací 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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  [0,M-2] ◼ Načti kyblík i pro S ◼ Načítej kyblík i pro R a proveď vyhledání odpovídajících si záznamů a jejich spojení PA152, Vlastislav Dohnal, FI MUNI, 2019 40 Algoritmy pro spojení – HashJoin ◼ Spojování kyblíků Kyblík S načti celý (≤ M-2) ◼ Pro zrychlení si vytvoř paměťové hašování Kyblík R čti po blocích KyblíkyR ... Si paměť ... KyblíkyS PA152, Vlastislav Dohnal, FI MUNI, 2019 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 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, 2019 42 Algoritmy pro spojení – HashJoin ◼ Minimální paměťové nároky Hašování S, optimální naplnění kyblíků ◼ Celkem máme M paměťových bloků ◼ Velikost kyblíku = B(S) / (M-1)  Musí být menší než M (kvůli spojení)  → Τ𝐵(𝑆) 𝑀 − 1 ≤ 𝑀 − 2 ◼ ≈ 𝑀 − 1 > 𝐵 𝑆 PA152, Vlastislav Dohnal, FI MUNI, 2019 43 Algoritmy pro spojení – HashJoin ◼ Optimalizace ponech některé kyblíky v paměti Hybrid HashJoin ◼ Optimum počtu kyblíků pro R B(S)=500  𝐵 𝑆  23 Tj. 22 bloků má každý kyblík M=102 ◼ → ponechej 3 kyblíky v paměti (66 bloků) ◼ → zbývá 36 bloků paměti PA152, Vlastislav Dohnal, FI MUNI, 2019 44 Alg. pro spojení – Hybrid HashJoin ◼ Paměť pro vytvoření hašovaného indexu S paměť G0 G2 in ... 22 bloků 23-3=20 kyblíků S Využití paměti (M=102): G0-2 3*22 bloků Ostatní kyblíky 20 bloků Čtení S 1 blok Výstup 1 blok Celkem 88 bloků 14 bloků je volných! ...... PA152, Vlastislav Dohnal, FI MUNI, 2019 45 Alg. pro spojení – Hybrid HashJoin ◼ Paměť pro vytvoření hašovaného indexu R 1000/23 = 44 bloků na kyblík Záznamy hašované do kyblíků 0-2 ◼ Vyřešit hned (S0-2 jsou v paměti) → výstup paměť G0 G2 in ... 44 bloků 23-3=20 kyblíků R ... ... PA152, Vlastislav Dohnal, FI MUNI, 2019 46 Alg. pro spojení – Hybrid HashJoin ◼ Spojení kyblíků Pouze pro kyblíky s id 3-22 Načti jeden kyblík celý do paměti, druhý procházej po blocích paměť Hi výstupní ...22 23-3=20 výsledek ... 44 23-3=20 Kyblíky S Kyblíky R jeden kyblík S jeden blok kyblíku R PA152, Vlastislav Dohnal, FI MUNI, 2019 47 Alg. pro spojení – Hybrid HashJoin ◼ Náklady: Hašování S: 500 + 2022 = 940 čtení/zápisů Hašování R: 1000 + 2044 = 1880 čtení/zápisů ◼ Pouze 20 kyblíků k zápisu! Spojení: 2044 + 2022 = 1320 čtení ◼ 3 kyblíky jsou již zpracovány Celkem: 4140 čtení/zápisů PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 53 Algoritmy pro spojení – IndexJoin ◼ Situace 2 Index se nevejde do paměti Index na Y pro R má 201 bloků ◼ V paměti M=102 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, 2019 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, 2019 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 4140 Pointers 1600 PA152, Vlastislav Dohnal, FI MUNI, 2019 Join Algorithms – Summary R  S Assume B(S) < B(R), Y are common attributes Algorithm Costs Limits Block-based Nested-loop 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 3 𝐵 𝑅 + 𝐵(𝑆) − 2 𝐵 𝑅 + 𝐵(𝑆) 𝐵 𝑅 𝑀 = 𝐵(𝑅) 𝐵 𝑅 + 𝐵 𝑅 + 1 Pointers B(S)+B(R)+T(R)   e.g.  = T(S)/V(S,Y) M=B(hash index on S)+3 56 PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 58 Dvouprůchodové algoritmy ◼ Pomocí třídění Rušení duplicit Agregační funkce (GROUP BY) Množinové operace PA152, Vlastislav Dohnal, FI MUNI, 2019 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) ≤ M*(M-1) ◼ Optimální M ≥ 𝐵 𝑅 + 1 PA152, Vlastislav Dohnal, FI MUNI, 2019 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) ≤ M*(M-1) ◼ Optimální M ≥ 𝐵 𝑅 + 1 PA152, Vlastislav Dohnal, FI MUNI, 2019 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í: 𝐵 𝑅 + 𝐵 𝑆 ≤ 𝑀 ◼ Potřebuji jeden blok pro všechny dávky R i S PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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í: 𝐵 𝑅 + 𝐵 𝑆 ≤ 𝑀 ◼ Potřebuji jeden blok pro všechny dávky R i S PA152, Vlastislav Dohnal, FI MUNI, 2019 64 Dvouprůchodové algoritmy ◼ Pomocí hašování Rušení duplicit Agregační funkce (GROUP BY) Množinové operace PA152, Vlastislav Dohnal, FI MUNI, 2019 65 Rušení duplicit ◼ Postup zpracování Proveď hašování R do M-1 kyblíků ◼ → kyblíky ukládej 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 max. M-1 ◼ Vlastnosti Náklady: 3B(R) Omezení: B(R) ≤ (M-1)2 PA152, Vlastislav Dohnal, FI MUNI, 2019 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čítej po blocích postupně a ◼ Vytvářej skupiny a počítej agregační funkce  Max. velikost kyblíku neomezená, ale skupiny se musí vejít do max. M-1. ◼ Vypiš výsledky na výstup ◼ Vlastnosti Náklady: 3B(R) Omezení: B(R) ≤ (M-1)2 lze téměř zrušitlze téměř zrušit PA152, Vlastislav Dohnal, FI MUNI, 2019 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 (záleží na operaci)  velikost kyblíku max. M-2 ◼ Druhý zpracuj postupně ◼ Vlastnosti Náklady: 3(B(R) + B(S)) Omezení M záleží na operaci Množinový průnik, rozdíl ◼ Průnik (menší relace je S) Do paměti načítej kyblíky S Omezení: min(B(R), B(S)) ≤ (M-2)*(M-1) ◼ Rozdíl R-S: Kvůli eliminaci duplicit v R, měj v paměti kyblík R Omezení: B(R) ≤ (M-2)*(M-1) ◼ Rozdíl S-R: Měj v paměti kyblík S Omezení: B(S) ≤ (M-2)*(M-1) PA152, Vlastislav Dohnal, FI MUNI, 2019 68 Množinové sjednocení ◼ Musíme eliminovat duplicity v R i S for each i in hash addresses: ◼ read BktS i , build in-mem hash table & eliminate dups  also gradually output the records ◼ read BktR i gradually:  for each r in BktR i : ▪ if r not in in-mem hash table ▪ output r and add to in-mem hash table ◼ Omezení: 𝐵 𝑅 + 𝐵 𝑆 < 𝑀 musíme načíst oba kyblíky do M PA152, Vlastislav Dohnal, FI MUNI, 2019 69 Summary ◼ Operations  distinct, group by, set operations, joins ◼ Algorithm type  one-pass, one-and-a-half pass, two-pass ◼ Implementation  Sorting  Hashing  Exploiting indexes ◼ Costs  blocks to read/write  memory footprint PA152, Vlastislav Dohnal, FI MUNI, 2019 70