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:

Sök efter en turnering _v2 som har year = 1950, via index om det finns
Sök sen efter en match m som har played_in = turneringen _v2, via index om det finns
Hämta spectators för matchen m, kalla det för _v1
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:

Först kostnaden för att köra loophuvudet i den yttre loopen (svamp-loopen). Att hitta alla svampar i skogen tar, tänker vi oss, en tid som är proportionell mot antalet svampar. Låt oss anta att det finns 100 svampar i skogen, så vi säger att det tar 200 enheter tid att hitta alla svamparna. Vi räknar alltså med att det kostar 2 enheter tid att ta fram en svamp.
Sen kostnaden för att köra loophuvudet i den inre loopen (mask-loopen). Att hitta alla maskar i en svamp tar, tänker vi oss, en tid som är proportionell mot antalet maskar. Låt oss anta att det i genomsnitt finns 10 maskar i en svamp, så vi säger att det tar 20 enheter tid att hitta alla maskarna i svampen. Vi räknar alltså med att det kostar 2 enheter tid att ta fram en mask.
Och till sist antar vi att det tar 5 enheter tid att måla en mask gul.

Men det blir förstås fel att räkna ut den totala tiden som 200 + 20 + 5 = 225!

Loop-huvudet i den yttre loopen körs bara en gång, så den kommer verkligen att kosta 200.
Men den yttre loopen körs 100 gånger, för det fanns ju 100 svampar, så loop-huvudet i den inre loopen kommer att köras 100 gånger. Dess verkliga kostnad blir alltså 100 * 20 = 2000 enheter.
Och maskmålningen, som kostar 5 enheter, kommer att köras 1000 gånger, så dess verkliga kostnad blir 1000 * 5 = 5000 enheter.

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:

kostnad = 200, för det var ju kostnaden för att köra loophuvudet en gång
fanout = 100, för det är så många svampar som man hittar, och så många varv som kroppen på loopen sen ska köras
verklig kostnad = 200, för loophuvudet kostar ju 200, och ska köras en gång
total kostnad = 200, för än så länge är detta allt vi gjort
total fanout = 100, för det är ju de yttersta loopen, så kroppen ska köras totalt 100 gånger

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:

kostnad = 20, för det var ju kostnaden för att köra loophuvudet en gång
fanout = 10, för det är så många maskar man (i genomsnitt) hittar i en svamp, och så många varv som kroppen på loopen sen ska köras
verklig kostnad = 2000, för loophuvudet kostar ju 20, och ska köras 100 gånger (för total fanout från svamp-loopen är 100)
total kostnad = 2200, för vi har ju också kostnaden för den yttre loopens huvud
total fanout = 1000, för det var 10 maskar, men dessa 10 maskar finns i var och en av de 100 svamparna

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:

kostnad = 5, för det var ju kostnaden för att köra loophuvudet en gång
fanout = 1, i den mån man nu alls kan tala om fanout här
verklig kostnad = 5000, för funktionen kostar ju 5, och ska köras 1000 (för total fanout från mask-loopen är 1000)
total kostnad = 7200, för vi lägger till kostnaden 5000 till föregående totala kostnad, 2200
total fanout = 1000, i den mån man kan tala om fanout här

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:

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