Műveletek optimalizálása

A relációs adatbáziskezelő rendszereket korábban egy kis operációs rendszerhez hasonlítottuk az elvégzendő feladatok és a rendszer bonyolultságát illetően. A számos RDBMS által elvégzendő tevékenységek közül már érintettük a konkurens hozzáférést és a védelmet szabályozó mechanizmusokat. Az itt tanult fogalmak az operációs rendszereknáél megismert mechanizmusok között számos rokon vonást figyelhettünk meg, de láthattuk azt is, hogy az RDBMS-ekben mennyivel sokréttűbben és sokoldalúbban jelentkeznek e feladatok. A következő fejezetben egy olyan RDBMS komponensre térünk rá, melynek nehezebben lehetne operációs rendszerbeli megfelelőjét megkeresni, amely sokkal egyedibb vonása az adatbáziskezelésnek, mint az előző elemek. Ez a komponens a műveletek optimalizálásának feladata. Amikor egy RDBMS előtt ülve kiadunk egy lekérdezési parancsot, akkor e 2parancsot a már jól ismert SQL nyelv segítségével fogalmazzuk meg. Ha például egy kereskedelmi vállalat információs rendszerébe jelentkeztünk be, és a piros színű kerékpárok vevőnként összesített rendelési értékeire vagyunk kiváncsiak, akkor az adatokat a követekező SQL SELECT utasításhoz hasonló paranccsal tudjuk előállítani: SELECT SUM(r.db*t.ear), r.vevo FROM rendeles r, termek t WHERE r.termek = t.tid AND t.szin = 'PIROS' GROUP BY r.varos; A példában a rendelés tábla darabszám mezőjét szorozzuk meg az illeszkedő termék tábla ear (egységár) mezőjével, hogy megkapjuk a rendelési értéket. A kiadott SQL utasítás az RDBMS-nek szól. Az RDBMS a megkapott utasítás alapján beolvassa az adatbázisból a szükséges adatokat és elvégzi az eredmény eléréséhez szükséges műveleteket. Az adatokat elemi adatkezelő utasítások sorozatával tudja az RDBMS beolvasni és feldolgozni, hiszen az alacsony, esetleg RMS szintű utasítások között nincs olyan művelet, mely megfeleltethető lenne példáula fenti SELECT utasításnak. A RDBMS egyik feladata tehát a magas absztrakciós szinten (SQL) megfogalmazott utasításokat átkonvertálni alacsony szintű adatkezelő utasításokká, hogy azokat végrehajtva megkapja a kívánt eredményt. Ez a konverzió nem idegen számunkra, hiszen még a DBMS funkciók tárgyalásakor említettük a DBMS-ekhez kapcsolódó függetlenségi szinteket és e sziintek jelentőségét. Az SQL - RMS konverzió épp e függetlenséget biztosítja, hiszen a felhasználó mindíg ugyanazon módon, az SQL szintaktikával adhatja ki utasításait, függetlenül attól, hogy az adatbázis milyen fizikai szerkezettel rendelkezik. Amennyire hasznos e függetlenség és konverzió a felhasználó szemszögéből názve, annyira nagy fejtörést okozhatnak e szolgáltatások az RDBMS tervezőinek, impelemtálóinak. A megfelelő műveletvégzéshez készíteni kell egy olyan RDBMS komponenst, amley elvégzi e konverziót. Sőt nemcsak hogy elvégzi, hanem a lehető legjobban végzi el. Ugyanis egy összetett, több elemi műveletből összeálló műveletsort többféleképpen is végre lehet hajtani, miközben a különböző végrehajtási változatok igen eltérő hatékonyságot adhatnak. Ha például vesszük az előző SQL utasítást, akkor a rekordok beolvasását és a rekordok értékvizsgálatát véve elemi műveleteknek, akkor már itt megadhatunk két olyan végrehajtási műveletsort, melyek mindegyike a kivánt eredményhez vezet, úgy hogy lényeges hatékonyság különbséget mérhetünk e két út között. Az első út az lesz, amikor beolvassuk sorba a rendeles rekordokat, majd minegyiknél sorba vesszük a összes termek rekodot, s képezzük a párosukat.Ezután minden párosnál ellenőrizzük, hogy a szín mező értéke piros- e. Ha nem lefeledjük a rekordot, ha pedig igen aktualizáljuk a megfelelő cvsoportot. A másik megoldásnál előbb átnézzük a termék rekordokat, s csak a piross színűeket hagyjuk meg a következő fázishoz, melyben a piros színű termékek rekordjait párosítjuk az előbb leírt módon a rendeles rekordokkal, s a párosított rekordokat rögtön bevonhatjuk a megfelelő csoportba. E két módszer hatékonyság különbsége könnyen ellenőrizhetőp az alábbi egyszerű számítással. Az első esetben N*M nagyságrendű rekordolvasásra volt szükség, ha N jelöli a rendeles és M a termék rekordokat, hiszen minden termek és rendeles rekordpárosítást képeztünk és ellenőriztünk is. A második változatban M lépésben kiszűrhettük a piros színű termékhez tartozó rekordokat. Ha felteszszük, hogy kb. a termékek 1 százaléka piros bicikli, akkor csak 0.01*N*M a vizsgált rekordpárosok darabszáma. A két végrehajtás között így egy két nagyságrandi különbség állt elő. E kis példa is mutatja, hogy éredmes megvizsgálni a műveletek különböző végrehajtási változatait, kiválasztva a felhasználó számára a leghatékonyabb változatot. A változatok hatékonyságvizsgálata is az RDBMS-ek feladatkörébe tartozik, ahol a változayok elemzésének célja a leghatékonyabb, a legoptimálisabb változat kiválasztása. Az RDBMS rendszerhez tartozik tehát egy művelet optimalizálási (query optimization) modul. E modul feladata a magas szinten megadott adatkezelő utasítások leghatékonyabb végrehajtási változatának a meghatározása. A műveletek optimalizálása az RDBMS-ek egyik lényeges, hangsúlyos komponensét testesítik meg. E kiemelkedő fontosságot az indokolja, hogy az RDBMS esetében igen nagy a függetlenségi, konverziós szint,amelyet át kell hidalnia az RDBMS-nek. Mivel minnél nagyobb e távolság, annál lazább a indulú utasítás és a kapott utasítás kapcsoltata, annál nagyobb a megoldási változatok sokszínűsége, annál nagyobb lehet az egyes változatok közötti hatékonysági különbségek. Az optimalizáslási modul nélkül egy fix, rögzített konverziós mechanizmus a legtöbb esetben igen rossz megoldást eredményezhetne, ezáltal jelentősen megnövelve a lekérdezéshez tartozó válaszidőt. A válaszidők két nagyságrendeli növekedése azonban már oda vezetne, hogy az RDBMS-ek csak igen kis méretű feladatok megoldására lennének alkalmasak, így elterjedségük és szerepük is jóval kisebb szerepet foglalna el. Ebben az esetben valószínűleg nagyobb teret foglalnának el még ma is hálós adatbázisok, mivel ott a sokkal kisebb konverziós szint miatt hatékonyabb adatkezelés érhető el, aminek az ára azonban az, hogy a felhasználónak kell leereszkednie a fizikai szinthez. Az RDBMS-ek tehát az optimalizálási komponens nélkül nem játszhatnának akkora szerepet az adatkezelésben, mint ma játszanak. Ezért azt mondjuk, az optimalizálási komponens az RDBMS-ek szükségszerű komponense. A másik oldalról az opttimalizálási komponens a szükségszerűség mellett egyfajta lehetőséget is jelent. Lehetőséget a kiemelkedése, a versenyképsesség fokozására. Durva hasonlattal az optimalizálás olyan mint az autók üzemanyag ellátó rendszere, mely szükséges minden autónál, hogy elfogadható sebességgel tudjon menni, de egyben lehetőség is arra, hogy a másik, a konkurencia által alkalmazott módszerektől eltérő, azoktól jobb megoldást valósítsunk meg a saját rendszerünkben. Az RDBMS esetén annyiban is jelenthet az optimalizálási elem versenylehetőséget, hogy nem létezik egyértelmű, legjobb megoldás. Vannak bevált módszerek, mechanizmusok, de az egyre újabb szolgáltatások, funkciók megjelenésével, mindíg szükség nyílik a jelentkező műveletek optimalizálására, esetenként a régi,bevált módszerek mellett is lehet még hatékonnyabbat felfedezni. Mielőtt az optimalizálás részleteibe belemennénk, néhánt általános megjegyzés kívánkozik bevezetésként. - A felhasznált algoritmusok alapvetően heurisztikus jellegűek, azaz az optimalizálás menete az emberi természetes gondolkodásmódot követve, egy kevesebb számításokat igénylő módszert alkalmaz. A heurisztikus módszerek általános jellemzője, hogy a módszerrel kapott megoldások feltétlenül, sőt igen ritkán esnek egybe a globális optimum ponttal, ehelyett egyfajta jó közelítést szolgáltatnak. A pontosság terén okozott hátrányt viszont a módszer a gyorsaságával kompenzálja. Egyszerű döntések, döntési elvek sorozatán keresztül jutunk el a megoldáshoz. A különböző heuriszitikus módszereket igen gyakran alkalmazzák összetett rendszerek optimalizálásához, amikor nem létezik olyan egzakt módszer, amellyel elfogadható időn belül eredményt lehetne elérni. - Az RDBMS rendszerek művelet optimalizáló komponensét és az optimalizálás mechanizmusát is gyakran nevezik query optimalizálásnak. Az optimalizáló modul azonban nemcsak a SELECT műveletekben kerülhet bevonásra, hanem minden olyan esetben is, amikor az adatokhoz hozzá kell férni. Így egy UPDATE utasításnál is szerepe lehet az optimalizálásnál, különösen akkor, ha az UPDATE művelet egy összetettebb WHERE taggal rendelkezik. A query jelölést viszont az indokolja, hogy elsősorban az információk összegyüjtésénél van szükség optimalizáló elemre, mivel a lekérdező utasítás alakja a legrugalmasabb és legsokrétűbb az SQL utasítások között. - Az RDBMS-eknél a korábbi adatmodelleken alapuló adatbázis kezelőktől eltérően a műveletek hatékony végrehajtásának biztosítása elsősorban az adatbáziskezelő feladata. A korszerűbb RDBMS esetében a felhasználó szerepe egyre csökken az optimális végrehajtás kiválasztásában. Ezen változási tendenciát elemezve, felmerülhet a kérdés, vajon jó-e, ha a rendszer teljes egészében kezébe veszi a felügyelte, kell-e hagyni valamilyen szerepet a felhasználónak is. Ezzel a kérdéssel kapcsolatban igen különböző véleményeket lehet hallani, amelyből az a következetetés vonható le, hogy a mai rendszerekben és a jövőben is még sokáig a felhasználónak is lényeges szerepe lesz. Az Oracle kézikönyv a következőképpen jellemzi a fennálló helyzetet: '... adódhatnak olyan helyzetek, amikor a felhasználó jobb, hatékonyabb végrehajtási módot tud kijelölni, mint amit az optimalizáló választ.' A felhasználó és az optimalizáló modul mellett a következő érvéket szokták felhozni. Az optimalizáló modul előnyei: - Szélesebb ismeret a letárolt adatérétekekről - Gyorsabb numerikus kiértékelési mechanizmus - Szisztematikus értékelés - Algoritmusa több szakember együttes tudását hordozza - Dinamikusan, minden művelet előtt, az aktuális feltételeket figyelembe véve értékelődik ki. Az emberi irányítás előnyei: - Szélesebb általános ismeret, a probléma szemantikai tartalmának megértése - Nagyobb szabadság a felhasználható módszerek, eszközök tekintetében. - Váratlan helyzeteke jobban felkészült. Ezen érveket összevetve azt mondhatjuk, hogy az emberi és RDBMS-be épített optimalizálás egymást kiegészítve meűködik a legjobban. A tökéletes működés egy jó optimalizáló modult és egy széles látókörű, sok tapasztalattal rendelkező rendszergazdát igényel, aki tudja hogy az adott problémánál mely fizikai tárolási paramétereken kell változtatni a hatékonyság javításához. Az optimalizálás vizsgálatakor mindenek előtt tekintsük át, hogy hogyan illeszkedik bele az RDBMS működési mechanizmusába az optimalizálás folyamata. Az optimalizáló modul az RDBMS data system komponsnéhez tartozik, amelyben a fiziaki műveletek előkészítése történik. A felhasználó által kapott SQL utasítást a parancsértelmező előbb darabokra szedi, hogy ellenőrizze annak helyességét és kigyüjtse a hivatkozott objektumok listáját. Ezen lista alapján ellenőrizhető, hogy léteznek-e és elérhetők a megjelölt objektumok. Ha minden objektumhoz engedélyezett a hozzáférés, akkor következik a műveleti elemek értelmezése, az optimális végrehatási terv összeállítása, vagyis az optimalizálás folyamat. Az optimalizálás vázlatos menetét szemlélteti a következő ábra. A működési vázlatnak megfelelően a felhasználó által megadott SQL utasításból a rendszer értelmezi, hogy milyen műveleteket kell végrehajtania az eredmény eléréséhez. Első lépésben a műveleteket még nem a fizikai IO szinten értelmezi, hanem a magasabb absztarkciós szinten álló relációs algebrai szinten. Ez azért is könnyebb feladat, mivel a bejöző SQL utasítás is a relációs algebra műveleteire épül, azaz sokkal közvetlenebb a kapcsolat az SQL utasítás és a relációs algebrai műveletek között, mint az SQL utasítás és az alacsony szintű rekord orientált műveletek között. Az optimalizálás induló fázisában tehát az SQL utasításokat felbontják relációs algebrai műveletekre. Ha újra elővesszük a korábbi SQL példát, vagyis a SELECT SUM(r.db*t.ear), r.vevo FROM rendeles r, termek t WHERE r.termek = t.tid AND t.szin = 'PIROS' GROUP BY r.varos; utasítást, akkor ebben az SQL utasításban több, különböző művelet tipusokhoz tartozó elemi relációs algebrai műveleteket is felfedezhetünk: - szelekció ... t.szin = 'PIROS' ... ... r.termek = t.tid ... - projekció SELECT ... r.vevo... SELECT ... r.db*t.ear ... - join ... FROM rendeles r, termek t ... - csoportképzés .. GROUP BY r.varos - számított mező, aggregációs függvények .. SUM(...) Mivel a SELECT utasítások egymásba is ágyazhatók, ezért a rendszernek igen sok elemi relációs műveletet tartalmazó, összetett SQL utasításokra is fel kell készülnie. Az értelmezés során azonban nem elegendő csupán az elemi relációs műveletek felsorolása, hiszen adott művelethalmaz esetén az elemi műveletek sorrendje is lényeges szerepet játszik. A kijelölt elemi műveleteket nem lehet tetszőleges sorrendben végrehajtani. Ha ugyanis az r.db*t.ear mezőt a join művelet előtt próbálnánk végrehajtani, akkor hibába ütköznénk, hiszen még nem létezik olyan tábla, mely mindkét hivatkozást tartalmazná. A helyes sorrendben előbb a join művelet kerül végrehajtásra, aztán következhet csak a projekció és számítás elvégzése. Az egyes relációs algebrai műveletek között tehát egyfajta végrehajtási sorrenden alapuló függőség van. E függőség pontos alapja az adatkapcsolatok rendszere lesz, ami arra utal, hogy az egyes műveletek más elemi műveletek eredményeire épülnek. Az előbbi példában a projekció a join eredményét használja fel. Az elemi relációs algebrai műveletek és a közöttük fenálló kapcsolatok együttes ábrázolására egy hierarchikus gráfot alkalmaznak, melynel elnevezése QGM (query graph model). A QGM leírás megadja, hogy milyen műveleteket és milyen sorrendben kel végrehajtani. Az induló QGM előállításához a kapott SQL utasítást fordítják át műveleti gráffá. A lekézés során az SQL utasítások természetesen strukturális felépítéséből indulnak ki. Ez a sorrend azonban nem mindíg jelent egyben optimális sorrendet. Így például az SQL strukturális sorrendje esetén a szelekció később következik, mint az join alaptábla előállítása, viszont sok esetben célszerűbb a szelekciót előbb elvégezni. Ezért az optimalizálás soronkövetkező lépésében a QGM gráfot alakítják át oly módon, hogy az hatékonyabb műveletvégrehajtást eredményezzen, mintaz induló QGM hierarchia. A javított QGM leírás még nem használható fel közvetlenül a végrehajtáshoz, mivel olyan magasabb sizntű, relációs algebrai műveleteket tartalmaz, melyeknek nincs megfelelő RMS szintű utasításpárjai. A végrehajtáshoz előbb le kell fordítani a relációs algebrai műveleteket a fizikai szintre. Ennek során többek között el kell dönteni, hogy milyen módon fogja a rendszer beolvasni az érintett adatokat az adatbázisból. Az SQL utasításnak a fizikai szinten leírt struktúráját nevezik QEP (query execution plan) szerkezetnek. Egy adott QGM esetén a legtöbb relációs elgebrai műveletet több különböző elemi műveletsorozattal is meg lehet oldani. Az optimalizálás következő feladata e változatok közül a megfelelő kiválasztása. A kiválasztás során értékelve az adatbázis aktuális állapotát, módosíthatók az induláskor felállított QEP leírások. A javított QEP az optimalizáló modul kimenő eredménye, melyet a végrehajtó modul fog megkapni. A QEP elemei már olyan szinten vannak, hogy közvetlenül végrehajthatók az ott megadott alacsony szintű fizikai szintű utasítások. A következőkben részletesen elemezzük a QGM, QEP felépítését és az optimalizálásának lépéseit. A QGM csomópontjaiban az egyes relációs algebrai műveletek helyezkednek el. A QGM élei irányítottak, egy A csomópontból akkor mutat él a B csomópontba, ha a B művelet felhasználja az A művelet eredményét. A csomópontokban a műveletek megadására számos formalizmus létezik, melyek közül mi a Starburst sémát fogjuk bemutatni. A Starburst formalizmusban a csomópontokat téglalappal jelölik, melyekhez csatolják a művelet azonosítását, a művelet paramétereit. A művelet bemenő adatait azon csomópontokból lehet meghatározni, melyekből adatfüggőségi nyíl mutat ezen csomópontba. A téglalap tehát minden olyan információt tartalmaz, mely alapján egyértelműen meghatározható az oda tartozó művelet. A teljes művelet lefedése érdekében az egyes alaptáblákhoz való hozzáférést, az alaptáblákat is külön szimbólummal jelölik, melynek alakja egy duppla keretű téglalap. A QGM Startburst rendszer teljes hierchiájának bemutatására vegyük az alábbi SQL utasítást: SELECT o.megv, a.fiz FROM osztaly o, atlfiz a WHERE o.oid = a.oid AND a.fiz > 50000; ahol az atlfiz tabla egy nézeti tábla, melyet az alábbi utasítással hozzunk létre: CREATE VIEW atlfiz(fiz,oid) AS SELECT AVG(fiz), oid FROM dolgozok GROUP BY oid; A példában egy dolgozó tábla tartalmazza a dolgozók adatait, köztük egy fizetés (fiz) mezőt és egy idegen kulcsot az osztályra (oid). A SELECT utasítással azon osztályok megnevezését és az ott dolgozók átlagfizetését kérdezzük le, amelyekben az átlagfizetés értéke nagyobb, mint 50000. Az osztályok kódjait és átlagfizetését az atlfiz view számolja ki. A végrehajtás során az RDBMS előbb behelyettesíti a VIEW definíót a végrehajtandó SELECT utasításba: SELECT o.megv, a.fiz FROM osztaly o, (SELECT AVG(fiz), oid FROM dolgozok GROUP BY oid) a WHERE o.oid = a.oid AND a.fiz > 50000; Egy zárójelen, vagyis azonos prioritási szinten belül az egyes műveleti elemek természetes sorrendje: - alaptábla olvasása - szelekció - csoportképzés - csoportszelekció - projekció Az induló SQL utasítás feldarabolásánál az SQL kulcsszavai játszanak nagy szerepet, hiszen e kulcsszvak jelzik az egyes részek határait (SELECT, FROM, WHERE, GROUP BY, HAVING). Az esetleges rendezés (ORDER BY) mindig csak a legkülső szint eredményére értelmezhető és ez lesz a legutólsó lépés. A végrehajtás során a nem tartalmazott műveletek átugorhatók. A példánkban e sorrendnek megfelelően előbb a dolgozók tábla olvasása kerül sorra, majd erre a táblára végrehajtanak egy csoportképzést, végül egy projekciót. Az eredményül kapott táblát ezután join-nal összekapcsolják az osztaly táblával. A kapott join táblán előbb egy szelekciót, majd egy projekciót végeznek el. A megfelelő QGM leírás az alábbi alakot ölti. A QGM leírásának egy egyszerűbb változata az operation tree formalizmus, melyben az egyes csomópontokba a részletes szöveges leírás helyett a tömörebb algebrai műveleti jelet (S:szelekció, P:projekció, *:join ) adják meg. Ebben a fejezetben a join alatt a táblák Descartes-szorzatát értjük (amely az SQL alapértelmezése is), ezért a továbbiakban a szorzásjellel fogjuk jelölni a join műveletet. A következő ábra egy ilyen formalizmust mutat be. A szokástól eltérően a hierarchiát most fektetve ábrázoljuk. A példában a piros színű autók rendszámait és tulajdonosuk neveit kérdezzük le. auto -> * -> S (eid = tulaj AND szin='piros') -> P (rsz, nev) ^ | ember A kijelzésben megjelenő formai különbségek ellenére minden QGM azonos elvi felépítésű. Ugyan az SQL utasításhoz generált QGM a fejlesztő számárára is érdekes információkat hordoz, a QGM elsődlegesen mégsem a külső szemlélő részére, a nézgetésre készült. A QGM az optimalizálónak gyujt hasznos információt a végrehajtandó műveletről. Mint mondtuk, az induló QGM még rendszerint nem az optimális végrehajtási sorrendet tükrözi. Az optimális QGM eléréshez elemezni kell a QGM felépítését, s szükség esetén bizonyos transzformációkat kell végrehajtani rajta. A transzformációk meghatározásánál fő cél a végrehajtási idő csökkentése. A QGM átalakításában elsődlegesen heurisztikus elvek irányítják az optimalizálást. A fő cél a művelet végrehajtása során mind az igényelt adatmennyiséget, mind az adathozzáférések darabszámát minimálisra csökkenteni. A tapasztalatok és a józan ész alapján ez a törekvés a következő, az query végrehajtáshoz konkrétabban kapcsolódó optimalizálási irányelvekben testesíthetők meg: - A szelekciót és a projekciót minnél hamarabb el kell végezni - Egy adatot minnél kevesebbszer kell érinteni Az első elv azt mondja ki, hogy célszerűbb minnél hamarabb leszűkíteni az érintett adatmennyiséget, hogy a későbbi műveletekben már kevesebb adatot kelljen megmozgatni. Vagyis az érintett adatok leszűkítését a lehető legkorábbi időpontban végre kell hajtani. Ennek oka, hogy a join műveletnél a végrehajtási költség a lineárisnál jobban nől a résztvevő táblák méreteinek függvényében. Emiatt minnél kisebb méretű táblákat kell a join műveletbe bevonni. A második elv azt hangsúlyozza, hogy ha egy táblán több elemi műveletet is kell végezni, például egy projekciót és egy szelekciót, akkor egyszer fésüljük csak át az adattáblát, elvégezve mindkét műveletet egyidejűleg. Ha egymástól elkülönítve hajtanánk végre a két elemi műveletet, akkor a táblát is kétszer kellene átfésülni, ami szintén jelentős többletköltségel járna. A két fő irányelv alapján még konkrétabban megfogalmazhatók a QGM optimalizálásakor követendő lépések. Összeállítható egy optimalizálási algoritmus, melyet követve biztosíthatók a fennti irányelvek betartása. Az optimalizálás egymásutáni lépései a következőkben foglalható össze: - szelekciók felbontása elemi szelekciókra - szelekciók lefele mozgatása - projekciók lefele mozgatása - összetartozó elemek összevonása Az első lépés tehát a szelkciók felbontása elemi szelekciókra. Egy elemi szelekció egy relációs operátorhoz kötődik. Az összetett feltételekben az elemi szelekciókat az AND, OR operátorok kötik össze. Így egy S (auto.tul=ember.id AND auto.szin='piros') feltétel az alábbi két elemi feltételre bontható: S (auto.tul=ember.id) S (auto.szin='piros') Az elemi feltéyelek előnye, hogy jobban behatárolható, hogy mely alaptáblákra vonatkozik. Ezután az egyes elemi feltételek az optimalizálás során egy darabig önnálló életet fognak élni, hogy felhasználásukkal hatékonyabbra alakítsuk át a QGM struktúrát. A második lépésben az egyes elemi szelekciókat áthelyezzük a hierarchiában úgy, hogy minnél előbb végrehajtásra kerüljenek, vagyis minnél közelebb legyenek a hierarchia alsó leveleihez. A lefele mozgatás tehát azt jelenti, hogy a hierarchia alsóbb szintjeihez, az alaptáblákhoz közelebb kerülnek át a szelekciók. Ezzel biztosítjjuk azt, hogy az adatok leszűkítése az első adandó alkalommal megtörténjen. A harmadik lépésben a szelekcióhoz hasnolóan a projekciókat is lecsúsztatjuk az alaptáblák közelébe, hogy ott elvégezve őket, minnél hamarabb leszűkítsük a kezelt adatmennyiséget. Az utólső lépésben az azonos objektumhoz összegyült elemi műveletek egy kötegbe gyüjtjük, hogy egyszerre, az objektum egyszeri átolvasásával hajtsuk végre őket. Az így kapott QGM elrendezést egy optimális elrendezésnek lehet tekinteni. Visszatérve az elemi műveletek lecsúszatatására látható, hogy nem lehet minden szelekciót vagy projekciót rögtön az alaptáblákhoz lecsúszatatni, bizonyos szelekciók,projekciók fennakadhatnak a köztes műveleti csomópontoknál. Annak eldöntésére, hogy meddig mozgatható le egy elemi művelet, a relációs algebrából adódó formai szabályokat, tételeket lehet alkalmazni. Az egyes szabályok arra vonatkoznak, hogy milyen átalakítást végezhetünk a végrehajtási sorrenden úgy, hogy közben a végeredmény nem változik. Az induló és a javított QGM ekvivalenciája, vagyis az, hogy mindkettő ugyanazt az értéket adja, elemi követelmény, hiszen az optimalizálónak nem szabad változtatni a kiadott utasítás értelmén jelentésén. Ezért az optimalizálás során csak olyan átalakítások végezhetők, melyek a QGM-et ekvivalens QGM-be viszik át. Ez a követelmény az optimalizálás ekvivalenci követelményének is nevezhető. A megengedett átalakítások a relációs algebra definíciájából következnek és a következő szabályokat foglalják magukba: Az első két szabályazt mondja ki, a join művelete kommutatív és asszociatív. A harmadik szabály szerint két egymáskövető projekcióból az első elhagyható, ha a második magába foglalja azt. A negyedik sabály szerint ugyanazon objektumra vonatkozó szlekciók sorrendje tetszőleges lehet. Az ötödik szabály szerint egy projekció és egy szelekció sorrendjét felcserélni, ha a szelekció csak a projekcióban is szereplő mezőkre vonatkozik. A hatodik szabály pedig azt mondja ki, hogy egy joinra vonakozó szelekciónál, ha a szelekció csak az egyik táblára vonatkozik, akkor az eredmény előállítható a szelektált alaptábla és a másik tábla join műveletével is. A hetedik szabály szerint a projekció és a join sorrendje felcserélhető úgy, hogy a tényező táblákra levisszük a megfelelő projekciót. Vagyis előbb elvégezhető a táblára vonatkozó projekció rész, s elegendő a projekcióval szűkített táblákra elvégezni a join műveletet. A nyolcadik szabály alapján egy projekció és egy szelekció előtt a táblát nyugodtan le lehet szűkíteni azon mezőire, melyek vagy a projekciónál vagy a szelekciónál válnak szükségessé. Más mezőkre nincs szükség, hiszen azok úgyis el fognak veszni a projekció után. E szabályok mindegyike igen fontos az optimális QGM elrendezés kialakításában és a valóságban e szabályok segítségével lehet a QGM algebrai optimalizálását elvégezni. Itt most azért emeltük ki az algebrai jelzőt az optimalizálás előtt, mivel az átalakításnál formális algebrai szabályokra alapozva végezzük el a javításokat. Ettől egy letérő mechanizmust fogunk tapasztalni a QEP optimalizálásánál, ahol az aktuális rendszer állapotot figyelembe vételével összehasonlítjuk az egyes változatok költségigényét és e számítások eredményei alapján jelöljük a ki a legjobbnak bizonyuló algoritmust. A QGM algebrai optimalizálására vegyük az alábbi példát: SELECT A1,A2,B4,C3 FROM A,B,C WHERE A.A1 = B.B3 AND B.B4 = C.C3 AND A.A2 = X; A SELECT utasítás értelmezésével kapott induló QGM gráf az alábbi alakot ölti. Az átalakítás első lépcsőjében a szelekciókat felbontjuk elemi szelekciókra. Az így kapott QGM struktúrát mutatja a következő ábra. Eztkövetően az elemi szelekciókat levisszük az alaptáblákhoz közel. A mozgatásnál a megadott transzformációs szabályokat betartva haladhatunk előre. A mozgatás után kapott QGM elrendezést adja meg a következő ábra: A következő lépésben a projekciós elemeket hozzuk le ameddig csak lehet. Ennél a műveletnél is a megadott transzformációs szabályokra támaszkodhatunk. Az így kapott QGM-et mutatja a soromkövetkező ábra. A kapott QGM gráfban minden tábla olvasás után csak egyetlen egy projekció és csak egyetlen egy szelekció elem áll, ezért most további összevonásokra nincs szükség. Az QGM előállítása után a fizikai szintű műveletek felé fordul a figyelem. Ezen a szinten már nem absztrakt relációs algebrai műveletk állnak a végrehajtást leíró gráf csomópontjaiban, hanem konkrét fizikai algoritmusok és módszerek. E gráfot nevezzük a QEP (query execution plan) gráfnak. A QEP csomópontjaiban már nevesített eljárásokat adunk meg, melyek mögött implementált rutinok állnak, melyek meghívhatók, végrehajthatók. A gráf felépítése különben megegyeik a QGM felépítésével. A következő ábra egy minta QEP szerkezetet mutat be. Mint látható itt olyan jelölések szerepelnek a csomópontoknál, mint nested loop, table scan, stb. Ezek mindegyike egy-egy konkrét mechanizmust, algorimtust jelent. A nested loop például egy join műveletet megvalósító eljárást azonosít. Amikor a végrehajtó megkap majd egy QEP szerkezetet, akkor a levelektől elindulva, sorra meghívja az ott megadott eljárásokat, majd az eredmények birtokában továbblép. Akkor kezdi meg egy új csomópont végrehajtását, ha a hozzá szükséges bemenő adatok már mind megvannak, vagyis az odavezető nyilak induló csomópontjaiban már mindenhol lefutott a kijelölt művelet. A gyökérben megadott művelet befejesésekor lesz kész az SQL utasítás végrehajtása. A QEP optimalizálása is lényeges feladata az RDBMS-nek, hiszen még itt is lényeges előnyt lehet szerezni a megfelelő algoritmus kiválasztásával. Az optimalizálásnak két különböző elveken nyugvó változata is létezik e feladat megoldására. Az egyik a szabályokon alapuló optimalizálás. Ekkor a megoldást egy szabályrendszer alapján határozzák meg, melyben általánosan igaz irányelveket tartanak nyilván. Ez a módszer az algebrai optimalizáláshoz hasonlítható, hogy nem vizsgálja meg, pontosan milyen táblákon is kell a műveletet végrehajtani. Ez ugyan lerövidíti a módszer kiválasztásának idejét, de számos esetben a kezelt táblák mérete is befolyásolhatja, hogy melyik is az optimális választás. Ha például kicsi a tábla mérete, akkor olyan mechanizmust célszerű választani, mely a memóriában is gyorsan végrehajtható. Nagyobb állományok esetén nár fontos a lemez IO műveletek minimalizálása is. Az aktuális táblaméreteket is figyelembe vévő módszer a költség függvény alapú optimalizálás. A költségfüggvény egy olyan függvényt jelent, melynek függő változója valamilyen költségérték, amely rendszerint idő szokott lenni, de ritkábban tárolási igényt takar. A költségfüggvény az egyes algoritmusokhoz, eljárásokhoz kapcsolódik és célja az eljárás paramétereinek függvényében megadni az eljárás várható költségét. A paraméterek jelentései és értékhatárai feladatspecifikusak. Egy rendező algoritmus esetén például az elem összehasonlítások számát, mint költséget vizsgálva, a rendezendő tömb mérete lehet egy paraméter. E paraméter függvényében megadva a költséget egy költség függvényt kapunk. A buborék rendezés esetén például e függvénygörbe az x2 függvénnyel azonosan futó alakot vesz fel. A költség függvényen alapuló optimalizálás esetén minden figyelembe vett algoritmus esetére kiszámolják a költség értéket, s összehasonlítva az egyes értékeket, a lekkisebb értékű módszert választják ki végrehajtásra. A query optimalizálásnál a fellépő költségek nagy részét a lemez IO műveletek költsége teszi ki. Mint ismert, egy lemez olvasási/írási művelet ezerszer több időt igényel, mint egy memórán belüli művelet. Ezért a költségek értékelésénél az egyszerűbb algoritmusok csak a lemez kezelési költségeket veszik figyelembe. Ez a legtöbb esetben megfelelő eredményt hoz, viszont vannak olyan esetek, amikor nagyonis rossz eredményt szolgáltat. Ez akkor következik be, ha az algoritmusnak nagyságrendekkel több memórián belüli műveletet kell elvégeznie, mint lemez IO műveletet. Ez bekövetkezhet például szerencsétel adateloszlás esetén is. Ebben az esetekben csak az ad jó megoldást, ha a memórián belüli költségeket is figyelembe vesszük. A gyakorlatban tehát több különböző szintű költségfüggvény definiálható az egyes változatok kiértékelésére és összehasonlítására. Mi példaként két területen fogunk költségfüggvény számolást bemutatni, méghozzá a két legfontosabbnak tekinthető műveleti területen: az első az adatábla egy rekordjának megkeresése, míg a második a natural join megvalósítása. Egy rekord megkersésénél a végrehajtási költséget jelentősen befolyásoló tényezőket véve sorra, érehető, hogy a tábla mérete fontos szerepet játszik. Emellett az indexek, a tárolási paraméterek is beleszólnak az algoritmus végrehajtási költségébe. A költségfüggvények felírásánál új szimbólumokat vezetünk be ezen paraméterek leírásához. A következő szimbólumokra lesz szükségünk: - R: a relációban tárolt rekordok darabszáma (a reláció kardinalitása) - P: egy lapon tárolható rekordok darabszáma, ahol feltesszük, hogy egy IO művelet egylapot mozgat meg egyszerre - I: az index bejegyzések darabszáma a táblára vonatkozóan (ez lehet kisebb értékű, mint R hiszen több rekordban is lehet a kijelölt mezőérték ugyanaz, hiszen nem feltétlenül kulcsmező szerint folyika keresés) - H: a memórián belüli költségek becslése (nincs részletezve) A következőkben részletesen megnézzük, hogy milyen módszerek állnak rendelkezésre egy rekord megkereésére egy táblában. Az egyes lehetőségeknél meghatározzuk a módszer közelítő költségigényét is. A leírásnál nagyjából abban a sorrendben haladunk, ahogy egyre nől a költségigény. A különböző megoldások különböző előzeteses adatstruktúrát tételeznek fel, azaz minnél több kiegészítő infornáció áll rendelkezésre a rekordok elhelyezkedéséről, annál gyorsabb lesz rekord megkeresése is. A példákban a költség értékét a c szimbólummal jelöljük. 1. Clustering index, * m = e c = [R/P/I] Az első esetnek azt válasszuk, amikor egy konkrét mezőértékkel rendelkező rekordot kell megkeresni, s létezik a táblához egy kapcsolódó clustering index szerkezet. A clustering index struktúra egy speciális index struktúrát jelent, amely közel áll a fizikai sorbarendezés elvéhez. A clustering index esetén az azonos indexértékű rekordok fizikailag egymás mellett helyezkednek el. Vagyis, ha két rekordnál azonos az indexmező értéke, akkor e két rekord egyazon lapon, vagy olyan lapokon helyezkedik el, melyek között csupa ilyen indexmező értékű rekord foglal helyet. Mivel egy indexmező értékhez több rekord is tartozhat, annyi lapot kell átolvasbi, amennyi a kijelölt indexmező értékhez tartozik. Mivel R/P a teljes lapok száma, I a különböző indexértékek száma, ezért [R/P/I] jelzi az egy értékhez tartozó lapok darabszámát, ahol [] az egészrész függvényt jelöli. 2. Clustering index, * m < e c = R/P/2 Ha lekérdezés egy intervallumra vonatkozik, nem pedig egyetlen egy értékre, akkor nincs más megoldás, mint bejárni az intervallum minden elemét. Clustering index esetén előbb kikeressük a határelemhez tartozó rekordokat, mely ezután az indextáblában előre lépegetünk az intervallum bejárására. Mivel minden lehetséges indexérték benne van az indexben, ezért minden intervallumbeli rekordot érinteni fogunk. Az egyes indexértékekhez az indextáblából közvetlenül jön a rekord lappoziciója. Mivel a rekordok fizikailag is folytonosan helyezkednek el, ezért a teljes tábla R/P lapot foglal le. Mivel a kerestt intervallum átlagosan a teljes tábla felét teszi ki, ezért az intervallum keresésénél átlagosan a lapok felét kell beolvasni. 3. Normál index, * m = e c = [R/I] Ha keresés egyetlen értékre vonatkozik és normál index létezik a táblához, akkor már [R/I] lapolvasásra van szükség az elem megkereséséhez. A normál index alkalmazásánál az azonos indexértékű rekordok nem feltételenül egymás mellett helyezkednek el, mivel nincs semmi kapcsolat az indexérték és a rekord fizikai poziciója kzöött. Ebben az esetben két azonos indexértékű rekord akár a tábla két egymástól legtávolabbi pontjában is elheytezkedhet. Ezért ebben az esetben minden rekord egy újabb lap beolvasását vonhatja maga után. Mivel a táblában I különböző indexérték fordul elő, így egy indexértékhez [R/I] rekord kapcsolódik, s mivel minden rekord egy lap beolvasását jelentheti, azért ez az érték egyben a keresés költségét is fogja jelenteni. 4. Normál index, * m < e c = [R/2] Ha a keresés nem egy értékre, hanem egy intervallumra vonatkozik, akkor is célszerű az index alkalmazása. Az index előnmye, hogy csak a táblához tartozó lapokat kell beolvasni. Ha az indexet figyelmen kívül hagynánk, akkor jóval több lapot is át kellene olvasni, mint ezt majd nemsokára érinteni is fogjuk, hiszen egy tábla rekordjai az RDBMS-ben rendszerint más táblák adataival keveredve foglalnak helyet. A vizsgált esetben az indexen végigmenve sorra beolvassuk az értékhez tartozó lapokat. Mivel átlagosan a rekordok felét kell érinteni és minden rekord külön lapon is elhelyezkedhet, ezért [R/2] lesz az olvasás költsége. 5. Clustered, de nem akt. index c = R/P + H*R Ha a keresett mezőhöz nem létezik index, akkor nem marad más hátra, mint egy soros olvasási mechanizmust alkalmazása. Ha létezik clustering index, akkor célszerű azt felhasználni, mivel ekkor közvetlenül rá tudunk ugrani a tábla rekodjait tartalmazó lapokra. Mivel a lapok száma R/P, így ennyi lesz lemez IO költsége is. Most azonban a beolvasás után még egy ellenőrzésre is szükség van, amely eldönti, hogy a beolvasott rekord megfelel-e a keresési feltételnek vagy sem. Igy a teljes költség kibővül egy memórián belüli ellenőrzési lépéseket magába foglalóó taggal. 6. Normál index, de nem akt. index c = R + H*R Ha keresett mezőhöz nincs index és a táblához is csak normál index létezik, akkor ezen indexet felhasználva célszerű bejárni a tábla rekordjait. Mivel az egymástkövető indexbejegyzések itt tetszőlegesen különböző lap poziciókra mutathatnak, ezért minden rekordnál egy újabb lapolvasásra lehet szükség. Emiatt ebben az esetben a lemez IO költsége R lesz, hiszen annyi lapot kell átolvasni, ahány rekord tartozik a táblához. Mivel a beolvasott rekord nem feltétlenül fogja a keresési feltételt kielégíteni, ezért most is szükség van egy memórián belüli ellenőrzési lépésre. Ennek mértékle H*R lesz, hiszen minden beolvasott rekodordot ellenőrizni kell. 7. Nincs index, scan c > R + H*R Ha a kereséshez semmilyen kiegészítő információs struktúra nem áll rendelkezésre, akkor át kell olvasni minden olyan lapot, melyen a táblához tartozó rekordok helyezkedhetnek el. Mivel az egymástkövető lemez lapok nem feltétlenül fognak táblabeli elemet tartalmazni, ezért a keresés közben több felesleges lap átolvasását is el kell végeni. Emiatt a tényleges lapolvasások darabszáma, és a keresés IO költsége nagyobb lehet mint R. A lapolvasási költségek mellett itt is figyelmbe kell venni az értékellenőrzés lépését is, így itt is e két elem együttese határozza meg az eredő költséget. A felvázolt költségek elemzéséből kiderül, hogy minden esetben jelentősen meggyorsítja a keresést, ha clustering index létezik a táblához. A minnél több clustering indexnek viszont az szab határt, hogy egyrészt egy táblához csak egyetlen egy clustreing index létezhet (ami egyben a fizikai tárolási poziciót is meghatározza),. m'sr;szt azt is figyelembe kell venni, hogy minden ]jabb index megnöveli a rendszer helyigényét, és megnöveli a DML utasítások végrehajtási idejét. A második példánkban a join algoritmus módszereit tekintjük át. A join művelet az egyik legfontosabb relációs algebrai művelet. Az optimalizálásban a join központi szerepet játszik, aminek két fő oka is van. Az egyik ok az, hogy a join igen gyakori elem, hiszen a felhasználó saját logikai képében igényli a tervezés során a normalizáció jóvoltából szétválasztott elemek újbóli, ideiglenes összefűzését. A felhasználó nemcsak egyes különálló táblák elszigetelt adataira kiváncsi, hanem az egyes táblákban tárolt adatelemek közötti kapcsolatokra is. A kapcsoldódó adatok megjelenítése viszont csak a join művelet segítségével lehetséges. A másik ok abból ered,hogya join egy igen időigényes művelet. Két tábla rekordjainak illesztése sok adatelem átolvasását igényli. Mivel a join időigényes és gyakori műveleti elem, ezért hatékony végrehajtásávaljelentősen fokozható az RDBMS gyorsasági is. E központi szerep miatt az optimalizálásal foglalkozó kutatások egyik fő területévé vált a join művelete. Mi most a join egyik tipusát, a naturtal join műveletét elemezzük. A natural join esetén az illeszkedő táblák mindegyike tartalmaz egy-egy mezőt, melyek értékazonossága szolgál illeszkedési feltételként. Vagyis két rekord akkor lesz illeszkedő, ha mindekettőben ugyanazon értéket tartalmaznak a kiejlölt mezők. A naturál join algoritmusai közül három fő algoritmust mutatunk be. Az első egy egyszerűbb, de kevésbé hatékony eljárás, a nested loop algoritmus. A második egy sort-merge módszer, míg a harmadik módszer a hash join családod mutatja be. A nested loop módszer egy naív módszernek is nevezhető, hiszen egy egyszerű és természetesnek tűnő megoldást választ: képzi az összes lehetséges rekordpárost a kapcsolódó táblákból, majd mindegyik párosra ellenőrzi, hogy megfelel-e a kapcsolódási feltételnek. A rekordpárosok képzésénél egy kettős, egymásba ágyazott ciklust alkalmaz. Ehhez sorba veszi az egyik tábla rekordjait, majd mindegyik rekordra végignézi a másik tábla rekordjait egyenként. Vagyis e másik tábla rekordjait nem egyszer, hanem annyiszor olvassa át, amennyi rekord szerepel az első táblában. Ha R1 és R2 a két tábla rekordjainak darabszáma, akkor a join művelete c * R1 + R2*R1 költségű lesz. Érdekes, hogy a költség nem szimmetrikus. Az első tag az első tábla rekordjainak átolvasási költségét jelenti. A költségfüggvényből látható, hogy a rövidebb táblát célszerű az első táblának választani. A nested-loop módszerhez a következő algoritmus tartozik: for r in T1 do for s in T2 do if illeszkedik(r,s) kiir(r,s) endfor endfor A másik ismertett módszer a sorted merge módszere. Ez azon az elven alapul, hogy rendezett tábléák esetén sokkal kevesebb rekordolvasásra van szükség. A rendezéttség ugyanis azt jelenti, hogy a tábla valamely pozicióján állva, az előtte elhelyezkedő rekordok nem nagyobbak, az utána elhelyezkedő rekordok pedig nem lehetnek kisebbek, mint az aktuális pozición álló rekord. A sorted-merge algoritmus esetén előbb rendezik mindkét táblát a kapcsolódó mezők alapján. Ezután a merge módszerhez hasonlóan egy-egy pointer vezetnek be a két táblához, indulásként mindkettőt a megfelelő tábla elejére pozicionálva. Ezután megnézik, hogy a ponterek által kijelölt rekordok illeszkednek-e. Ha nem, akkor valamelyik kisebb értékű, mint a másik. A továbblépéshez a kisebb értékre mutató pointert mozgatják eggyel előre, miáltal az az előzőnél nagyobb vagy ismét vele egyenlő értékre fog mutatni. E két új elemre újból elvégezzük az illeszkedés vizsgálatot. Ha a két érték illeszkedi, akkor kiírjuk őket az eredmény táblába, majd továbblépünk. A továbblépésnél figyelni kell azonban arra, hogy egyetlen egy lehetséges párosítást sem vétsünk el. Ennek megoldására egy kis nested-loop algoritmust kell megvalósítani az azonos értékű rekordok mindennemű párosítására. Az algoritmus költségében a legnagyobb tételt a táblák rendezése jelenti. A rendezés optimális költsége, mint ismert az n*log(n) hat;konys'goszt'lyba esik. Mivel a rendezéás után az illeszkedés vizsgálatnál minden rekordot nagyjából egyszer érintjük, így a join költsége c * R1*log(R1) + R2*log(R2) + R1 + R2 alakú lesz. A valós költség ettől mindíg nagyobb, hiszen itt nem vettük figyelembe a tőbbszörös értékelőfordulás hatását az illeszkedé vizsgálatnál. A join módszer algoritmusa. rendez (T1) rendez (T2) p1 = eleje (T1) p2 = eleje (T2) while (p1 < vege(T1) and p2 < vege(T2)) do if illeszkedik(p1,p2) do pp = p2 while (p1 azonos értékű) for p2=pp to p2 azonos értékű do kiir(p1,p2) endfor p1++ endwhile else if ertek(p1) < ertek(p2) p1++ else p2++ endif endif endwhile A harmadik ismertett módszer a hash alapú hozzáféréseken alapszik. Tekintsük át röviden mit is jelent hash hozzáférési módszer. Az adatok keresésénél a legfontosabb szempont a hozzáférési idő csökkentése. Egy szekvenciális listában, ha semmilyen kiegészítő információ nem áll rendelkezésre, akkor a soros, szekveneciáli hozzáférés valósítható meg, melynél átlagosan az elemek felét érinteni kell, mire eljutunk a keresett elemhez. Ha a lista már rendezett, akkor vannak olyan kereső algoritmusok, mint például a bineáris keresés, melyek gyorsabban, az elemszám logaritmusával arányos idő alatt megtalálják a kívánt elemet. Sajnos a rendeszettség viszont igen sok problémát okoz a lista módosításánál, ott ahol dinamikus adatokat kell kezelni. Ezért továbra is igény van olyan tárolási módszerre, amely dinamikus adatok esetében is hatékonyan alkalmazható az elemek megkeresésére. A hash módszer egy ilyen tárolási alternatívát kínál. A hash lényege, hogy az elemeket nem egy nagy egységbe, egy nagy listába helyezi el, hanem több kisebb részlistába, amit bucket-nek is szokás nevezni. A listába bekerülő elemek a hash módszer mintegy szétválogatja a bucketek között, minden elem belekerül valamely bucketbe. A szétválogatás egy gyors algoritmussal történik, amely csak az elem értékére támaszkodik, s független a többi elem értékétől. Vagyis egy módszernél egy elem mindíg ugyanabba a bucketbe kerül, güggetlenül attól, hogy milyen más elemek vannak még benn a listában. Ez a tárolási mechanizmus igen hasonlít egy postai küldemény szétválogató rendszerhez, ahol az irányítószám alapján külön fiókokba szortírozzák a továbbítandó küldeményeket. A szétválogatáshoz felhasznált függvénytnevezik hash függvénynek. Egy hash függvényt akkor tekintük jónak, ha az elemeket egyenletesen és véletlenszerűen osztja szét a bucket-ek között. Numerikus kulcs értékek esetén igen gyakran alkalmazzák a modulo, az egész osztási maradék, operátorát a hash függvény alapjául. A hash join módszer alapelve az, hogy az illesztendő tábla elemeit elősször egy hash függvénnyel szétosztja különböző bucket-ekbe, majd ezután az egyes bucket-ekre külön-külön elvégzi az illeszkedés vizsgálatot. A módszer két elvi pilléren alapszik: egyrészt tudjuk, hogy az illeszkedésnél az azonos kulcsú rekordpárokat kell megkeresni, másrészt az is látható, hogy bármely hash függvény az azonos kulcsú rekordokat mindíg ugyanabba a bucket-be helyezi le. A rekordok szétosztásánál mindkét táblára ugyanazt a hash függvényt kell alkalmazni, hogy azonos legyen a szétválogatás mechanizmusa. Ezzel elérhető az, hogy a két tábla egyező kulccsal rendelkező rekordjai ugyanazon sorszámú bucket-be kerüljenek. A hash módszer előnye, hogy az illeszkedés vizsgálatnál csak azonos bucket-en belüli rekordpárokat kell vizsgélni, hiszen azonos kulcsértékű rekordok nem kerülhetnek különböző bucketbe. Mivel egy bucket rendszerint jóvval kevesebb rekordot tartalmaz, mint a teljes tábla, ezért jóval kevesebb idő alatt elvégezhetők az illeszkedés vizsgálatok, mint a teljes táblánál. A sok bucket ellenére a teljes illesztési idő is alacsonyabb értéken lesz, mint amit a teljes tábla igényelne. Nézzük meg ezt például a nested loop esetére vonatkoztatva. Tegyük fel, hogy mindkét tábla azonos méretű, a rekordok darabszáma legyen N. Ekkor a nested-loop algoritmus N2 költséggel dolgozik. Ha most felbontjuk a táblát M bucket-re, akkor a felbontás költsége 2*N míg egy bucket illesztési költsége (N/M)2 Így e teljes költség a hash join algoritmusnál 2*N + M*(N/M)2 lesz. Ha N=100, M=10 paraméterekkel kiszámoljuk a két költségértéket, akkor a nested-loop esetén 10000-at, s a hash join esetén csak 1200-at kapunk. Tehát egy nagyságrenddel sikerült csökkenteni a végrehajtási időt. A hash join algoritmus előnyét grafikusan is szemlélteti a következő ábra, melyben a téglalap x oldala az R2 táblának, míg az y oldala az R1 táblának felel meg. Az oldalak mentén húzódnak a tábla rekordjai. A nested-loop esetén mivel minden R1-beli rekord minden R2-beli rekorddal ileszkedési ellenőrzésre kerül, minden rekordpárost érinteni kell. Grafikusan ez azt jelenti, hogy a téglalap minden pontját meg kell vizshálni, vagyis a vizsgált rekordpárok darabszáma a teljes négyzet területével arányos. A hash join algoritmus esetén viszont a rekordok bucket-ekbe kerünek, s csak az azonos bucket-be került rekordpárokat kell vizsgálni illeszkedés céljából. Így ebben az esetben csak azon pontokkerülenk vizsgálatra, melyek azonos bucketben vannak mindkét oldal mentén. Grafikusan szemléltetve csak az ábrán x-szel jelölt területeken lehelyezkedő potokat kell vizsgálni. A hash join költsége ezen területek összegével arányos. Az ábrán megfigyelhető, hogy a teljes téglalap területe mennyivel nagyobb, mint az x-szel jelölt területek összege. E két terület viszonya egyben a két algoritmus költség viszonyát is tükrözi. A hash join algoritmus költségére azért nehéz pontos értéket adni, mivel az az egeys bucket-ek foglaltságától függ. Így az alábbi képletben az egyes bucket- ekben tárolt rekord darabszámokra a B szimbólummal hivatkozunk. c * R1 + R2 + * B1i*B2i A hash join algoritmusnak, mint minden hash algoritmusnak a legnagyobb nehézsége az túlcsordulások kezelése. A tulcsordulás akkor lép fel, ha egy bucket-be több rekord kerül, mint amennyi a bucket kapacitása. Sajnos a buckete-eket igen körülményes menetközben dinamikusan változtatni, ezért a legkülönbözőbb trükkökkel próbálkoznak a tulcsordulás következményeinek kivédésére. A hash join megvalósításának több különböző tipusa is elterjedt, ahol az egyes változatok elsősorban a tulcsordulás kezelésének mechanizmusában különböznek egymástól. Ami viszont általánosságban jellemez minden hash join algoritmust, az az, hogy a végrehajtás két fázisban történik: - szétosztási fázis: az egyik tábla rekordjait szétosztják a hash táblában a bucket-ek között - illesztési fázis: a másik tábla rekordjait sorban egymásután beolvassák. Minden rekordot a beolvasás után rögtön leképzik valamely bucket-re a hash függvény segítségével, s elvégzik az illesztés ellenőrzést. A felvázolt algoritmusok mind egy-egy join végrehajtási változatot reprezentálnak. Mindhárom változat reális alternatívát jelent, hiszen - kis táblák esetén jó lehet a nested-loop algoritmus; - indexelt táblák esetén (tehát már rendezve van), jó a sorted merge; - nagy táblák esetén pedig a hash join tűnik előnyösnek. E fejezet befejezéseként vegyük néhány példát arról, hogy mit is érezhetünk az optimalizásál mechanizmusából az Oracle RDBMS esetén. Tanulságos lehet, ha áttekintjük, hogy az Oracle rendszerben egy adott kifejezés kiértékelése milyen sorrendben megy is végbe. Az Oracle leírások alapján a beérkezett parancsot az alábbi lépéseken keresztül vezetik le olyan alakra,melyből már könnyebb a QGM leírás elkészítése. A lépésekből látható, hogy hogyan alakítják át az összetettebb kifejezéseket elemi kifejezésekké, melyek már közvetlenebb kapcsolatban vannak az elemi relációs algebrai műveletekkel. Az elemzés a következő lépéseket tartalmazza: - konstans kifejezések kiértékelése - IN, BETWEEN helyettesítése - tranzítivitási szabályok alapján átrendezés - OR feltételek felbontása - VIEW-k behelyettesítése - alszelekciók átírása join-ra Az elkészült QGM-re vonatkozólag viszonylag kevesebb információt kaphatunk a kézikönyvekben, ezzel szemben a QEP vonatkozásában már bővebb információ források állnak rendelkezésre, melyekből itt most két lehetőséget említünk meg. Az SQL utasítások között található olyan, mellyel be tudjuk állítani, hogy az RDBMS a QEP optimalizálásánál mely módszert válassza, a költség függvény alapút, vagy a szabály alapút. A szabály alapú módszernél általános elvek alapján dönt,míg a költség alapúnál kiszámolja a változatok becsült költségét az adattáblák paraméterei alapján. Az optimalizálási mód beállításának parancsa: ALTER SESSION SET OPTIMIZER_GOAL=mód; ahola mód lehet - RULE: szabály alapú optimazlizálás - ALL_ROWS: költség alapú, melyben a teljes eredmény előállításának az idejére optimalizálunk - FIRST_ROWS: költség alapú, melyben az első eredményrekord megjelenésének idejére optiamlizálnuk. A másik érdekes utasítás az EXPLAIN PLAN, mellyel lekérdezhető a generált QEP szerkezet. A QEP leírását egy normál táblázatba írja ki az utasítás, s a feltöltött táblát ezután a normál SELECT segítségével lehet lekérdezni. Az QEP kiíratásának utasítása EXPLAIN PLAN FOR SQL-utasítás; A leírás egy PLAN_TABLE elnevezésű táblázatba fog kikerülni. Mivel a parancs nem törli a PLAN_TABLE táblát, hanem hozzáfűzi az új leírást, ezért célszerű a EXPLAIN PLAN kiadása előtt törölni a PLAN_TABLE táblát. Az utasítás kiadásakor a PLAN_TABLE táblának már léteznie kell, különben hibajelzést ad a rendszer. Maga a PLAN_TABLE tábla szerkezete előírt, rögzített, s mintegy 15 mezőt tartalmaz. A mezők között az alábbiakat lehetne kiemelni, mint fontosabb mezők: - ID: művelet azonosító száma - PARENT_ID: a szülő művelet ID-je. Egy művelet szülő művelete az a művelet, amely fel fogja használni az előállított eredményt. - OPERATION: a művelet megnevezése - OPTION: a művelet egyedi paramétere - OBJECT_NAME: az érintett objektum azonosítója. A tábla létrehozására az Oracle rendszer tartalmaz egy UTLXPLAN.SQL gyári parancsállományt. Példaként vegyük az kék színű autók és tulajdonosainak kiíratását, ahol feltesszük, hogy létezik egy auto és egy ember tábla. A QEP lekérdezésének parancsa: EXPLAIN PLAN FOR SELECT nev, rsz, tip FROM auto, ember WHERE auto.tul=ember.id AND auto.szin='KEK'; A feltöltött PLAIN_TABLE lekérdezése: SELECT id, parent_id, operation, options,object_name FROM PLAN_TABLE; Az eredményül kapott lista: ID PARENTID OPERATION OPTIONS OBJECT ----------------------------------------------------------------------- 0 SELECT ... ----------------------------------------------------------------------- 1 0 NESTED LOOP ----------------------------------------------------------------------- 2 1 TABLE ACCESS FULL AUTO ----------------------------------------------------------------------- 3 1 TABLE ACCESS BY ROWID EMBER ----------------------------------------------------------------------- 4 3 INDEX UNIQ. SCAN SYS_CO.. ----------------------------------------------------------------------- A kapott QEP szemléltetésére rajzoljuk meg a hierarchiát is. A kapott listából kiderül, hogy a RDBMS az ember táblában egy index segítségével kereste végig a rekodokat. Ehhez előbb az indextáblát olvassa, majd a kapott pointer (ROWID) alapján ráugrik a megfelelő lapra és beolvassa az adattábla rekordot is. Az auto táblát szekvenciálisan olvassa végig a rendszer. A két tábla összefűzésére egy nested loop algoritmus került kiválasztásra. Az EXPLAIN PLAN utasítás révén szemléltetni tudjuk a belső végrehajtyás logikáját, s emberközelibbé lesznek az RDBMS-ben zajló belső folyamatok is.