Kapittel 6 · 6A · Forelesning 11

Lagring — records, blokker, buffer

Bratsbergs notater kap 1–8. Hvordan en rad faktisk er bytes på en disk — og hvordan DBMS-en ber om dem.

01 · DBMS-arkitektur

Komponentene i en SQL-DBMS

Et DBMS er ikke ett program — det er et lag-på-lag-system hvor hver komponent har én jobb. Når du kjører en SQL-spørring vandrer den gjennom hele stakken før den når disken og tilbake.

SQL-spørring fra klient til disk. SQL-laget kjenner bare rader; alt under buffer pool snakker bare i blokker.

SQL-kompilatoren parser teksten og slår opp i katalogen for å oversette til et internt algebra-tre med konkrete tabell- og kolonnereferanser.
Optimizeren genererer mange mulige kjøreplaner (med ulike join-rekkefølger og indekser) og velger den med lavest forventet I/O-kostnad basert på katalogstatistikk.
Executoren kjører planen — den ber om blokker fra buffer pool, tar låser via lock manager, og skriver til logfilen hvis den endrer noe.
Buffer pool er det eneste laget som faktisk leser/skriver disk. Alt over snakker kun med buffer pool.

Spørsmål 1 · Lett

Hvorfor må optimizeren ha tilgang til SQL-katalogen?

For å vite hvilke indekser som finnes på hver tabell, hvor mange rader og distinct-verdier hver tabell har (statistikk), og for å estimere kostnaden av forskjellige planer. Uten katalogen kan ikke optimizeren ranke planer.

02 · Device og blokker

Hvor disken slutter og blokkene begynner

Et device er enten en hel disk (raw partition) eller en stor fil i filsystemet. DBMS-en ser den som en lang vektor av blokker, indeksert med en BlockId.

HDD — rotating disk

Mekaniske armer søker fysisk til riktig sektor. Random seek: ~10 ms. Sekvensiell I/O kan være 100× raskere enn random.

SSD — flash

Ingen mekaniske deler. Random read: ~100 µs. Skriving krever blokk-erasure (write amplification). Begrenset levetid pr. celle.

Hvordan en BlockId er bygget opp

BlockId-en kombinerer hvilken disk og hvor i disken. Med 4 byte: 1 byte for deviceId + 3 byte for offset → 2²⁴ blokker per device. Med 16 KiB blokker blir det 256 GiB per device. 8-byte BlockIds spenner over alt vi trenger.

Spørsmål 2 · Lett

Hvorfor velger DBMS-er typisk en blokkstørrelse på 4–32 KiB i stedet for å lese mindre enheter — for eksempel en enkelt rad om gangen?

Disker er optimalisert for store sekvensielle overføringer. Selve seek-tiden (på HDD) eller flash-controllerens fixed cost (på SSD) er den dominerende kostnaden. Når du først er der, er det nesten gratis å lese mer. Å hente 16 KiB tar nesten samme tid som å hente 1 byte. Større blokker → bedre amortisering av seek-kostnaden.

03 · Record-format

Tre måter å pakke en rad

Når en tabell har kun fixed-length attributter (INT, CHAR(N), DATE), er hvert felt på fast offset. Da er decoding triviell. Men så kommer VARCHAR…

Format 1 — Fixed length

Format 2 — Record vector (variable length)

Format 3 — Delimiter

Row store vs column store

Tradisjonell DBMS bruker row store: hele raden som én record. Bra for OLTP der man jobber på enkelt-rader. Column store lagrer hver kolonne for seg — bra for analytiske queries (SUM(salary), AVG(age)) der man kun trenger få kolonner men mange rader. Komprimerer også bedre fordi like verdier ligger sammen.

Spørsmål 3 · Middels

Du har en tabell Person(name VARCHAR(50), age INT). Hvorfor kan ikke fixed-length-formatet brukes direkte?

