Lekérdezés optimalizálás

Országok listájaHungaryBudapesti Műszaki és Gazdaságtudományi EgyetemVillamosmérnöki és Informatikai KarMérnök informatikusAdatbázisokJegyzetekLekérdezés optimalizálás

Lekérdezés-feldolgozás és optimalizálás
Segédanyag az Adatbázisok c. tárgyhoz
Gajdos S. 2007.
Az anyag a ,,relációs lekérdezések feldolgozása és optimalizálása" gazdag témakörének csak egy viszonylag kis, de alapvet részét fedi le. Nem foglalkozunk a lekérdezés fordításával és szintaktikai ellen rzésével, a dinamikus programozás alkalmazásával, adaptív technikákkal, és még számos más kapcsolódó problémával sem. Az anyag csupán egy bevezetést kínál a témakörbe kifejezetten a BSc 3. MI Adatbázisok kurzus hallgatói számára.

Tartalom
1. 2. ÁTTEKINTÉS..................................................................................................................................................... 2 KATALÓGUS KÖLTSÉGBECSLÉS............................................................................................................... 4 2.1. 2.2. 2.3. 3.
KATALÓGUSBAN TÁROLT EGYES RELÁCIÓKRA VONATKOZÓ INFORMÁCIÓK:............................................... 4 KATALÓGUS INFORMÁCIÓK AZ INDEXEKR L .............................................................................................. 4 A LEKÉRDEZÉS KÖLTSÉGE .......................................................................................................................... 5

M VELETEK KÖLTSÉGE ............................................................................................................................. 5 3.1. SZELEKCIÓ.................................................................................................................................................. 6 3.1.1. Alap szelekciós algoritmusok................................................................................................................ 6 3.1.2. Indexelt szelekciós algoritmusok .......................................................................................................... 6 3.1.3. Összehasonlítás alapú szelekció............................................................................................................ 7 3.2. JOIN OPERÁCIÓ ........................................................................................................................................... 7 3.2.1. Az illesztés fontosabb típusai:............................................................................................................... 7 3.2.2. Nested-loop join (egymásba ágyazott ciklikus illesztés)....................................................................... 8 3.2.3. Block nested-loop join (blokkalapú egymásba ágyazott ciklikus illesztés) .......................................... 8 3.2.4. Indexed nested-loop join (Indexalapú egymásba ágyazott ciklikus illesztés) ....................................... 9 3.2.5. Merge join (Összefésülés alapú illesztés) ............................................................................................. 9 3.3. EGYÉB M VELETEK .................................................................................................................................... 9

4.

KIFEJEZÉS KIÉRTÉKELÉS......................................................................................................................... 10 4.1. MATERIALIZÁCIÓ (MEGTESTESÍTÉS, LÉTREHOZÁS)................................................................................... 10 4.2. PIPELINING ............................................................................................................................................... 10 4.2.1. Pipeline kiértékelési algoritmus .......................................................................................................... 11

5.

RELÁCIÓS KIFEJEZÉSEK TRANSZFORMÁCIÓI .................................................................................. 11 5.1. 5.2. EKVIVALENS KIFEJEZÉSEK ........................................................................................................................ 11 EKVIVALENCIA SZABÁLYOK ..................................................................................................................... 12 KÖLTSÉGALAPÚ OPTIMALIZÁLÁS ............................................................................................................. 13 HEURISZTIKUS OPTIMALIZÁLÁS ................................................................................................................ 14

6.

A KIÉRTÉKELÉSI TERV KIVÁLASZTÁSA .............................................................................................. 13 6.1. 6.2.

7.

IRODALOMJEGYZÉK................................................................................................................................... 15

Lekérdezés-feldolgozás és optimalizálás

2

1. Áttekintés
A lekérdezés feldolgozás els dleges célja az adatok adatbázisból való kinyerése. Az egyértelm en megfogalmazott célhoz a megoldás megtalálása azonban korántsem egyszer . Számos igen bonyolult részfeladatot kell az adatbáziskezel -rendszernek megoldania, amíg eljut a kívánt végeredményhez. Ezek a következ k: 1. Elemzés (szintaktikus), fordítás 2. Költség optimalizálás 3. Kiértékelés Az els lépés az elemzés (szintaktikus) és a fordítás. Egy magas szint nyelven (tipikusan az SQL valamilyen dialektusában) megfogalmazott kérést a számítógép számára használhatóbb formába kell hozni. Az SQL-t, mint kommunikációs interfészt az emberi igényekhez tervezték, minden SQL mondat megfeleltethet egy természetes nyelv (speciálisan az angol) egy mondatának. Sajnálatos módon azonban a számítógép ezt az idegen nyelvet csak tolmács segítségével beszéli. A legtöbb adatbáziskezel -rendszer anyanyelve a relációs algebra kiterjesztett változatára épül.

Ábra 1.1 A lekérdezés feldolgozás tipikus lépései

Persze a fordítás csak akkor valósulhat meg, ha az SQL nyelvet a felhasználó helyesen beszéli, ezért a fordítást minden esetben megel zi egy szintaktikai elemzés. Az elemzésnél megvizsgáljuk a lekérdezés szintaktikáját: pl. meggy z dünk arról, hogy a lekérdezésben szerepl relációnevek ténylegesen el fordulnak-e az adatbázisban, stb. A lekérdezés elemeit ez után le kell fordítani és valamilyen bels ­ általában reláció algebra alapú ­ reprezentációba átalakítani. Miután sikerült egy matematikailag helyes kifejezést konstruálnunk az SQL mondatból, érdemes pár dolgot végiggondolni. Vajon egyértelm -e egy lekérdezés, ill. a hozzárendelt bels reprezentáció a kiértékelés sorrendjét tekintve? Lehetséges-e formális módszerekkel a lekérdezésünkkel ekvivalens másik lekérdezés(eke)t konstruálnunk? Mert ha lehetséges, akkor nyilvánvalóan több végrehajtási út létezik, amelyek sebességben, végrehajtási id ben, lemezhasználatban stb.-ben esetleg eltérnek egymástól. Ebben az esetben érdemes lenne

