Relációs lekérdezések optimalizálása forrásának megtekintése

{{GlobalTemplate|Infoszak|InfoMenRelacOptim}}


__TOC__
	<center> {{InLineImageLink|Infoszak|InfoMenRelacOptim|lekredezes.PNG}}  </center>
==Heurisztikus, szabály alapú optimalizálás==

'''Módszer''' : Reláció algebrai alakból felrajzolt fa optimalizálása. Lekérdezési fa elkészítése során célunk a lehető leggyorsabb alak kiválasztása:
* induljunk ki a kanonikus alakból (Descartes-szorzat, szűrés, projekció). 
* lesüllyesztjük a szelekciókat
* átrendezzük a leveleket (először a kisebbeket descartes szorozzuk)
* join-ná alakítjuk a descatres-szorzat+szelekció-kat
* lesüllyesztjük a projekciókat

===Műveletek===

'''Felmerül a kérdés, hogy két fa mikor ekvivalens?'''
''lásd slideok'' Használjuk ki a halmazműveletek(unió, metszet) kommutativitását és a join Descartes-szorzat és a halmazműveletek asszociativitását.
Összefoglalva a szabályokat:
* konjunktív szelekciós feltételeket szelekciós feltételek sorozatává bontjuk.
* szelekciós műveleteket felcseréljük a többi művelettel
* átrendezzük a leveleket
* a Descartes szorzatokat és a fölüttök lévő szelekciós kapcsolási feltételt egy join műveletté vonjuk össze.
* projekciós műveleteket lecseréljük a többi művelettel.

==Költség alapú optimalizálás==

A relációkról a rendelkezésre álló információk alapján kiszámolunk több végrehajtási tervre egy költséget, és az optimálisat kiválasztjuk. 

===Katalógusadatok===

Ehhez katalógusadatokat tárolunk az egyes relációkról:
* '''n_r''' az r rel-ben található rekordok száma (number)
* '''b_r''' az r rel-et tartalmazó blokkok száma (block)
* '''s_r''' egy rekord mérete (size)
* '''f_r''' mennyi rekord fér egy blokkba (blocking factor) pl.: ha a rel rekordjai fizikailag együtt vannak tárolva, akkor b_r = [n_r/f_r]	(felső egész)
* '''V(A, r)''' hány különböző értéke fordul elő az r rel-ben az A attr-nak
* '''SC(A, r)''' selection cardinality, azon rekordok átlagos száma, amelyek egy kiválasztási feltételt kielégítenek. Pl.: ha A kulcs: SC(A, r)=1 illetve általánosan: SC(A, r) = n_k / V(A, r)
* '''f_i''' fa struktúrájú index esetén (pl B*), pointer kimenetek átlagos száma (elágazási tényező)
* '''HT_i''' az index szintjeinek a száma, Pl.: HT_i = [log f_i (V(A,r))]  (alsó egész), illetve hash esetén HT_i = 1
* '''LB_i''' a levélszintű indexblokkok száma (lowest level index block).

===Hátrányok ===

* a relációk elemszámának nyilvántartása nem triviális
* lekérdezni hosszú idő (~100 milliós rekordszámnál pl.)
* folyamatos frissítés is nagy overhead
* ezért pl. az ORACLE-nél külön, explicit módon kell frissíteni a katalógust (ANALYZE) itt még azt is meg lehet adni, hogy hány százaléka alapján analizálja az adatbázist

===Költségszámítás===

Felmerül a kérdés: hogyan határozzuk meg egy reláció költségét:
* igényelt és felhasznált erőforrások alapján?
* válaszidő alapján? (az összes rekord vagy az első válasz rekord válaszideje alapján?)
* kommunikációra fordított idő alapján? (elosztott rendszereknél fontos)

A definicó szerint legyen egy reláció költsége a háttértár blokkolvasások és írások száma a válasz kiíratásának költsége nélkül (ugyanis a diszkolvasás ms nagyságrendű, a blokk feldolgozása pedig ennek pl. 100-ada). 
Ez az érv kezdi érvényét veszteni, amikor ~100GB-os memóriák is vannak, és lehet az egész db-t memóriában tárolni. 

===Operációk, műveletek költsége===

Ha a feltétel a kulcson van, akkor csak egy eredmény-sor van, és így csak egy eredmény-blokkot kell olvasni, ha nem a kulcson van, lehet, h többet is (SC(A, r)/f_r-t).

====SELECT attribútum = alapján====

E jelentése itt: Estimate 

