21. Adatbázisok optimalizálása és konkurencia kezelése Flashcards
Adatbázis-kezelő rendszer
Adatbázis-kezelő rendszer alatt olyan számítógépprogramot értünk, mely megvalósítja nagy tömegű adat biztonságos tárolását, gyors lekérdezhetőségét és módosíthatóságát, tipikusan egyszerre több felhasználó számára.
Az adatbázis-kezelési tevékenységeket két csoportra szokás osztani: adatmanipulációra (lekérdezés), illetve definiálásra (adatszerkezetek kialakítása, módosítása).
Az adatok manipulációjára szolgáló nyelveket összefoglalóan Data Manipulation Language-nek (DML), míg a definíciós eszközökkel rendelkező nyelveket Data Definition Language-nek (DDL) szokás nevezni.
Lekérdezésfordító
A lekérdezésfordító elemzi és optimalizálja a lekérdezést, ami alapján elkészíti a lekérdezés-végrehajtási tervet (lekérdezéstervet).
Végrehajtómotor
A végrehajtómotor a lekérdezésfordítótól megkapja a lekérdezéstervet, majd kisebb
adatdarabokra (tipikusan rekordokra, egy reláció soraira) vonatkozó kérések sorozatát adja át az erőforrás-kezelőnek.
Erőforrás-kezelő
Az erőforrás-kezelő ismeri a relációkat tartalmazó adatfájlokat, a fájlok rekordjainak formátumát, méretét, valamint az indexfájlokat. Az adatkéréseket az erőforrás-kezelő lefordítja lapokra, amit átad a pufferkezelőnek.
Pufferkezelő
Feladata, hogy a másodlagos adattárolóról (lemez, stb.) az adatok megfelelő részét olvassa be a központi memória puffereibe. A pufferkezelő információkat cserél a tárkezelővel, hogy megkapja az adatokat a lemezről.
Tárkezelő
Adatokat ír-olvas a másodlagos adattárolóról. Előfordulhat, hogy igénybe veszi az oprendszer parancsait is, de sokszor közvetlenül a lemezkezelőhöz intézi a parancsait.
Tranzakciókezelő
A lekérdezéseket és más tevékenységeket tranzakciókba szervezzük. A tranzakciók olyan egységek, amelyeket atomosan és elkülöníthetően kell végrehajtani, valamint a végrehajtásnak tartósnak kell lennie, illetve a tranzakció végrehajtása nem állíthat elő érvénytelen adatbázis-állapotot (azaz konzisztens). Ezeket a követelményeket
az ACID mozaikszóval szokás összefoglalni. A tranzakciókezelő hajtatja végre a tranzakciókat és gondoskodik a naplózásról és helyreállításról, valamint a konkurenciakezelésről.
Indexstruktúrák
Az indexek keresést gyorsító segédstruktúrák. Több mezőre is lehet indexet készíteni. Nem csak a főfájlt, hanem az indexet is karban kell tartani, ami plusz költséget jelent. Ha a keresési mező egyik indexmezővel sem esik egybe akkor kupac szervezést jelent. Az indexrekordok szerkezete (a,p) , ahol “a” egy érték az indexelt oszlopban, “p” egy blokkmutató, arra a blokkra mutat, amelyben az A=a értékű rekordot tároljuk. Az index mindig rendezett az indexértékek szerint.
Elsődleges index
Elsődleges index esetén a főfájl is rendezett (az indexmező szerint), így emiatt csak egy elsődleges indexet lehet megadni. Elég a főfájl minden blokkjának legkisebb rekordjához készíteni indexrekordot, így azok száma: T(I) = B (ritka index). Indexrekordból sokkal több fér egy blokkba, mint a főfájl rekordjaiból: bf(I) > > bf, azaz az indexfájl sokkal kisebb rendezett fájl, mint a főfájl: B(I) = B/bf(I) < < B = T/bf.
Keresésnél, mivel az indexfájlban nem szerepel minden érték, ezért csak fedő értéket kereshetünk, a legnagyobb olyan indexértéket, amely a keresett értéknél kisebb vagy egyenlő. Fedő érték keresése az index rendezettsége miatt bináris kereséssel történik: log{2}(B(I)). A fedő indexrekordban szereplő blokkmutatónak megfelelő blokkot még be kell olvasni. Így a költség 1+log{2}(B(I)) < < log{2}(B) (rendezett
eset).
Módosításnál a rendezett fájlba kell beszúrni. Ha az első rekord változik a blokkban, akkor az indexfájlba is be kell szúrni, ami szintén rendezett. A megoldás az, hogy üres helyeket hagyunk a főfájl, és az indexfájl blokkjaiban is. Ezzel a tárméret duplázódhat, de a beszúrás legfeljebb egy főrekord, és egy indexrekord visszaírását jelenti.
Másodlagos index
Másodlagos index esetén a főfájl rendezetlen (az indexfájl mindig rendezett).
Másodlagos indexből többet is meg lehet adni. A főfájl minden rekordjához kell készíteni indexrekordot, így az indexrekordok száma: T(I) = T (sűrű index). Indexrekordból sokkal több fér egy blokkba, mint a főfájl rekordjaiból: bf(I) > > bf, azaz az indexfájl sokkal kisebb fájl, mint a főfájl: B(I) = T/bf(I) < < B =T/bf.
Az indexben a keresés az index rendezettsége miatt bináris kereséssel történik: log{2}(B(I)) . A talált indexrekordban szereplő blokkmutatónak megfelelő blokkot még be kell olvasni. Így a költség 1+log{2}(B(I)) < < log{2}(B) (rendezett eset). Az elsődleges indexnél rosszabb a keresési idő, mert több az
indexrekord. A főfájl kupac szervezésű. Rendezett fájlba kell beszúrni. Ha az első rekord változik a blokkban, akkor az indexfájlba is be kell szúrni, ami szintén rendezett. Megoldás: üres helyeket hagyunk a főfájl, és az indexfájl blokkjaiban is. Ezzel a tárméret duplázódhat, de a beszúrás legfeljebb egy főrekord és egy
indexrekord visszaírását jelenti.
Bitmap index
A bitmap indexeket az oszlopok adott értékeihez szokták hozzárendelni, az alábbi módon:
- Ha az oszlopban az i. sor értéke megegyezik az adott értékkel, akkor a bitmap index i. tagja egy 1-es.
- Ha az oszlopban az i. sor értéke viszont nem egyezik meg az adott értékkel, akkor a bitmap index i. tagja egy 0.
Így egy lekérdezésnél csak megfelelően össze kell AND-elni, illetve OR-olni a bitmap indexeket, és az így kapott számsorozatban megkeresni, hol van 1-es. A bináris értékeket szokás szakaszhossz kódolással tömöríteni a hatékonyabb tárolás érdekében.
Többszintű indexek
Az indexfájl (1. indexszint) is fájl, ráadásul rendezett, így ezt is meg lehet indexelni, elsődleges index-szel. A főfájl lehet rendezett vagy rendezetlen (az indexfájl mindig rendezett) . A t. szintű index: az indexszinteket is indexeljük, összesen t szintig.
A t. szinten bináris kereséssel keressük meg a fedő indexrekordot. Követjük a mutatót, minden szinten, és végül a főfájlban: log{2}(B(I(t))) + t blokkolvasás. Ha a legfelső szint 1 blokkból áll, akkor t+1 blokkolvasást jelent. Minden szint blokkolási faktora megegyezik, mivel egyforma hosszúak az indexrekordok.
A t. szinten 1 blokk: 1 = B/(bf(I)^t). Azaz t = log{bf(I)}(B) = log{2}(B), tehát jobb a rendezett fájlszervezésnél. A log{bf(I)}(B) < log{2}(B(I)) is teljesül általában, így az egyszintű indexeknél is gyorsabb.
B-fa index
Logikailag az index egy rendezett lista. Fizikailag a rendezett sorrendet táblába rendezett mutatók biztosítják. A fa struktúrájú indexek B-fákkal ábrázolhatóak. A B-fák megoldják a bináris fák kiegyenlítetlenségi problémáját, mivel “alulról” töltjük fel őket. A B-fa egy csomópontjához több kulcsérték tartozhat. A mutatók más csomópontokra mutatnak, és így az összes kulcsértékre az adott csomóponton.
Mivel a B-fák kiegyenlítettek (minden ág egyenlő hosszú, vagyis ugyanazon a szinten fejeződik be), kiküszöbölik a változó elérési időket, amik a bináris fákban megfigyelhetőek. Bár a kulcsértékek és a hozzájuk kapcsolódó címek még mindig a fa minden szintjén megtalálhatók, és ennek eredménye:
egyenlőtlen elérési utak, és egyenlőtlen elérési idő, valamint komplex fakeresési algoritmus az adatfájl logikailag soros olvasására. Ez kiküszöbölhető, ha nem engedjük meg az adatfájl címek tárolását levélszint felett. Ebből következően: minden elérés ugyanolyan hosszú utat vesz igénybe, aminek egyenlő elérési idő az eredménye, és egy logikailag soros olvasása az adatfájlnak a levélszint elérésével megoldható. Nincs szükség komplex fakeresési algoritmusra.
A B+ fa egy olyan B-fa, mely legalább 50%-ban telített. A szerkezeten kívül a telítettséget biztosító algoritmusokat is beleértjük.
A B* fa egy olyan B-fa, mely legalább 66%-ban telített.
Hasító index
A rekordok edényekbe (bucket) particionálva helyezkednek el, melyekre a h hasítómezőn értelmezett függvény osztja szét őket. Hatékony egyenlőségi keresés, beszúrás, és törlés jellemzi, viszont nem támogatja az intervallumos keresést.
A rekordokat blokkláncokba soroljuk, és a blokklánc utolsó blokkjának első üres helyére tesszük a rekordokat a beérkezés sorrendjében. A blokkláncok száma lehet előre adott (statikus hasítás, ekkor a számot K-val jelöljük), vagy a tárolt adatok alapján változhat (dinamikus hasítás).
A besorolás az indexmező értékei alapján történik. Egy y h(x) ∈ {1, .., K} hasító függvény értéke mondja meg, hogy melyik kosárba tartozik a rekord, ha x volt az indexmező értéke a rekordban. A hasító függvény általában maradékos osztáson alapul (például mod(K)). Akkor jó egy hasító függvény, ha nagyjából egyforma hosszú blokkláncok keletkeznek, azaz egyenletesen sorolja be a rekordokat. Ekkor a blokklánc B/K blokkból áll.
A keresés költsége:
- Ha az indexmező és keresési mező eltér, akkor kupac szervezést jelent.
- Ha az indexmező és keresési mező megegyezik, akkor csak elég a h(a) sorszámú kosarat végignézni, amely B/K blokkból álló kupacnak felel meg, azaz B/K legrosszabb esetben. A keresés így K-szorosára gyorsul.
A tárméret B, ha minden blokk nagyjából tele van. Nagy K esetén azonban sok olyan blokklánc lehet, amely egy blokkból fog állni, és a blokkban is csak 1 rekord lesz. Ekkor a keresési idő: 1 blokkbeolvasás, de B helyett T számú blokkban tároljuk az adatokat. Módosításnál B/K blokkból álló kupac szervezésű kosarat kell módosítani
Lekérdezés végrehajtás lépései
- Elemzés: egy elemző fát építünk fel, amely a lekérdezést és annak szerkezetét jellemzi (attribútumok, táblák, jogosultságok ellenőrzése)
- Lekérdezés átírás: Az elemző fából egy kezdeti lekérdezéstervet készítünk, amelyet átalakítunk egy ezzel ekvivalens tervvé, aminek végrehajtási ideje várhatóan kisebb lesz. Elkészül a logikai lekérdezésterv, amely relációs algebrai kifejezéseket tartalmaz.
- A logikai tervet átalakítjuk fizikai tervvé úgy, hogy a logikai terv operátoraihoz kiválasztunk egy algoritmust, valamint meghatározzuk az operátorok végrehajtási sorrendjét. A fizikai terv olyan részeket is tartalmaz, hogy pl. kell-e rendezni, hogyan férünk hozzá az adatokhoz.
Algebrai optimalizálás
Az optimalizáló algoritmus a következő heurisztikus elveken alapul:
- Minél hamarabb szelektáljunk, hogy a részkifejezések várhatóan kisebb relációk legyenek.
- A szorzás utáni kiválasztásokból próbáljunk természetes összekapcsolásokat képezni, mert az összekapcsolás hatékonyabban kiszámolható, mint a szorzatból történő kiválasztás.
- Vonjuk össze az egymás utáni unáris műveleteket (kiválasztásokat és vetítéseket), és ezekből lehetőleg egy kiválasztást, vagy vetítést, vagy kiválasztás utáni vetítést képezzünk. Így csökken a műveletek száma, és általában a kiválasztás kisebb relációt eredményez, mint a vetítés.
- Keressünk közös részkifejezéseket, amiket így elég csak egyszer kiszámolni a kifejezés kiértékelése során.
Konzisztens adatbázis
Az adatbázisokra különböző megszorítások adhatóak meg. Az adatbázis konzisztens állapotban van, ha kielégíti az összes ilyen megszorítást. Konzisztens adatbázis egy olyan adatbázis, amely konzisztens állapotban van.
A konzisztencia sérülhet a következő esetekben:
- Tranzakcióhiba: hibásan megírt, rosszul ütemezett, félbehagyott tranzakciók.
- Adatbázis-kezelési hiba: az adatbázis-kezelő valamelyik komponense nem, vagy rosszul hajtja végre a feladatát.
- Hardverhiba: elvész egy adat, vagy megváltozik az értéke.
- Adatmegosztásból származó hiba.
