Lze bez nadsßzky °φci, ₧e optimalizßtor dotaz∙ tvo°φ nejd∙le₧it∞jÜφ komponentu relaΦnφho S╪BD. V jakΘmkoli databßzovΘm stroji (Φi SQL-serveru) by m∞l p°edstavovat jßdro systΘmu, m∞l by b²t zodpov∞dn² za vybrßnφ vhodnΘ strategie pro vyhodnocenφ dotazu. RelaΦnφ S╪BD je velmi pravd∞podobn∞ tak dobr², jak je dobr² jeho optimalizßtor dotaz∙. Optimalizßtor dotaz∙ je softwarov² modul, kter² transformuje neprocedurßlnφ dotaz do procedurßlnφho plßnu vyhodnocenφ, tak aby zp∙sob vyhodnocenφ byl co nejefektivn∞jÜφ.

Pot°eba pro optimalizaci dotaz∙ vznikß jako d∙sledek zßkladnφ filosofie relaΦnφho S╪BD - odd∞lit formulaci u₧ivatelsk²ch po₧adavk∙ od fyzickΘho ulo₧enφ dat. TΘto vlastnosti se takΘ °φkß nezßvislost na fyzick²ch datech. Ka₧d², kdo n∞kdy zkouÜel zapsat dotaz v relaΦnφ algeb°e nebo v SQL, zjistil, ₧e jeden a t²₧ dotaz lze v jazyce formulovat vφce zp∙soby, kterΘ jsou z hlediska v²sledku vyhodnocenφ ekvivalentnφ, avÜak z hlediska efektivnosti vyhodnocenφ jsou zcela r∙znΘ. Optimalizßtor dotaz∙ by m∞l v ideßlnφm p°φpad∞ zajistit, aby vyhodnocenφ dotazu bylo nezßvislΘ na zvolenΘ syntaktickΘ verzi dotazu.

Uva₧ujme nap°. dotaz ôNajdi pro kino Prßce re₧isΘry vÜech film∙, kterΘ se v n∞m hrajφö. Tento dotaz lze v SQL zapsat nap°. jako

SELECT FILM.REÄIS╔R

FROM P╪EDSTAVEN═ X, FILM Y

WHERE X.JM╔NO_FILMU = Y.JM╔NO_FILMU AND X.N┴ZEV_KINA=ôPR┴CEö

Vyhodnocenφ by mohlo b²t provedeno ve t°ech krocφch:

1. Spoj relace P╪EDSTAVEN═ a FILM p°es atribut JM╔NO_FILMU;

2. Vyber jen ty °ßdky, pro kterΘ N┴ZEV_KINA=ôPR┴CEö;

3. Prove∩ projekci na atribut REÄIS╔R;

Jinß a z°ejm∞ efektivn∞jÜφ varianta plßnu vyhodnocenφ by nejprve provedla selekci °ßdk∙ relace P╪EDSTAVEN═ a teprve pak operaci spojenφ s relacφ FILM, tj. uplatnila by se zßsada "zmenÜi p°ed operacφ spojenφ co mo₧nß nejvφce relace-operandy". K tomu je t°eba mφt k dispozici soustavu pravidel, kterΘ umo₧≥ujφ nahradit jeden v²raz relaΦnφ algebry jin²m, ekvivalentnφm. Postupu se pak °φkß algebraickß optimalizace. Prakticky se provßdφ transformacemi strom∙ dotazu. V t∞chto stromech jsou v listech zßkladnφ relace, ostatnφ uzly jsou dßny operacemi relaΦnφ algebry. Na obrßzku 1 jsou stromy uva₧ovanΘho dotaz (p∙vodnφ a optimalizovanß verze).

[ REÄIS╔R]

N┴ZEV_KINA=ôPR┴CEö [ REÄIS╔R]

* N┴ZEV_KINA=ôPR┴CEö

FILM

P╪EDSTAVEN═ FILM P╪EDSTAVEN═

Obr. 1: Dotaz p°ed a po transformaci

Optimalizace m∙₧e ovÜem b²t provßd∞na podle dalÜφch princip∙, nap°. v zßvislosti na velikosti relacφ, velikosti aktußlnφ domΘny danΘho atributu apod. Jeli jedna relace dostateΦn∞ malß, je ji mo₧nΘ naΦφst do vnit°nφ pam∞ti, co₧ znaΦn∞ zjednoduÜφ algoritmy spojenφ. V²znamnou roli m∙₧e hrßt existence indexu pro n∞kter² z atribut∙, nebo set°φd∞nφ relace. Na zßklad∞ vybranΘ strategie se urΦuje i velikost pot°ebnΘ vnit°nφ pam∞ti, nebo naopak velikost pam∞ti ovliv≥uje v²b∞r strategie. Obecn∞ lze v²b∞r optimßlnφ strategie chßpat jako optimalizaci pomocφ jistΘ cenovΘ funkce.