* '''A1''' - lineáris keresés ktg: E_A1=b_r
* '''A2''' - bináris keresés
** feltételezi, hogy a blokkok folyamatosan az A attribútum szerint rendezettek legyenek a diszkeken, illetve, hogy a szelekció feltétele az A attribútumon legyen.
** ktg '''E_A2''' = [log2(b_r)] + [SC(A,r)/f_r] -1 ,  ahol  az első tag: binárisan megkerünk 1 blokkot, a második tag: több rekord is egyezhet, ezek ennyi rekordban vannak, illetve a harmadik tag: az első blokk megtalálását kétszer számolnánk egyébként.
* '''A3''' - elsődleges indexszel, kulcsot vizsgálva
** ktg: '''E_A3''' = HT_i + 1 , ahol az első tag: indexfa végigjárása illetve a második tag: adatblokk beolvasása.
* '''A4''' - elsődleges indexszel, de ez nem kulcs
** ktg '''E_A4''' = HT_i + [SC(A, r)/f_r] , ahol első tag: indexfa végigjárása második tag: adatblokkok beolvasása
* '''A5''' - másodlagos index használatával
** ktg: '''E_A5''' = HT_i + SC(A, r), ahol az első tag: indexfa végigjárása illetve a második tag: adatblokkok beolvasása (ui a blokkok nem sorban vannak egymás utáni blokkokban) '''E_A5''' = HT_i + 1 (ha A kulcs).


====SELECT összehasonlítás alapú szelekció: A<v====

* ha v-t nem ismerjük: n_r/2-t kapunk vissza
* ha v-t ismerjük, egyenletes eloszlás esetén n_ált = n_r((v-min(A,r))/(max(A,r)-min(A,r)))
* '''A6''' - elsődleges index használatával
** ha a v-t nem ismerjük '''E_A6''' = HT_i + b_r/2
** ha v-t ismerjük '''E_A6''' = HT_i + [c/f_r], ahol c a találati halmaz várható nagysága
* '''A7''' -  másodlagos index '''E_A7''' = HT_i + LB_i/2 + n_r/2 , ahol az első tag: végigmegyünk az indexfán, a  második tag: az indexfa leveleit olvassuk illetve a harmadik tag: az adatblokkok olvasás. Ez igencsak nem gazdaságos, ugyanis, ha bután, kimerítően keresek, akkor b_r-nyit kell csak olvasni


====SELECT komplex szelekció====

Mind a konjunkció és diszjunkció esetén nem bonyolultabb, mint egy szimpla szelekció becslése.

====JOIN====