Lekérdezés-feldolgozás és optimalizálás

3

Ezzel szemben a relációs algebrai modellekben az optimalizáció megvalósítható (jelent s részben a deklaratív szemlélet miatt) a programozó közbeavatkozása nélkül is. Mivel a dominánsan deklaratív szemlélet mondatok els sorban nem azt mondják meg, hogy hogyan hajtsunk végre valamit, hanem leginkább azt, hogy mit szeretnének eredményül kapni, ezért a bels megvalósítás rejtve maradhat. A deklaratív elvek realizálása algebrai eszközökkel megoldható. Köszönhet en a formális matematikai módszereknek viszonylag könny lesz egyazon kérdéshez több, eredményét tekintve ekvivalens alakot találni, és kiválasztani közülük a legkevésbé költségeset. A továbbiakban megnézzük, hogy az algebrai formák hogyan támogatják a lekérdezések optimalizálását. Formális lépéseken keresztül megkeressük egy adott SQL mondat több különböz ekvivalens alakját. Az eltér alakok eltér kiértékelési sorrendet jelenthetnek. Megpróbáljuk megbecsülni, melyik végrehajtása mekkora terhelést jelentene a rendszer számára. Egy egyszer példával illusztrálva a lépéseket nézzük az alábbi SQL mondatot: select balance from account where balance < 2500 Egy bank nyilvántartásából szeretnénk megtudni, milyen 2500 egységnél kisebb érték egyenlegek léteznek. A lekérdezés átalakíthatjuk például a következ két relációalgebrai alakba:

A hálós és a hierarchikus modellben a lekérdezés optimalizálás legtöbbször a programozó feladata. Ennek oka, hogy az adatmanipulációs nyelven megfogalmazott kifejezések általában a programokba beágyazva szerepelnek és ezeknek optimális hálós illetve hierarchikus lekérdezéssé transzformálása az egész program ismerete nélkül általában nem megoldható. Az optimalizációhoz tehát rendkívül bonyolult algoritmus futtatására lenne szükség, amely túl nagy terhelést jelentene a rendszer számára ­ különösen az akkori rendszerek számára.

különböz végrehajtási terveket is kidolgoznunk. Ha már kidolgoztunk több tervet, akkor ezeket valamilyen szempont szerint össze kellene hasonlítani. Nyilvánvalóan az optimális megoldást keressük a problémára, de mi az a paraméter, amely alapján az optimalitást értelmezzük? Esetleg nem egy, hanem több paramétert is számításba kell venni? Mivel bizonyosan lesznek eleminek tekintett m veleteink, vajon milyen algoritmusok léteznek a végrehajtásukra, és melyiket válasszuk? Összefoglalva: optimalizációs stratégiák alapján végrehajtási terveket kell készíteni és kiértékelni, majd ezekb l a legjobbat kiválasztani és végrehajtani.

balance ( balance<2500 (account ))
balance<2500 ( balance (account ))
Láthatóan a két alak két különböz végrehajtási sorrendet kínál. Az els esetben az account relációból kiválasztjuk azokat az elemeket, amelyben az egyenleg értéke kisebb 2500-nál, majd ezután végrehajtunk egy projekciót az így kapott relációra. A második forma pont a fordított sorrendet írja le, el ször egy projekció, majd egy szelekció m veletet kell elvégezni. Ezután el kell döntenünk, melyik végrehajtási sorrendet kövessük. Az optimum mértéke lehet a lekérdezés teljes (fiktív) "költsége", amelynek a kiszámításához szükséges az egyes eleminek tekintett m veletek költségeinek ismerete. Sajnos a helyzet feloldása nem ennyire egyszer , mert egy elemi m velet költsége más és más eltér környezetekben. Tekintsük például a szelekció m veletet, amelynek végrehajtási ideje, ha lineáris keresést alkalmazunk arányos a reláció összes elemének számával, azonban ha valamilyen indexet állítottunk a szelekció feltételére a költséget nagyságrenddel csökkenthetjük. Érezhet en nem mindegy, hogy milyen algoritmusokat tudunk alkalmazni az elemi operációk vagy kiértékelési primitívek végrehajtásánál. A primitívek összefoghatóak egy nagyobb munkafolyamati egységbe, egy pipeline-ba. A cs vezetékben lév egyik operáció bemenetét az el tte álló primitív kimenete szolgáltatja. A primitív feldolgozza a bemenetét, majd a kimenetét

Lekérdezés-feldolgozás és optimalizálás

4

átadja a sorban utána álló m veletnek. A primitív m veletek szekvenciája a lekérdezési terv. Az 1.2-es ábra a példánkra mutat be egy lehetséges tervet.

balance

balance < 2500
account
1.2. ábra

A különböz tervek megalkotása még önmagában nem elegend , hiszen meg kell mondani, hogy az egyes elemi m veletek végrehajtásához pontosan milyen algoritmusokat alkalmazunk. A lehetséges tervek közül az optimális megtalálása nem egyszer feladat.

