Kapittel 7 · Forelesning 13 · Del 2

Spørringsutføring

Aksessmetoder, sortering og join-algoritmer — hvordan en SELECT faktisk blir kjørt mot disk.

Helhetsbilde

Fra plan til resultat

I forrige kapittel så vi hvor data ligger — heap, B+-tre, hash. Nå ser vi hvordan databasen faktisk plukker dem opp og setter dem sammen.

Optimizer velger plan, executor kjører den
Aksessmetoder: full scan, index scan, index-only scan, bitmap scan
External merge sort — sortering når data er større enn RAM
Tre join-algoritmer: nested loop, sort-merge, hash join — hver med sine kostnadsprofiler
EXPLAIN viser den valgte planen og hjelper med feilsøking

Slides

Se også queries.pdf for figurer og eksempelplaner.

Læringsmodul

Utforsk kapittelet

Innholdssiden er bygget som en gjennomgang med interaktive figurer og innebygde sjekkspørsmål mellom hver del. Bruk «Neste steg»-knappene i animasjonene for å følge merge sort, nested loop, sort-merge og hash join trinn for trinn.

Aksessmetoder, sortering, join-algoritmer

Bratsberg kap. 12–14 · 9 seksjoner · 4 animasjoner · innebygde quizer

→

Nøkkelbegreper

Vokabular du må kunne

Begrep	Forklaring
Aksessmetode	Hvordan executoren henter rader: full scan, index scan, index-only, bitmap.
Selektivitet	Andel rader som tilfredsstiller et predikat. Brukes til å estimere kost.
External merge sort	Sortering på disk i to faser: initialfase + merge. n_R, d_M, antall passer.
Block nested loop join	Ytre tabell i biter inn i bufferet; indre scannes per bit.
Sort-merge join	Sorter begge sider, gå gjennom med to pekere.
Hash join	Bygg hash på liten side, probe stor side.
Grace hash join	Partisjoner begge tabeller når hash-tabellen ikke får plass i RAM.
EXPLAIN	Viser plantreet uten å kjøre. EXPLAIN ANALYZE kjører og rapporterer faktisk tid.
Histogram	Statistikk-struktur som lagrer fordelingen av verdier — bedre selektivitetsestimater enn min/max.

Test deg selv

Hurtig sjekk på de viktigste konseptene. Den fyldige sluttquizen ligger på innholdssiden.

Spørsmål 1 · Lett

Hva er forskjellen på en optimizer og en executor i et DBMS?

Optimizeren velger en utføringsplan basert på statistikk og kostnadsestimater. Executoren kjører den valgte planen ved å kalle aksessmetoder mot lagring og kombinere resultater.

Spørsmål 2 · Lett

Nevn de fire grunnleggende aksessmetodene.

Full table scan, index scan, index-only scan, bitmap scan.

Spørsmål 3 · Middels

Hvorfor er clustered versus unclustered indeks så avgjørende ved range-spørringer?

Clustered = radene ligger fysisk i nøkkelorden, så et range-treff blir et sammenhengende blokk-scan. Unclustered = radene er spredt; hvert treff kan bety en ny RID-pekerfølging og en ny blokk-aksess. Ved bredt treff blir unclustered ofte verre enn full scan.

Spørsmål 4 · Middels

I external merge sort: hva er totalformelen for I/O og hvorfor multipliseres b med 2?

Total I/O = 2b · (1 + #merge-passes). 2-en kommer av at hvert pass både leser og skriver hele datasettet — initial-passet inkludert.

Spørsmål 5 · Vanskelig

b = 1024 blokker, n_B = 5 buffer. Hva er n_R, d_M og antall mergepasser?

n_R = ⌈1024/5⌉ = 205. d_M = 4. Antall passes = ⌈log₄(205)⌉ = 4. Total I/O = 2·1024·(1+4) = 10 240 blokker.

Spørsmål 6 · Lett

Hvilken tabell bør være ytre i en block nested loop join?

Den minste. Antall passer over indre tabell er ⌈|ytre|/(n_B−2)⌉, og det vil vi minimere.

Spørsmål 7 · Middels

Department har 5 blokker, Employee har 1000 blokker, buffer 5. Beregn block nested loop med Department ytre.

5 + ⌈5/3⌉·1000 = 5 + 2·1000 = 2005 blokker. Med Employee ytre: 1000 + ⌈1000/3⌉·5 = 2670. Department ytre vinner.

Spørsmål 8 · Middels

Når er sort-merge join klart bedre enn hash join?

(a) Når begge tabeller allerede er sortert på join-attributtet — sortfasen er gratis. (b) Når output uansett skal sorteres. (c) For ulikhets-join (R.x < S.y) der hash er ubrukelig.

Spørsmål 9 · Vanskelig

Hvorfor bygger hash join hash-tabellen på den minste tabellen, og ikke den største?

Hash-tabellen må holdes i minnet. Mindre build-side ⇒ får plass i mindre buffer ⇒ unngår grace-fasen. I/O-kosten er strukturelt symmetrisk (én scan av hver), men minneforbruket avgjør om vi klarer å unngå disk-partisjonering.

Spørsmål 10 · Middels

Hva er selektivitet, og hvilken statistikk bruker optimizeren for å estimere den?

Selektivitet = andel rader som passer et predikat. Optimizeren bruker n(R), V(A,R), min/max og — for skjeve fordelinger — histogrammer. Standardformler: WHERE A=c ⇒ 1/V(A,R); WHERE A>c ⇒ (max−c)/(max−min).

Spørsmål 11 · Vanskelig

EXPLAIN ANALYZE viser estimat 12 rader, faktisk 180 000. Hva er problemet og hvilket tiltak fungerer ofte?

Statistikken er utdatert eller for grov. Optimizeren har sannsynligvis valgt nested loop forventet å prosessere 12 rader, men kjører den nå på 180 000 ⇒ kvadratisk eksplosjon. Tiltak: kjør ANALYZE table, vurder histogram med flere bins, sjekk at predikatet ikke skjuler indeksbruk via funksjon eller cast.

Spørsmål 12 · Vanskelig

En unclustered B+-indeks finnes på salary. Spørringen er WHERE salary > 0. Optimizeren velger full table scan. Forklar.

Predikatet matcher alle radene. Med unclustered indeks blir kostnaden antall treff × en blokk pr. RID = opp mot 100 000 blokker for 100 000 rader. Full scan = ~1961 blokker. Optimizerens kostnadsmodell ser raskt at indeksen er verre selv om den teknisk er anvendelig.