Databasteknik II: Några anteckningar om optimering i AMOS

En exempelfråga i AMOSQL: 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>
("RANKSORT", som returnerades från funktionen optmethod, är den optimeringsmetoder som användes innan man bytte till exhaustive.)

Vi "packar upp" de kedjade funktionerna, som year(played_in(m)), så vi bara får ett predikat (eller "funktionsanrop") i varje del av where-villkoret. Till exempel gör vi om

year(played_in(m))=1950
till
and played_in(m) = _v2
and year(_v2) = 1950
Som synes behövs det då extra variabler (_v2 ovan) för att koppla ihop villkoren. Så här blir den "uppackade" frågan:
select m
from match m, integer _v1, tournament _v2
where spectators(m) = _v1
and played_in(m) = _v2
and year(_v2) = 1950
and _v1 > 100000
AMOS översätter frågan till en Lisp-lista med de fyra villkoren ("predikaten"). Denna lista är indata till optimeringsfunktionen:
((#[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
Så här ser en korrekt optimerad exekveringsplan ut, och den ska vara utdata från optimeringsfunktionen:
((#[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
Planen är ett "program", som körs som nästlade loopar. Den betyder följande:
  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

Eller, om vi försöker vara tydligare:

1. Hitta alla turneringar som uppfyller villkoret year(turneringen) = 1950. För varje sådan turnering (låt oss kalla den _v2), gör följande:
Här inne är _v2 bunden, dvs den har ett värde.

2. Hitta alla matcher som uppfyller villkoret played_in(matchen) = _v2. För varje sådan match (låt oss kalla den m), gör följande:

Här inne är _v2 och m bundna, dvs de har värden.

3. Hitta alla heltal som uppfyller villkoret spectators(m) = heltalet. För varje sådant heltal (låt oss kalla det _v1), gör följande:

Här inne är _v2, m och _v1 bundna, dvs de har värden.

4. Kolla om _v1 > 100000. I så fall:

Ta med matchen m i resultatet.

För att vi ska kunna jämföra olika exekveringsplaner, och se vilken som är billigast (dvs snabbast), måste vi ha en kostnadsfunktion. Hur kan man räkna ut kostnaden (dvs tiden) för att köra den här planen?

Man kan jämföra med loopar i ett vanligt programmeringsspråk, som Java. Antag att skogen är full med svampar, som innehåller maskar. Vi ska hitta alla maskar som finns i skogen, och måla dem gula:

for (Svamp denna_svamp : hitta_alla_svampar_i_skogen()) {
    for (Mask denna_svamp : hitta_alla_maskar_i(denna_svamp)) {
        måla_masken_gul(denna_mask);
    }
}
Vad kostar detta? Jo: Men det blir förstås fel att räkna ut den totala tiden som 200 + 20 + 5 = 225!

Vi lägger till lite information i programmet, först om den yttre loopens huvud:

for (Svamp denna_svamp : hitta_alla_svampar_i_skogen()) {
        kostnad = 200, fanout = 100,
        verklig kostnad = 200,
        total kostnad = 200, total fanout = 100
    for (Mask denna_svamp : hitta_alla_maskar_i(denna_svamp)) {
        måla_masken_gul(denna_mask);
    }
}
Noteringarna med rött betyder: Sen den inre loopens huvud:
for (Svamp denna_svamp : hitta_alla_svampar_i_skogen()) {
        kostnad = 200, fanout = 100,
        verklig kostnad = 200,
        total kostnad = 200, total fanout = 100
    for (Mask denna_svamp : hitta_alla_maskar_i(denna_svamp)) {
            kostnad = 20, fanout = 10,
            verklig kostnad = 2000,
            total kostnad = 2200, total fanout = 1000
        måla_masken_gul(denna_mask);
    }
}
Noteringarna med blått betyder: Och till sist maskmålningsfunktionen:
for (Svamp denna_svamp : hitta_alla_svampar_i_skogen()) {
        kostnad = 200, fanout = 100,
        verklig kostnad = 200,
        total kostnad = 200, total fanout = 100
    for (Mask denna_svamp : hitta_alla_maskar_i(denna_svamp)) {
            kostnad = 20, fanout = 10,
             verklig kostnad = 2000,
            total kostnad = 2200, total fanout = 1000
        måla_masken_gul(denna_mask);
                kostnad = 5, fanout = 1,
                verklig kostnad = 5000,
                total kostnad = 7200, total fanout = 1000
    }
}
Noteringarna med grönt betyder: Kostnaden för att köra den här Java-snutten är alltså 7200.

Men kom ihåg! Detta tal är inte den verkliga, uppmätta tiden från en körning, utan vad vi uppskattar att tiden kommer att bli. Det kan vara fel, till exempel om det visar sig att det genomsnittliga antalet maskar i en svamp inte alls var 10. Det är inte heller någon riktig tid, mätt i sekunder eller tusendelar eller klockcykler, utan mätt i någon "kostnadsenhet" som vi inte säger något närmare om vad den egentligen motsvarar. Vi ska bara ha uppskattningen så vi kan jämföra olika planers kostnad, och välja den som vi uppskattar blir billigast!

Åter till exekveringsplanen för frågan om vilka matcher från 1950 som hade mer än 100 000 åskådare! Precis som vi gjorde med Java-programmet lägger vi till noteringar, först för "huvudet på den yttersta loopen", dvs det första predikatet:

1. Hitta alla turneringar som uppfyller villkoret year(turneringen) = 1950. För varje sådan turnering (låt oss kalla den _v2), gör följande:
kostnad = 2*14 = 28, fanout = 1,
verklig kostnad = 28,
total kostnad = 28, total fanout = 1
Här inne är _v2 bunden, dvs den har ett värde.

2. Hitta alla matcher som uppfyller villkoret played_in(matchen) = _v2. För varje sådan match (låt oss kalla den m), gör följande:

Här inne är _v2 och m bundna, dvs de har värden.

3. Hitta alla heltal som uppfyller villkoret spectators(m) = heltalet. För varje sådant heltal (låt oss kalla det _v1), gör följande:

Här inne är _v2, m och _v1 bundna, dvs de har värden.

4. Kolla om _v1 > 100000. I så fall:

Ta med matchen m i resultatet.

Om vi tittar i databasen, eller i filen med AMOSQL-kod som skapar den, ser vi att det finns 14 turneringar. Om det fanns ett index på år för turneringar, skulle man kanske snabbt kunna hitta de turneringar som spelades 1950, men nu måste vi gå igenom var och en av de 14 turneringarna, och kolla om den spelades 1950. Vi antar att det kostar 2 enheter tid att besöka en turnerings och köra en funktion. Alltså blir kostnaden av det första predikatet 28. Eftersom bara en turnering spelades 1950, blir fanout 1.

Vi behöver inte räkna ut kostnaden och fanouten för ett steg själva. AMOS har en inbyggd funktion som heter simple-pred-cost, som returnerar kostnaden och fanouten. För det första predikatet ovan, får vi alltså 14 och 1 som svar från den funktionen.

simple-pred-cost tar två argument: dels själva predikatet, och dels en lista som talar om vilka av de två argumenten som är bundna, dvs vilka variabler som man redan vet värdena på. Kostnaden, och fanouten, blir nämligen helt olika beroende på vilka variabelvärden som man redan vet!

Ta till exempel predikatet year(x) = y. Om man (som i planen ovan) vet årtalet y, och söker matchen x, måste man gå igenom alla de 14 matcherna, hämta årtalet för var och en, och behålla de matcher där årtalet var de sökta. Kostnaden blir 28.

Om man i stället vet matchen x, och söker årtalet y, räcker det med att hämta årtalet för den sökta matchen. Kostnaden blir (ungefär) 2.

Vi fortsätter och kommenterar de följande stegen i exekveringsplanen med samma noteringar om kostnad och fanout. Vi använder AMOS-funktionen simple-pred-cost för att få (den beräknade) kostnaden och fanouten för varje steg i planen. Hela tiden blir total fanout lika med steges fanout multiplicerat med föregående totala fanout. Den verkliga kostnaden blir stegets kostnad gånger föregående totala fanout. Den totala kostnaden blir föregående totala kostnad, plus stegets verkliga kostnad.

1. Hitta alla turneringar som uppfyller villkoret year(turneringen) = 1950. För varje sådan turnering (låt oss kalla den _v2), gör följande:
kostnad = 2*14 = 28, fanout = 1,
verklig kostnad = 28,
total kostnad = 28, total fanout = 1
Här inne är _v2 bunden, dvs den har ett värde.

2. Hitta alla matcher som uppfyller villkoret played_in(matchen) = _v2. För varje sådan match (låt oss kalla den m), gör följande:

kostnad = 2*51 = 102, fanout = 5.1,
verklig kostnad = 1*102 = 102,
total kostnad = 28+102 = 130, total fanout = 1*5.1 = 5.1
Här inne är _v2 och m bundna, dvs de har värden.

3. Hitta alla heltal som uppfyller villkoret spectators(m) = heltalet. För varje sådant heltal (låt oss kalla det _v1), gör följande:

kostnad = 1.98, fanout = 0.99,
verklig kostnad = 5.1*1.98 = 10.10,
total kostnad = 130+10.10 = 140.10,
total fanout = 5.1*0.99 = 5.05
Här inne är _v2, m och _v1 bundna, dvs de har värden.

4. Kolla om _v1 > 100000. I så fall:

kostnad = 0.5, fanout = 0.4,
verklig kostnad = 5.05 * 0.5 = 2.52,
total kostnad = 140.10 + 2.52 = 142.62
total fanout = 5.05*0.4 = 2.02
Ta med matchen m i resultatet.

Den här exekveringsplanen förväntas alltså kosta 142.62 enheter att köra, och förväntas ge 2.02 matcher i resultatet.

Ungefär ovanstående sa jag på föreläsningen, och ritade som en bild på tavlan:

Ett foto på tavlan från föreläsningen


Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se), 28 februari 2008