Aksessmetoder, sortering, join-algoritmer

Fra SQL-tekst til resultat

Når du sender en SQL-spørring til databasen, går den gjennom en kjede av komponenter før den faktisk berører data på disk. Hvert ledd har en jobb — og kapittel 7 handler om de siste leddene: hvordan data hentes, sorteres og joines.

Optimizeren regnes som «black art» (mørk kunst — den er notorisk vanskelig å lage god) fordi den vurderer alle joinrekkefølger, alle aksessmetoder, alle sorterings­strategier og velger billigst plan. Vi skal forstå hvilke valg den har, og hvorfor de koster det de koster.

Fire måter å lagre én tabell

Hvor billig en spørring kan kjøres henger på hvordan tabellen er lagret. Pensum bruker fire varianter, og vi skal gjenta det samme eksemplet på alle for å se kostnadsforskjellen.

Liten ordliste: Clustered betyr at radene er fysisk lagret i indeksens nøkkelorden — bladene er tabellen. Unclustered betyr at indeksen peker til rader som ligger spredt i en separat heap-fil. Detaljene er forklart i kap. 6, men disse to ordene dukker opp overalt under.

Eksempel: tabellen Employee

• 100 000 rader, hver er 80 bytes
• Blokkstørrelse: 4 KiB = 4096 bytes
• Skjema: Employee(empno, name, age, depno, salary)

Aksessveiene

• Filscan / tabellscan — les alle blokker i filen. Brukes når det ikke finnes nyttig indeks, eller når vi henter «mye» av tabellen uansett.
• Indeksscan — gå sekvensielt gjennom bladnivået i en indeks. Nyttig f.eks. for SELECT * med sortert resultat.
• Range-scan — gå ned i B+-treet til startnøkkelen, og scan bladene sidelengs til endenøkkelen. Bruk pekere til å hente rader om indeksen er unclustered.
• Indeks-lookup — direkte oppslag på én nøkkel: ned i treet (eller ett hashoppslag), hent rad.

Notasjon — variabler du ser i alle formlene

Før vi regner kostnader trenger vi navn på tingene. Disse seks variablene dukker opp på tvers av hele kapittelet — alle senere formler bygger på dem. Bli komfortabel med dem nå, så slipper du å oversette på nytt under hver formel.

• |R| — antall rader i tabellen R
• b — antall blokker tabellen tar på disk
• bf — blocking factor: antall rader som får plass i én blokk
• h — høyden til et B+-tre (antall interne nivåer over bladene)
• V(A, R) — antall distinkte verdier av attributt A i R (eks: V(depno, Employee) = antall ulike avdelinger)
• sf — selektivitetsfaktor: andel av tabellen som overlever et predikat (mellom 0 og 1)

Kostnadsformler pr. aksessvei — med utledning

Tabellen over viste tall for Employee. Formlene under regner det samme på nye tall — det er disse du faktisk bruker når eksamensoppgaven kommer med andre tabellstørrelser. Hver formel har en kort utledning slik at du forstår hvorfor den er som den er, ikke bare at den finnes.

Den samme spørringen, ulik lagring

Nå sammenligner vi: hva koster SELECT-en med predikatet WHERE key = c, WHERE key > c og full SELECT * på de fire lagrings­alternativene? Tabellen er den samme Employee-eksemplet (100 000 rader, 1961 heap-blokker).

Sortering når RAM ikke holder

Mange spørringer trenger sortert resultat: ORDER BY, GROUP BY, DISTINCT, og senere sort-merge join (se §6 nedenfor). Vanlig sortering (quicksort, mergesort i RAM) forutsetter at hele lista er i minnet — men en stor tabell er per definisjon ikke det. Vi må sortere bit-for-bit og bruke disk som arbeidsplass, helst uten å lese samme blokk altfor mange ganger.

External merge sort («ekstern» fordi den går utenfor RAM, til disk) løser dette i to faser:

1. Initialfase: Les så mye som får plass i bufferet, sorter internt med vanlig sort, skriv ut som en sortert «run». Gjenta til hele tabellen er prosessert.
2. Mergefase: Flett flere runs om gangen ved å sammenligne front-verdiene — siden inputene er sorterte, holder det med én peker per run. Gjenta inntil vi har én sortert fil.

Notasjon (les denne først)

• b = antall datablokker i tabellen
• n_B = antall blokker tilgjengelig i bufferet
• n_R = antall sorterte «runs» etter initialfasen
• d_M = mergegrad — hvor mange runs vi kan flette sammen i ett pass