Uva₧ujme dotazovacφ jazyk SQL. Pak zpracovßnφ m∙₧e vypadat tak, jak ukazuje obrßzek 2.

dotaz v SQL

kontrola syntaxe

syntakticky sprßvn² dotaz

sΘmantickß kontrola

sΘmanticky sprßvn² dotaz

transformace

dotaz v relaΦnφ algeb°e

optimalizace v relaΦnφ algeb°e

optimalizovan² dotaz v relaΦnφ algeb°e

v²b∞r strategie

provßd∞cφ plßn vyhodnocenφ

generovßnφ k≤du

program dotazu

Obr.2: Proces vyhodnocenφ dotazu

Zφskanφ ekvivalentnφho v²razu relaΦnφ algebry je umo₧n∞no platnostφ n∞kter²ch zßkon∙ vypl²vajφcφch z definice relaΦnφch operacφ. Pomocφ [q ] budeme oznaΦovat q -spojenφ (kde q je n∞jakΘ porovnßnφ), zßpis E₁ » E₂ oznaΦuje, ₧e v²razy relaΦnφ algebry E₁ a E₂ jsou ekvivalentnφ. Platφ nßsledujφcφ zßkony:

(1) Komutativita spojenφ a kartΘzskΘho souΦinu

E₁ [q ] E₂ » E₂ [q ] E₁

E₁ * E₂ » E₂ * E₁

E₁ ´ E₂ » E₂ ´ E₁

(2) Asociativita spojenφ a kartΘzskΘho souΦinu

(E₁ [q ₁] E₂) [q ₂] E₃ » E₁ [q ₁] (E₂ [q ₂] E₃)

(E₁ * E₂) * E₃ » E₁ * (E₂ * E₃)

(E₁ ´ E₂) ´ E₃ » E₁ ´ (E_{2 ´} E₃)

Proto₧e se pomocφ operace spojenφ spojujφ takovΘ n-tice relacφ, kterΘ majφ spoleΦnou hodnotu danΘho atributu, umo₧≥uje asociativita a komutativita hledat v p°φpad∞ n∞kolika spojenφ relacφ takovΘ po°adφ operacφ, aby meziv²sledky byly co nejmenÜφ, tj. aby se co nejvφce redukoval poΦet p°φstup∙ na disk.

Strategii optimalizace uvedenou v p°φkladu umo₧≥ujφ pravidla, kde projekce odstranφ zbyteΦnΘ atributy, selekce redukujφ poΦet n-tic relacφ.

(3) Komutativita selekce a projekce

Jsou-li vÜechny atributy z formule j selekce v mno₧in∞ atribut∙ {A₁,...,A_k}, pak

E₁[A₁,...,A_k](j ) » E₁(j )[A₁,...,A_k]

Nejsou-li B₁,...,B_s ve j , pak

E₁(j )[A₁,...,A_k] » E₁[A₁,...,A_kB₁...B_s](j )[ A₁,...,A_k]

Propagaci selekce k (zßkladnφm) relacφm lze pou₧φt i u operacφ sjednocenφ, rozdφl a kartΘzsk² souΦin.

(4) Komutativita selekce a kartΘzskΘho souΦinu

Jestli₧e vÜechny atributy ve j jsou souΦasn∞ v E₁, pak

(E₁ ´ E₂)( j ) » E₁(j ) ´ E₂

(5) Komutativita selekce a sjednocenφ

(E₁ È E₂)(j ) » E₁(j ) È E₂(j )´

(6) Komutativita selekce a rozdφlu

(E₁ - E₂)( j ) » E₁(j ) - E₂(j )

Podobn∞ lze pou₧φt i projekci.

(7) Komutativita projekce a kartΘzskΘho souΦinu

(E₁ ´ E₂)[A₁,...,A_k] » E₁[B₁...B_k] ´ E₂[C₁...C_m]

kde sjednocenφ atribut∙ v projekcφch na pravΘ stran∞ je rovno mno₧in∞ atribut∙ projekce na levΘ stran∞, B_i se t²kajφ E₁ a C_j se t²kajφ E₂.

(8) Komutativita projekce a sjednocenφ

(E₁ È E₂)[A₁,...,A_n] » E₁[A₁,...,A_n] È E₂[A₁,...,A_n]

Dßle lze nap°. selekci rozd∞lit ve dv∞, je-li j konjunkcφ. Tomuto procesu se °φkß vytvß°enφ kaskßd selekcφ. Podobn∞ lze vytvß°et i kaskßdy projekcφ. P°i optimalizaci se ale pravidla obvykle pou₧φvajφ pouze v jednom, v²hodnΘm sm∞ru, tj. ruÜφ se kaskßdy.