VARCHAR betyr at navnet kan være alt fra 0 til 50 tegn — så faktisk lengde varierer mellom rader. Hvis vi reserverer 50 byte uansett, sløser vi diskplass for korte navn. Med record vector eller delimiter pakker vi tett. Alternativt kan VARCHAR-feltet nullpaddes til 50 byte for å bevare fixed-length-egenskapen — det gjør noen DBMS-er.

Spørsmål 4 · Middels

Når lønner det seg å bruke column store fremfor row store?

For analytiske spørringer som leser få kolonner men mange rader: SELECT AVG(salary) FROM Employee. I row store må DBMS-en lese alle kolonner i hver rad, selv om bare salary brukes. I column store er hele salary-kolonnen sammenhengende → mindre I/O og bedre kompresjon. OLTP-arbeidslast (SELECT * på enkelt-rader) favoriserer fortsatt row store.

04 · Block-format

Slot directory: anatomi av en blokk

For variable-length records trenger vi en mer fleksibel layout. Standardmønsteret er two-pointer-layout: records vokser fra starten, slot directory fra slutten. De møtes i midten — når det blir trangt, må man kompaktere eller splitte blokken.

Slot directory layout. Records vokser fra start, slots fra slutt. Ledig plass = avstand mellom dem.

Hvorfor er denne layouten genial?

RID forblir stabil ved kompaktering. Hvis vi sletter Record B og senere flytter C nedover for å fjerne hullet, oppdaterer vi bare slot[2].pointer. Indekser ute som peker til (BlockId, slot=2) virker fortsatt.
Slot directory kan sorteres etter nøkkel. Da kan vi binærsøke i directoriet — selv om de fysiske recordene ligger i innsettingsorden.
Flip/flop-stempel ved start og slutt: ved en torn write hvor halve blokken har gammel data og halve har ny, vil de to stemplene være ulike. Da kan vi forkaste blokken som korrupt og hente fra log.

Interaktivt — sett inn og slett records

Slot directory simulator

Trykk på knappene for å se hvordan blokken endrer seg.

Klar. Blokken har 4 slots, fritt område på 220 byte.

Spørsmål 5 · Vanskelig

Hva er fordelen med flip/flop-stempel ved start og slutt av blokken — hva forhindrer det?

Det forhindrer at vi leser en halvskreven blokk (torn write). Hvis strømmen forsvinner midt under en blokk-skriving, kan halve blokken være ny og halve gammel. Stemplene oppdateres rett før hver skriving til samme verdi. Hvis vi etter en crash leser en blokk hvor stemplet i header ikke matcher stemplet i trailer, vet vi at den er korrupt og må gjenopprettes fra loggen (WAL).

Spørsmål 6 · Middels

Hvorfor kan slot directory-en sorteres etter nøkkelverdi mens selve recordene ligger i innsettingsrekkefølge?

Fordi slot directory bare inneholder pekere — ikke selve dataen. Å sortere slottene endrer rekkefølgen på pekerne, ikke posisjonene til recordene. Da kan vi gjøre binærsøk innenfor blokken: les slot[mid], følg peker, sammenlikn nøkkel. Recordene trenger ikke flyttes fysisk.

05 · Buffer pool

Den eneste broen mellom RAM og disk

Buffer pool-en er typisk svært stor — flere GB i serverdatabaser. Den fungerer som en cache: én gang en blokk er lest inn, kan flere transaksjoner og spørringer dele den. Hash-indeksert på BlockId for O(1) lookup.

Buffer pool er hash-indeksert på BlockId. Hvert frame holder én blokk pluss metadata: pin-count og dirty-flag.

Hva skjer når en blokk forespørres?

Slå opp BlockId i hash-indeksen. Hit → returner pekeren til frame, øk pin-count, ferdig.
Miss → må finne et ledig frame. Hvis ingen er tomme, velg et offer via erstatningsstrategi (LRU/MRU/clock). Offerets pin-count må være 0.
Hvis offeret er dirty, skriv først ut til disk (gjerne via WAL).
Les den ønskede blokken inn i frame. Oppdater hash-indeksen. Returner.

