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.