2. Katalógus költségbecslés
A lekérdezés feldolgozáshoz a megfelel végrehajtási stratégia kiválasztása valamilyen költségmérték becsült hozzárendelése alapján végezhet . A becslés tényét nem lehet eléggé hangsúlyozni, nem szabad és nem is érdemes egzakt számokat várni a költségbecslés eredményét l. Az adatbázis-kezel rendszernek a relációkról különböz statisztikákat, mér számokat kell karbantartania, amelyek alapján elvégezhet ek a költségbecslések. A statisztikákat az adatbázis-kezel k egyéb más rendszerleíró paraméterek mellett egy ú.n. katalógusban tárolják.
2.1. katalógusban tárolt egyes relációkra vonatkozó információk:

nr : az r relációban lev rekordok (elemek) száma (number) br : az r relációban lev rekordokat tartalmazó blokkok (blocks) száma sr : egy rekord nagysága (size) byte-okban fr : mennyi rekord fér egy blokkba (blocking factor) V (A, r): hány különböz értéke (Values) fordul el az A attribútumnak az r relációban: V (A, r) = |A (r)| ; speciálisan ha az A kulcs, akkor V (A, r) = nr . SC(A, r) : azon rekordok átlagos száma, amelyek kielégítenek egy egyenl ségi feltételt az A attribútumra (Selection Cardinality); feltéve, hogy legalább egy rekord kielégíti ezt az egyenl ségi feltételt. Például, ha az A egyediséget biztosít, akkor SC(A,r) = 1. Ha az A nem biztosít egyediséget, és feltesszük, hogy a V (A, r) különböz érték egyenletesen oszlik el a rekordok között, akkor SC(A,r) = nr/V(A,r). Az utóbbi két mennyiség definiálható tetsz leges A attribútumhalmazra is: V (A, r) illetve SC(A, r). n Megfigyelés: Ha a relációk rekordjai fizikailag együtt vannak tárolva, akkor: br = r fr
2.2. Katalógus információk az indexekr l

Lekérdezés-feldolgozás és optimalizálás

5

Az indexek ­ leggyakrabban B* fák ­ olyan segédstruktúrák, amelyek gyorsíthatják a relációkban adott attribútum vagy attribútumok szerinti keresést. Indexek létrehozása a rendszer számára nagyobb adminisztrációs költséggel jár, ami a használatuk során térülhet meg. Az egységes tárgyalás érdekében itt a hash-táblákat is speciális ,,indexnek" tekinthetjük. Az indexeket az alábbi paraméterekkel fogjuk jellemezni: fi: az átlagos pointer-szám a fa struktúrájú indexek csomópontjaiban, mint pl. a B* fáknál, azaz a csomópontokból induló ágak átlagos száma HTi: az i index szintjeinek a száma, azaz az index magassága B* fáknál (Height of Tree) HTi = log f i V ( A, r ) , ill. hash-indexnél HTi = 1. LBi: az i index legalsó szint blokkjainak a száma, azaz a levélszint indexblokkok száma (Lowest level index Block) A statisztikákat elvileg minden adatbázis módosító m velet után módosítani kellene, de ez óriási terhelést jelente a rendszer számára. A valós alkalmazásokban a statisztika felülírása ezért csak akkor történik meg, amikor a rendszernek ,,van rá ideje". Ebb l következ en a statisztika nem mindig konzisztens a rendszer állapotával, de elég jól leírja a rendszerben zajló folyamatokat. Tehát egy régebbi statisztika alapján nem is végezhetünk pontos költségszámítást, de egy elfogadható becslésnek jó kiindulási alapja lehet.
2.3. A lekérdezés költsége

A bevezet b l kiderül, hogy különböz kiértékelési tervek végrehajtási költsége más és más. Definiáljuk most pontosabban, hogy költség és optimalitás alatt mit kell érteni. A lekérdezés kiértékelés költségének meghatározása történhet az igényelt és a felhasznált er források alapján, ez lehet például a felhasznált processzorid , a háttértárhoz fordulás ideje vagy elosztott rendszerekben a kommunikációra fordított id stb. Egy másik kézenfekv lehet ség a válaszid alapján történ költség-becslés. Azonban, ha jobban végiggondoljuk ez nem is olyan jó alternatíva, hiszen a válaszid er sen függ a környezet állapotától is (egy túlterhelt rendszer valószín leg lassabban generálja le a végeredményt, mint egy kevésbé leterhelt). A válaszid érezhet en nem biztosít elemi költség-meghatározási szempontot. A nagy adatbáziskezel kben a költség becslésére a háttértár blokkm veletek számát használják, mivel ez lényegében független a rendszer terhelését l és mert ennek id igénye nagyságrenddel nagyobb, mint a processzor- és memóriam veletek id igénye. A használható költségmérték megalkotásához azonban szükséges a probléma megfelel szint egyszer sítése. Nem szabad különbséget tennünk az egyes blokkok elérési ideje között, azaz alapfeltételezés, hogy a diszken elhelyezked minden blokkhoz azonos id alatt férünk hozzá. Nem vesszük figyelembe a lemez forgási irányát, a fej mozgását; ezeket nem tudjuk megbecsülni, és nem tudunk különbséget tenni az egyes írások és olvasások között sem. Ez alapján legyen a költség a diszk blokkok olvasásának és írásának a száma azzal a további megszorítással, hogy az írásba csak a köztes blokkírások számát számítjuk bele, hiszen a végeredmény kiírása mindenképpen szükséges.
Jelölés: Ealg = az algoritmus becsült költsége (estimate) .

3. M veletek költsége

Lekérdezés-feldolgozás és optimalizálás

6

A relációs adatbázis-kezel k világában szükséges a relációkon végezhet alapm veletek definiálása, ezek lesznek azok az elemi épít kövek, amelyek segítségével minden más lekérdezés megszerkeszthet . Jelen anyagban csak az alapesetekkel foglalkozunk.
3.1. Szelekció

