Databasteknik II, Örebro, 11 februari 2015: Kostnadsbaserad frågeoptimering =========================================================================== Förra gången: Relationsalgebra 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 Problem med heuristisk frågeoptimering Idag: Kostnadsbaserad frågeoptimering Inte än: AMOS, AMOSQL, labb 8 Exempeldatabas (OH) ------------------- create table A ( Anr integer not null primary key, Anamn varchar(40) not null, Lon integer not null); /* Anställda: 1 000 000 rader, 48 byte per rad */ create table P ( Pnr integer not null primary key, Pnamn varchar(36) not null, Budget integer not null); /* Projekt: 1 000 rader, 44 byte per rad */ create table AP ( A integer not null, P integer not null, primary key (A, P)); /* Arbetar På: 2 000 000 rader, 8 byte per rad */ Exempelfråga: Nummer och namn på alla som jobbar på Apollo-projektet och har en lön större än 1000? select Anr, Anamn from A, AP, P where Anr = A and P = Pnr and Lon > 1000 and Pnamn = 'Apollo'; Enkla exempel på när heuristisk optimering inte räcker ------------------------------------------------------ select * from A where Anamn = 'Olle' and Lon > 2000 Ska den köra detta som: SELECT Anamn = 'Olle' and Lön > 2000 | A SELECT Anamn = 'Olle' | SELECT Lön > 2000 | A SELECT Lön > 2000 | SELECT Anamn = 'Olle' | A (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 A where Anamn = 'Olle' and Lön = 2000 Ska den köra detta som: SELECT Anamn = 'Olle' and Lön = 2000 | A SELECT Anamn = 'Olle' | SELECT Lön = 2000 | A SELECT Lön = 2000 | SELECT Anamn = 'Olle' | A Finns det index? Till exempel bara på Anamn? SELECT Lön = 2000 | SELECT Anamn = 'Olle' <-- Snabb indexuppslagning (behövs: veta indexen) | A Finns det index BÅDE på Anamn och Lön? SELECT Lön = 2000 | SELECT Anamn = 'Olle' <-- Snabb indexuppslagning, bättre selektivitet (behövs: veta selektivitet, dvs antal olika värden!) | A 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. Obs; Olika databashanterare kan ha olika kostnadsmodeller. Vi visar ett exempel. 3. Vad behöver man veta om en tabell? 3a. Fysiskt schema: Lagringsstruktur, sorteringsordning, index R = radstorleken i bytes bfr = blockningsfaktorn = antal poster per datablock b = antalet datablock blockstorleken ("page size"), som kan varieras, till exempel i MySQL 3b. Innehållet som det (ungefär) ser ut (ungefär) just nu: r = antal rader = card(T) Och även: Statistik om värdena i de olika kolumnerna! (Mer om det sen.) Exempel från exempeldatabasen: Tabellen A: 1 000 000 rader, 48 byte per rad "The size of a Mimer SQL page is 2 kilobytes." "The default database page size in InnoDB is 16KB." Antag: blockstorlek = 2 kilobyte = 2048 byte R = 48 bfr = 2048 / 48 = 42 (antagligen lite mindre, säg 40) r = card(A) = 10**6 b = r / bfr = 25000 Tabellen AP: 2 000 000 rader, 8 byte per rad R = 8 bfr = 2048 / 8 = 256 (antagligen lite mindre, säg 250) r = card(A) = 2*10**6 b = r / bfr = 8000 Tabellen P: 1 000 rader, 44 byte per rad R = 44 bfr = 2048 / 44 = 46 (antagligen lite mindre, säg 40) r = card(A) = 1000 b = r / bfr = 25 Tabellen K: 1 000 rader, 48 byte per rad R = 48 bfr = 2048 / 48 = 42 (antagligen lite mindre, säg 40) r = card(A) = 1000 b = r / bfr = 25 Men även statstik om innehållet (tänk på Mimers "update statistics"-kommando): 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 4. Algoritmer för selektion 4.1 Oindexerad selektion = läs tabellen sekvensiellt Exempel: Selektion på en tabell: SELECT villkor T villkor: T.A = C, A inte nyckel, inga index eller sökordningar -> cost = b, fanout = r/d SQL-exempel: select * from A where Lön = 2000 villkor: T.A = C, A en nyckel, inga index eller sökordningar -> cost = b/2, fanout = 1 SQL-exempel: select * from A where Anr = 4711 -- om inget index fanns på Anr! Det var om T är en tabell. Men om det är en ström nerifrån trädet? Räkna med Bcost (kostnad att läsa ett block) och Scost (kostnad att läsa en rad från en ström) Exempel: Bcost = 1000, Scost = 1 (dvs: Bcost = 1000 * Scost) villkor: T.A = C, A inte nyckel, inga index eller sökordningar -> cost = r * Scost, fanout = r/d (samma som ovan!) villkor: T.A = C, A en nyckel, inga index eller sökordningar -> cost = r * Scost / 2, fanout = 1 4.1 Indexerad selektion = gå via indexet villkor: T.A = C, A nyckel, T är hashad på A -> cost = 1, fanout = 1 SQL-exempel: select * from A where Anr = 4711 (om hashindex på Anr) villkor: T.A = C, A nyckel, T har B-trädsindex på A -> cost = x + 1, fanout = 1 SQL-exempel: select * from A where Anr = 4711 (om hashindex på Anr) villkor: T.A > C, inga index eller sökordningar -> cost = b, fanout = r/2 SQL-exempel: select * from A where Lön < 2000 P-M/R-boken skriver SELECTI för indexerad selektion Den sista har egentligen fanout = r i just vårt exempel (för jag la bara in löner under 2000) men det vet inte databashanteraren. (Eller gör den det???) 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. 5. Join-algoritmer Även join, sortering m fl operationer kostnadsuppskattas, olika för olika join- och sorteringsalgoritmer 5.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) } } } Exemplet med Gnesta-chefen: select Anamn from A, K where Anr = Chef and Kstad = 'Gnesta'; for each A as a { for each K as k { if (a.Anr = k.Chef and k.Kstad = 'Gnesta') { print a.Anamn } } } Det här var (ungefär i alla fall) en nested-loop-join: for each K as k { if (k.Kstad = 'Gnesta') { for each A as a { if (a.Anr = k.Chef) { print a.Anamn } } } } (Men det finns ju ett index på Anr? Glöm det för tillfället.) Vi måste alltså läsa hela tabellen K (1000 rader, 25 block) OCH en gång för varje rad i K ska vi läsa hela tabellen A (1 000 000 rader, 25000 block) cost = antal block i T1 + antal RADER i T1 * antalet block i T2 Här: 25 + 1000 * 25000 = 25000025 fanout = ? Om vi gör tvärtom, loopar med A i yttre loopen och K i inre? cost = 25000 + 1 000 000 * 25 = 25025000 Det blir billigare att ha den stora tabellen i den inre loopen. 5.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 } } Exemplet med Gnesta-chefen igen: select Anamn from A, K where Anr = Chef and Kstad = 'Gnesta'; for each A as a { slå upp k.Chef = a.Anr i K via indexet ... -- Nej, det finns ju inget index på k.Chef! } Det här var (ungefär i alla fall) en nested-loop-join: for each K as k { if (k.Kstad = 'Gnesta') { slå upp a.Anr = k.Chef i A via indexet på a.Anr print a.Anamn } } Vi måste alltså läsa hela tabellen K (1000 rader, 25 block) (och filtrera på Gnesta), OCH en gång för varje rad i K (som matchar Gnesta) ska vi göra en indexuppslagning i A Kommandot "explain" i MySQL --------------------------- mysql> explain extended select Anamn -> from A, K -> where Anr = Chef -> and Kstad = 'Gnesta'; +----+-------------+-------+--------+---------------+---------+---------+-------------+------+----------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+--------+---------------+---------+---------+-------------+------+----------+-------------+ | 1 | SIMPLE | K | ALL | NULL | NULL | NULL | NULL | 957 | 100.00 | Using where | | 1 | SIMPLE | A | eq_ref | PRIMARY | PRIMARY | 4 | test.K.Chef | 1 | 100.00 | | +----+-------------+-------+--------+---------------+---------+---------+-------------+------+----------+-------------+ 2 rows in set, 1 warning (0.03 sec) Kommandot "set explain on" i Mimer ---------------------------------- SQL>set explain on; SQL> select Anamn SQL& from A, K SQL& where Anr = Chef SQL& and Kstad = 'Gnesta'; Start of explain result L1: Sequential read EXEMPEL.K, end of table goto end compare, no hit goto L1 Direct key lookup EXEMPEL.A, end of table goto L1 Record found, goto L1 end: End of explain result ANAMN ======================================== Jonas-Thomas Carlsson 1 row found SQL> 5.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) } } 5.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) } } 6. 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 7. Sökning i tillståndsrymden av möjliga exekveringsplaner för att hitta en billig Ofta en trädsökning 7a. Fullständig (exhaustive) sökning (en del planer kan skippas om garanterat dyrare) - men komplicerade frågor ger väldigt många planer - O(n!) där n = frågestorleken 7b. En del planer kan skippas om de garanterat är dyrare: dynamic programming - snabbare, men har samma komplexitet som fullständig sökning 7c. "Slumpmässiga", "heuristiska" algoritmer (ex: ren slump, många slump + hill climbing, simulated annealing) 1! = 1 2! = 2 3! = 6 5! = 120 10! = 3628800 13! = 6227020800 (32-bit integer overflow) 20! = 2432902008176640000 (en per klockcykel i 4 GHz = 19 år)