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) TP-MergeSort ­ 3B čtení / zápisů Finální zápis ignorujeme Relace není shlukovaná (non-clustered) Čtení je až T(R) bloků! TP-MergeSort ­ T(R) + 2B čtení / 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 relaci 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 Množinové operace Multimnožinový průnik 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 B(S) M-1, 1 blok pro výstup Binární operátory 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 = 10000(1+5000) = 50 010 000 čtení 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 Příklad: B(R) = 1000 B(S) = 500 Náklady = 1000(1+500) = 501 000 č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 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 Upořá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í/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í 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 + 3131 = 1961 čtení/zápisů Hašování S: 500 + 3116 = 996 čtení/zápisů Pouze 31 kyblíků! Spojení: 3131 + 3116 = 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 z S Prohledej index na shodu záznamy A Pro každý záznam r z 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 + 500011 = 5500 čtení B) V(R,Y) = 5000 T(R) = 10 000 rovnoměrné rozložení 2 záznamy Výsledek: 500 + 500021 = 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) = 3000 č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 index, 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í MB(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í MB(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) M2 PA152, Vlastislav Dohnal, FI MUNI, 2009 59 Množinový průnik a rozdíl RS, R-S, RBS, 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) M2 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 Zruš duplicity zbytek na výstup 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