Aksessmetoder, sortering, join-algoritmer
Hva skjer egentlig mellom SELECT … og resultatet? Vi følger en spørring fra parser til disk — og regner I/O-kost for hvert valg underveis.
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.
1 · Parser
SQL-tekst → algebraisk tre. Sjekker syntaks og slår opp tabeller i SQL-dictionary.
2 · Optimizer
Genererer flere planer, leser statistikk, velger den med lavest forventet I/O-kost.
3 · Executor
Kjører plan-treet rotnoden ned. Bruker aksessmetoder mot lagring.
4 · Storage
Heap-fil, B+-tre, hash-fil. Leverer blokker via buffer-poolen.
Optimizeren regnes som «black art» — den vurderer alle joinrekkefølger, alle aksessmetoder, alle sorteringsstrategier og velger billigst plan. Vi skal forstå hvilke valg den har, og hvorfor de koster det de koster.
Alt måles i blokk-I/O. RAM-operasjoner regnes som «gratis» sammenlignet med å lese en blokk fra disk. Derfor handler så mye av kapittelet om å minimere antall blokker som leses og skrives.
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.
Eksempel: tabellen Employee
- 100 000 rader, hver er 80 bytes
- Blokkstørrelse: 4 KiB = 4096 bytes
- Skjema:
Employee(empno, name, age, depno, salary)
| Lagring | Records/blokk | Blader | Indeks-blokker | Totalt |
|---|---|---|---|---|
| Heap-fil | ⌊4096/80⌋ = 51 | ⌈100 000/51⌉ = 1961 | — | 1961 |
| Clustered B+-tre | ⌊4096·⅔/80⌋ = 34 | ⌈100 000/34⌉ = 2942 | 13 + 1 = 14 | 2956 |
| Heap + unclustered B+ | 170 (i indeks) | 589 (indeksblader) | 3 + 1 = 4 | 1961 + 593 |
| Clustered hash | ⌊4096·0.8/80⌋ = 40 | ⌈100 000/40⌉ = 2500 | — | 2500 |
⅔-faktoren for B+-tre kommer av at noder typisk er to-tredjedeler fulle. Hash bruker 80 % fyllgrad.
De fire aksessmetodene
- Full table scan — les alle blokker. Brukes når det ikke finnes nyttig indeks, eller når vi henter «mye» av tabellen uansett.
- Index scan — gå ned i B+-treet til riktig blad, bruk pekere til å lese radene fra heap.
- Index-only scan — alle kolonnene som trengs ligger i indeksen selv. Vi slipper å besøke heap-filen.
- Bitmap scan — bygg en bitmap over RID-er fra én eller flere indekser, sorter, slå opp i datafilen i blokk-rekkefølge. Viktig for «AND»-betingelser med flere indekser.
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 lagringsalternativene? Tabellen er den samme Employee-eksemplet (100 000 rader, 1961 heap-blokker).
| Lagring | Strategi | Blokker lest |
|---|---|---|
| Heap | Full scan | 1961 |
| Clustered B+ | Tre nivåer ned, så scan blader | 2 + 2942 = 2944 |
| Heap + unclustered | Bare scan heap (indeksen hjelper ikke her) | 1961 |
| Clustered hash | Scan hele hash-fila | 2500 |
Heap vinner — ingen indeks-overhead, og ekstra utfylling i B+/hash blir bare ekstra arbeid når vi vil ha alt likevel.
| Lagring | Strategi | Blokker lest |
|---|---|---|
| Heap | Lineær scan, gj.snitt halvparten | ≈ 981 |
| Clustered B+ | Tre nivåer ned (+ binærsøk i blokk) | 3 |
| Heap + unclustered | 3 ned i indeks + 1 i heap | 4 |
| Clustered hash | Hash → blokk (+ litt overflow) | ≈ 1.2 |
| Lagring | Strategi | Blokker lest |
|---|---|---|
| Heap | Full scan (ingen sortering å utnytte) | 1961 |
| Clustered B+ | Ned i tre + scan 20 % av bladene | 2 + 0.2·2942 = 591 |
| Heap + unclustered | 2 + 118 + opptil 20 000 RID-er ⟶ velg heller heap-scan! | 1961 (ikke indeks) |
| Clustered hash | Hash bevarer ikke orden — full scan | 2500 |
Med unclustered indeks og bred range-treff kan optimizeren ende opp med å lese hver datablokk flere ganger. Da er en ren heap-scan nesten alltid raskere — og dette er en sentral grunn til at clustered versus unclustered betyr så mye for ytelsen.
salary, og kjører WHERE salary > 0 (alle ansatte tjener noe). Hvorfor velger optimizeren full table scan framfor indeksen?Sortering når RAM ikke holder
Mange spørringer trenger sortert resultat: ORDER BY, GROUP BY, DISTINCT, sort-merge join. Når tabellen er større enn RAM, bruker vi external merge sort. Idéen er to faser:
- Initialfase: Les inn så mye som får plass i bufferet, sorter internt, skriv ut som en sortert «run».
- Mergefase: Merge flere runs om gangen til vi har én sortert fil.
Formler
- Antall initialruns:
n_R = ⌈b / n_B⌉(b = antall datablokker, n_B = antall bufferblokker) - Mergegrad:
d_M = n_B − 1(én buffer reserveres til output) - Antall mergepasser:
⌈log_(d_M)(n_R)⌉ - Total I/O:
2b · (1 + antall mergepasser)
Eksempel fra pensum
n_B = 5, b = 1024. Da er n_R = ⌈1024/5⌉ = 205, og d_M = 4. Antall mergepasser = ⌈log₄(205)⌉ = 4. Total I/O = 2·1024·(1+4) = 10 240 blokker.
Hvert pass leser og skriver hele datasettet — derfor 2b. En større buffer gir høyere mergegrad, færre passer og mindre I/O. Det er ikke RAM-tregheten som dominerer, men antall ganger vi må røre disken.
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'
| Strategi | Regnestykke | Blokker |
|---|---|---|
| Department ytre, Employee indre | 5 + ⌈5/3⌉·1000 = 5 + 2·1000 | 2005 |
| Employee ytre, Department indre | 1000 + ⌈1000/3⌉·5 = 1000 + 334·5 | 2670 |
| Filtrer Department først (én rad) | 5 (lese Dept) + 1000 (Employee én gang) | ≈ 1001 |
Liten tabell utenfor, stor tabell innenfor. Antall passes over indre tabell er ⌈|ytre| / (n_B − 2)⌉ — minimere dette betyr å minimere ytre.
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.
R (ytre)
S (indre)
Index nested loop
Hvis indre tabell har en indeks på join-attributtet, hopper vi over hele scanningen og slår opp direkte. Da blir kostnaden ca. |R| · (kost pr. oppslag), ofte 3–4 blokker pr. rad i R. Dramatisk billigere når R er liten.
⌈10/(n_B−2)⌉ ganger. Hadde vi snudd, måtte vi scannet den lille ⌈10000/(n_B−2)⌉ ganger — flere hundre passer.Sorter begge, gå parallelt
Når begge tabellene er store, eller allerede sortert på join-attributtet, blir to-pekere-strategien attraktiv. Vi sorterer R og S én gang (ofte med external merge sort), og går så gjennom dem samtidig.
Algoritmen
- Sorter R på
r.k, sorter S pås.k. - To pekere i på R, j på S, begge starter på 0.
- Hvis
R[i].k < S[j].k→ i++. Hvis > → j++. Hvis = → emit, og avanser likt. - Stopp når en av listene er tom.
R sortert på k
S sortert på k
Når lønner det seg?
- Når begge tabellene allerede er sortert (f.eks. fra clustered indeks) — da er kostnaden bare scan.
- Når begge er store og join-resultatet skal sorteres uansett.
- Mindre bra hvis kun én tabell er liten — da er nested loop med indeks oftest billigere.
Bygg en hash-tabell, probe mot den
Hvis ingen er sortert og vi ikke har en god indeks på indre, kan hash join være billigste valg.
Build + probe
- Build phase: Velg den minste tabellen (build side). Les den én gang og bygg en hash-tabell på join-attributtet i RAM.
- Probe phase: Les den større tabellen (probe side) én blokk om gangen. For hver rad: hash join-verdien, slå opp i bucket, emit alle treff.
R (liten — build)
Hash-tabell
S (stor — probe)
Grace hash join
Når den lille tabellen ikke får plass i RAM, partisjonerer vi begge tabeller med samme hash-funksjon i en forfase. Da er det nok å ha én partisjon i minnet om gangen — vanlig hash join på hver partisjon. I/O-kost: 3·(|R|+|S|).
Hash er ofte raskere når én tabell er klart mindre, mens sort-merge skinner når begge er sortert eller når vi trenger sortert output uansett. Optimizeren regner kost for begge og velger.
R.x < S.y. Hvorfor?Hvordan optimizeren gjetter
Optimizeren sammenligner planer, men har ikke kjørt dem ennå. Den må estimere kost basert på statistikk. Hva har den å jobbe med?
Statistikk i SQL-dictionaryet
- n(R) — antall rader i R
- b(R) — antall blokker som inneholder R
- V(A, R) — antall distinkte verdier av attributt A i R
- min/max — for B+-indeksert attributt
- histogrammer — fordeling av verdier (bin-baserte estimater)
- Indeksinfo: høyde av B+-treet, om det er clustered, fyllgrad
Selektivitet
Selektivitet er andelen rader som passer et predikat. Optimizeren bruker enkle modeller:
WHERE A = c⇒ sel ≈ 1 / V(A, R)WHERE A > c⇒ sel ≈ (max − c) / (max − min)WHERE p₁ AND p₂⇒ sel ≈ sel(p₁) · sel(p₂) (antar uavhengighet)
Den enkle min/max-formelen feiler når data er skjev. Histogrammer deler verdiområdet i bins og lagrer telling pr. bin — selektiviteten regnes pr. bin og summeres. Det er hovedgrunnen til at ANALYZE i moderne databaser samler histogrammer.
ANALYZE for å oppdatere statistikk, eller sjekke om histogrammer er utdaterte.Be databasen vise planen
Når noe går tregt, er EXPLAIN det viktigste verktøyet. Den lar deg se eksakt hva optimizeren har valgt — uten å kjøre spørringen — og EXPLAIN ANALYZE kjører den i tillegg og rapporterer faktisk tid.
Eksempel-plan
HashJoin (cost=1245.00..1899.32 rows=4500) Hash Cond: (e.depno = d.dno) → SeqScan on employee e (cost=0..961 rows=100000) → Hash (cost=10.50..10.50 rows=1) → IndexScan using dept_name_idx on department d Index Cond: (dname = 'Sales')
Hvordan lese treet
- Rotnode er øverst og produserer det endelige resultatet.
- Innrykk = barn. Barna leverer rader til foreldrene.
costhar to tall: oppstart..total, i pseudo-units.rowser optimizerens estimat — sammenlign med faktisk fraANALYZE.
Det viktigste å sjekke i en EXPLAIN ANALYZE: store avvik mellom estimerte og faktiske rader. Et estimat på 10 rader som faktisk gir 100 000 betyr at planen er valgt på sviktende grunnlag — kjør ANALYZE på tabellen.
SeqScan på en tabell med 5 millioner rader, men du har en indeks på filterkolonnen. Hva kan være årsaken?WHERE upper(name)=…) hindrer indeksbruk.Test deg selv på hele kapittelet
Tolv blandet vanskelighetsspørsmål. Klikk «Se svar» når du har tenkt.
empno. Hvorfor velger optimizeren full table scan for WHERE empno > 80000 (20 % treff)?2b · (1 + #merge-passes) og ikke b · #passes?⌈|ytre| / (n_B−2)⌉.S ytre: 5000 + ⌈5000/10⌉·200 = 5000 + 500·200 = 105 000. R som ytre vinner.
city) = 50 distinkte byer. Estimer selektiviteten av WHERE city = 'Trondheim' uten histogram.rows=12 men actual rows=180000 for et SeqScan-trinn. Hva er konsekvensen lenger oppe i planen, og hva gjør du?ANALYZE table for å oppdatere statistikk, vurder histogram med flere bins, og se om predikatet bruker funksjon/cast som hindrer indeksbruk.Nå er du klar for kapittel 8 — Transaksjoner. Spørringer er bare halve historien; den andre halvparten er hvordan vi kjører flere spørringer samtidig uten å trampe på hverandre.