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