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)