DEL 1 TEORI: FORELESNINGER I TILKNYTNING TIL LÆREBOKEN
18.6 Pipelining
i. Med variabel rekordlengde i indeksen kan man telle antall pekere for hver indeksverdi
ii. Med fast rekordlengde i indeksen kan man telle antall pekere i pekerblokken 3. GROUP BY. Med gruppering blir det mer komplekst, fordi gruppene må finnes først. Det kan
gjøres med sortering eller hashing og først deretter kan aggregeringen foretas for hver gruppe.
18.5.2 Outer joins
Et eksempel på outer join:
SELECT Lname, Fname, Dname FROM EMPLOYEE LEFT OUTER JOIN DEPARTMENT ON Dno=Dnumber; Her må man gjennomgå alle EMPLOYEE-poster e og for hver e enten
finne riktig Dname ved hjelp av likhet Dno=Dnumber, eller
fylle på med null (kalles padding)
Forhåpentlig er DEPARTMENT sortert eller indeksert etter Dnumber, ellers blir det tungt!
Note: Tidligere fantes ikke OUTER JOIN og man skrev det annerledes:
SELECT Lname, Fname, Dname FROM EMPLOYEE, DEPARTMENT WHERE (Dno=Dnumber) OR NOT EXIST (SELECT * FROM EMPLOYEE, DEPARTMENT WHERE Dno=Dnumber);
Den siste ville sikre at også de postene i EMPLOYEE som ikke hadde motpost i DEPARTMENT kom med selvom Dno ikke var null. Hvis Dno var fremmednøkkel men null tillatt blir det enklere:
SELECT Lname, Fname, Dname FROM EMPLOYEE, DEPARTMENT WHERE (Dno=Dnumber) OR (Dno is null);
18.6 Pipelining
Mange spørringer produserer temporære filer og det er tungt. Da kan det være bedre å "gjøre seg ferdig med én post av gangen". Da lar man hver post i første operasjon brukes som input til neste operasjon osv. Dette kalles pipelining. Algoritmen blir tyngre, men man slipper de temporære filene.
Eksempel:
SELECT Lname, Fname, Dname FROM EMPLOYEE, DEPARTMENT WHERE (Dno=Dnumber AND Dno=5 AND Sex="F");
Her kan vi lage temporære filer og ta en operasjon av gangen:
1) Lage tempfil1 med bare ansatte som har Dno=5
2) Lage tempfil2 med bare ansatte fra tempfil1 som har Sex="F"
3) Lage tempfil3 med kartesisk produkt av tempfil2 og DEPARTMENT 4) Lage tempfil4 med bare de i tempfil3 som har Dno=Dnumber
5) Lage resultatfil med bare de tre angitt kolonnene Isteden kan vi pipeline, f.eks. slik:
1. Les én EMPLOYEE. Ved slutt gå til 9 2. Hvis Dno<>5 OR Sex<>"F" så gå til 1 3. Start forfra i DEPARTMENT
4. Les én DEPARTMENT. Ved slutt gå til 1 5. Hvis Dno<>Dnumber så gå til 3
6. Skriv Lname, Fname, Dname til resultatfilen
Knut W. Hansson 27
7. Gå til 3 8. Gå til 1 9. Ferdig
Hvis det finnes ordninger og/eller indekser for noen av kolonnene, så utnytter vi naturligvis det.
18.7.1 Query trees og query graphs (kursorisk) Boken har følgende eksempel kalt Q2:
SELECT P.Pnumber, P.Dnum, E.Lname, E.Address, E.BDate FROM PROJECT P, DEPARTMENT D, EMPLOYEES E
WHERE p.Dnum=D.Dnumber AND D.Mgr_ssn=E.Ssn AND P.Plocation="Stafford";
Den tilsvarende algebraen er
((( ( ))
( )) ( ))
Hvis denne løses direkte, vil det først bli laget kartesisk produkt av P, D og E (project, department og employee). Deretter velges de radene som tilfredsstiller where-klausulen og til slutt velges de angitt kolonnene. Det kan vises slik i et tre:
Vi ser at det trengs fire operasjoner for å løse oppgaven. Dette er en første "oversettelse" og vil gi riktig resultat, men den er svært treg fordi kartesisk produkt lages to ganger først. Dette treet er helt uoptimalisert. Det vil bli tungt å eksekvere fordi alle – og hele – postene tas med i det kartesiske produktet PxDxE Det gir svært mange og svært store poster og dermed stor fil med få poster pr blokk.
Den kan åpenbart optimaliseres.
Treet er kanonisk. Det vil forenklet si at operasjonene kan tas i en annen rekkefølge med samme resultat. (Man må allikevel sørge for at tilstrekkelig kolonner er med til at man kan gjennomføre utvalg etter where-klausulen.) I nedenstående tre, som er et forsøk på optimalisering, gjør man først et utvalg av poster i P. Utvalget kobles til D og E med equijoin (det er raskere enn først å lage kartesisk produkt og deretter velge ut fordi en equijoin kan "pipelines"). Til slutt velges de riktige kolonnene.
P D E
X
X
σwhere-klausulen
πangitte kolonner
Knut W. Hansson 28
Dette er da bare én av mange mulige optimaliseringer.
De to trærne angir en rekkefølge for handlingene, mens en graf (se lærebokens figur 18.4 c)grafen ikke har noen rekkefølge. Siden optimizer uansett må legge inn en rekkefølge, brukes grafer nå lite.
(a) er optimalisert, og da blir PROJECT først "filtrert" så det blir vesentlig færre poster i de kartesiske produktene (avhengig av hvor mange som faktisk har Plocation="Stafford"). Det kan finnes mange optimaliserte trær som alle tilsvarer (b) – trikset er å velge den mest effektive.
Da brukes enten
heuristiske regler ("tommelfingerregler), eller
beregner "kostnaden" og velger den "billigste"
Ofte gjør optimizer begge deler.
Bokens figur 18.5 (se figuren i læreboken) viser optimalisering av følgende spørring:
SELECT lName
FROM EMPLOYEE, WORKS_ON,PROJECT
WHERE Pname='Aquarius' AND Pnumber=Pno AND Essn=Ssn AND Bdate>'1957.12.31';
Optimaliseringen gjøres med heuristiske regler. Forklaring av optimaliseringen:
(a) Viser det initiale, kalt kanoniske, treet. Det vil gi meget store kartesiske produkter og er derfor svært lite effektivt.
(b) Seleksjonene flyttes nedover. Dermed blir det færre poster som inngår i det kartesiske produktet.
(c) Den mest restriktive seleksjonen (som begrenser antallet poster mest) anvendes først (flyttes nedover).
(d) Kartesisk produkter erstattes med JOIN der det er mulig. En JOIN er bedre enn et kartesisk produkt, fordi bare de postene som tilfredsstiller JOIN-kriteriet kommer med.
(e) Projeksjoner flyttes nedover og tas så snart som mulig. Da blir postene mindre og følgelig de temporære filene mindre (og med flere poster pr blokk evt. færre blokker pr post).
Det avsluttende treet (e) vil eksekvere svært mye rasker enn det kanoniske, (a).
Generelt gjelder at seleksjon er bra – det gir færre poster. Restriktive seleksjoner er bedre enn mindre restriktive. Videre er projeksjoner bra – de gir færre kolonner, altså mindre poster.
E
D
P
Knut W. Hansson 29
Læreboken gjengir en rekke lover som gjelder for transformasjon av relasjonsalgebra. Dette er regler som optimizer bruker for å forbedre treet. I eksemplet ovenfor, har f.eks. optimizer anvendt loven om at en seleksjon konjunktiv seleksjon (med AND) kan brytes opp i en sekvens av seleksjoner – loven om kaskade av konjunktiv seleksjon.
18.7.3 Query Execution Plan (kursorisk)
Når treet er ferdig optimalisert, gjøres det om til en execution plan som inkluderer hvordan postene skal hentes (med indekser, hashing sortert fil eller full filgjennomgang) og om resultatet av hver operasjon skal mellomlagres ("materialized evaluation") eller pipelines ("pipelined evaluation").
18.8.1 Cost optimization (kursorisk)
Med heuristiske regler ble bare query-treet optimalisert. Det ble ikke tatt hensyn til størrelse på filene, tilgjengelige indekser o.l.
Med kostnadsoptimalisering beregnes en tenkt kostnad for hvert tre, og den "billigste" velges. Husk da at optimalisering også tar tid og kostnadsoptimalisering tar lengre tid enn den heuristiske.
Kostnadsoptimalisering er derfor vanligst for kompilerte spørringer som antas å bli brukt igjen, og ikke så vanlig for interpreterte. De fleste DBMS vil tilby begge.
Kostnadsfaktorene er gjengitt i læreboken og gjelder:
tilgang til eksternt lager
lagringskostnad for midlertidige filer
beregningskostnad (internt) f.eks. søking, sortering, merging og beregninger på kolonneverdier
minnekostnad
kommunikasjonskostnad
Et problem er hvilken vekt som skal legges på de forskjellige. For større databaser er det – som nevnt flere ganger tidligere – tilgang til eksternt lager som er det viktigste. En måte å få ned
optimaliseringstiden på, er derfor å bare se på antall diskaksesser. Man beregner simpelthen antall blokker inn og ut. Man må ta hensyn til indekser o.a. og må også vurdere antall distinkte verdier i en kolonne og selektiviteten. Man bruker da gjennomsnittsberegninger.
Ved distribuerte databaser (databasen lagret på flere maskiner/steder) vil kommunikasjonskostnaden bli den viktigste. Man beregner antall bytes som sendes. Ved å velge bare en kostnadsfaktor, slipper man problemet med å velge vekting.
18.8.2 Kataloginformasjon i kostnadsberegninger (kursorisk)
Til hjelp med optimaliseringen, kan DBMS holde orden på ekstra informasjon om databasen. Noen eksempler på interessant informasjon:
Filstørrelse (det er tyngre å lete sekvensielt i en stor fil), antall blokker
Antall poster, poststørrelse, og antall poster pr blokk (blocking factor).
Hvordan filen er organisert
Alle indekser og antall nivåer i flernivåindekser
Antall distinkte verdier for hvert attributt og selektivitet (andel av postene som tilfredsstiller et likhetskrav) – med disse to kan vi beregne gjennomsnittlig antall poster som vil bli returnert med likhet (alltid 1 for en primærnøkkel)
Noen av dette er enkelt å vedlikeholde fordi det endres sjelden, f.eks. informasjon om indeksene.
Andre ting endres dynamisk, og er tunge å holde helt á jour. Optimaliseringen trenger imidlertid ikke
Knut W. Hansson 30
helt oppdaterte og eksakte tall. Derfor kan slike data oppdateres innimellom, til faste tider eller når serveren ellers er ledig.
En spesiell mulighet som gjelder ikke-nøkkel attributter er å lage et histogram med angivelse av hvor mange det er av hver verdi, f.eks. antall menn og antall kvinner, eller antall som er ansatt i hver avdeling.
18.8.3 og 18.8.4 Eksempler (kursorisk)
I disse kapitlene gjengis er eksempler på noen kostnadsberegninger.