Spørringens reise gjennom DBMS-en

Klient sender SQL-tekst til serveren

Reisen starter et helt annet sted enn der du tror at databasen «lever». Klienten — kanskje en JDBC-driver, kanskje psql, kanskje webserveren din — pakker SQL-strengen inn i en TCP-pakke og sender den til DBMS-prosessens session manager. Før noen som helst spørringsbehandling kan skje, må forbindelsen autentiseres og en sesjonskontekst etableres: hvem du er, hvilke roller du har, hvilken default-database og hvilket isolasjonsnivå du opererer på.

Den faktiske spørringen er bare en byte-streng på dette tidspunktet. DBMS-en har ingen anelse om hva Employee betyr, eller om name er gyldig. Det blir avklart i de neste stasjonene.

Parser tokeniserer og bygger et AST

SQL-kompilatoren har to oppgaver: tokenisere strengen og parse token-strømmen til et abstrakt syntakstre (AST). Tokenizeren skiller nøkkelord fra identifikatorer fra litteraler. Hver token vet sin posisjon — nyttig for feilmeldinger.

Parseren forsøker å matche tokens mot SQL-grammatikken. Lykkes det, har vi et tre der hvert nivå representerer en grammatikkregel: SelectStmt → SelectList + FromClause + WhereClause. Mislykkes det, kastes en syntaksfeil — og reisen er over allerede her.

Token-strømmen

Katalog gir AST-et mening

Et AST har formen riktig — men er Employee en tabell? Finnes name som kolonne? Hva er typen til depno? Slike spørsmål besvares av SQL-katalogen: en samling systemtabeller som beskriver alle tabeller, kolonner, indekser, constraints og rettigheter. Katalogen er selv en database, og slås opp på samme måte som hvilken som helst annen tabell.

Tre ting skjer her parallelt:

1. Navneoppløsning — kvalifiser name til Employee.name, slå opp tabell-OID-er.
2. Typesjekk — er depno = 4 meningsfullt? Er 4 en INT som kan sammenliknes med depno?
3. Privilegiekontroll — har brukeren SELECT-rett på Employee?

Resultatet er at AST-et omformes til et algebra-tre der nodene er relasjonsoperatorer fra kap. 2.

Et lite utdrag av katalogen

πname, salary ( σdepno=4 ∧ age>50 ( Employee ) )

Optimizer enumererer planer og velger den billigste

Algebra-treet er logisk — det sier hva, ikke hvordan. Optimizeren genererer mange likeverdige varianter (algebraiske ekvivalenser: dytt σ ned forbi join, omorganiser join-rekkefølge, …) og knytter fysiske operatorer til løvnodene: full table scan, index scan, hash join, sort-merge join. For hver kandidat estimerer den I/O-kostnaden ved hjelp av statistikk fra katalogen. Plan-treet med lavest forventet kostnad vinner.

To kandidatplaner for vår spørring

πname,salary
└─ σdepno=4 ∧ age>50
   └─ TableScan(Employee)

πname,salary
└─ Fetch(RID)
   └─ IndexScan
       depno=4 ∧ age>50

Lek deg med kostnadsmodellen

Anta heap-fil + uclustered B+-tre. Plan A skanner hele heap-filen (1 961 blokker). Plan B traverserer 2 indeks-blokker ned, scanner sideveis i bladet, og følger så en RID-peker per matchende rad. Når blir Plan B billigst?

Executor begynner å kjøre — men ber først om låser

Når den fysiske planen er valgt, tar executor over. Før den faktisk leser eller skriver, må to subsystemer engasjeres: lock manager (eller MVCC-snapshot) for isolasjon, og log writer for atomisitet og durability.

Akkurat hvilke låser som tas avhenger av isolasjonsnivå. Ved Strict 2PL og READ COMMITTED tas typisk en shared (S) lås per leste rad eller blokk, som slippes når raden er konsumert. Ved REPEATABLE READ holdes S-låsene til commit. Ved en UPDATE/INSERT/DELETE tas exclusive (X) lås, og den holdes alltid til commit (Strict 2PL).

Lock-tabellen oppdaterer seg

Buffer-oppslag: hit eller miss?

For å lese en blokk spør executor først bufferet: «har du blokk N?». Bufferet er en stor del av RAM, organisert som frames som hver kan holde én blokk. Et hash-indeks på BlockId gjør oppslaget O(1) på snittet.

• Hit — frame-pekeren returneres umiddelbart. Ingen disk-I/O.
• Miss — frame må allokeres. Hvis bufferet er fullt, må en frame eviktes — og hvis den er skitten (modifisert), må den først flushes til disk.

Bufferet vårt — 16 frames

Erstatningsstrategier

• LRU — least recently used. Klassiker, men tabell-scans kan «forgifte» hele bufferet.
• MRU — most recently used. Bedre for repetisjons-mønstre.
• Clock — billig approksimasjon av LRU. En referanse-bit roterer.

Når bufferet bommer går vi til disk

Buffer miss → eviction-policy plukker en kandidat-frame. Hvis frame er skitten flushes den til disk først (skrive-I/O). Deretter slås BlockId opp: deviceId + offset gir disken et fysisk eller logisk sted å lese fra. Blokken leses inn i frame, hash-indeksen oppdateres, og alle som ventet på den får signal.

Anatomi av en blokk-lesing

Hva sjekker DBMS-en på blokken den nettopp leste?

• Flip/flop-stempel ved start og slutt — atomisitet.
• Checksum — bit rot fra disken?
• PageLSN — hvilket log-record sist endret denne blokken? Avgjørende ved recovery.

Topp-ned søk + sideveis range scan

Med blokken i buffer kan vi endelig traversere. Optimizeren valgte index scan på (depno, age). Vi starter ved roten, binærsøker lokalt etter «første nøkkel der depno=4», følger barn-pekeren ned, gjentar til vi treffer bladet. Der scanner vi sideveis (blader er lenket sammen) til depno > 4.

Tupler streames tilbake — og loggen sluttføres

Executor er en pipeline. Iteratoren returnerer ett tuple om gangen («Volcano-modellen»). Klienten ser de første radene før spørringen er ferdig kjørt. På toppen sitter projeksjonen π og kaster bort kolonnene klienten ikke spurte om.

For en SELECT er det ikke noe egentlig commit å gjøre — vi har ikke endret noe. Men sesjonens auto-commit eller eksplisitte COMMIT resulterer i:

1. Et commit-record skrives til log-bufferet.
2. Log-bufferet force-flushes til disk (durability!).
3. Lock manager slipper alle låser (Strict 2PL).
4. Tuples som ennå er igjen i prosjeksjons-pipelinen sendes ut.

Resultatet streamer tilbake

Hele bildet på én side

Du har nå sett hva hvert eneste subsystem i kurset gjør på den samme spørringen. Tabellen oppsummerer hvor du finner mer.

Avsluttende sjekk