Databasteknik II, Örebro, 18 februari 2008: Kostnadsbaserad frågeoptimering =========================================================================== Igår: Samma SQL-fråga kan ge flera olika relationsalgebrauttryck, olika effektiva Frågeoptimering = databashanteraren väljer den bästa = billigaste = snabbaste Materialiserat och strömmande Heuristisk frågeoptimering Idag: Problem med heuristisk frågeoptimering Kostnadsbaserad frågeoptimering Optimering i AMOS Exempeldatabasen (OH) --------------------- create table Personer ( P_Nummer integer not null primary key, P_Namn char(10) not null, Telefon char(10) not null, "Lön" integer not null, Arbetsplats integer not null ); /* 1 000 000 rader, 32 byte per rad */ create table Avdelningar ( A_Nummer integer not null primary key, A_Namn char(10) not null ); /* 10 000 rader */ alter table Personer add foreign key (Arbetsplats) references Avdelningar(A_Nummer); select Personer.Telefon from Personer, Avdelningar where Personer.Arbetsplats = Avdelningar.A_Nummer and Personer.P_Namn = 'Olle' and Avdelningar.A_Namn = 'Data'; Enkla exempel på när heuristisk optimering inte räcker ------------------------------------------------------ select * from Personer where P_Namn = 'Olle' and Lön > 2000 Ska den köra detta som: SELECT P_Namn = 'Olle' and Lön > 2000 | Personer SELECT P_Namn = 'Olle' | SELECT Lön > 2000 | Personer SELECT Lön > 2000 | SELECT P_Namn = 'Olle' | Personer (men jo, om den är smart kan den gissa att = har bättre selektivitet än >) (och även om en kolumn är en nyckel = bästa selektivitet) select * from Personer where P_Namn = 'Olle' and Lön = 2000 Ska den köra detta som: SELECT P_Namn = 'Olle' and Lön = 2000 | Personer SELECT P_Namn = 'Olle' | SELECT Lön = 2000 | Personer SELECT Lön = 2000 | SELECT P_Namn = 'Olle' | Personer Finns det index? Till exempel bara på P_Namn? SELECT Lön = 2000 | SELECT P_Namn = 'Olle' <-- Snabb indexuppslagning (behövs: veta indexen) | Personer Finns det index BÅDE på P_Namn och Lön? SELECT Lön = 2000 | SELECT P_Namn = 'Olle' <-- Snabb indexuppslagning, bättre selektivitet (behövs: veta selektivitet, dvs antal olika värden!) | Personer Man kan göra regler i heuristiken för detta, men när det blir många olika val räcker inte det heller. Kostnadsbaserad frågeoptimering ------------------------------- 1. Exekveringsplan: inte bara relationsalgebra, utan även vilka index och algoritmer man använder 2. Kostnadsfunktion "Kostnaden" för en exekveringsplan Normalt: kostnad = tid Normalt: inte exakt uppmätta tider! I diskbaserade databaser kan det räcka med bara antalet diskaccesser Obs: Den BERÄKNADE kostnaden, enligt kostnadsfunktionen. Kan vara oexakt, eller fel. 3. Vad behöver man veta om en tabell? Lagringsstruktur, sorteringsordning, index r = antal rader = card(T) R = radstorleken i bytes bfr = blockningsfaktorn = antal poster per datablock b = antalet datablock Exempel från exempeldatabasen: Tabellen Personer: 1 000 000 rader, 32 byte per rad "The size of a Mimer SQL page is 2 kilobytes." R = 32 bfr = 64 (antagligen lite mindre, säg 60) r = card(Personer) = 10**6 b = r / bfr = 16667 Tabellen Avdelningar: 10 000 rader, 14 byte per rad R = 14 bfr = 146 (antagligen lite mindre, säg 140) r = card(Personer) = 10**4 b = r / bfr = 69 Men även statstik om innehållet: d = antal olika värden på ett visst attribut (ibland med histogram!) Ungefärliga värden räcker ofta! - "verkligt optimal plan" är oftast inte så noga x = antal nivåer i ett trädindex sl = selektivitet på ett villkor s = selektionskardinalitet = fan-out = sl * r bI1 = antal indexblock på indexnivå 1 Exempel: select på en tabell: SELECT villkor T villkor: T.A = C, A en nyckel, inga index eller sökordningar -> cost = b/2, fanout = 1 Exempel: select * from Personer where P_Nummer = 4711 Kostnad: villkor: T.A = C, A inte nyckel, inga index eller sökordningar -> cost = b, fanout = r/d Exempel: select * from Personer where Lön = 2000 villkor: T.A = C, A nyckel, T är hashad på A -> cost = 1, fanout = 1 Exempel: select * from Personer where P_Nummer = 4711 (om hashindex på P_Nummer) villkor: T.A = C, A nyckel, T har B-trädsindex på A -> cost = x + 1, fanout = 1 Exempel: select * from Personer where P_Nummer = 4711 (om hashindex på P_Nummer) villkor: T.A > C, inga index eller sökordningar -> cost = b, fanout = r/2 Exempel: select * from Personer where Lön > 2000 P/R-boken skriver SELECTI för indexselektering Den sista har egentligen fanout = r i vårt exempel (för jag la in såna data) men det vet (nog?) inte databashanteraren. Och det är kanske inte heller så noga, för databashanteraren behöver inte räkna ut exakt tid, utan bara ungefär, så den kan jämföra planerna, och ofta är det inte så noga om det blir den allra snabbaste planen (0.1 sekunder eller 1 sekund). Avvägning mot hur mycket man ska slöa ner databashanteraren med statistikinsamling och omfattande optimering. 4. Join-algoritmer Även join, sortering m fl operationer kostnadsuppskattas, olika för olika join- och sorteringsalgoritmer 4.1 Nested-loop-join ("NLJ" i P-M/R) ------------------------------------ Resultat = T1 join VILLKOR T2 Resultat = T1 join T1.k=T2.k T2 (Rita upp T1 och T2, med k) T1 T2 Resultat ... k k ... ... k k ... 1 1 1 1 1 3 1 1 2 3 3 3 3 6 3 3 5 7 8 Pseudokod: for each T1 as t1 { for each T2 as t2 { if (VILLKOR) Resultat += t1+t2 } } } Eller: open(T1) <-- "scan", dvs läs hela datafilen open(Resultat) while (t1 = read(T1)) { open(T2) <-- "scan", dvs läs hela datafilen while (t2 = read(T2)) { if (VILLKOR) write(Resultat, t1+t2) } } } Gamla exemplet med Data-Olles telefonnummer: for each Person as p { for each Avdelning as a { if (p.Arbetsplats = a.A_Nummer and p.P_Namn = 'Olle' and a.A_Namn = 'Data') { print p.Telefon } } } Det här var (ungefär i alla fall) en nested-loop-join: for each Person as p { if (p.P_Namn = 'Olle') { for each Avdelning as a { if (a.A_Namn = 'Data') { if (p.Arbetsplats = a.A_Nummer) { print p.Telefon } } } } } 4.2 Indexerad nested-loop-join = single-loop-join ("INLJ" i P-M/R) ------------------------------------------------------------------ Resultat = T1 join VILLKOR T2 Resultat = T1 join T1.k=T2.k T2 Kräver index på aktuell kolumn (k) i T2 Pseudokod: for each T1 as t1 { t2 = slå upp t1.k i T2 Resultat += t1+t2 // om t1.k finns i T2; behöver inte kolla VILLKOR } Men, om T2.k inte är en nyckel, dvs det kan finnas flera rader med T2.k = t1.k i T2? for each T1 as t1 { for each T2 med k = t1.k as t2 { <-- Indexuppslagning, och läs sen i indexet Resultat += t1+t2 } } Eller: open(T1) <-- "scan", dvs läs hela datafilen open(Resultat) while (t1 = read(T1)) { indexopen(T2, t1.k) <-- "index scan", dvs läs via indexet while (t2 = read(T2)) { write(Resultat, t1+t2) // behöver inte kolla VILLKOR } } 4.3 Sort-merge-join ("SMJ" i P-M/R) ----------------------------------- Resultat = T1 join VILLKOR T2 Resultat = T1 join T1.k=T2.k T2 Kräver att T1 och T2 är SORTERADE på k, eller så måste man sortera dem först! Pseudokod: open(T1) <-- "scan", dvs läs hela datafilen open(T2) <-- "scan", dvs läs hela datafilen open(Resultat) t1 = read(T1) t2 = read(T2) while (not eof(T1) and not eof(T2)) { if (t1.k > t2.k> { t2 = read(T2) } else if (t1.k < t2.j) { t1 = read(T1) } else { write(Resultat, t1+t2) } } 4.4 Hash-join ("HJ" i P-M/R) ---------------------------- Stoppa in den ena (minsta) tabellen i en hashtabell i primärminnet = mycket snabb indexuppslagning! Resultat = T1 join VILLKOR T2 Resultat = T1 join T1.k=T2.k T2 Pseudokod: open(T1) <-- "scan", dvs läs hela datafilen h = new Hashtabell() while (t1 = read(T1)) { stoppa in t1 i hashtabellen h } open(T2) <-- "scan", dvs läs hela datafilen open(Resultat) while (t2 = read(T2)) { t1 = hitta t2.k i hashtabellen if (t1) { write(Resultat, t1+t2) } } 5. Join-ordning select * from T1, T2 where ... T1 join T2 T2 join T1 select * from T1, T2, T3 where ... (T1 join T2) join T3 (T1 join T3) join T2 (T2 join T1) join T3 (T2 join T3) join T1 (T3 join T1) join T2 (T3 join T2) join T1 6. Sökning i tillståndsrymden av möjliga exekveringsplaner för att hitta en billig Ofta en trädsökning 6a. Fullständig (exhaustive) sökning (en del planer kan skippas om garanterat dyrare) - men komplicerade frågor ger väldigt många planer - O(frågestorlek!) 6b. En del planer kan skippas om de garanterat är dyrare: dynamic programming - snabbare, men har samma komplexitet som fullständig sökning 6c. "Slumpmässiga", "heuristiska" algoritmer (ex: ren slump, många slump + hill climbing) 1! = 1 2! = 2 3! = 6 5! = 120 10! = 3628800 13.0! = 6.22702e+09 (32-bit integer overflow) AMOS ---- Exempelfråga: Vilka matcher 1950 hade mer än 100 000 åskådare? Amos 7> select m from match m where spectators(m)>100000 and year(played_in(m))=1950; #[OID 1187] #[OID 1184] #[OID 1189] #[OID 1188] 0.547 s Amos 8> Man kan välja olika optimeringsmetoder: Amos 2> optmethod("exhaustive"); "RANKSORT" Amos 3> Översätt till SQL utan funktionsnotation, och bara en operation i varje del av where-satsen: select m from match m, integer _v1, tournament _v2 where m.spectators = _v1 and m.played_in = _v2 and _v2.year = 1950 and _v1 > 100000 Indata till optimeringsfunktionen är en lista med de fyra "predikaten": ((#[OID 1038 "P_MATCH.SPECTATORS->INTEGER"] M _V1) <-- spectators(m) = _v1 (#[OID 1035 "P_MATCH.PLAYED_IN->TOURNAMENT"] M _V2) <-- played_in(m) = _v2 (#[OID 1001 "P_TOURNAMENT.YEAR->INTEGER"] _V2 1950) <-- year(_v2) = 1950 (#[OID 121 "OBJECT.OBJECT.>->BOOLEAN"] _V1 100000)) <-- _v1 > 100000 Korrekt optimerad exekveringsplan: ((#[OID 1001 "P_TOURNAMENT.YEAR->INTEGER"] _V2 1950) <-- year(_v2) = 1950 (#[OID 1035 "P_MATCH.PLAYED_IN->TOURNAMENT"] M _V2) <-- played_in(m) = _v2 (#[OID 1038 "P_MATCH.SPECTATORS->INTEGER"] M _V1) <-- spectators(m) = _v1 (CALL GT-- #[OID 121 "OBJECT.OBJECT.>->BOOLEAN"] _V1 100000)) <-- _v1 > 100000 Kör som nästlade loopar. Betyder: 1. Sök efter en turnering _v2 som har year = 1950, via index om det finns 2. Sök sen efter en match m som har played_in = turneringen _v2, via index om det finns 3. Hämta spectators för matchen m, kalla det för _v1 4. Kolla om detta tal _v1 > 10000 Amos' kostnadsmodell: För varje predikat, med en viss bindning (ex: played_in(m) = t, vet vi m, t eller båda?) kan man få ut "kostnad" (2*antalet besökta tupler=objekt eller lagrade funktionsdatarader) och "fan-out" (antal tupler i svaret) Ex: year(_v2) = 1950 Vi vet 1950 men inte variabeln _v2 Kostnad = 2*14 för det finns 14 turnerings-objekt och inget index på year för dem fanout = 1 för det var bara en turnering som spelades 1950 Dynamisk programmering ---------------------- En fråga med tre predikat, kalla dem X Y Z Exempel: Amos 7> select name(host(t)) from tournament t where year(t)=1982; "Spain" 0.235 s Amos 8> Indata till optimeraren: ((#[OID 1006 "P_TOURNAMENT.HOST->COUNTRY"] T _V1) <-- host(t) = _v1 (#[OID 1003 "P_COUNTRY.NAME->CHARSTRING"] _V1 _V2) <-- name(_v1) = _v2 (#[OID 1001 "P_TOURNAMENT.YEAR->INTEGER"] T 1982)) <-- year(t) = 1982 Optimerad plan: ((#[OID 1001 "P_TOURNAMENT.YEAR->INTEGER"] T 1982) <-- year(t) = 1982 (#[OID 1006 "P_TOURNAMENT.HOST->COUNTRY"] T _V1) <-- host(t) = _v1 (#[OID 1003 "P_COUNTRY.NAME->CHARSTRING"] _V1 _V2)) <-- name(_v1) = _v2 Förklara dynamisk programmering