Erstatningsstrategier

Strategi	Velger ut	Bra for	Dårlig for
LRU	Lengst siden bruk	Hot data, lokalitet	Skanninger forurenser bufferet
MRU	Sist brukte	Repeterte scans	Hot working set
Clock	Tilnærmet LRU, billigere	Praktisk default	Skanninger (samme som LRU)

Interaktivt — LRU i aksjon

Tre buffer frames, LRU-eviction

Skriv en BlockId og trykk «Hent». Den eldste blokken kastes ut når bufferet er fullt.

Hent en blokk for å starte.

Hvorfor egen buffer?

OS-en har sin egen page cache, men den vet ikke at en sekvensiell scan forurenser cachen, eller at en hot indeks-rotnode bør pinnes. DBMS-en kjenner semantikken og kan prefetche, pinne, og force-skrive ved behov.

Spørsmål 7 · Middels

Hvorfor er LRU et dårlig valg når DBMS-en kjører en stor table scan?

En full scan leser hver blokk én gang. LRU vil gradvis kaste ut hot data (B+-tre-røtter, ofte brukte blokker) til fordel for skannet-blokker som aldri vil bli lest igjen. Bufferet «forurenses». MRU er bedre her: vi kaster ut den sist leste skann-blokken med en gang, så hot data forblir.

Spørsmål 8 · Vanskelig

En transaksjon endrer en blokk. Buffer pool-en velger denne blokken som offer i en eviction. Hva må DBMS-en gjøre før blokken skrives til disk, og hvorfor?

WAL — Write-Ahead Logging: DBMS-en må først tvinge ut alle log-records som beskriver endringene (opp til høyeste LSN på blokken). Hvis ikke: kræsj rett etter blokk-skrivingen ville etterlate datablokken med endringer som ikke ligger i loggen — recovery klarer da ikke å reprodusere transaksjonen. Loggen er sannhet, datablokken er bare en optimalisering.

06 · Heapfiler

Tabell uten orden

Heapfilen er den enkleste lagringsformen — bare en lenkeliste av blokker, og records legges inn der det er plass. Ingen sortering, ingen indeks-i-seg-selv.

Heapfilen organisert som to lenkelister: full og med ledig plass. Insert er O(1), søk uten indeks er O(N).

Fordeler

Trivielt enkelt å implementere
Insert er konstant tid
Ingen indeks-vedlikehold ved oppdatering
Velegnet for tabeller som likevel skal fullskannes

Ulemper

Søk er lineært i tabellstørrelsen
Range-spørringer er like dårlige
Blir spredt etter mange sletter — krever reorganisering
Brukes nesten alltid sammen med indekser

Spørsmål 9 · Lett

Hvorfor brukes en heapfil ofte sammen med en B+-tree-indeks i stedet for å lagre dataen direkte i indeksen?

Fordi en tabell kan ha flere indekser. Hver kan peke til samme heapfil via RID. Hadde dataen ligget i indeksen ville vi måttet duplisere den for hver indeks vi laget. Heap+B+ er løsningen MyISAM, PostgreSQL og Microsoft SQL Server bruker ved sekundære indekser.

07 · Statisk hashing

Konstant-tid likhetsoppslag

Hashing leverer det heapfilen ikke kan: O(1) likhetssøk. Men den har en akilleshæl — du må bestemme antall blokker på forhånd.

Statisk hashing med separat overflow. Når en bøtte fylles opp, kobles overflow-blokker etter.

Tre overflow-strategier

Open addressing: prøv neste blokk (eller fast hopp). Enkelt, men gjør sletting komplisert.
Separat overflow: dedikerte overflow-blokker som bøtte-blokker peker til. Kan deles eller være per-bøtte.
Multiple hashing: bruk en alternativ hash-funksjon ved kollisjon. Distribuert overflow.