A lekérdezés feldolgozásban egy reláció végigolvasása a legalacsonyabb szint m velet. Egy adott érték megtalálását az adott szelekciós feltételek figyelembevétele mellett valamilyen keresési algoritmus alapján kell elvégezni. A relációk egyszer esetben egyetlen állományban tárolódnak, ezért a keresési m veletet csupán egy fájlra korlátozódik. 3.1.1. Alap szelekciós algoritmusok

A szelekció m velet megvalósítását lehet vé tev két alapalgoritmus a következ : A1: Lineáris keresés (,,full table scan"): Minden rekordot beolvasunk, és megvizsgáljuk, hogy kielégíti-e a szelekció feltételét. EA1 = br A2: Bináris keresés. Bináris keresést csak akkor tudunk végrehajtani, ha a blokkok folyamatosan helyezkednek el a diszken, a fájl az A attribútum szerint rendezett és a szelekció feltétele az egyenl ség az A attribútumon. Összesen SC(A, r) darab ilyen SC ( A, r ) -1 rekordunk van, ezért az algoritmus költsége: E A 2 = log 2 br + fr (Az els ilyen blokk megtalálása a relációban lév rekordokat tartalmazó blokkok logaritmusával arányos, az összeg második része a szelekció feltételét kielégít összes rekord tárolásához szükséges maximális blokkméret. A ­1 azért szükséges, mert az els és a második tagja az összegnek már tartalmazza az els megfelel blokk olvasásának költségét.) Ha az A attribútum egyediséget biztosító attribútum, akkor a keresés költsége: log br
3.1.2. Indexelt szelekciós algoritmusok

A szakirodalom megkülönbözteti az els dleges és másodlagos indexeket. Az els dleges index a rekordok olyan sorrendben való olvasását teszi lehet vé, amely megfelel a rekordok fizikai tárolási sorrendjének. Minden egyéb indexet másodlagos indexnek tekintünk. A legfontosabb indexelt szelekciós algoritmusok ezek alapján a következ k:
A3: Els dleges index használatával, egyenl ségi feltételt a kulcson vizsgálunk. Az algoritmus költsége EA3 = HTi + 1, az index szintek plusz az adatblokk olvasása. A4: Els dleges index használatával egyenl ségi feltétel nem a kulcson. SC ( A, r ) E A 4 = HTi + Az egyenl ségi feltételt SC(A,r) rekord elégíti ki, amelyhez fr SC(A,r)/fr blokkm velet szükséges. A5: Másodlagos index használatával. EA5 = HTi + SC(A, r) (a második tag mutatja, hogy mennyi különböz blokkon lehetnek). Ha az A egyediséget biztosít, akkor EA5 = HTi + 1.

Lekérdezés-feldolgozás és optimalizálás

7

3.1.3.

Összehasonlítás alapú szelekció

Tekintsük a Av(r) alakú lekérdezéseket. Ha v értékét nem ismerjük, azt mondhatjuk, hogy átlagosan nr/2 rekord elégíti ki a feltételt. Ha ismerjük a v értékét, és egyenletes eloszlást feltételezünk az A attribútum maximális (max(A,r)) és minimális értéke között (min(A,r)), akkor: v - min( A, r ) nátlagos = nr ( ) rekord elégíti ki átlagban a feltételt. rekord elégíti ki átlagban a feltételélt. max( A, r ) - min( A, r ) A6: Els dleges index használatával. EA6=HTi+br/2 (átlagosan a keresési feltételt a rekordok fele kielégíti). Ha a v-t ismerjük, és c jelöli azon rekordok számát, ahol c Av, akkor: E A6 = HTi + fr LB n A7: Másodlagos index használatával. E A7 = HTi + i + r A második tag jó becslés, ha 2 2 a levélszint indexblokkok legalább fele kielégíti a feltételt. Az utolsó tagra azért van szükség, mert ha a rekordok legalább fele kielégíti a feltételt, akkor ezeket a másodlagos index jellegéb l következ en csak egyesével, azaz egy blokkm velet költséggel tudjuk elérni. A másodlagos indexek használatával kapcsolatban meglep következtetésre juthatunk. Az összehasonlítás alapú lekérdezéseknél szerencsétlen esetben kifizet d bb egy egyszer lineáris keresést alkalmazni, mert az kevesebb blokkm veletet igényel.
3.2. Join operáció

A join (illesztés vagy összekapcsolás) m velet általános értelemben két reláció Descartes szorzatának adott feltétel (predikátum) szerinti szelekciója (Theta-join): R1 R2 = ( R1 × R2 ) A továbbiakban bemutatjuk a legfontosabb join típusokat, megbecsüljük, hogy két reláció illesztéséhez várhatóan mekkora tárterület szükséges, majd áttekintjük a join megvalósítását lehet vé tev algoritmusokat. 3.2.1. Az illesztés fontosabb típusai:

· Természetes összekapcsolás (Natural join) Két tábla között a megegyez nev attribútumok létesítenek kapcsolatot. Általában, tekintsük az A és B attribútumhalmazok feletti R1(A) és R2(B) sémákat, ahol X = A B nem üres. Az R1 és R2 feletti T1 és T2 táblák természetes összekapcsolása egy R(A U B) feletti T tábla, amelyet a következ képp definiálunk: T = A U B(R1.X=R2.X(T1 x T2) ) Vagyis, a két tábla Descartes-szorzatából kiválasztjuk azokat a sorokat, amelyek az R1.X és R2.X attribútumokon megegyeznek, majd a projekcióval a duplán szerepl Xbeli attribútumokat csak egy példányban tartjuk meg (az A U B halmazelméleti unió, vagyis benne az X elemei csak egyszeresen szerepelnek). · Küls összekapcsolás (Outer join)

Lekérdezés-feldolgozás és optimalizálás

8

A természetes összekapcsolás veszélye, hogy általában a kapcsolt táblák nem minden sora szerepel az eredménytáblában. Ha egy sor nem párosítható a másik tábla egyetlen sorával sem, akkor lógó sornak nevezzük. A küls összekapcsolás (outer join) garantálja az összekapcsolt két tábla egyikénél vagy mindkett nél valamennyi rekord meg rzését. Egy elterjedt implementáció jelölési konvenciója (+) alapján megkülönböztetjük:
·

· ·

Bal oldali küls összekapcsolás: T1 (+)* T2. Azt jelenti, hogy az eredménytáblában T1 azon sorai is szerepelnek, amelyek T2 egyetlen sorával sem párosíthatók. Ezen sorokban a T2-beli attribútumok értéke NULL. Jobb oldali küls összekapcsolás: T1 *(+) T2. Hasonlóan a T2 táblára. Teljes küls összekapcsolás: T1 (+)*(+) T2. Itt mindkét tábla nem párosított rekordjai meg rz dnek.

· Theta-összekapcsolás (theta-join) Általános illesztés. A táblák Descartes-szorzatából tetsz leges feltétel szerint választunk ki sorokat: T = feltétel (T1 x T2) )

