PA152: Efektivní využívání DB 6. Zpracování dotazů Vlastislav Dohnal PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 24 Příklad: odhad velikostí výsledků Odhadnout velikost StarsIn MovieStar name sextract(year from birthdate) = 1960 PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 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, 2019 28 Optimalizace relační algebry ◼ Transformační pravidla Musí zajistit ekvivalenci výsledků Jaké transformace jsou vhodné? PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 30 Transformační pravidla ◼ Stejné pro kartézský součin, sjednocení, průnik 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, 2019 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, 2019 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 = ?  MIN: R  S = {b,b,c} v SQL: INTERSECT ALL ◼ R  S = ?  SUM: R  S = {a,a,b,b,b,b,b,c,c,c,d} v SQL: UNION ALL  MAX: R  S = {a,a,b,b,b,c,c,d} PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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))] PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 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, 2019 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, 2019 44 Transformační pravidla pxy (sp (R  S)) = ? PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 46 Vhodné transformace ◼ Selekce co nejdříve: ◼ 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))) px [sp (R)] → px (sp [pxz (R)]) sp (R  S) → [sp (R)]  S PA152, Vlastislav Dohnal, FI MUNI, 2019 47 Vhodné transformace sp1p2 (R) → sp1 [sp2 (R)] → sp2 [sp1 (R)] → [ sp1 (R)]  [ sp2 (R)] sp1p2 (R) → sp1(R) max sp2(R) R  S → S  R PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 50 starName,studioName MoviesOf1996 StarsIn syear=1996 starName,studioName Movie StarsIn syear=1996 starName,studioName Movie StarsIn syear=1996 PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 52 Odhad ceny plánu dotazu 1. Odhad velikosti výsledku operace 2. Odhad počtu V/V operací PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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) = 16 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 62 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 ◼ Intervaly hodnot (se stejným počtem záznamů) ◼ Percentily ◼ Pouze pro nejfrekventovanější  ostatní dohromady (tj. výsledně rovnoměrně) 10 23 37 42 8 15 28 37 f PA152, Vlastislav Dohnal, FI MUNI, 2019 63 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, 2019 64 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, 2019 65 Odhad velikosti: přirozené spojení ◼ Předpoklad Z={A} a také: 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, 2019 66 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, 2019 67 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, 2019 68 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, 2019 70 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, 2019 71 Odhad velikosti: projekce, selekce ◼ Projekce W = AB(R) T(W)=T(R) S(W)=S(R, AB) ◼ Selekce W = 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, 2019 72 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, 2019 73 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, 2019 74 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, 2019 75 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, 2019 76 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, 2019 77 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, 2019 78 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, 2019 79 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) = min{ V(R1,B), V(R2,B) } = 100 ◼ V(U,C) = 300 PA152, Vlastislav Dohnal, FI MUNI, 2019 80 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, 2019 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, 2019 82 Příklad statistik PostgreSQL ◼ Tabulka hotel PA152, Vlastislav Dohnal, FI MUNI, 2019 83 Příklad statistik PostgreSQL ◼ Atribut hotel.id ◼ Atribut hotel.name PA152, Vlastislav Dohnal, FI MUNI, 2019 84 Příklad statistik PostgreSQL ◼ Atribut hotel.state ◼ Atribut hotel.distance_to_center PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 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, 2019 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ů