COMPUTERWORLD
pod kapotou
Optimalizace dotazů - volba prováděcího plánu

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.

Optimalizace založená na relativní selektivitě relačních operátorů.

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 nR 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 pR, ve kterých je uložena relace R, nR/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.

selekce

F

R.i-atribut = k

 

R.i-atribut IS NULL

1/V(R.i-atribut,R)

R.i-atribut = S.i-atribut

1/max(V(R.i-atribut,R),V(S.i-atribut,S))

i-atribut > k

(2max-k)/(2max-2min)

i-atribut < k

(k - 2min)(2max-2min)

atribut IS NULL

 

atribut = výraz

1/10

atribut > výraz

 

atribut < výraz

1/3

atribut LIKE výraz

1/5

EXISTS poddotaz

1, jestliže je odhadováno, že výsledek je TRUE,

0 v opačném případě

NOT selekce

1 - F(selekce)

selekce1 AND selekce2

F(selekce1) * F(selekce2)

selekce1 OR selekce2

F(selekce1) + F(selekce2) - F(selekce1) * F(selekce2)

atribut IN seznam-hodnot

je ekvivalentní atribut=k1 OR ...OR atribut=kn

atribut q ANY

je ekvivalentní atribut q k1 OR ...OR atribut q km

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.

Optimalizace založená na indexech a velikostech relací

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 (((R1*R2)*R3)*R4). 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 R1.A=R2.B a R3.C=R4.D s nižší F, a R2.F=R4.G s vyšší F, je zřejmě lepší zvolit způsob zpracování (R1*R2)*(R3*R4). 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í.

Uživatel a optimalizace

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.



<seznam dílů seriálu>   <COMPUTERWORLD>