Formler — og hvorfor de stemmer

Eksempel fra pensum

Sett n_B = 5, b = 1024 (en tabell på 1024 blokker, buffer på 5).

• n_R = ⌈1024/5⌉ = 205 initialruns (vi får 205 «bufferets» med data å sortere internt)
• d_M = 5 − 1 = 4 (én slot reservert til output)
• Antall mergepasser = ⌈log₄(205)⌉ = 4 (205 → 52 → 13 → 4 → 1)
• Total I/O = 2·1024·(1+4) = 10 240 blokker (initial + 4 merge = 5 passer, hver à 2·1024)

Merk hvor mye buffer-størrelsen betyr: med n_B = 257 ville d_M = 256 og vi hadde merget alt i ett pass — total I/O 2·1024·2 = 4096. Det er én av grunnene til at databaser allokerer mest mulig RAM til sort-bufferne.

Steg-for-steg-animasjon

Et lite eksempel: b = 6 blokker, hver med 2 verdier; n_B = 3. Da er n_R = 2, d_M = 2, og vi trenger akkurat ett mergepass. Total I/O = 2·6·(1+1) = 24 blokk-aksesser. Klikk «Neste steg» for å se hva som skjer i bufferet og hvordan I/O-telleren stiger — eller «Spill auto» for å la den gå selv.

For hver rad i ytre … for hver rad i indre

Den mest grunnleggende join-algoritmen, og — som pensum understreker — ofte den raskeste når en av tabellene er liten eller når vi har en god indeks på indre.

Block nested loop

I praksis sammenligner vi ikke én rad om gangen; vi laster en bunke blokker fra ytre tabell inn i bufferet, og scanner indre én blokk om gangen for hver bunke.

Eksempel fra pensum

• Department = 5 blokker (500 rader, 100 pr. blokk)
• Employee = 1000 blokker
• Buffer = 5 blokker (3 til ytre, 1 til indre, 1 til output)
• Spørring: Employee ⋈ Department WHERE dname='Sales' (⋈ = naturlig join — slå sammen rader der join-attributtet, kolonnen vi joiner på, er likt)

Animasjon — nested loop med matching

To små tabeller, R og S. Vi joiner på lik nøkkel. Klikk «Neste» og se hvordan ytre står stille mens indre scanner — og hvordan to vinduer av matchende rader fanges opp.

Index nested loop (J2)

Hvis indre tabell har en indeks på join-attributtet, hopper vi over hele indre-scanningen og slår opp direkte for hver ytre rad. Vi bytter altså ut én scan av S pr. ytre bunke mot ett indeks-oppslag pr. ytre rad. Det blir billig når R er liten i radantall, og indeksen er klargjort.

Worked example — J1 vs J2 på samme data

Samme join, samme tabeller — kun algoritmen varierer. Vi har R = 50 blokker (1000 rader), S = 500 blokker, n_B = 5, og det finnes en clustered B+-tre på S.pk med høyde h_S = 2 (3-nivåtre).

• J1 (block NL), R ytre:  50 + ⌈50/3⌉·500 = 50 + 17·500 = 8550 blokker
• J2 med clustered S.pk:  50 + 1000·(2 + 1) = 50 + 3000 = 3050 blokker

J2 vinner med 65 % færre I/O — fordi 1000 indeks-oppslag à 3 blokker er mye billigere enn 17 fulle scans av en 500-blokkers tabell.

Men hvor er kryssingspunktet? Hvis R hadde vært 100 000 rader, ville J2 kostet 50 + 300 000 = 300 050 — verre enn J1 (som vokser sakte i ytre). Generelt vinner J2 når |R| · (h_S + 1) < ⌈b_R/(n_B − 2)⌉ · b_S. Venstre side vokser lineært med |R|; høyre side vokser med b_R men er begrenset av b_S. Når |R| er stor nok til at venstre side overstiger høyre, snur dominansforholdet — og optimizeren bytter algoritme.

Sort-merge og hash join — med formler

Pensum behandler nested loop i detalj. De to neste — sort-merge (J3) og partition-hash (J4) — nevnes ofte «konseptuelt», men eksamen kan be deg sammenligne kost mellom dem. Da trenger du formlene. Begge bygger på byggesteiner du allerede kan: J3 bruker external merge sort fra §04, og J4 minner om en grov hashing-strategi som speiler statisk hash-fil fra kap. 6.

Sort-merge join (J3)

