TDT4150 · NTNU

Studieguide for TDT4150 Avanserte databasesystemer

Komplett pensumoversikt for avanserte databasesystemer ved NTNU — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.

Introduksjon

Denne studieguiden dekker hele pensum i TDT4150 Avanserte databasesystemer ved NTNU (7,5 stp, masternivå). Emnet bygger videre på TDT4145 og går dypere inn i databasesystemers indre arkitektur, spørringsoptimalisering, parallelle og distribuerte systemer, samt moderne spesialiserte databaser og avanserte spørreoperatorer.

Vurderingsformat: 4-timers skriftlig skoleeksamen, ingen trykte hjelpemidler, enkel kalkulator tillatt (kode D). Settet består fast av seks oppgaver med prosentvis vekting per (del-)oppgave. Oppgavene er overveiende forklarings- og drøftingsoppgaver («Forklar», «Begrunn svaret», «Lag et eksempel som illustrerer …») kombinert med små regne-/utledningsoppgaver og steg-for-steg-utføringer (Rank Join, cracking). Den siste oppgaven er fast viet temaer fra seminarartikler. Du blir bedt om å gjøre rimelige antagelser der oppgaveteksten er ufullstendig — gjør dem eksplisitt.

Emnet tester at du kan:

Forklare databasesystemets interne komponenter og samspillet mellom dem (bufferhåndtering, lagringsstrukturer, loggmekanismer).
Anvende kostnadsbasert spørringsoptimalisering: relasjonsalgebra-transformasjoner, join-algoritmer og eksekveringsplaner.
Analysere parallell og distribuert spørringseksekvering: partisjoneringsstrategier, two-phase commit, fragmentering og replikering.
Sammenligne rad- og kolonneorientert lagring, og forstå komprimeringstekniker og LSM-trær.
Utlede top-k-resultater med Fagins algoritmer (TA og NRA) og forstå skyline-beregning.
Resonnere om romlige indekser (R-trær, R*-trær) og spatio-tekstuelle søkestrukturer.
Forklare database cracking og adaptiv indeksering som inkrementell indeksbygging.
Beskrive MMDB, HTAP og nye operatorer tilpasset moderne maskinvare.

Pensum er primært basert på Database System Concepts (Silberschatz m.fl.) og Database Management Systems (Ramakrishnan & Gehrke), supplementert med forskningsartikler om kolonneorienterte databaser, top-k-algoritmer og adaptiv indeksering.

Databasearkitektur

Eksamensrelevant

Oppbygning av databasesystemer innenfra: bufferhåndtering, lagringsstrukturer og komponentinteraksjon.

Systemoversikt

Et databasesystem er delt i to hovednivåer: lagringsbehandleren (storage manager) og spørringsbehandleren (query processor). Disse kommuniserer via bufferpulen og katalogen.

Lagringsbehandler: buffer manager, file manager, disk manager, loggbehandler.
Spørringsbehandler: parser, rewriter, optimizer, executor.
Transaksjonsstyring: concurrency control manager og recovery manager.

Disksystemet og I/O-modellen

Tradisjonelle databaser antar at data bor på roterende disk (HDD). Tilgangstid er summen av seek time + rotational latency + transfer time. For HDD er dette typisk 5–15 ms per tilfeldig blokk, mens sekvensielle leser er langt raskere.

Databaser organiserer data i blokker (typisk 4 KB–64 KB), som er den minste atomære I/O-enheten. Antall blokk-leser/-skriver er den primære kostnadsmåleenheten i ytelsesanalyse.

Eksempel — I/O-kostnad: En relasjon R har 50 000 tupler, 25 tupler per blokk, altså 2 000 blokker. Et sekvensielt fullstendig tabellscan koster 2 000 I/O-er. En tilfeldig aksess per tuppel ville koste 50 000 I/O-er — 25× dyrere.

Bufferhåndtering

Buffermanageren holder et sett med rammer (frames) i minnet. Når en blokk forespørres:

Sjekk om blokken allerede er i bufferpulen (buffer hit).
Hvis ikke: finn en ledig ramme (eller erstatt en gammel), les blokken fra disk.
Pinn blokken (pin count++) mens den brukes; unpin ved ferdig.
Skitne (dirty) sider skrives tilbake til disk ved erstatning.

Erstatningspolicyer

LRU (Least Recently Used): Erstatt den rammen som ble aksessert lengst tilbake. Fungerer bra for random access, men dårlig ved sekvensielle gjennomganger (sequental flooding problem).
MRU (Most Recently Used): Bedre for fullstendige tabellscans i sykler — beholder «de gamle» dataene i buffer.
Clock (second-chance): En variant av LRU med lav overhead: en «klokke-peker» søker etter en ramme med reference bit = 0; hvis 1, nullstill biten og flytt pekeren.
LIRS og ARC: Mer avanserte policyer for adaptive bufferstrategier.

