PA152: Efektivní využívání DB 8. Optimalizace dotazu Vlastislav Dohnal PA152, Vlastislav Dohnal, FI MUNI, 2013 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, 2013 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, 2013 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í  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, 2013 5 PA152, Vlastislav Dohnal, FI MUNI, 2013 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, 2013 7 Operace čtení relace: table scan  Relace je shlukovaná (clustered) Čtení je B(R) TwoPhase-SortMerge = 3B(R) čtení a zápisů  Finální zápis ignorujeme  Relace není shlukovaná (non-clustered) Čtení je až T(R) bloků! TwoPhase-SortMerge  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, 2013 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:  (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í PA152, Vlastislav Dohnal, FI MUNI, 2013 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, 2013 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, 2013 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ů? PA152, Vlastislav Dohnal, FI MUNI, 2013 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  Organizace skupin – např. hašování  Agregační funkce  MIN, MAX, COUNT, SUM – pouze jedno „číslo“  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, 2013 13 Množinové operace  Požadavek min(B(R), B(S)) < M-1 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, 2013 14 Množinové operace  Množinové sjednocení a 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  Sjednocení:  Je, pak nic.  Není, pak přidej do struktury  Průnik:  Je, pak vypiš a smaž z interní struktury.  Není, pak nic. Nakonec vypiš interní strukturu  Pouze při sjednocení! PA152, Vlastislav Dohnal, FI MUNI, 2013 15 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  a přidej i 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 PA152, Vlastislav Dohnal, FI MUNI, 2013 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 zruš z interní struktury. Záznam nebyl nalezen, pak nic PA152, Vlastislav Dohnal, FI MUNI, 2013 17 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, 2013 18 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, 2013 19 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 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, 2013 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, 2013 21 Algoritmy pro spojení  Relace uloženy v blocích  Blokované vnořené cykly (M=3) 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, 2013 22 Algoritmy pro spojení  Využití vyrovnávací paměti (M bloků) 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, 2013 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, 2013 24 Dvouprůchodové algoritmy  Princip: Předzpracování vstupu  uložení Zpracování  Předzpracování: Třízení (Víceprůchodový SortMerge) Hašování  Operace: Rušení duplicit (DISTINCT) Agregační funkce (GROUP BY) Spojení relací, množinové operace PA152, Vlastislav Dohnal, FI MUNI, 2013 25 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, 2013 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 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, 2013 27 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, 2013 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, 2013 29 Algoritmy pro spojení – MergeJoin  Cena SortMerge 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í block-based nested-loop join  5500 čtení PA152, Vlastislav Dohnal, FI MUNI, 2013 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í Block-based Nested-loop Join – kvadratické  od jisté velikosti relací je MergeJoin lepší PA152, Vlastislav Dohnal, FI MUNI, 2013 31 Algoritmy pro spojení – MergeJoin  Jiný příklad B(R) = 10000 B(S) = 5000 M = 102 bloků 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ů PA152, Vlastislav Dohnal, FI MUNI, 2013 32 Algoritmy pro spojení – MergeJoin  Paměťové nároky Omezení na B(R) < M2 a B(S) < M2  Optimální paměť Používáme SortMerge 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, 2013 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 (1. fáze SortMerge) PA152, Vlastislav Dohnal, FI MUNI, 2013 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 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, 2013 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 (M=102) Uspořádání dávek: 2(1000 + 500) Spojení: 1000 + 500 Celkem: 4 500 čtení/zápisů   lepší než block-based nested-loop join PA152, Vlastislav Dohnal, FI MUNI, 2013 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, 2013 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, 2013 38 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, 2013 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-2  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, 2013 40 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   M-2 > √B(R) PA152, Vlastislav Dohnal, FI MUNI, 2013 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=102   ponechej 2 kyblíky v paměti (62 bloků)   zbývá 40 bloků paměti PA152, Vlastislav Dohnal, FI MUNI, 2013 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 (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, 2013 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, 2013 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, 2013 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íky jsou již zpracovány Celkem: 4414 čtení/zápisů PA152, Vlastislav Dohnal, FI MUNI, 2013 46 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, 2013 47 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, 2013 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, 2013 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í (B(S)=500, T(S)=5000)  Prohledání indexu: zdarma  Pokud shoda, načti záznam R  1 čtení PA152, Vlastislav Dohnal, FI MUNI, 2013 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, 2013 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.505 čtení PA152, Vlastislav Dohnal, FI MUNI, 2013 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, 2013 53 Algoritmy pro spojení – shrnutí R  S B(R) = 1000 B(S) = 500 Algorithm Costs 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) 5500  550 Hash Join 4500 Hybrid 4414 Pointers 1600 PA152, Vlastislav Dohnal, FI MUNI, 2013 55 Algoritmy pro spojení – doporučení  Block-based 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  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, 2013 56 Dvouprůchodové algoritmy  Pomocí třídění Rušení duplicit Agregační funkce (GROUP BY) Množinové operace PA152, Vlastislav Dohnal, FI MUNI, 2013 57 Rušení duplicit  Postup zpracování Proveď první fázi SortMerge   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, 2013 58 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, 2013 59 Množinové sjednocení  Pro multimnožiny není třeba dvou průchodů  Množinové sjednocení Proveď první fázi SortMerge 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, 2013 60 Množinový průnik a rozdíl  RS, R-S, RBS, R-BS  Postup Proveď první fázi SortMerge 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, 2013 61 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í: B(R) + B(S) ≤ M PA152, Vlastislav Dohnal, FI MUNI, 2013 62 Dvouprůchodové algoritmy  Hašování Rušení duplicit Agregační funkce (GROUP BY) Množinové operace PA152, Vlastislav Dohnal, FI MUNI, 2013 63 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 (velikost kyblíku max. M-1)  Zruš duplicity  zbytek na výstup  Vlastnosti Náklady: 3B(R) Omezení: B(R) ≤ (M-1)2 PA152, Vlastislav Dohnal, FI MUNI, 2013 64 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, 2013 65 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, 2013 66