PA152: Efektivní využívání DB 6. Zpracování dotazů 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 Vyhodnocení dotazu Dotaz Strom dotazu Logický plán Úpravy Fyzický plán Vyhodnocení PA152, Vlastislav Dohnal, FI MUNI, 2009 4 Příklad Select B,D From R,S Where R.C=S.C and R.A="c" and S.E=2 PA152, Vlastislav Dohnal, FI MUNI, 2009 5 Příklad R A B C S C D E a 1 10 10 x 2 b 1 20 20 y 2 c 2 10 30 z 2 d 2 35 40 x 1 e 3 45 50 y 3 PA152, Vlastislav Dohnal, FI MUNI, 2009 6 Příklad R A B C S C D E a 1 10 10 x 2 b 1 20 20 y 2 c 2 10 30 z 2 d 2 35 40 x 1 e 3 45 50 y 3 Odpověď B D 2 x PA152, Vlastislav Dohnal, FI MUNI, 2009 7 Jak vyhodnotit tento dotaz? Kartézský součin Výběr záznamů Projekce 1. způsob PA152, Vlastislav Dohnal, FI MUNI, 2009 8 RXS R.A R.B R.C S.C S.D S.E a 1 10 10 x 2 a 1 10 20 y 2 . . C 2 10 10 x 2 . . PA152, Vlastislav Dohnal, FI MUNI, 2009 9 RXS R.A R.B R.C S.C S.D S.E a 1 10 10 x 2 a 1 10 20 y 2 . . C 2 10 10 x 2 . . Tento záznam vyhovuje PA152, Vlastislav Dohnal, FI MUNI, 2009 10 Popis plánů provedení dotazu Použití relační algebry Příklad plánu I: B,D R.A="c" S.E=2 R.C=S.C × R S Alternativně: B,D [ R.A="c" S.E=2 R.C = S.C (R×S)] PA152, Vlastislav Dohnal, FI MUNI, 2009 11 Popis plánů provedení dotazu Příklad plánu II: B,D R.A = "c" S.E = 2 R S natural join PA152, Vlastislav Dohnal, FI MUNI, 2009 12 Fyzický plán Příklad plánu II: R S A B C (R) (S) C D E a 1 10 A B C C D E 10 x 2 b 1 20 c 2 10 10 x 2 20 y 2 c 2 10 20 y 2 30 z 2 d 2 35 30 z 2 40 x 1 e 3 45 50 y 3 PA152, Vlastislav Dohnal, FI MUNI, 2009 13 Popis plánů provedení dotazu Plán III: Použití indexů pro R.A a S.C Použijeme index R.A k nalezení záznamů R splňující R.A = "c" Pro každou nalezenou hodnotu R.C použijeme index S.C pro nalezení odpovídajících záznamů Vypustíme záznamy S, kde S.E 2 Spojíme odpovídající záznamy R,S Provedeme projekci na atributy B,D PA152, Vlastislav Dohnal, FI MUNI, 2009 14 R S A B C C D E a 1 10 10 x 2 b 1 20 20 y 2 c 2 10 30 z 2 d 2 35 40 x 1 e 3 45 50 y 3 A C I1 I2 PA152, Vlastislav Dohnal, FI MUNI, 2009 15 R S A B C C D E a 1 10 10 x 2 b 1 20 20 y 2 c 2 10 30 z 2 d 2 35 40 x 1 e 3 45 50 y 3 A C I1 I2 ="c" PA152, Vlastislav Dohnal, FI MUNI, 2009 16 R S A B C C D E a 1 10 10 x 2 b 1 20 20 y 2 c 2 10 30 z 2 d 2 35 40 x 1 e 3 45 50 y 3 A C I1 I2 ="c" <10,x,2> PA152, Vlastislav Dohnal, FI MUNI, 2009 17 R S A B C C D E a 1 10 10 x 2 b 1 20 20 y 2 c 2 10 30 z 2 d 2 35 40 x 1 e 3 45 50 y 3 A C I1 I2 ="c" <10,x,2> kontrola=2? výstup: <2,x> PA152, Vlastislav Dohnal, FI MUNI, 2009 18 další záznam: R S A B C C D E a 1 10 10 x 2 b 1 20 20 y 2 c 2 10 30 z 2 d 2 35 40 x 1 e 3 45 50 y 3 A C I1 I2 ="c" <10,x,2> kontrola=2? výstup: <2,x> PA152, Vlastislav Dohnal, FI MUNI, 2009 19 Přehled optimalizace dotazů parser konverze pravidla odhad velikostí porovnání fyz. plánů odhad nákladů zvol nejlepší vykonání {P1,P2,.....} {(P1,C1),(P2,C2)...} Pi výsledek SQL dotaz strom dotazu logický plán dotazu ,,vylepšený" l.p.d l.p.d. s velikostmi statistiky PA152, Vlastislav Dohnal, FI MUNI, 2009 20 Příklad: SQL dotaz SELECT title FROM StarsIn WHERE starName IN ( SELECT name FROM MovieStar WHERE birthdate LIKE `%1960' ); (Find the movies with stars born in 1960) PA152, Vlastislav Dohnal, FI MUNI, 2009 21 Příklad: strom dotazu SELECT FROM WHERE IN title StarsIn ( ) starName SELECT FROM WHERE LIKE name MovieStar birthDate `%1960' PA152, Vlastislav Dohnal, FI MUNI, 2009 22 Příklad: převod do relační algebry Selekce má dva argumenty Třeba převést... Operátor IN Tj. odstranění vnořených dotazů title StarsIn IN name birthdate LIKE `%1960' starName MovieStar PA152, Vlastislav Dohnal, FI MUNI, 2009 23 Příklad: logický plán dotazu Operátor IN nahrazen součinem title starName=name StarsIn name birthdate LIKE `%1960' MovieStar × PA152, Vlastislav Dohnal, FI MUNI, 2009 24 Příklad: Vylepšení logického plánu Nahrazení součinu a selekce Provedení spojení Další možnost Posunou projekci k relaci StarsIn? title starName=name StarsIn name birthdate LIKE `%1960' MovieStar PA152, Vlastislav Dohnal, FI MUNI, 2009 25 Příklad: odhad velikostí výsledků Odhadnout velikost StarsIn MovieStar Před generováním fyzických plánů Ovlivňují odhad ceny provedení PA152, Vlastislav Dohnal, FI MUNI, 2009 26 Příklad: jeden fyzický plán Parametry: pořadí spojení, velikost paměti, projekce,... Hash join SEQ scan index scan Parametry: volba podmínky, ... StarsIn MovieStar PA152, Vlastislav Dohnal, FI MUNI, 2009 27 Příklad: ohodnocení plánů cenou L.P.D. P1 P2 .... Pn C1 C2 .... Cn Vyber plán s nejnižší cenou! PA152, Vlastislav Dohnal, FI MUNI, 2009 28 Optimalizace dotazu Úroveň relační algebry Úroveň podrobného plánu dotazu Odhad ceny Bez indexů S indexy Vytvoření a porovnání plánů PA152, Vlastislav Dohnal, FI MUNI, 2009 29 Optimalizace relační algebry Transformační pravidla Musí zajistit ekvivalenci výsledků Jaké transformace jsou vhodné? PA152, Vlastislav Dohnal, FI MUNI, 2009 30 Transformační pravidla Přirozené spojení Protože jsou všechny atributy zachovány, není pořadí důležité Příklad: R S = S R (R S) T = R (S T) R S S T RT PA152, Vlastislav Dohnal, FI MUNI, 2009 31 Transformační pravidla Stejné pro kartézský součin a sjednocení R × S = S × R (R × S) × T = R × (S × T) R S = S R R (S T) = (R S) T PA152, Vlastislav Dohnal, FI MUNI, 2009 32 Transformační pravidla Selekce p1p2(R) = p1vp2(R) = p1 [ p2 (R)] [ p1 (R)] [ p2 (R)] PA152, Vlastislav Dohnal, FI MUNI, 2009 33 Problém duplicit Množiny nebo multimnožiny? Relace jsou multimnožiny Příklad R = {a,a,b,b,b,c} S = {b,b,c,c,d} R S = ? Možnost 1: SUM R S = {a,a,b,b,b,b,b,c,c,c,d} Možnost 2: MAX R S = {a,a,b,b,b,c,c,d} PA152, Vlastislav Dohnal, FI MUNI, 2009 34 Možnost 1: SUM Sjednocení relací R S PA152, Vlastislav Dohnal, FI MUNI, 2009 35 Možnost 2: MAX Rozklad selekce: Příklad: R={a,a,b,b,b,c} P1 splňují a,b; P2 splňují b,c p1p2 (R) = p1(R) p2(R) p1p2 (R) = {a,a,b,b,b,c} p1(R) = {a,a,b,b,b} p2(R) = {b,b,b,c} p1(R) p2 (R) = {a,a,b,b,b,c} PA152, Vlastislav Dohnal, FI MUNI, 2009 36 Volba správné možnosti Pragmatické rozhodnutí Použití "SUM" pro sjednocení multimnožin Některá pravidla nemůžeme pro multimnožiny použít PA152, Vlastislav Dohnal, FI MUNI, 2009 37 Transformační pravidla Značení: X = množina atributů Y = množina atributů XY = X Y Projekce xy (R) = x [y (R)] PA152, Vlastislav Dohnal, FI MUNI, 2009 38 Transformační pravidla Kombinace selekce a přirozeného spojení Nechť p = výraz obsahující pouze atributy R q = výraz obsahující pouze atributy S m = výraz obsahující atributy R a S [p (R)] S R [q (S)] p (R S) = q (R S) = PA152, Vlastislav Dohnal, FI MUNI, 2009 39 Transformační pravidla Kombinace selekce a přirozeného spojení Další pravidla lze odvodit pq (R S) = [p (R)] [q (S)] pqm (R S) = m [(p (R)) (q (S))] pq (R S) = [(p (R)) S] [R (q (S))] PA152, Vlastislav Dohnal, FI MUNI, 2009 40 Příklad odvození pravidla pq (R S) = p [q (R S) ] = p [ R q (S) ] = [p (R)] [q (S)] PA152, Vlastislav Dohnal, FI MUNI, 2009 41 Transformační pravidla Kombinace projekce a selekce Nechť x = podmnožina atributů R z = atributy použité ve výrazu P (podmnožina R) {p [ x (R) ]}x[p (R) ] = PA152, Vlastislav Dohnal, FI MUNI, 2009 42 Transformační pravidla Kombinace projekce a selekce Nechť x = podmnožina atributů R z = atributy použité ve výrazu P (podmnožina R) {p [ x (R) ]}x xz x[p (R) ] = PA152, Vlastislav Dohnal, FI MUNI, 2009 43 Transformační pravidla Kombinace projekce a přirozeného spojení Nechť x = podmnožina atributů R y = podmnožina atributů S z = průnik atributů R,S xy{[xz (R) ] [yz (S) ]} xy (R S) = PA152, Vlastislav Dohnal, FI MUNI, 2009 44 Transformační pravidla xy {p (R S)} = xy {p [xz' (R) yz' (S)]} z' = z {atributy použité v P} Kombinace navíc se selekcí PA152, Vlastislav Dohnal, FI MUNI, 2009 45 Transformační pravidla Kombinace selekce a sjednocení Kombinace selekce a rozdílu Selekci je možné aplikovat i na S Může být vhodné pro zmenšení relace před provedením rozdílu Otázka: Musí P něco splňovat? p(R S) = p(R) p(S) p(R - S) = p(R) - S = p(R) - p(S) PA152, Vlastislav Dohnal, FI MUNI, 2009 46 Volba vhodné transformace p1p2 (R) p1 [p2 (R)] p (R S) [p (R)] S R S S R x [p (R)] x {p [xz (R)]} p1p2 (R) p1 [p2 (R)] p (R S) [p (R)] S R S S R x [p (R)] x {p [xz (R)]} PA152, Vlastislav Dohnal, FI MUNI, 2009 47 Volba transformace Projekce co nejdříve Příklad: R(A,B,C,D,E) výsledek={E} Filtr P: (A=3) and (B="cat") x {p (R)} vs. E {p{ABE(R)}} PA152, Vlastislav Dohnal, FI MUNI, 2009 48 Volba transformace (2) Máme indexy Pro A i pro B B = `cat' A = 3 Průnik seznamu ukazatelů dává výsledek přímo PA152, Vlastislav Dohnal, FI MUNI, 2009 49 Volba transformace (3) Obecná pravidla: Bez transformací neuděláme chybu Většinou výhodné Selekce nejblíže relacím Eliminace společných podvýrazů Eliminace duplicit PA152, Vlastislav Dohnal, FI MUNI, 2009 50 Zpracování dotazu: přehled Úroveň relační algebry Transformační pravidla Volba vhodných pravidel Úroveň podrobného plánu dotazu Odhad ceny Vytvoření a porovnání plánů PA152, Vlastislav Dohnal, FI MUNI, 2009 51 Odhad ceny plánu dotazu 1. Odhad velikosti výsledku operace 2. Odhad počtu V/V operací PA152, Vlastislav Dohnal, FI MUNI, 2009 52 Odhad velikosti výsledku operace Statistiky pro relaci R T(R) ­ počet záznamů S(R) ­ velikost záznamu v bajtech B(R) ­ počet obsazených bloků V(R, A) ­ počet unikátních hodnot atributu A Pro správné odhady Statistiky musí být aktuální PA152, Vlastislav Dohnal, FI MUNI, 2009 53 Příklad statistik Relace R Atribut A ­ řetězec, 20 bajtů Atribut B ­ celé číslo, 4 bajty Atribut C ­ datum, 8 bajtů Atribut D ­ řetězec, 5 bajtů Statistiky T(R) = 5 S(R) = 37 V(R,A) = 3 V(R,B) = 1 V(R,C) = 5 V(R,D) = 4 A B C D cat 1 10.2.98 a cat 1 20.3.98 b dog 1 30.4.98 a dog 1 14.6.98 c bat 1 15.6.98 d PA152, Vlastislav Dohnal, FI MUNI, 2009 54 Odhad velikosti Kartézský součin W = R1 × R2 T(W) = T(R1) T(R2) S(W) = S(R1) + S(R2) PA152, Vlastislav Dohnal, FI MUNI, 2009 55 Odhad velikosti Selekce W = Z=val(R) S(W) = S(R) T(W) = ? W = A=`cat'(R) A B C D cat 1 10.2.98 a cat 1 20.3.98 b dog 1 30.4.98 a dog 1 14.6.98 c bat 1 15.6.98 d V(R,A)=3 V(R,B)=1 V(R,C)=5 V(R,D)=4 T(W) = T(R) V(R,A) = 5/3 PA152, Vlastislav Dohnal, FI MUNI, 2009 56 Odhad velikosti Předpoklad předchozího odhadu Rovnoměrné rozložení hodnot mezi hodnotami v R! Tj. f(val) = T(R) / V(R,Z) Alternativní předpoklad Rovnoměrné rozložení hodnot v celé doméně Počet hodnot v doméně označujeme DOM(R,Z) PA152, Vlastislav Dohnal, FI MUNI, 2009 57 Odhad velikosti: příklad Selekce W = Z=val(R) T(W) = ? Odvození W = C=val(R) T(W) = (1/10)1 + (1/10)1 + ... = 5/10 = 0,5 W = B=val(R) T(W) = (1/10)5 W = A=val(R) T(W) = 0,5 A B C D cat 1 10.2.98 a cat 1 20.3.98 b dog 1 30.4.98 a dog 1 14.6.98 c bat 1 15.6.98 d V(R,A)=3 DOM(R,A)=10 V(R,B)=1 DOM(R,B)=10 V(R,C)=5 DOM(R,C)=10 V(R,D)=4 DOM(R,D)=10 PA152, Vlastislav Dohnal, FI MUNI, 2009 58 Odhad velikosti Selekce W = Z=val(R) Původní návrh Alternativní návrh A B C D cat 1 10.2.98 a cat 1 20.3.98 b dog 1 30.4.98 a dog 1 14.6.98 c bat 1 15.6.98 d T(W) = T(R) V(R,Z) V(R,A)=3 DOM(R,A)=10 V(R,B)=1 DOM(R,B)=10 V(R,C)=5 DOM(R,C)=10 V(R,D)=4 DOM(R,D)=10 T(W) = T(R) DOM(R,Z) PA152, Vlastislav Dohnal, FI MUNI, 2009 59 Odhad velikosti Selekce W = Zval(R) Návrh 1 T(W) = T(R) / 2 Návrh 2 T(W) = T(R) / 3 Návrh 3 Podle velikosti rozsahu PA152, Vlastislav Dohnal, FI MUNI, 2009 60 Odhad velikosti Selekce ­ podle velikosti rozsahu Vypočítej podíl hodnot (unikátních) T(W) = f T(R) Min=1 V(R,Z)=10 W= z 15 (R) Max=20 ZR f = 20-15+1 20-1+1 6 20 = PA152, Vlastislav Dohnal, FI MUNI, 2009 61 Odhad velikosti Přirozené spojení W = R1 R2 Značení X ­ atributy R1 Y ­ atributy R2 Případ 1 X Y = Stejné jako R1 × R2 Případ 2 X Y = A Viz dále... PA152, Vlastislav Dohnal, FI MUNI, 2009 62 Odhad velikosti: přirozené spojení Předpoklad V(R1,A) V(R2,A) každá hodnota A z R1 je i v R2 V(R2,A) V(R1,A) každá hodnota A z R2 je i v R1 R1 A B C R2 A DR1 R2 PA152, Vlastislav Dohnal, FI MUNI, 2009 63 Odhad velikosti: přirozené spojení V(R1,A) V(R2,A) 1 záznam se spojí s T(R2) / V(R2,A) záznamy Výsledek: R1 A B C R2 A D Vezmi 1 záznam Vyhledej a spoj T(W) = T(R2) V(R2,A) T(R1) PA152, Vlastislav Dohnal, FI MUNI, 2009 64 Odhad velikosti: přirozené spojení Shrnutí obou variant V(R1,A) V(R2,A) V(R2,A) V(R1,A) Rozdíl je pouze v děliteli T(W) = T(R1) V(R1,A) T(R2) T(W) = T(R2) V(R2,A) T(R1) PA152, Vlastislav Dohnal, FI MUNI, 2009 65 Odhad velikosti: přirozené spojení Obecný závěr W = R1 R2 T(W) = T(R1) T(R2) max { V(R1,A), V(R2,A) } PA152, Vlastislav Dohnal, FI MUNI, 2009 66 Odhad velikosti: přirozené spojení Alternativní definice Rovnoměrné rozložení v doméně 1 zázn. se spojí s T(R2)/DOM(R2,A) záznamy Výsledek: R1 A B C R2 A D Vezmi 1 záznam Vyhledej a spoj T(W) = T(R1) T(R2) DOM(R2,A) = T(R1) T(R2) DOM(R1,A) předpokládáme stejné PA152, Vlastislav Dohnal, FI MUNI, 2009 67 Odhad velikosti: přirozené spojení W = Velikost záznamu S(W) = S(R1) + S(R2) ­ S(A) Platí pro všechny varianty R1 R2 PA152, Vlastislav Dohnal, FI MUNI, 2009 68 Odhad velikosti: ostatní operace Projekce AB(R), T(W)=T(R), S(W)=S(AB) Selekce A=aB=b(R), S(W)=S(R), nechť n=T(R) T(W) = n(1 ­ (1-m1/n)(1-m2/n)) m1=T(R) / V(R,A) m2=T(R) / V(R,B) Sjednocení, průnik, rozdíl , , T(W) ­ počítá se průměrná velikost PA152, Vlastislav Dohnal, FI MUNI, 2009 69 Odhad velikosti Pro složitější výrazy jsou třeba ostatní statistiky Příklad W = [A=a(R1)] R2 označme jako U T(U) = T(R1) / V(R1,A) S(U) = S(R1) Pro výsledek potřebujeme i V(U,*) ! PA152, Vlastislav Dohnal, FI MUNI, 2009 70 Odhad počtu hodnot Odhady V(U,*) U = A=a(R1) Předpokládejme, že R1(A,B,C,D) PA152, Vlastislav Dohnal, FI MUNI, 2009 71 Odhad počtu hodnot: příklad Relace R1 U = A=a(R1) Výsledek V(U,A) = 1 V(U,B) = 1 V(U,C) = 1 .. (T(R1) / V(R1,A)) V(U,D) = 1 .. (T(R1) / V(R1,A)) A B C D cat 1 10.2.98 a cat 1 20.3.98 b dog 1 30.4.98 a dog 1 14.6.98 c bat 1 15.6.98 d V(R,A)=3 V(R,B)=1 V(R,C)=5 V(R,D)=4 PA152, Vlastislav Dohnal, FI MUNI, 2009 72 Odhad počtu hodnot: praxe Obvyklé řešení U = A=a(R1) V(U,A) = 1 V(U,*) = V(R,*) PA152, Vlastislav Dohnal, FI MUNI, 2009 73 Odhad počtu hodnot: spojení U = R1(A,B) R2(A,C) Výsledek: V(U,A) = min{ V(R1, A), V(R2, A) } V(U,B) = V(R1, B) V(U,C) = V(R2, C) PA152, Vlastislav Dohnal, FI MUNI, 2009 74 Odhad počtu hodnot: spojení Příklad Z = R1(A,B) R2(B,C) R3(C,D) T(R1) = 1000 V(R1,A)=50 V(R1,B)=100 T(R2) = 2000 V(R2,B)=200 V(R2,C)=300 T(R3) = 3000 V(R3,C)=90 V(R3,D)=500 PA152, Vlastislav Dohnal, FI MUNI, 2009 75 Odhad počtu hodnot: spojení Mezivýsledek U = R1(A,B) R2(B,C) Výsledek: T(U) = T(R1) T(R2) / max{ V(R1,B), V(R2,B) } = = 1000 2000 / 200 V(U,A) = 50 V(U,B) = 100 V(U,C) = 300 PA152, Vlastislav Dohnal, FI MUNI, 2009 76 Odhad počtu hodnot: spojení Celkový výsledek Z = U R3(C,D) Výsledek: T(Z) = 10 000 3 000 / 300 V(Z,A) = 50 V(Z,B) = 100 V(Z,C) = 90 V(Z,D) = 500 PA152, Vlastislav Dohnal, FI MUNI, 2009 77 Odhad počtu hodnot: histogram Histogram hodnot atributu Zpřesnění odhadů Počet různých hodnot Málo pro každou počet Hodně segmentace Stejné intervaly Percentily Pouze pro nejfrekventovanější, ostatní dohromady 10 20 30 40 10 20 30 40 PA152, Vlastislav Dohnal, FI MUNI, 2009 78 Shrnutí Odhad velikosti výsledků je ,,umění" Nezapomeňte: Pro korektní odhad potřebujeme korektní statistiky nutnost udržovat tabulky při modifikacích Jaké jsou náklady takové údržby? PA152, Vlastislav Dohnal, FI MUNI, 2009 79 Aktualizace statistik Statistiky se příliš nemění v krátkém časovém úseku I nepřesné statistiky mohou být užitečné Okamžitá aktualizace statistik Může být úzkým místem ­ statistiky jsou velmi často používány Neaktualizuj příliš často PA152, Vlastislav Dohnal, FI MUNI, 2009 80 Aktualizace statistik Prováděno periodicky Po uplynutí určitého času Po určitém počtu změn Pomalé pro V(R,A) Zejména pokud se počítají histogramy Počítáno na vzorku dat Pokud je většina hodnot různých V(R,A)T(R) Pokud je málo různých hodnot pravděpodobně jsme většinu ze všech viděli PA152, Vlastislav Dohnal, FI MUNI, 2009 81 Odhad ceny plánu dotazu: přehled Odhad velikosti výsledku operace Již probráno Odhad počtu V/V operací Další přednáška Vytvoření a porovnání plánů