8. rész

Relációs lekérdezések optimalizálása
Heurisztikus optimalizálás, ekvivalens kifejezések
Költség alapú optimalizálás, költségbecslések

lekérdezés feldolgozásának lépései:
- elemzés, fordítás (SQL lekérdezésből relációs algmbrai kifejezés)
- költségoptimalizálás (relációs algebrai kifejezésből végrehajtási terv)
- kiértékelés (végrehajtási terv alapján lekérdezés kimenetelének visszaadása)
katalógusban tárolt információk a relációkra
- \(n_r\): rekordelemek száma
- \(b_r\): rekordokat tartalmazó blokkok száma
- \(s_r\): rekord nagysága bájtokban
- \(f_r\): mennyi rekord fér az r reláció egy blokkjába (blocking factor)
- \(V(A, r)\): hány különböző értéke fordul elő az A attribútumnak (kulcs esetén \(n_r\))
- \(SC(A, r)\): azon rekordok várható száma, amelyek kielégítenek egy egyenlőségi feltételt az A attribútumra (Selection Cardinality)
  - ha A egyediséget biztosít: \(SC(A, r) = 1\)
  - különben feltesszük, hogy a különböző értékek egyenletesen oszlanak el: \(SC(A, r) = \frac{n_r}{V(A, r)}\)
- \(\left \lceil{\frac{SC(A, r)}{f_r}} \right \rceil\) = blokkok száma amelyek kielégítenek egy egyenlőségi feltételt A attribútumra
- infok az indexekről:
  - \(f_i\): átlagos pointer szám a fa-struktúrájú indexek csomópontjaiban (egy csp-ben az elágazások száma)
  - \(HT_i\): i index szintjeinek száma (magassága)
  - \(LB_i\): levélszintű indexblokkok száma

Műveletek költsége¶

szelekció:
- lineáris keresés: \(E_{lin} = b_r\)
- bináris keresés: \(E_{bin} = \left \lceil{\log_2 b_r} \right \rceil + \left \lceil{\frac{SC(A, r)}{f_r}} \right \rceil - 1\)
  - (első megkeresése binárisan, majd feltételt kielégítő összes rekord tárolásához szükséges blokk átlagos száma, minusz egy mert kétszer olvastuk az első blokkot)
  - csak akkor jó, ha A szerint rendezettek, és a blokkok folyamatosan vannak a discen, és egyenlőségvizsgálat van
indexelt szelekció:
- elsődleges index használatával, egyenlsőégi feltétel a kulcson:
  - \(E = HT_i + 1\)
- elsődleges index használatával, egyenlőségi feltétel nem a kulcson:
  - \(E = HT_i + \left \lceil{\frac{SC(A, r)}{f_r}} \right \rceil\)
- másodlagos index használatával
  - \(E = HT_i + SC(A, r)\), (nem biztos, hogy egy blokkban vannak, mert másodlagos indedx alapján keresünk)
  - \(E = HT_i + 1\), ha A kulcs
összehasonlítás alapú szelekció:
- elsődleges indexxel
  - \(E = HT_i + \frac{b_r}{2}\), ha nem ismerjük a feltételt
  - \(E = HT_i + \left \lceil{\frac{c}{f_r}} \right \rceil\), ha ismerjük a feltételt (c azon rekordok száma, ahol A <= v)
- másodlagos indexxel
  - \(E = HT_i + \frac{LB_i}{2} + \frac{n_r}{2}\)
  - mert nincsenek rendezve, és másodlagos index szerint keresünk
join operiáció:
- Nested-loop join
  - r külső, s belső ciklus
  - legrosszabb: \(n_r*b_s+b_r\)
  - ha legalább az egyik elfér a memóriában -> \(b_r + b_s\)
- Block-Nested-loop join
  - legrosszabb: \(b_r*b_s+b_r\)
  - sok memóriával: \(b_r+b_s\)
- Indexed Nested-loop join
  - \(b_r + n_r*c\), ahol \(c\) az s költsége
- Hash join
  - \(b_r + n_r * c\), ahol \(c\) a vödör átnézés költsége)
- Merge join
  - rendezzük a két relációt és utána összefésüljük az elemeket
  - \(b_s + b_r + c\), ahol \(c\) a rendezés költsége

Kiértékelési terv kiválasztása¶

DB manager átfordítja az SQL-t relációs algebrai nyelvre
ekvivalens kifejezések generálása
konkrét algoritmus hozzárendelése
meg kell adnunk, hogy milyen műveleteket, milyen sorrendben, milyen algoritmus szerint, milyen munkafolyamatba szervezve hajtunk végre

Materializáció és pipeline¶

materializáció
- összetett kifejezéseknek egyszerre egy műveletét értékeljük ki egy adott sorrendben
- háttértárra írjuk ki
- eredő költség: végrehajtott műveletek + tárolás és visszaolvasás költsége
- előny: könnyen implementálható
- hátrány: nagy memóriaigény
pipeline
- egyszerre több művelet kiértékelése
- az eredményt azonnal átadjuk
- nem számítja ki az egész relációt
- típusai:
  - igényirányított
  - termelőirányított
- előny: kis memóriaigény
- hátrány:
  - kevés algoritmus (indexed Nested-loop join lehet pl)
  - NINCS rendezés

Ekvivalens kifejezések¶

optimalizálás első lépése
jelölések
- \(\Theta\) predikátum, \(L\) attribútumhalmaz és \(E\) reláció algebrai kifejezés
szelekció kaszkádosítása
szelekció kommutativitása
projekció kaszkádosítása (ha csökkennek az attribútumhalmazok)
theta illeszés és Descartes-szorzat
theta illesztés kommutativitása
természetes illesztés asszociativitása
metszés és unió
projekció disztributivitása
projekció disztributív az unió felett

Heurisztikus optimalizálás¶

folyamata:
1. kanonikus alakból indulunk (Descartes, szelekció, projekció)
2. szétbontás -> szelekciók konjunkcióját szelekciók szorzatára bontjuk
3. szelekciók süllyesztése a fában (közbülső műveletek kevesebb eredményt adjanak tovább)
4. levelek átrendezése úgy, hogy a legkisebb relációt előállító dolgok legyenek alul (fa gyökere felé)
5. ha egy join megegyezik a Descartes-szorzattal és utána szelekció jön, akkor ebből theta illesztés készíthető (\(r \underset{\Theta}{\Join} s\))
6. projekciók széttördelése és süllyesztése (akár újak létrehozása)
7. részfák keresése, ahol pipeline használata lehetséges
több fát kapunk -> fákhoz algoritmusokat és pipeline-stratégiákat rendelünk, majd kiszámoljuk a költségeket

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

lépések:
1. minden kifejezéssel ekvivalens kifejezés felsorolása
2. minden forma kiértékelése plusz végrehajtási terv hozzárendelése
3. minden végrehajtási terv kiszámolása -> nagyon sok idő plusz terhelés
pl n reláció join-ja nagyon sok különböző ekvivalens alakot jelent
előny: herisztikusnál optimálisabb
hátrány ha részfákra használjuk: MOHÓ megközelítés (lokális jobbat választja a globális jobb helyett)