Relációs lekérdezések optimalizálása

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

Ezen a helyen volt linkelve a lekredezes.PNG nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

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

CSONK

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

• Materializáció: def 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 (hópihe,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. 

[http://learndatamodeling.com/snow_flake.htm

Ezen a helyen volt linkelve a snow_flake.gif nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

]

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

[http://learndatamodeling.com/star.htm

Ezen a helyen volt linkelve a star_schema.gif nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

]

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)

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.

Lássunk egy csillag queryt:

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;

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:

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'));

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 - 2007.11.25.