* nested loop join
** worst case ktg: n_r*b_s + b_r (ha legalább az egyik belefér a memóriába, akkor a ktg b_r+b_s)
* block nested loop join
** 4 ciklus egymásban (2: 1-1 blokkok mindig felolvasok mind2 relációból + 2: blokkon belül illesztek
** worst-case ktg: b_r*b_s+b_r (sok memory: b_r+b_s)
* indexed nested-loop join
** az egyik rel-hez van indexünk
** az első alg-ot nézzük, a belső ciklusban az indexelt reláció legyen
** ktg: b_r+n_r*c , ahol a c a szelekció ktg-e s-en
* sorted merge-join
** a rel-kat a join feltételben meghatározott attr-ok mentén rendezzük, majd fésüljük
* hash-join
** az egyik rel-t hash-táblán keresztül érjük el, miközben a másik rel-t egy adott rekordjához illeszkedő rekordok keressük 
* egyéb
** pl bitmap indexszel, bitmap join

====Egyéb operációk====

<span style="color:red"> '''CSONK'''  </span>

===Workflow: Egy kifejezés kiértékelésnek módjai===

* Materializáció: <span style="color:red"> def </span> A különböző részeredmény-táblákat a diszkre írjuk. Egyszerűen implementálható viszont sok háttértár műveletet igényel.
* Pipelineing: Szimultán kiértékelés, a részegységek az előttük álló elemből kapott eredményekből a sorban következő számára állítanak elő részeredményeket. Nincs szükség a teljes reláció előre kiszámolására. Ezáltal az ideiglenes tárolási igényeket minimalizálja, kicsi a memóriaigénye, viszont leszűkíti az alkalmazható algoritmusok körét.

===A kiértékelési terv kiválasztása===

A terv során válaszolnunk kell a következő kérdésekre:
* milyen műveleteket kívánunk elvégezni
* milyen sorrendben
* milyen algoritmus használatával
* milyen workflow szerint.

Ha minden ekvivalens kifejezést (költség alapú optimalizáció) megvizsgálnának és minden formát kiértékelnénk (azzal a céllal, hogy a végén az optimálisat válasszuk ki), túl nagy terhelést jelentene a rendszer számára. Ezért Heurisztikus költség alapú optimalizálást érdemes használni. Mindezt '''automatikusan''' vagy *manuálisan*?

Az '''automata''' szélesebb ismerettel rendelkezik a letárolt adatelemekről, gyorsabb a numerikus kiértékelési mechanizmusa, szisztematikusan értékel, 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. Ezzel szemben az '''ember''' szélesebb általános ismerettel rendelkezik, a probléma szemantikai tartalmát megérti, nagyobb szabadsággal rendelkezik a felhasználható módszerek, eszközök tekintetében, illetve jobban fel van készítve a váratlan helyzetek kezelésére.

==Lekérdezés optimalizálás csillagsémákon==

Az Oracle 7-es verziójától érhető el, különbözik a korábbi filozófiától, nagyságrendekkel hatékonyabb: lényegében egy illesztés a ténytábla és a dimenziós táblák között. A dimenziós táblák join-jának kiküszöbölése, lehetőség az automatikus felismerésre. 
Két ismert séma  ([http://en.wikipedia.org/wiki/Snowflake_schema hópihe],[http://en.wikipedia.org/wiki/Star_schema csillag] közül a csillagsémákon vizsgáltuk részletesen a lekérdezésoptimalizálást.

===Hópihe séma===

 A '''hópihe sémáról''' megemlítettük, hogy gyenge browsing teljesítménnyel rendelkezik ha növeljük a relációk számát. Itt a dimenziós táblák nem önmagukban állnak, hanem több tábla írja le a különböző hierarchia-szinteket. A gyakorlati tapasztalat azt mutatja, hogy az adattárház hozzáférések 80-90%-a dimenziók megfelelő kezelésével, a hatalmas lekérdezés előkészítésével foglalkozik. 

<center>	
[http://learndatamodeling.com/snow_flake.htm {{InLineImageLink|Infoszak|InfoMenRelacOptim|snow_flake.gif}}]
 </center>
===Csillag séma===

A '''csillag séma''' kialakításának feltételi (Oracle):
* egyattribútumos bitmap index definiálása a tény valamennyi idegen kulcsára
* inicializáló paraméter beállítása (STAR_TRANSFORMATION_ENABLED should be set to TRUE)
* költségalapú optimalizálás használata


<center>	
[http://learndatamodeling.com/star.htm {{InLineImageLink|Infoszak|InfoMenRelacOptim|star_schema.gif}}]
 </center>
===Bitmap (bittérkép) index===

* lehetőleg alacsony kardinalitású attribútumot válasszunk (azaz kevés különböző érték forduljon elő)
* Pl.: Az alkalmazott nemének (férfi-nő) tárolására: definiálunk egy kétoszlopos indexet, az értékeknek megfelelően (annyi oszlop, ahány érték). A táblázat sorai a sorszámnak megfelelően be van indexelve külső kulccsal a relációhoz. 
* mivel alacsony kitöltésű a táblázat, ezért tömöríteni szokták: a töredékére összenyomható
* bizonyos szelekciók kiértékelését nagyon meg tudja könnyíteni (a bitmap indexek jóval kisebbek, könnyebb vele bánni)

[http://en.wikipedia.org/wiki/Bitmap_index bővebben lásd wikipédia].

===Csillag transzformáció===

Az Oracle query optimalizáló modulja végzi el az SQL utasítás átírását, ahol ez hasznos lehet. A művelet két lépésből áll, elsőnek a szükséges  sorokat választja ki a tény táblából, ez a bitmap indexelés használata miatt igen hatékony. A második lépésben az így kapott eredményhalmazt ==JOIN== -oljuk a dimenziós táblákkal. 

[http://download-uk.oracle.com/docs/cd/B19306_01/server.102/b14223/schemas.htm Lássunk egy csillag queryt:]

<pre>
SELECT ch.channel_class, c.cust_city, t.calendar_quarter_desc,
	SUM(s.amount_sold) sales_amount
FROM sales s, times t, customers c, channels ch
WHERE s.time_id = t.time_id
AND	s.cust_id = c.cust_id
AND	s.channel_id = ch.channel_id
AND	c.cust_state_province = 'CA'
AND	ch.channel_desc in ('Internet','Catalog')
AND	t.calendar_quarter_desc IN ('1999-Q1','1999-Q2')
GROUP BY ch.channel_class, c.cust_city, t.calendar_quarter_desc;
</pre>

Az első transzformációs lépés után a három '''bitmap''' (time_id, cust_id, channel_id) index felismerése után ==AND== operátorral kötjük össze:

<pre>
SELECT ... FROM sales
WHERE time_id IN
  (SELECT time_id FROM times 
	WHERE calendar_quarter_desc IN('1999-Q1','1999-Q2'))
	AND cust_id IN
  (SELECT cust_id FROM customers WHERE cust_state_province='CA')
	AND channel_id IN
  (SELECT channel_id FROM channels WHERE channel_desc IN('Internet','Catalog'));
</pre>

Az így kapott eredményhalmazon végül a dimenziók mentén ==JOIN== művelet következik. Ennek hatékonyságát növeli, hogy a bitmapnak köszönhetően effektíve egyetlen ==JOIN== művelet elegendő a dimenziónkénti ==JOIN== -ok helyett.

 
Megállapíthatjuk, hogy a csillagtranszformáció elég jól működik, ha a ==WHERE== predikátum kellően szelektív a tényrekordra, viszont ha sok tényrekord értintett az eredmény előállításában, akkor "full table scan" jobb lehet...

-- [[AdamO|adamo]] - 2007.11.25.


[[Category:Infoszak]]