Eksempel — sekvensiell flooding: Et nested-loop join leser en stor ytre relasjon sekvensielt. LRU vil kontinuerlig kaste ut nyttige blokker fordi de sist brukte er de ytre blokk-sidene. MRU (eller pinning av indre relasjon) er bedre her.

Lagringsstrukturer

Data lagres i heap files (ingen rekkefølge), sorterte filer eller som del av en trestruktur (clustered index). Innenfor en side organiseres tupler typisk med et slot directory i starten av siden og tuplene vokser fra bunn:

Slot directory: array av (offset, lengde)-par.
Frie sider spores av en free-space directory på filnivå.
Overflowsider brukes når tupler vokser utover den opprinnelige siden.

Record-formater

Fast lengde: Attributtverdier av kjent størrelse plasseres på faste offsets. Aksess O(1).
Variabel lengde: VARCHAR og BLOB. Offsettabell peker til faktiske verdier. Nødvendig komprimering og fragmenteringshåndtering.
NSM (N-ary Storage Model) / «rowstore»: Hele tuppelen lagres sammenhengende. Bra for OLTP (hent hele rader), dårlig for analytiske spørringer som aksesserer få kolonner.
DSM (Decomposition Storage Model) / «columnstore»: Se eget tema om kolonneorienterte databaser.

Write-Ahead Log (WAL)

Kjerneprinsipp for recovery: skriv alltid loggposten til disk FØR den tilhørende datasiden. Dette sikrer at systemet etter en krasj kan gjenta (redo) eller angre (undo) operasjoner. Loggposten inneholder: LSN (Log Sequence Number), transaksjons-ID, operasjonstype, «before image» og «after image».

Dette er også grunnen til at DBMS-et selv må styre når en datablokk treffer permanent lager — hvis operativsystemet fritt kunne skrive ut buffer-sider, kunne en datablokk nå disk før den tilhørende loggposten, og WAL-garantien (og dermed recovery) ville brutt sammen.

Komponenter og lag — slik eksamen ber om det

Eksamen ber gjentatte ganger om å skille mellom de to topp-komponentene og mellom stegene inne i spørringsbehandleren:

Relational Query Processor: parser SQL, omskriver (rewrite), optimaliserer og lager utføringsplan, og utfører SQL-setningene.
Transactional Storage Manager: håndterer lagring av data og indekser, buffer, logging og låsing (transaksjoner).
Query Rewrite vs. Query Optimizer: Rewrite gjør logiske, statistikk-uavhengige forenklinger (utfolding av views, eliminering av redundante predikat/nøsting) og produserer fortsatt logisk algebra. Optimizer velger fysisk plan (join-algoritmer, rekkefølge, indeksbruk) basert på kostnadsmodell og statistikk.

Logisk og fysisk data-uavhengighet

Logisk data-uavhengighet: man kan endre det logiske skjemaet (legge til kolonner, splitte tabeller) uten å måtte endre applikasjonene som bruker views over skjemaet. Fysisk data-uavhengighet: man kan endre den fysiske lagringen (indekser, filorganisering, partisjonering) uten å endre det logiske skjemaet eller applikasjonene. Begge er ønskelige fordi de isolerer applikasjoner fra endringer på lavere abstraksjonsnivå og dermed reduserer vedlikeholdskostnad.

Nøkkelformler

•I/O-kostnad for sekvensielt scan: $B(R)$ blokk-leser, der $B(R) = \lceil |R| / T_R \rceil$
•Buffer hit ratio: $\displaystyle h = \frac{\text{buffer hits}}{\text{totale blokk-forespørsler}}$
•Slot directory overhead: én (offset, lengde)-post per tuppel per side
•WAL-prinsippet: loggpost til disk FØR tilhørende datablokk

Vanlige feil

⚠️Anta at LRU alltid er best — ved sekvensielle full-table scans er MRU eller «no steal»-politikk bedre
⚠️Glemme at pin-count hindrer erstatning — en pinnet ramme kan ikke kastes ut selv om bufferpulen er full
⚠️Blande sekvensielle og tilfeldige I/O-kostnader i estimater

Eksamenstips

💡Oppgave 1 spør nesten alltid kort og presist om arkitektur: kunne forklare RQP vs. TSM, Query Rewrite vs. Optimizer, og logisk vs. fysisk data-uavhengighet på 3-5 setninger hver
💡Forklar HVORFOR DBMS-et må kontrollere når sider skrives til disk (WAL-garantien), ikke bare AT det gjør det
💡Lag eksplisitt I/O-regnestykke når oppgaven inviterer til det: antall blokker for R og S, deretter kostnad per join-algoritme
💡Erstatningspolicyen påvirker join-ytelse — sekvensiell flooding ved LRU er en typisk drøftingsvinkel

Laster...

Laster…