3.2.2.

Nested-loop join (egymásba ágyazott ciklikus illesztés)

Az egymásba ágyazott ciklikus illesztés egy általános algoritmus két reláció (r és s) theta-join m veletének implementálására. Az algoritmus logikája könnyen végigkövethet a megadott pszeudokód alapján. FOR minden tr r rekordra DO BEGIN FOR minden ts s rekordra DO BEGIN teszteljük (tr, ts ) párt, hogy kielégíti-e a -join feltételt END IF igen, THEN adjuk a tr.ts rekordot az eredményhez

END (ahol a . m velet a konkatenációt jelöli) Láthatóan ez egy elég költséges eljárás, mert minden egyes tr,ts párt külön megvizsgál. A legrosszabb esetben nr*bs+br blokkm veletre van szükségünk a teljes algoritmus lefuttatására (az r reláció végigolvasása br blokkm velet, egy r-beli rekordhoz az összes s-beli blokk végignézése bs blokkm velet). Ha a két reláció befér a memóriába, akkor br+bs blokkm veletre van szükség a beolvasáshoz. Ha a memória csupán az egyik reláció tárolását teszi lehet vé, akkor is br+bs lesz a költség. Legyen az algoritmus szerinti s reláció az, amely elfér a memóriában, olvassuk be s-et (bs költség), így minden r-beli rekordhoz az összehasonlítást gyorsan, azaz költség nélkül megtehetjük, ehhez járul még az r-beli rekordok beolvasási költsége. 3.2.3. Block nested-loop join (blokkalapú egymásba ágyazott ciklikus illesztés)

Lekérdezés-feldolgozás és optimalizálás

9

A blokkalapú egymásba ágyazott ciklikus illesztés algoritmus okosabb, mint az els algoritmusunk, mert kihasználja a tárolás fizikai sajátosságait. A gyorsítást azáltal éri el, hogy blokkalapú rekord-összehasonlítást végez. A bels két ciklus összehasonlítja a két reláció egyegy beolvasott blokkjának minden rekordját, a küls kett pedig végigmegy a két reláció összes blokkján. FOR minden br r blokkra DO BEGIN FOR minden bs s blokkra DO BEGIN FOR minden tr br rekordra DO BEGIN FOR minden ts bs rekordra DO BEGIN END teszteljük le a (tr,ts) párt

END Az algoritmus ,,worst-case" költsége br * bs + br, kedvez bb esetben (az els algoritmusnál bemutatott gondolatmenet alapján) br + bs. 3.2.4. Indexed nested-loop join (Indexalapú egymásba ágyazott ciklikus illesztés)

END

END

Az indexelt egymásba ágyazott ciklikus illesztés algoritmus kihasználja, hogy az egyik relációhoz van indexünk. Ha az els esetben bemutatott algoritmus bels ciklusába az indexelt relációt tesszük, akkor nem szükséges minden egyes s-beli rekordot végigvizsgálnunk, hogy megfelel-e a feltételnek, hiszen a keresés index alapján kisebb költséggel is elvégezhet . Az eljárás költsége br + nr *c, ahol c a szelekció költsége s-en, amely nyilván a konkrét indexstruktúra függvénye. 3.2.5. Merge join (Összefésülés alapú illesztés)

Az illesztés úgy is elvégezhet , ha mindkét relációt el ször rendezzük az illesztési feltételnek megfelel attribútum értékeinek megfelel en. Ez után már elég csak egyszer-egyszer végigolvasni mindkét relációt, hiszen az illeszked elemek a rendezés következtében egymás után kerültek. Az ilyen módon végzett illesztés költsége br+bs+a rendezések költsége. Ha a relációk igen nagyok, és hatékonyan tudunk rendezni, akkor gyakran a legkisebb költségre vezet.
Megjegyzés: A join megvalósítására számos egyéb algoritmus is létezik. . 3.3. Egyéb m veletek

A két legfontosabb m velet, a select és a join bemutatása után pár mondatban kitérünk egyéb gyakran használt m veletekre is.
·

Ismétl dés kisz rése: (Ha ugyanabból a rekordból több példány van, akkor csak egy maradjon) El ször rendezést hajtunk végre. Az azonos rekordok közvetlenül egymás után fognak megjelenni, ekkor már könnyen törölhet k. Költség: a rendezés költsége.