Hovedproblem

Statisk hashing antar at antall records er kjent på forhånd. I praksis varierer datamengden, og lange overflow-kjeder gjør at oppslag som skulle vært O(1) blir O(N).

Spørsmål 10 · Middels

Hvorfor egner statisk hashing seg dårlig for range-spørringer som WHERE empno BETWEEN 100 AND 200?

Fordi hash-funksjonen fjerner naboskapet mellom nøkkelverdiene. Empno 100, 101, 102 ender på helt forskjellige bøtter etter mod N. For å finne alle i intervallet må vi enten hashe hver mulig verdi (101 oppslag) eller skanne hele filen. B+-trær bevarer sortering og er mye bedre her.

08 · Extendible hashing

Hashing som vokser elegant

Extendible hashing introduserer et lag mellom hash-verdien og blokken — en directory. Når en blokk fylles, dobles directory-en (eller bare blokken splittes), uten å rehasher hele filen.

Hovedideen — global vs. local depth

Global depth (d): hvor mange bits av hashen som directory-en bruker for å indeksere.
Local depth (d'): hvor mange bits hver enkelt blokk faktisk skiller på.
Når d' < d for en blokk: flere directory-slots peker til samme blokk. Splitting skjer uten directory-doubling.
Når d' = d og blokken splittes: directory må først dobles.

Extendible hashing etter 11 innsettinger med h(K) = K mod 16. Directory bruker 3 bit, men noen blokker har bare local depth 2.

Søk i extendible hashing — alltid 2 blokk-aksesser

Beregn h(K), ta de siste d bitene → finn directory-slot.
Les den datablokken slot-en peker til.
Søk i blokken (lite, kan være lineært eller binær).

Sammenliknet med statisk hashing er ekstrakostnaden én directory-aksess. Til gjengjeld blir ytelsen ikke kvalt av lange overflow-kjeder.

Spørsmål 11 · Vanskelig

Hva betyr det at en blokk har local depth 2 mens directoriet har global depth 3?

At flere directory-slots peker til samme blokk. Med local depth 2 skiller blokken bare på de 2 siste bitene. Slots 000 og 100 har samme 2 siste bit (00) og peker derfor til samme blokk. Når denne blokken senere splittes (uten å fylle opp directoriet) blir det to blokker, hver med local depth 3.

Spørsmål 12 · Middels

Hvilken klar ytelse-fordel og hvilken klar ulempe har extendible hashing fremfor B+-tre for likhetssøk?

Fordel: 2 blokk-aksesser uavhengig av filstørrelse (directory + datablokk). B+-tre har 3–4 nivåer for store tabeller. Ulempe: ingen sortering — range-søk og ORDER BY er ubrukelige. Også: directoriet kan bli stort hvis dataene er sterkt skjeve, og verken ORDER BY eller foreign key-traversering har noen hjelp av strukturen.

09 · Oppsummering

Det du må huske

Konsept	Hva	Når
Blokk	4–32 KiB enhet for I/O	Alltid — ikke noe mindre
RID	(BlockId, slot)	Indeks → rad-peker
Slot directory	Pekere på slutten av blokk	Variable-length, sletting/kompaktering
Buffer pool	RAM-cache + hash-indeks	Minimere disk-I/O
Heapfil	Usortert lenkeliste av blokker	Sammen med en eller flere indekser
Statisk hash	h(K) mod N → blokk	Faste datamengder, kun likhet
Extendible hash	directory + lokal/global depth	Voksende datamengder, kun likhet

Neste steg

Nå vet du hvordan en rad ligger i en blokk og hvordan blokker går mellom RAM og disk. Neste skritt: B+-trær — den indeksstrukturen som gjør raske søk og range-spørringer mulige på tabeller med milliarder rader.