Cφlem optimalizace je vybrat plßn provedenφ operacφ nad relacemi relaΦnφ databßze tak, aby celkovΘ vyhodnocenφ bylo co nejefektivn∞jÜφ. Jde jednak o Φas pot°ebn² k vyhodnocenφ ka₧dΘ operace, jednak o prostor pot°ebn² pro tvorbu meziv²sledk∙. V minulΘm Φφsle DatabßzovΘ abecedy jsme uva₧ovali algebraickß pravidla umo₧≥ujφcφ ·pravy v²raz∙ relaΦnφ algebry zachovßvajφcφ ekvivalenci odpovφdajφcφch dotaz∙. SmysluplnΘ pou₧itφ algebraickΘ optimalizace ovÜem vy₧aduje existenci profil∙ relacφ, ale i dalÜφch ·daj∙, jako jsou velikosti buffer∙ apod. Jde o data, kterß tvo°φ vstup do algoritmu v²poΦtu cenovΘ funkce.

Za zmφnku stojφ, ₧e v∞tÜina optimalizaΦnφch technik byla vyvinuta ji₧ v 70. letech na S╪BD System R, p°edch∙dci DB/2. Pat°φ sem zejmΘna optimalizace zalo₧enß na relativnφ selektivit∞ relaΦnφch operßtor∙. PokroΦilejÜφ systΘmy pou₧φvajφ podrobn∞jÜφ statistickß data o relacφch. V t∞chto p°φpadech se hovo°φ o statisticky °φzenΘ optimalizaci. DalÜφ typ optimalizace je zalo₧en na indexech a velikostech relacφ. Pon∞kud magicky p∙sobφ tzv. syntakticky °φzenß optimalizace. Jde o to, ₧e u₧ivatel m∙₧e volbou syntaktickΘ varianty dotazu ovlivnit pr∙b∞h vyhodnocenφ. Zam∞°φme se zde hlavn∞ na prvnφ t°i p°φstupy.

Pro dotazy obsahujφcφ spojenφ a selekce ve tvaru konjunkce jednoduch²ch podmφnek je u₧iteΦnΘ v∞d∞t, jak jsou jednoduchΘ podmφnky omezujφcφ. Na tom bude zßviset, v jakΘm po°adφ se provedou spojenφ (selekcemi redukovan²ch) relacφ. Nap°. FILM.CENA>80 (milion∙ KΦ) je z°ejm∞ vφce omezujφcφ ne₧ nap°. FILM.CENA>8, jeÜt∞ vφce omezujφcφ je (mo₧nß) selekce FILM.REÄIS╔R = Sv∞rßk J.

Jin²mi slovy °eΦeno, je t°eba znßt velikosti selekcφ pro jednotlivΘ porovnßvacφ operßtory a atributy. Pro dan² operßtor vyjßd°φme tuto velikost v procentech z velikosti p∙vodnφ relace a budeme hovo°it o selektivit∞ F relaΦnφho operßtoru. ╚φm menÜφ je Φφslo F, tφm vφce omezujφcφ operßtor je. Selektivitu lze ekvivalentn∞ vyjad°ovat jako Φφslo z intervalu <0,1>.

Ukß₧eme zde postup zalo₧en² na relativnφ selektivit∞ operßtor∙ SQL vychßzejφcφ z p∙vodnφho nßvrhu v System R. Byl pou₧it v r∙zn²ch modifikacφch v mnoha relaΦnφch serverech.

Vychßzφ se z p°edpoklad∙, ₧e operßtor porovnßnφ = mß menÜφ selektivitu ne₧ >. V prvnφm p°φpad∞ ji lze selektivnost odhadnout nap°. na 20%, ve druhΘm nap°. na 40%. DalÜφ informaci zφskß optimalizßtor z katalogu, kde se dozvφ poΦet n-tic n_R danΘ relace. Nev²hodou tohoto postupu je ovÜem pou₧itφ Φasto hrubΘho a pouze unifikovanΘho odhadu. Nap°. ob∞ podmφnky FILM.CENA>80 a FILM.CENA>8 vedou v tomto p°φstupu ke stejnΘmu odhadu - 40%.

