PA152: Efektivní využívání DB 6. Zpracování dotazů Vlastislav Dohnal PA152, Vlastislav Dohnal, FI MUNI, 2017 2 Vyhodnocení dotazu  Postup: Dotaz Syntaktická a sémantická kontrola  Strom dotazu Logický plán  Úpravy plánu Fyzický plán Vyhodnocení PA152, Vlastislav Dohnal, FI MUNI, 2017 3 Příklad  Relace R(A,B,C) S(C,D,E)  Dotaz select B,D from R,S where R.C=S.C and R.A=‘c’ and S.E=2 PA152, Vlastislav Dohnal, FI MUNI, 2017 4 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 select B,D from R,S where R.C=S.C and R.A=‘c’ and S.E=2 PA152, Vlastislav Dohnal, FI MUNI, 2017 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 Odpověď B D 2 x PA152, Vlastislav Dohnal, FI MUNI, 2017 6 Jak vyhodnotit tento dotaz? 1) Kartézský součin 2) Výběr záznamů 3) Projekce 1. způsob PA152, Vlastislav Dohnal, FI MUNI, 2017 7 R  S 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, 2017 8 Tento záznam vyhovuje R  S 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 . . Výstup – výsledek dotazu select B,D from R,S where R.C=S.C and R.A=‘c’ and S.E=2 PA152, Vlastislav Dohnal, FI MUNI, 2017 9 Popis plánů provedení dotazu  Použití relační algebry B,D [ sR.A=‘c’ S.E=2  R.C = S.C (RS)]  Příklad plánu 1: Strom dotazu B,D sR.A=‘c’ S.E=2  R.C=S.C  R S PA152, Vlastislav Dohnal, FI MUNI, 2017 10 Popis plánů provedení dotazu  Příklad plánu 2: B,D sR.A = ‘c’ sS.E = 2 R S natural join PA152, Vlastislav Dohnal, FI MUNI, 2017 11 Fyzický plán  Příklad pro 2: Table-scan pro selekce R S A B C s (R) s(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, 2017 12 Popis plánů provedení dotazu  Plán 3: Máme indexy 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, 2017 13 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, 2017 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 =‘c’ PA152, Vlastislav Dohnal, FI MUNI, 2017 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” <10,x,2> PA152, Vlastislav Dohnal, FI MUNI, 2017 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> Kontrola e=2? Výstup: <2,x> PA152, Vlastislav Dohnal, FI MUNI, 2017 17 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, 2017 18 Schéma optimalizace dotazů parser konverze pravidla odhad velikostí tvorba fyz. plánů dotazu odhad nákladů f.p.d. 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, 2017 19 Příklad: SQL dotaz  Relace  StarsIn(title, year, starName)  MovieStar(name, birthdate)  Dotaz  Najdi filmy, ve kterých hrají herci narození v roce 1960:  SELECT title FROM StarsIn WHERE starName IN ( SELECT name FROM MovieStar WHERE extract(year from birthdate) = 1960 ); PA152, Vlastislav Dohnal, FI MUNI, 2017 20 Příklad: strom dotazu SELECT FROM WHERE IN title StarsIn ( ) starName SELECT FROM WHERE = name MovieStar extract(year from birthdate) 1960 PA152, Vlastislav Dohnal, FI MUNI, 2017 21 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 s StarsIn IN name sextract(year from birthdate) = 1960 starName MovieStar PA152, Vlastislav Dohnal, FI MUNI, 2017 22 Příklad: logický plán dotazu  Operátor IN nahrazen součinem title sstarName=name StarsIn name sextract(year from birthdate) = 1960 MovieStar  PA152, Vlastislav Dohnal, FI MUNI, 2017 23 Příklad: vylepšení logického plánu  Nahrazení součinu a selekce Provedení spojení  Další možnost Posunout projekci k relaci StarsIn? title starName=name StarsIn name sextract(year from birthdate) = 1960 MovieStar  Před generováním fyzických plánů  Ovlivňují odhad ceny provedení PA152, Vlastislav Dohnal, FI MUNI, 2017 24 Příklad: odhad velikostí výsledků Odhadnout velikost StarsIn MovieStar name sextract(year from birthdate) = 1960 PA152, Vlastislav Dohnal, FI MUNI, 2017 25 Příklad: jeden fyzický plán Parametry: pořadí relací, velikost paměti, projekce,... Hash join SEQ scan index scan Parametry: volba podmínky, ... StarsIn MovieStar PA152, Vlastislav Dohnal, FI MUNI, 2017 26 Příklad: ohodnocení plánů cenou Logický plán dotazu Plán1 Plán2 …. Plánn Cena1 Cena2 …. Cenan Vyber plán s nejnižší cenou! PA152, Vlastislav Dohnal, FI MUNI, 2017 27 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, 2017 28 Optimalizace relační algebry  Transformační pravidla Musí zajistit ekvivalenci výsledků Jaké transformace jsou vhodné? PA152, Vlastislav Dohnal, FI MUNI, 2017 29 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, 2017 30 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, 2017 31 Transformační pravidla  Selekce sp1p2(R) = sp1p2(R) = sp1p2(R) = sp1 [ sp2 (R)] [ sp1 (R)]  [ sp2 (R)] [ sp1 (R)]  [ sp2 (R)] PA152, Vlastislav Dohnal, FI MUNI, 2017 32 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žnosti   SUM: R  S = {a,a,b,b,b,b,b,c,c,c,d}  MAX: R  S = {a,a,b,b,b,c,c,d}  R  S = ?  MIN: R  S = {b,b,c} v SQL: INTERSECT ALL PA152, Vlastislav Dohnal, FI MUNI, 2017 33 Možnost SUM: sjednocení relací  Sjednocení dvou relací R  S v SQL: UNION ALL  Příklad  Poslanci(id, rok, partaj, jméno, …)  Senátoři(id, rok, partaj, jméno, …)  R = prok,partaj(Senátoři) S = prok,partaj(Poslanci) rok partaj 1997 ODS 2003 ČSSD 2007 SZ rok partaj 1997 ODS 1998 KDU 1996 ČSSD PA152, Vlastislav Dohnal, FI MUNI, 2017 34 Možnost MAX: rozklad selekce  Rozklad selekce:  Příklad: R={a,a,b,b,b,c} p1 splňují a,b; p2 splňují b,c sp1 p2 (R) = sp1(R)  sp2(R) sp1 p2 (R) = {a,a,b,b,b,c} sp1(R) = {a,a,b,b,b} sp2(R) = {b,b,b,c} sp1(R) max sp2(R) = {a,a,b,b,b,c} PA152, Vlastislav Dohnal, FI MUNI, 2017 35 Volba správné možnosti  Pragmatické rozhodnutí pro  Použití “SUM” pro sjednocení multimnožin „MAX“ pro rozdělení podmínky „nebo“ ()  Některá pravidla nelze pro multimnožiny použít Asociativita rozdílu R – (S – T) Distributivita: R  (S  T) != (R  S)  (R  T) PA152, Vlastislav Dohnal, FI MUNI, 2017 36 Transformační pravidla  Značení: X = množina atributů Y = množina atributů XY = X  Y  Projekce pxy (R) = px [py (R)] PA152, Vlastislav Dohnal, FI MUNI, 2017 37 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 i S [sp (R)]  S R  [sq (S)] sp (R  S) = sq (R  S) = PA152, Vlastislav Dohnal, FI MUNI, 2017 38 Transformační pravidla  Kombinace selekce a přirozeného spojení Další pravidla lze odvodit spq (R  S) = [sp (R)]  [sq (S)] spqm (R  S) = sm [(sp (R))  (sq (S))] spq (R  S) = [(sp (R))  S] max [R (sq (S))] Transformační pravidla  Kombinace selekce a přirozeného spojení Příklad odvození pravidla PA152, Vlastislav Dohnal, FI MUNI, 2017 39 spq (R  S) = sp [sq (R  S) ] = sp [ R  sq (S) ] = [sp (R)]  [sq (S)] PA152, Vlastislav Dohnal, FI MUNI, 2017 40 Transformační pravidla  Kombinace selekce a přirozeného spojení Příklad odvození pravidla Nechť m = výraz obsahující pouze atributy společné R i S, ale neporovnává je [sm (R)]  [sm (S)]sm (R  S) = PA152, Vlastislav Dohnal, FI MUNI, 2017 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) (sp [ px (R) ])px pxz px[sp (R) ] = PA152, Vlastislav Dohnal, FI MUNI, 2017 42 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 pxy([pxz (R) ]  [pyz (S) ]) pxy (R  S) =  Kombinace navíc se selekcí (p, s, ) PA152, Vlastislav Dohnal, FI MUNI, 2017 43 Transformační pravidla pxy (sp (R  S)) = pxy (sp [pxz’ (R)  pyz’ (S)]) z’ = z  {atributy použité v P}  Kombinace projekce, selekce a kartézského součinu PA152, Vlastislav Dohnal, FI MUNI, 2017 44 Transformační pravidla pxy (sp (R  S)) = ? PA152, Vlastislav Dohnal, FI MUNI, 2017 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 Musí P něco splňovat? sp(R sum S) = sp(R) sum sp(S) sp(R – S) = sp(R) – S = sp(R) – sp(S) PA152, Vlastislav Dohnal, FI MUNI, 2017 46 Vhodné transformace sp1p2 (R)  sp1 [sp2 (R)]  sp2 [sp1 (R)] sp1p2 (R)  sp1(R) max sp2(R) sp (R  S)  [sp (R)]  S R  S  S  R px [sp (R)]  px (sp [pxz (R)]) PA152, Vlastislav Dohnal, FI MUNI, 2017 47 Vhodné transformace  Také projekce co nejdříve  Příklad: R(A,B,C,D,E,F,G,H,I,J) výsledek={E} Filtr P: (A=3)  (B=“cat”) pE (sp (R)) vs. pE (sp (pABE(R))) PA152, Vlastislav Dohnal, FI MUNI, 2017 48 Vhodné transformace  Máme indexy Pro A i pro B s(A=3)  (B=“cat”)(R) = s(A=3)(R)  s(B=“cat”)(R) B = ‘cat’ A = 3 Průnik seznamu ukazatelů je výsledek ukazatel na záznam: PA152, Vlastislav Dohnal, FI MUNI, 2017 49 Vhodné transformace  Obecná pravidla: Bez transformací neuděláme chybu Většinou výhodné  Selekce nejblíže relacím  Projekce nejblíže relacím  Eliminace společných podvýrazů  Eliminace duplicit Vhodné transformace: příklad  Přesun selekce co nejblíže relacím  zdánlivě ok  Ale: Nejdříve vhodné přesunout co nejdále a pak nejblíže  Příklad:  Relace: StarsIn(title, year, starName) Movie(title, year, studioName)  Pohled: create view MoviesOf1996 as select * from Movie where year = 1996;  Dotaz: select starName, studioName from MoviesOf1996 natural join StarsIn; PA152, Vlastislav Dohnal, FI MUNI, 2017 50 starName,studioName MoviesOf1996 StarsIn syear=1996 starName,studioName Movie StarsIn syear=1996 starName,studioName Movie StarsIn syear=1996 PA152, Vlastislav Dohnal, FI MUNI, 2017 51 Zpracování dotazu: shrnutí  Úroveň relační algebry Transformační pravidla Použití doporučených pravidel  Úroveň podrobného plánu dotazu Odhad ceny Vytvoření a porovnání plánů PA152, Vlastislav Dohnal, FI MUNI, 2017 52 Odhad ceny plánu dotazu 1. Odhad velikosti výsledku operace 2. Odhad počtu V/V operací PA152, Vlastislav Dohnal, FI MUNI, 2017 53 Odhad velikosti výsledku  Statistiky pro relaci R T(R) – počet záznamů S(R) – velikost záznamu v bajtech  S(R,A) – velikost atributu (hodnoty) v bajtech B(R) – počet obsazených bloků V(R, A) – počet unikátních hodnot atributu A  Pro správné odhady Aktuální statistiky nutné! PA152, Vlastislav Dohnal, FI MUNI, 2017 54 Příklad statistik  Relace R Atribut A – řetězec, max. 20 B  S(R,A) = 3 ← průměrná délka Atribut B – celé číslo, 4 B Atribut C – datum, 8 B Atribut D – řetězec, 5 B  S(R,D) = 1  Statistiky T(R) = 5 S(R) = 20 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, 2017 55 Odhad velikosti výsledku  Kartézský součin W = R1  R2 T(W) = T(R1)  T(R2) S(W) = S(R1) + S(R2) PA152, Vlastislav Dohnal, FI MUNI, 2017 56 Odhad velikosti výsledku  Selekce W = sZ=val(R) S(W) = S(R) T(W) = ?  W = sA=‘cat’(R)  W2 = sB=2(R) T(W2) = ? 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 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, 2017 57 Odhad velikosti výsledku  Předpoklad předchozího odhadu Rovnoměrné rozložení hodnot mezi hodnotami v R!  f(val) = 1 / V(R,Z)  T(sZ=val(R)) = T(R)  f(val)  Alternativní předpoklad Rovnoměrné rozložení hodnot v celé doméně  Počet hodnot v doméně označujeme DOM(R,Z)  f(val) = 1 / DOM(R,Z) PA152, Vlastislav Dohnal, FI MUNI, 2017 58 Odhad velikosti výsledku: příklad  Selekce W = sZ=val(R) T(W) = ?  Podle DOM(R,*)  Odvození W = sC=val(R)  T(W) = f(val)  T(R) = 1/10 * 5 = 0,5 W = sB=val(R)  T(W) = (1/10)*5 W = sA=val(R)  T(W) = 0,5 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 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, 2017 59 Odhad velikosti výsledku  Selekce W = sZ=val(R) Původní návrh Alternativní návrh 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) 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, 2017 60 Odhad velikosti  Selekce W = sZ≥val(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, 2017 61 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= sz  15 (R) Max=20 ZR f = 20-15+1 20-1+1 6 20 = PA152, Vlastislav Dohnal, FI MUNI, 2017 62 Odhad velikosti  Selekce W = szval(R) T(W) = T(R)(1 – f(val)) = T(R)(1 – 1/V(R,Z)) Obvyklé řešení pro V(R,Z) ≈ T(R)  T(W) = T(R) = T(R) – T(R) V(R,Z) PA152, Vlastislav Dohnal, FI MUNI, 2017 63 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 = Z Viz dále… PA152, Vlastislav Dohnal, FI MUNI, 2017 64 Odhad velikosti: přirozené spojení  Předpoklad V(R1,A) ≤ V(R2,A)  každá hodnota A z R1 je i v R2 V(R1,A) ≥ V(R2,A)  každá hodnota A z R2 je i v R1 R1 A B C R2 A DR1  R2 PA152, Vlastislav Dohnal, FI MUNI, 2017 65 Odhad velikosti: přirozené spojení  V(R1,A) ≤ V(R2,A)  1 záznam se spojí s T(R2) / V(R2,A) záznamy Opět předpoklad rovnoměrného rozložení  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, 2017 66 Odhad velikosti: přirozené spojení  Shrnutí obou variant V(R1,A) ≤ V(R2,A) V(R2,A) ≤ V(R1,A)  Rozdíl je pouze ve jmenovateli T(W) = T(R2) V(R2,A) T(R1)  T(W) = T(R1) V(R1,A) T(R2)  PA152, Vlastislav Dohnal, FI MUNI, 2017 67 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, 2017 68 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épředpokládáme stejné PA152, Vlastislav Dohnal, FI MUNI, 2017 69 Odhad velikosti: přirozené spojení  W = R1(X), R2(Y), X  Y = Z  Velikost záznamu S(W) = S(R1) + S(R2) – S(R1,Z) Platí pro všechny varianty  Počet záznamů, když Z má více atributů? Předpokládáme, že jsou nezávislé. R1  R2 T(W) = T(R1)  T(R2) max{ V(R1,A1), V(R2,A1) }  max{ V(R1,A2), V(R2,A2) } PA152, Vlastislav Dohnal, FI MUNI, 2017 70 Odhad velikosti: projekce, selekce  Projekce AB(R) T(W)=T(R) S(W)=S(R, AB)  Selekce sA=aB=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) PA152, Vlastislav Dohnal, FI MUNI, 2017 71 Odhad velikosti: množinové operace  Sjednocení, průnik, rozdíl (, , –) T(W) – choose average size  T(R  S) = T(R) + T(S) … if  means UNION ALL here  T(R  S) = [ max{T(R), T(S)} , T(R) + T(S) ]  So use: T(R  S) = avg{ max{T(R), T(S)} , T(R) + T(S) }  If set union is evaluated  T(R – S) = T(R) – ½ T(S)  T(R  S) = avg{ 0, min{T(R), T(S)} }  DISTINCT All attributes  min{ 1/2T(R), (V(R,A)*V(R,B)*…) } PA152, Vlastislav Dohnal, FI MUNI, 2017 72 Odhad velikosti  Pro složitější výrazy jsou třeba ostatní statistiky  Příklad W = [sA=a(R1)]  R2 označme jako U  T(U) = T(R1) / V(R1,A) S(U) = S(R1) Pro odhady pro W potřebujeme i V(U,*) ! PA152, Vlastislav Dohnal, FI MUNI, 2017 73 Odhad počtu hodnot  Odhady V(U,*) U = sA=a(R1) Předpokládejme, že R1(A,B,C,D) PA152, Vlastislav Dohnal, FI MUNI, 2017 74 Odhad počtu hodnot: příklad  Relace R1  U = sA=a(R1)  T(U) = T(R1)/V(R1,A)  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)) 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, 2017 75 Odhad počtu hodnot: praxe  Obvyklé řešení U = sA=a(R1) V(U,A) = 1 V(U,K) = T(U)  K = primární klíč relace R1 V(U,*) = V(R,*) resp. V(U,*) = T(U)  Výsledně lze využít původní V(R,*) V(U,*) = min { V(R,*), T(U) } PA152, Vlastislav Dohnal, FI MUNI, 2017 76 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)  Resp. min { V(R1,B), T(U) } V(U,C) = V(R2,C) PA152, Vlastislav Dohnal, FI MUNI, 2017 77 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, 2017 78 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 = 10 000  V(U,A) = 50  V(U,B) = 100  V(U,C) = 300 PA152, Vlastislav Dohnal, FI MUNI, 2017 79 Odhad počtu hodnot: spojení  Celkový výsledek Z = U  R3(C,D)  U(A,B,C) Výsledek:  T(Z) = 10 000  3 000 / 300 = 100 000  V(Z,A) = 50  V(Z,B) = 100  V(Z,C) = 90  V(Z,D) = 500 PA152, Vlastislav Dohnal, FI MUNI, 2017 80 Odhad počtu hodnot: histogram  Histogram hodnot atributu Místo V(R,A) a DOM(R,A) Zpřesnění odhadů  Počet různých hodnot Málo  pro každou počet Hodně  kvantizace  Stejné intervaly  Percentily  Pouze pro nejfrekventovanější  ostatní dohromady (tj. výsledně rovnoměrně) 10 20 30 40 8 15 28 37 f PA152, Vlastislav Dohnal, FI MUNI, 2017 81 Příklad statistik PostgreSQL  Připojte se k fakultní DB PostgreSQL Návod viz první přednáška  Ve schématu xdohnal jsou tabulky predmet, skupina, hotel  Statistiky jak na relacích, tak i atributech. Významy jednotlivých polí  http://www.postgresql.org/docs/9.6/interactive/view-pg-stats.html PA152, Vlastislav Dohnal, FI MUNI, 2017 82 Příklad statistik PostgreSQL  Tabulka hotel PA152, Vlastislav Dohnal, FI MUNI, 2017 83 Příklad statistik PostgreSQL  Atribut hotel.id  Atribut hotel.name PA152, Vlastislav Dohnal, FI MUNI, 2017 84 Příklad statistik PostgreSQL  Atribut hotel.state  Atribut hotel.distance_to_center PA152, Vlastislav Dohnal, FI MUNI, 2017 85 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, 2017 86 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, 2017 87 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, 2017 88 Odhad ceny plánu dotazu: shrnutí  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ů