Lekérdezés-feldolgozás és optimalizálás

10

·

· · ·

Projekció: Minden rekordra végrehajtjuk, aztán kiküszöböljük a másodpéldányokat a fenti módszerrel. Ha a rekordok eleve rendezettek, akkor a költség br, általános esetben br+ a rendezés költsége. Unió: El ször mindkét relációt rendezzük, majd összefésülésnél kisz rjük a duplikációkat. Metszet: Mindkét relációt rendezzük, az összefésülésnél csak a közös rekordokat vesszük figyelembe. Különbség: Mindkét relációt rendezzük, összefésülésnél csak azok a rekordok maradnak, amelyek csak az els relációban szerepelnek.

4. Kifejezés kiértékelés
Áttekintettük az elemi m veletek néhány algoritmikus megvalósítását. Nem foglalkoztunk azonban még az összetett, több elemi m veletb l álló kifejezések kiértékelésének módjával. A legkézenfekv bb stratégia, hogy az összetett kifejezésnek egyszerre egy m veletét értékeljük ki valamilyen rögzített sorrend szerint (materializáció). Ezzel azonban van egy nagy probléma, minden m velet végrehajtása után a keletkezett eredményt a kés bbi felhasználás miatt a háttértárra kell kiírni, ezért a módszer rengeteg blokkm veletet igényel. Egy másik kiértékelési alternatíva: egy ,,cs vezetékben" egyszerre több elemi m velet szimultán kiértékelése folyik, egy m velet eredményét ­ a háttértár bevonása nélkül ­ azonnal megkapja a sorban következ m velet operandusként (pipelining).
4.1. Materializáció (megtestesítés, létrehozás)

A customer _ name ( balance< 2500 (account )

customer ) kifejezést a m veletek mentén a 4.1 ábra

szerinti m veleti fába transzformálhatjuk. A fa leveleiben vannak a relációink, a bels csomópontokban pedig a m veletek. A fa alapján a materializációs stratégia lépései könnyen nyomon követhet ek. Az els lépésként hajtsunk végre egy olyan m veletet, amelyekhez az operandusaink rendelkezésre állnak. Ez a példánkban csak a szelekciós m veletre teljesül. Az így kapott ideiglenes relációt ezután illesszük a customer relációval, majd hajtsuk végre a projekciót.

customer_name

balance < 2500 customer
account
4.1 ábra

A stratégia minden relációt kiszámít a fában, közben létrejönnek közbüls relációink is. A materializáció költsége tehát a végrehajtott operációk költségének összege, plusz a közbüls relációk tárolásának a költsége.
4.2. Pipelining

Lekérdezés-feldolgozás és optimalizálás

11

A kiértékelés hatékonysága növelhet , ha redukáljuk az ideiglenesen tárolásra kerül rekordok számát. Ha megszervezünk egy olyan munkafolyamatot, amelyben a részegységek az el ttük álló elemt l kapott részeredményekb l a sorban következ számára állítanak el részeredményeket, akkor kiküszöbölhetjük az ideiglenes tárolás szükségességét. A fenti példán illusztrálva a lépéseket, mindhárom relációt egy pipeline-ba tesszük. A szelekció eredményét azonnal átadjuk a join-nak, nem számítjuk ki el re az egész relációt. További el nye, hogy kicsi a memóriakövetelmény, mert az eredményeket nem tároljuk sokáig, hanem továbbadjuk. Hátránya, ha nincs közbüls reláció, nem tudunk rendezni sem (nem történik materializáció). A feldolgozás vezérlése alapján kétféle pipeline-t különböztetünk meg: igényirányított és termel -irányított. Az igényirányított esetben maga a rendszer fordul a cs vezeték tetejéhez és kér rekordokat. Minden alkalommal, ha a cs vezeték megkapja ezt a kérést, akkor kiszámítja és átadja a rendszernek. Termel irányított pipeline esetén a cs vezeték mentén elhelyezked m veletek nem várnak kérésre. A cs vezeték legalsó szintjén minden m velet folyamatosan generálja a rekordokat, és egy pufferbe teszi, amíg a puffer meg nem telik (ugyanígy tesz minden szint). Minden szinten minden m velet ,,egymástól függetlenül" dolgozik. 4.2.1. Pipeline kiértékelési algoritmus

Tekintsük a példánkban azt a join m veletet, amelynek baloldala cs vezetéken érkezik. Az egész baloldali reláció nem áll rendelkezésre, a rekordok egyenként jönnek, ezért nem használhatjuk az összes JOIN algoritmust (pl. merge-join rendezés alapú illesztési algoritmus, nem alkalmazható, ha a baloldali input nincs rendezve az illesztési attribútumok szerint). Az indexelt nested-loop join azonban használható, mert ahogy beérkeznek a baloldali rekordok, az illesztési attribútum-értékek alapján a jobboldali reláció feletti index segítségével kikeressük a jobboldali relációból az illeszked rekordokat és összeillesztjük ket egymással.

5. Relációs kifejezések transzformációi
Láttuk az elemi m veletek és egy adott lekérdezés kiértékelésének lépéseit. A bevezet ben azonban említettük, hogy egy adott lekérdezéshez több formális algebrai alakot is konstruálhatunk, amelyek mind más és más költséggel hajthatók végre.
5.1. Ekvivalens kifejezések