Sorter begge tabellene på join-attributtet, og gå parallelt gjennom dem med to pekere. Når en peker leser et match, lar vi den andre stå stille til alle matchene er parret. Effektivt fordi sortert input gjør at vi aldri må gå tilbake — flettingen er én lineær gjennomgang.

Eksempel — koblet til external merge sort

R = 100 blokker, S = 500 blokker, n_B = 6 ⇒ d_M = 5.

• sortkost(R):  n_R = ⌈100/6⌉ = 17,  passes = ⌈log₅(17)⌉ = 2  ⇒ 2·100·(1+2) = 600
• sortkost(S):  n_R = ⌈500/6⌉ = 84,  passes = ⌈log₅(84)⌉ = 3  ⇒ 2·500·(1+3) = 4000
• flettetrinnet: 100 + 500 = 600
• Total: 600 + 4000 + 600 = 5200 blokker

Hvis begge alt var sortert: cost = 0 + 0 + 600 = 600. Faktor 8.7 forskjell. Det er nettopp derfor query-planlegging belønner planer som leverer sortert output billig (clustered indeks, eller en tidligere sortering som kan gjenbrukes).

Partition-hash join (J4)

Hash begge tabeller på join-attributtet — alle rader med samme hash-verdi havner garantert i samme partisjon (uansett hvilken tabell de kom fra). Innenfor en partisjon: bygg en hash-tabell i RAM på den minste siden (build-fasen), scan den andre siden og slå opp mot hash-tabellen (probe-fasen). Når en partisjon er liten nok til å få plass i RAM blir join-en innenfor den «gratis» — vi slipper både sortering og re-scan.

Eksempel — samme tall, ny algoritme

Samme R = 100, S = 500: cost = 3·(100 + 500) = 1800 blokker. Mye billigere enn J3 (5200) i dette scenarioet, fordi sortering var dyrt med så lite buffer (n_B = 6). Hadde n_B vært 30 ville J3 kostet bare ett pass og kommet på samme nivå som J4.

NTNUs Kjell Bratbergsengen er pioner på partition-hash join (publisert på VLDB-konferansen — Very Large Data Bases — i 1984).

Beslutningstabell — når vinner hvilken?

Hvordan optimizeren gjetter

Optimizeren sammenligner planer uten å kjøre dem. Den må estimere kost basert på statistikk lagret i SQL-dictionaryet (databasens metadata-katalog — der skjema, indekser og slik statistikk holdes). Denne paragrafen forklarer hvordan den gjetter — selve regnemaskineriet bak alle kostnadstallene vi har sett til nå.

Selektivitetsfaktor — andelen som overlever et predikat

Selektivitet er nøkkelen til alle kostnadsestimat. Hvert predikat (WHERE depno = 5, WHERE alder > 60) reduserer antall rader som går videre. Optimizeren tildeler hvert predikat en sf mellom 0 og 1 — andelen rader som matcher — og bruker den til å estimere både output-størrelse og hvilken aksessmetode som vinner. Hvorfor det er kritisk: alle formlene i §02–§06 har sf, |R| eller matches i seg. Disse beregnes alle fra selektivitet — det er den ene knaggen optimizeren lener seg på når den velger plan.

Statistikk i SQL-dictionaryet

• For hver tabell: antall rader, antall blokker.
• For hver indeks: antall distinkte nøkkelverdier, antall blokker, histogrammer (verdifordelinger).
• For hvert B+-tre: trehøyde, LowKey (laveste forekommende nøkkel), HighKey (høyeste), antall blokker.

Med disse tallene kan optimizeren estimere antall blokk-aksesser for hver kandidatplan og velge den billigste.

EXPLAIN i MySQL

Når noe går tregt, er EXPLAIN verktøyet for å se hva optimizeren faktisk har valgt — uten å kjøre spørringen.

mysql> explain select * from reg natural join loper;
+----+-------------+-------+------+---------+------+----------+---------+
| id | select_type | table | type | key     | rows | filtered | Extra   |
+----+-------------+-------+------+---------+------+----------+---------+
|  1 | SIMPLE      | loper | ALL  | PRIMARY |    3 |   100.00 | NULL    |
|  1 | SIMPLE      | reg   | ALL  | NULL    |   10 |    10.00 | Using   |
|    |             |       |      |         |      |          | join    |
|    |             |       |      |         |      |          | buffer  |
+----+-------------+-------+------+---------+------+----------+---------+

type = ALL betyr full table scan. MySQL leser tabellene i den oppgitte rekkefølgen og bruker en intern join-buffer (en enkel form for hash join) når ingen indeks er tilgjengelig.