OznaΦme adom(A) aktußlnφ domΘnu atributu A, tj. mno₧inu jeho vÜech hodnot, kterΘ se vyskytujφ v databßzi. Pak V(A,R) bude oznaΦovat velikost adom(A). Mezi informacemi pot°ebn²mi pro optimalizßtor dßle pat°φ: hloubka B-stromu pro ka₧d² index, poΦet strßnek p_R, ve kter²ch je ulo₧ena relace R, n_R/V(A,R). Proto₧e krajnφ hodnoty mohou statisticky vyboΦovat z rozsahu b∞₧n²ch hodnot z adom(A), je ovyklΘ mφsto minimßlnφ a maximßlnφ hodnoty pou₧φt v odhadech nejbli₧Üφ vyÜÜφ, resp. ni₧Üφ z adom(A), tj. 2min, resp. 2max.

F jako definovßno jako funkce BoolskΘho v²razu (selekce). i-atribut je atribut, ke kterΘmu existuje index, k je konstanta, m je odhadnutß velikost v²sledku vyhodnocenφ poddotazu SQL (vno°en² SELECT). Odhady pro F jsou uvedeny v tabulce 1.

Tabulka 1.: Aproximace ceny selekcφ pro SQL

Mnohem p°esn∞ji pracuje statisticky °φzenß optimalizace. Pro jednotlivΘ atributy jsou v S╪BD uklßdßna rozlo₧enφ hodnot v adom(A). Pr∙kopnφkem v tomto sm∞ru byl optimalizßtor v S╪BD INGRES. StatistickΘ informace jsou o jednotliv²ch relacφch a jejich atributech uklßdßny ve form∞ histogram∙ v systΘmovΘm katalogu. Nap°. CENA takto m∙₧e b²t kategorizovßna po 1 mil KΦ a skuteΦnΘ selektivity podmφnek typu FILM.CENA > 80 a FILM.CENA > 8 mohou b²t optimalizßtorem snadno a p°esn∞ji odhadnuty. Odpovφdajφcφ histogram pro atribut CENA obsahuje informaci o tom, kolik je °ßdk∙ relace FILM s cenou filmu od 0-1 mil., 1-2 mil, atd.

Jednoduchou heuristiku pro nalezenφ po°adφ zpracovßvan²ch relacφ zapsan²ch za WHERE pou₧φval produkt INFORMIX-SE v r. 1987. Byla zalo₧ena na 5 pravidlech se°azen²ch v pou₧itφ podle priority:

1. existuje vn∞jÜφ spojenφ relacφ

Zpracovßnφ zaΦφnß dominantnφ relacφ (je-li jich vφce, nelze pravidlo pou₧φt).

2. uva₧ujφ se indexy

Existuje-li index pro atribut spojenφ jednΘ ze dvou relacφ, Φte se druhß sekvenΦn∞ a index prvnφ se pou₧ije pro p°i°azenφ spojovan²ch n-tic. Existujφ-li indexy pro ob∞ relace a index jednΘ z nich je jednoznaΦn² (nap°. jde o primßrnφ klφΦ relace), zaΦφnß se druhou relacφ. Jsou-li oba indexy nejednoznaΦnΘ (nebo oba jednoznaΦnΘ), zaΦφnß se relacφ majφcφ index s mΘn∞ atributy. neexistuje-li index pro ₧ßdnou ze spojovan²ch relacφ, spustφ se proces zvan² autoindexace, kter² vytvo°φ pro jednu pro v∞tÜφ z relacφ doΦasn² index.

3. uva₧ujφ se selekce

Mß-li jedna z relacφ definovanou selekci na n∞jak² atribut, mß p°ednost. Existujφ-li selekce na ob∞ relace a jedna je p°es indexovan² atribut, pak mß p°ednost. Existujφ-li indexy pro ob∞ selekce a jeden z nich je jednoznaΦn², pak p°φsluÜnß relace mß p°ednost- Jsou-li oba indexy jednoznaΦnΘ nebo nejednoznaΦnΘ, p°ednost mß relace s indexem s vφce atributy.

4. uva₧uje se relace s mΘn∞ n-ticemi,

5. uva₧uje se relace prvnφ za FROM.