Tekintsük a következ természetes nyelven megfogalmazott kérdést. ,,Add meg azoknak a fogyasztóknak a nevét, akiknek van számlájuk Brooklyn-ban!".
(account customer _ name ( bran ch - city =" Brooklyn" (branch depositor )) A fenti relációs algebrai alak végrehajtása rengeteg er forrást pazarolna, hiszen három reláció összekapcsolása után végezné csak el a szelekciót. Egy sokkal hatékonyabb alak a következ : customer _ name (( bran ch - city =" Brooklyn" (branch)) (account depositor )) A második forma takarékosabban bánik az er forrásainkkal, el ször kiválasztja a branch relációból a Brooklyn-ban lév fiókokat, majd csak ezt illeszti a maradék kifejezéssel. A kezdeti és az átalakított kifejezés m veleti fáját mutatja az 5.1-es ábra.

Lekérdezés-feldolgozás és optimalizálás

12

A legkisebb költség végrehajtási terv megtalálása a lekérdezés optimalizáló feladata. Az optimalizáló els teend je adott lekérdezéshez ekvivalens algebrai alakok megtalálása. Majd az algebrai alakokhoz alternatív végrehajtási tervet kell készítenie.
5.2. Ekvivalencia szabályok

Az ekvivalens algebrai alakok legenerálásához az optimalizálónak szüksége van olyan szabályokra, amelyek mentén a feladat algoritmikusan elvégezhet , most ezeket a szabályokat vesszük sorra. Jelölések: , 1, 2 predikátumok, L1, L2, L3 attribútumok, E, E1, E2 relációs algebrai kifejezés. 1. 2. 3. 4. Szelekció kaszkádosítása: 12(E)=1(2(E)) A szelekció kommuntativitása: 1(2(E))=2(1(E)) Projekció kaszkádosítása: L1(L2(...(Ln(E))...)) =(L1(E)) Az illesztés és a Descartes szorzat kapcsolata:

( E1 × E2 ) = E1
5.



E2
1 2

E2 ) = E1 A theta-join kommuntativitása:
2

1 ( E1

E2

E1 E2 = E2 E1 6. A természetes és theta-illesztés asszociativitása: ( E1 7. E2 ) E3 = E1 ( E2 E3 )
2

( E1 1 E2 ) 2 3 E3 = E1 1 3 ( E 2 A szelekció m velet disztributivitása a join felett -Ha a 0 csak E1-beli attribútumokat tartalmaz:

E3 )

0 ( E1
8.



E2 ) = 0 ( E1 )



E2 )

A projekció disztributív a theta-join felett -Ha L1, L2 E1 illetve E2-beli attribútumokat tartalmaz és a join feltételében csak L1L2-beli attribútumok vannak.
L1 L 2 ( E1


E2 ) = ( L1 ( E1 ))



( L1 ( E 2))

Lekérdezés-feldolgozás és optimalizálás

13

9.

-Az L1 és L2 az E1 illetve L2-beli attribútumok halmaza. Az L3 olyan E1-beli és az L4 pedig olyan E2-beli attribútumok halmaza, amely nincs benne L1 és L2 uniójában. A join feltételében csak L3 és L4-beli attribútumok lehetnek. A metszet és az unió kommutativitása

L1 L 2 ( E1 E 2 ) = ( L1 L 2 ( L1 L3 ( E1 ))) ( L1 L 4 ( L 2 L 4 ( E 2 ))) E1 E2 = E2 E1 E1 E2 = E2 E1 10. Az unió és a metszet asszociativitása (E1 E2) E3 = E1 (E2 E3) (E1 E2) E3 = E1 (E2 E3) 11. A szelekció disztributív az unió, a metszet és a különbség m veletek felett P(E1 - E2)= P(E1) - P(E2) = P(E1)-E2 12. A projekció disztributív az unió m velet felett L(E1 E2)= L (E1) L (E2) A felsorolt szabályok nem tartalmazzák az összes ekvivalenciaszabályt, hanem csak ízelít t adnak bel lük. Számos egyéb, nem csak alapm veletekre kihegyezett átalakítási lehet ség is létezik.

6. A kiértékelési terv kiválasztása
Az ekvivalens kifejezések generálása csak az els lépése az optimalizálásnak. A második lépésben minden egyes kifejezéshez konkrét algoritmusokat kell rendelnünk. Meg kell mondanunk, hogy a m veleteket milyen sorrendben, milyen algoritmus szerint, milyen munkafolyamatba szervezve hajtjuk végre. Ennek egy grafikus alakban megadott példa reprezentációját mutatja a 6.1-es ábra.

6.1 ábra

6.1. Költségalapú optimalizálás

A fordító az el z fejezetben látott azonosságok alkalmazásával el ször felsorol minden, az eredeti kifejezéssel ekvivalens kifejezést (véges sokat). Ezután minden kifejezéshez hozzá tudunk rendelni kiértékelési tervet. A megfelel kiértékelési terv kiválasztásának folyamata tulajdonképpen a költség-optimalizálás. Minden kiértékelési tervre kiszámítjuk a költséget és kiválasztjuk a legolcsóbbat (becslések, statisztikák alapján). Hátránya, hogy túl sokféle kiértékelési terv lehet, amely rengeteg munkát ró a rendszerre. Tekintsünk például három reláció illesztését. Három relációt hatféleképpen állíthatunk sorrendbe, és ezt még be kell szorozni 2-vel

Lekérdezés-feldolgozás és optimalizálás

14