Slik angriper du oppgaven

Eksamen tester sjelden ett enkelt konsept — den ber deg ofte regne totalkostnaden for en plan, eller velge mellom 2–3 planer. Da må du jobbe deg gjennom verktøykassen i en bestemt rekkefølge. Denne paragrafen samler alt fra §02–§07 til én oppskrift, ett komplett worked example, og et formelark for raskt oppslag.

Pedagogisk poeng: oppskriften går «utenfra og inn» — først filtrerer vi (steg 2–3), så kombinerer (steg 4), så ordner (steg 5). Det speiler nøyaktig hvordan optimizeren tenker, og hvordan den fysiske planen er strukturert som et tre nedenfra og opp.

Komplett worked example

La oss kjøre sjekklisten på en realistisk oppgave — én som kombinerer aksess, join, sortering, og selektivitet. Følg med på hvert steg.

SELECT e.name
FROM Employee e JOIN Department d ON e.depno = d.depno
WHERE d.dname = 'Sales'
ORDER BY e.name;

Steg 1–2: selektivitet og output-størrelser

• WHERE d.dname = 'Sales': sf = 1/V(dname, Dept) = 1/50 = 0.02 ⇒ 1 rad ut av Department.
• Etter join: hver Department-rad matcher i snitt |Employee|/V(depno, Employee) = 100 000/50 = 2000 Employee-rader ⇒ join-output ≈ 2000 rader.

Vi vet allerede før vi regner kost at sluttresultatet bare er 2000 rader. Det er en sterk hint om at vi vil unngå å lese hele Employee om mulig.

Steg 3: aksessvei pr. tabell

• Department: ingen indeks ⇒ filscan = 5 blokker. Vi filtrerer på dname = 'Sales' mens vi scanner.
• Employee: hvilken aksessvei vi bruker avhenger av join-algoritmen — derfor regnes den i steg 4 sammen med joinen.

Steg 4: join-algoritme

Department er liten ⇒ ytre. Etter filtrering har vi 1 rad (≈ 1 blokk i mellomresultat). Vi sammenligner alle fire algoritmer:

• J1 (block NL), filtrert Department ytre, Employee indre:  5 (les Dept) + ⌈1/8⌉·1961 = 5 + 1961 = 1966. Kun én scan av Employee fordi ytre passer i én buffer-bunke.
• J2 med unclustered indeks på Employee.depno:  ett oppslag pr. ytre rad. matches_S = 2000. 5 + 1·(2 + 1 + 2000) = 2008. Litt verre — fordi 2000 RID-hopp er mye når indeksen er unclustered.
• J3 sort-merge: må sortere Employee. d_M = 9, n_R = ⌈1961/10⌉ = 197, passes = ⌈log₉(197)⌉ = 3 ⇒ sortkost = 2·1961·4 = 15 688. Verre med god margin — sortering er ikke verdt det her.
• J4 partition-hash: 3·(5 + 1961) = 5898. Også verre — fast 3 passes-kost slår dårlig ut når en side er bittesmå (J1 utnytter dette bedre).

Vinner: J1 med 1966 blokker. Pedagogisk poeng: når én side er bittesmå (1 rad etter filtrering!), faller alle de «smarte» algoritmene gjennom — den enkleste vinner. Liten ytre × stor indre × ingen revisning er nested loops naturlige hjem.

Steg 5: ORDER BY e.name

Output er 2000 rader. Forutsatt 100 rader pr. blokk ⇒ ~20 blokker. Sortering: n_R = ⌈20/10⌉ = 2, passes = ⌈log₉(2)⌉ = 1, sortkost = 2·20·2 = 80 blokker.

Steg 6: totalkostnad

Hva-hvis-analyse: hvis Employee.depno hadde vært clustered i stedet for unclustered, ville J2 kostet 5 + 1·(2 + 1) = 8 for å finne riktig blader, pluss å lese 2000-rad-segmentet ≈ 39 sammenhengende blokker — totalt rundt 50 blokker. Det er en faktor 40 forskjell. Det er denne sensitiviteten — at clustering på riktig kolonne kan endre kostnaden så dramatisk — som gjør indeks-design så viktig under databasedesign.

Formelark — alt på én side

For repetisjon rett før eksamen — alle formler i kapittelet samlet, slik at du kan bla rett til den du trenger. Ikke en erstatning for forståelsen, men praktisk når du jobber gjennom en oppgave under tidspress.

Test deg selv på hele kapittelet

Blandet vanskelighet. Klikk «Se svar» når du har tenkt.