DφlΦφm obtφ₧n²m problΘmem p°i °eÜenφ nalezenφ optimßlnφ alternativy vyhodnocenφ je stanovenφ po°adφ provßd∞nφ operacφ spojenφ. V∞tÜina S╪BD pou₧φvß jako zßkladnφ algoritmy pouze binßrnφ spojenφ, tj. je nutnΘ vφcenßsobnß spojenφ rozlo₧it v posloupnost binßrnφch. Techniky dynamickΘho programovßnφ °eÜφcφ tento problΘm v praxi ovÜem mohou vΘst v nejhorÜφm p°φpad∞ k exponencißlnφ slo₧itosti nalezenφ °eÜenφ, heuristiky zase negarantujφ optimum.

Jedna z pou₧φvan²ch heuristik nap°. generuje plßny tvaru (((R₁*R₂)*R₃)*R₄). Odpovφdajφcφ strom dotazu je zpracovßvan strategiφ vlevo a do hloubky. V²hodou tohoto postupu je mo₧no zpracovßnφ pipeline, tj. vystupujφcφ °ßdky v²sledku jednoho spojenφ mohou vstupovat do dalÜφho spojenφ. Nenφ tedy nutnΘ vyrßb∞t meziv²sledek. Takto postupuje nap°. optimalizßtor v INFORMIX-OnLine. Vybere nejlepÜφ plßn pro spojenφ dvou relacφ, potom plßn pro p°ipojenφ t°etφ relace atd. Obsahuje-li vÜak spojenφ nap°. podmφnky R₁.A=R₂.B a R₃.C=R₄.D s ni₧Üφ F, a R₂.F=R₄.G s vyÜÜφ F, je z°ejm∞ lepÜφ zvolit zp∙sob zpracovßnφ (R₁*R₂)*(R₃*R₄). Rozhodnutφ tohoto typu vÜak znamenajφ podstatnΘ zv²Üenφ slo₧itosti optimalizace.

Provßd∞cφ plßny spojenφ se strategiφ vlevo a do hloubky se liÜφ pouze v po°adφ relacφ, metod∞ p°φstupu ke ka₧dΘ relaci a metod∞ vybranΘ pro ka₧dΘ spojenφ. Pro N spojovan²ch relacφ lze vybφrat o oΦφslovat jednotlivΘ plßny v N pr∙chodech:.

• Pr∙chod 1: Najdi nejlepÜφ plßn pro p°φstup k relaci (1-relaΦnφ plßny).
• Pr∙chod 2: Najdi nejlepÜφ plßn pro p°ipojenφ dalÜφ relace (2-relaΦnφ plßny)
• Pr∙chod N: Najdi nejlepÜφ zp∙sob jak p°ipojit (N-1)-relaΦnφ plßn k N-tΘ relaci. (N-relaΦnφ plßny)

Pro ka₧dou podmno₧inu relacφ je vybrßn pouze nejlevn∞jÜφ plßn event. s nejzajφmav∞jÜφm uspo°ßdßnφm n-tic.

DalÜφ mo₧nostφ vedle p°φstupu pipline je provßd∞nφ selekcφ a projekcφ souΦasn∞ p°i tvorb∞ v²sledku spojenφ.

Strategie, kterß byla pou₧ita p°i optimalizaci dotaz∙ SQL m∙₧e b²t pro u₧ivatele zviditeln∞na pomocφ p°φkazu SET EXPLAIN ON.

Pro u₧ivatele je mnohdy u₧iteΦnΘ zjistit, jak² typ optimalizßtoru je v danΘm S╪BD pou₧it. JednoduchΘ to je v p°φpad∞, kdy jde o syntaxφ °φzen² systΘm. To se snadno zjistφ, radφ-li manußly zm∞nit po°adφ podmφnek k zlepÜenφ v²konu. To lze takΘ zjistit otestovßnφm spojenφ v SQL dotazu, kde jedna relace je omezena vφce a druhß mΘn∞, p°iΦem₧ spoleΦn² sloupec mß index. Zm∞na po°adφ podmφnek by pak m∞la mφt vliv na v²sledek.

JednotlivΘ S╪BD poskytujφ nejen r∙znΘ optimalizaΦnφ strategie, ale i mo₧nosti °φzenφ optimalizace. Nap°. n∞kde lze optimalizaci odmφtnout. Jde o to, ₧e u mnoha jednoduch²ch dotaz∙ je re₧ie na urΦenφ strategie optimalizace v∞tÜφ ne₧ Φas pot°ebn² k vyhodnocenφ standardnφm zp∙sobem.