attól függ en, hogy a zárójelet az els kett relációhoz vagy a második kett höz tesszük. Általános esetben n reláció join-ja (2*(n-1))!/(n-1)! különböz ekvivalens alakot jelent (és ebben nincs is benne az algoritmus hozzárendelés). Ez már kis n esetén is rengeteg ekvivalenst produkál, pl. n=7 esetén 665280-at, n=10 esetén már több, mint 176 billiót! Szerencsére azonban nincs is szükség az összes ekvivalens kiértékelésére. Némi heurisztikával kezelhet bb méret vé csökkenthetjük a problémateret. Tekintsük a következ kifejezést: (r1 r2 r3 ) r4 r5 Keressük meg el ször azt az optimális alakot, amely csak az els három relációt illeszti, majd utána az eredményt a maradék kett relációval illeszti. Az els három reláció illesztésére 12 lehet ség adódik, majd az eredmény és a maradék két reláció illesztése ismét 12 lehet séget kínál. Ha értelmetlenül minden verziót kipróbálunk, akkor összesen 144 lehet séget nézünk végig. Ha azonban el ször megkeressük az els három reláció optimális kiértékelését és a 4. és az 5. relációval már ezt az optimális eredményt illesztjük, akkor a kiértékelés csupán 12+12 lépést próbálgat végig. A bemutatott algoritmus egyik legnagyobb problémája, hogy elméletileg is rossz, mert nem minden esetben képes megtalálni az optimális megoldást. Ennek oka, hogy az algoritmus mohó lévén mindig a lokálisan legjobb megoldást választja, és nem mérlegeli azt, hogy egy kicsit rosszabb lokális megoldás globálisan esetleg jobb eredményre vezetne. Sajnos, nem létezik olyan algoritmus, amely kis komplexitás mellett képes az optimális megoldást legenerálni, ezért be kell érnünk szuboptimális megoldásokkal.
6.2. Heurisztikus optimalizálás

A költségalapú optimalizálás legnagyobb hátránya magának ­ mint láttuk - az optimalizációs algoritmusnak a költsége. A legtöbb kereskedelmi rendszer ezért valamilyen heurisztikát használ a megfelel kifejezés kiválasztásához. Egy heurisztika alapú optimalizációs stratégia szabályai lehetnek például a következ k: 1) Végezzük el a szelekciót olyan korán, ahogy csak lehet, mert ezzel csökkentjük a sorok számát (bizonyos esetekben ez ugyan növeli a költséget, de általában csökkenti). A szabály alapján az optimalizáló olyan ekvivalens átalakításokra fog törekedni, amelyben legbelül lesznek a szelekciós m veletek (7-es szabály). 2) Hamar végezzük el a projekciót, mert ezzel csökkenthet a sorok mérete. A szelekciót általában érdemesebb el bb elvégezni, mert a reláció mérete jobban csökken, mint a projekció alkalmazásával, de persze el fordulhat, hogy a projekció redukálja jobban a reláció méretét. 3) Bontsuk szét a szelekciók konjunkcióját szelekciók szorzatára, hogy minden szelekciónak csak egy tényez je legyen. Ez lehet vé teszi, hogy a fában a szelekciókat lefelé vándoroltassuk, ezáltal a közbens m veletek jóval kevesebb rekordot adjanak végeredményként. 4) A kiértékelési fában vándoroltassuk lefelé a szelekciókat. 5) Határozzuk meg, hogy mely szelekció és join eredményezi a legkisebb (=legkevesebb rekordot tartalmazó) relációkat. Használjuk fel join asszociativitását, alakítsuk át a fát úgy, hogy ezek a szelekciós és join m veletek hajtódjanak végre el ször. 6) El fordulhat, hogy a join megegyezik a Descartes-szorzattal. Ha ezt egy szelekció követi, akkor vonjuk össze a kett t egy join m velettét, így kevesebb rekordot kell generálni. 7) Törjük szét a projekció-listákat. Az egyes vetítéseket lökjük lefelé a fán, amennyire tudjuk. Ehhez új vetítéseket is létrehozhatunk, ha szükséges.

Lekérdezés-feldolgozás és optimalizálás

15

8) Keressük meg azokat a részfákat, ahol a cs vezetéket lehet alkalmazni. A szabályok alkalmazásával több kiértékelési fát kapunk. Ezeknek meghatározzuk a költségét és vesszük közülük a legolcsóbbat. Mint láttuk a költségalapú és heurisztikus optimalizálás is jelent s terhelést jelent a rendszer számára. Nem elég tehát a legjobb megoldást megtalálni, hanem a keresés költségét is optimalizálni kell. Az az érdekes helyzet adódik, hogy az optimális optimalizáló a saját m ködését (tehát a kiértékelési terv keresését) és magának a megtalált megoldásnak a végrehajtását kell, hogy optimalizálja.

7. Irodalomjegyzék
[1] Silberschatz, Korth, Sudarshan: Database System Concepts, McGraw-Hill 2005. [2] Joe Hellerstein, Eric Brewer: Query Processing, Advanced Topics in Computer Systems, Online http://www.cs.berkeley.edu/~brewer/cs262/QP.html [3] George Koch-Kevin Loney: Oracle 8, Panem Könyvkiadó, 1999. [4] Simon Zoltán: Lekérdezés feldolgozás és optimalizálás, Oktatási segédanyag, BME TMIT 2002. Ld. még http://www.informatik.uni-trier.de/~ley/db/dbimpl/qo.html



Hasonló témájú dokumentumok

Hozzászólások

1. előadás 15 15 bizonytalanság és játékelmélet0001 18. század 1eloadas 2008 2011 4. gyakorlat 5. gyak 7. gyakorlat adóigazgatás algoritmus analízis dolgozat megoldás anatómia bibó csokonai definíciók ea ergonómia érzékelő fejlődés fémek füvészkert gazdaság géntech házi dolgozat hónolás info jegyzőkönyv kérdések kiállítás környezetvédelmi mikrobiológia kötelező közig lakoma magyar premodern matrix méhen belüli fejlődés merőpiac példatár political science pót reklámelmélet és gyakorlat standardizálás szemiotika tb nemzetközi tektonika tematika tételek vegyes piacgazdaság