P°i optimalizaci dotaz∙ pomohou tedy pravidla, kterß mohou produkovat dobrΘ v²sledky, ale kterß ne v₧dy zaruΦujφ nejlepÜφ °eÜenφ. Zßkladnφ strategiφ je omezit velikosti meziv²sledk∙ operacemi selekce a projekce jak jen je mo₧nΘ. Tyto heuristiky lze shrnout nap°. do nßsledujφcφch 6 pravidel:

1. Prove∩ selekce co nejd°φve. Je-li to mo₧nΘ, pou₧ij kaskßd selekcφ, komutativity selekce s projekcemi a kartΘzsk²mi souΦiny, distributivnosti selekce nad mno₧inov²mi operacemi s cφlem dostat selekci ve stromu dotazu co nejnφ₧e k list∙m.

2. Prove∩ projekce co nejd°φve. Je-li to mo₧nΘ, pou₧ij kaskßd projekcφ, distributivity projekcφ nad kartΘzsk²m souΦinem a ostatnφmi mno₧inov²mi operacemi, komutativity selekce a projekce s cφlem dostat projekci ve stromu dotazu co nejnφ₧e k list∙m. VyzkouÜej, zdali n∞kterΘ projekce nejsou zbyteΦnΘ.

3. Jestli₧e se jako argument selekce vyskytuje kartΘzsk² souΦin a selekce zahrnuje atributy obou relacφ, transformuj kartΘzsk² souΦin na spojenφ. Zahrnuje-li selekce atribut pouze jednΘ z relacφ, aplikuj selekci nejd°φve na ni.

4. Jestli₧e je dßna posloupnost selekcφ a/nebo projekcφ, pou₧ij kombinaci komutativity a nahrazenφ kaskßdy selekcφ nebo projekcφ jednou selekcφ a jednou projekcφ v po°adφ selekce nßsledovanß projekcφ a aplikuj je souΦasn∞ na ka₧dou vybranou n-tici. Jestli₧e je operace spojenφ nebo kartΘzsk² souΦin nßsledovßna posloupnosti selekcφ nebo projekcφ, aplikuj je v okam₧iku, kdy jsou n-tice spojenφ Φi kartΘzskΘho souΦinu generovßny.

5. Pou₧ij asociativity spojenφ, kartΘzskΘho souΦinu, sjednocenφ a pr∙niku k p°eskupenφ v∞tvφ stromu dotazu tak, ₧e selekΦnφ operace, kterß produkuje menÜφ relaci, bude volßna nejd°φve.

6. Jestli₧e se n∞jak² podv²raz vyskytuje vφcekrßt ve stromu dotazu a v²sledek, kter² produkuje nenφ p°φliÜ velk², spoΦφtej ho jednou do pomocnΘ relace. To je vhodnΘ nap°. u dotaz∙ na pohled (view v SQL), kde stejn² podv²raz musφ b²t pou₧it pro konstrukci pohledu poka₧dΘ.

VÜimn∞te si, ₧e pravidlo 5 vy₧aduje jistou znalost o relaci odpovφdajφcφ v²sledku. Tu lze odvodit z jist²ch kvantitativnφch charakteristik relace obsa₧en²ch v tzv. profilu relace.

Nejvφce v²sledk∙, jak optimalizovat, existuje pro t°φdu jednoduch²ch dotaz∙. Jsou to ty dotazy, kterΘ se dajφ vyjßd°it pomocφ spojenφ, selekcφ a projekcφ. Algebraickß optimalizace nahrazuje jistΘ shluky operacφ jin²m shlukem operacφ (lokßlnφ optimalizace). JednoduchΘ dotazy lze ale optimalizovat i globßln∞ a to ve smyslu minimalizace poΦtu spojenφ (technika tabl≤). P°esto₧e jde o °eÜenφ obecn∞ Φasov∞ nßroΦnΘ vzhledem k dΘlce dotazu, jsou v²sledky pou₧itelnΘ, proto₧e v²razy dotaz∙ majφ "rozumnou" dΘlku.

Uva₧ujme nap°. R(ABC) a dotaz R(B=5)[ B,A] * (R[ A,B] * (R(B=5)[ A,C] ))[ B,C] . Pomocφ techniky tabl≤ lze dotaz °eÜit pomocφ jednoho spojenφ jako R(B=5)[ B,A] * R(B=5)[ B,C] .

Ukß₧eme v  pokraΦovßnφch DatabßzovΘ abecedy dalÜφ triky, jak optimalizovat. Pon∞kud pesimistick² je ovÜem dneÜnφ nßzor teoretik∙, ₧e optimalizace v podstat∞ vyΦerpala svΘ mo₧nosti, tj. slo₧it∞jÜφ v²poΦet cenovΘ funkce m∙₧e p°esßhnout ·nosnou mez. Tak₧e op∞t - i optimalizaci je t°eba sv∞°it paralelismu.