Optimalizace dotazu je 1) funkce DBMS , která hledá optimální plán provádění dotazu ze všech možných pro daný dotaz, 2) proces změny struktury dotazu a/nebo databáze za účelem snížení využití výpočetních zdrojů při provádění dotazu. dotaz. Stejný výsledek může DBMS získat různými způsoby ( plány provádění dotazů ), které se mohou výrazně lišit jak z hlediska nákladů na zdroje, tak z hlediska doby provádění. Problém optimalizace je najít optimální cestu.
V relačním DBMS je optimální plán provádění dotazů taková sekvence aplikace operátorů relační algebry na počáteční a mezilehlé vztahy, kterou lze pro konkrétní aktuální stav databáze (její strukturu a obsah) provést s minimálním využitím výpočetních zdrojů. .
V současné době jsou známy dvě strategie pro nalezení optimálního plánu:
Některé DBMS také umožňují programátorovi zasahovat do hledání optimálního plánu v různé míře, od minimálního ovlivnění až po úplné a jasné určení, který plán dotazů použít.
Plány provádění dotazů jsou porovnávány na základě různých faktorů (implementace se liší podle DBMS), včetně:
Obecně se spojení provádí ve vnořených smyčkách . Tento algoritmus však může být méně účinný než specializované algoritmy. Pokud například tabulky, které mají být sloučeny, mají indexy na spojovaných polích nebo jedna nebo obě tabulky jsou dostatečně malé na to, aby mohly být setříděny v paměti, je zkoumána možnost provedení sloučení .
Jak již bylo uvedeno, podstatou optimalizace je nalezení minima nákladové funkce z permutačních tabulek. Bez ohledu na strategii musí být optimalizátor schopen analyzovat náklady na libovolnou permutaci, zatímco samotné permutace pro analýzu poskytuje jiný algoritmus. Soubor zkoumaných permutací se může lišit od celého permutačního prostoru. Na základě toho lze zobecněný algoritmus optimalizátoru napsat takto:
Teoreticky při použití strategie hrubou silou optimalizátor dotazů prozkoumá celý permutační prostor všech původních načítacích tabulek a porovná odhady kombinovaných nákladů na spojení pro každou permutaci. V praxi, když byl System R navržen, bylo navrženo omezit prostor vyšetřování pouze na levá spojení, takže když se provede dotaz, jedna z tabulek bude vždy reprezentována obrazem na disku. Zkoumání jiných než levých spojení má smysl, pokud jsou tabulky ve spojeních umístěny na více než jednom uzlu.
Pro každou tabulku v každé z permutací je statisticky vyhodnocena možnost použití indexů. Permutace s minimálním skóre je konečný plán provádění dotazu.
Algoritmy pro generování všech permutací jsou diskutovány ve čtvrtém dílu sekce 2 "Umění počítačového programování" od Donalda Knutha (viz bibliografie).
Odhad nákladů na plán na základě aktuální permutace tabulek /* * Odpovídající provedení odhadu ceny dotazu * aktuální pořadí tabulek v dotazu * Funkce vrátí hodnotu < 0, pokud se rozhodne ne * provést všechny kroky odhadu, protože náklady na * tuto objednávku >> the_best_cost (pokud jsou_nejlepší_ceny > 0) * V jiném případě vrátí odhadované náklady (>=0) */ statický plovák est_cost_order ( i4_t * res_row_num ) { MASKA Depend = _AllTblMsk ; i4_t tbl_num , prdc_num , i , real_num , ColNum ; float cost_all = 0,0 , row_num = 1,0 ; float ind_best_sel , sel ; SP_Ind_Info * cur_ind_info ; /* odhad nákladů na skenování tabulek */ for ( tbl_num = 0 ; tbl_num < počet_tabulek ; tbl_num ++ ) { ind_best_sel = 1,0 ; skutečné_číslo = pořadí_kurzu [ číslo_tbl ]; TblAllBits [ tbl_num ] = Depend = BitOR ( Depend , TblBits [ real_num ]); /* init pole pro informace o culums */ for ( i = 0 ; i < tab_col_num [ skutečné_číslo ]; i ++ ) col_stat [ i ]. Sel = 1,0 ; /* kontrola informací o SP pro aktuální tabulku */ for ( prdc_num = 0 ; prdc_num < počet_SP ; prdc_num ++ ) if ( ! ( SPs [ prdc_num ]. příznak ) /* tento predikát ještě nebyl použit */ && CAN_BE_USED ( SP [ prdc_num ]. Závisí , závisí ) /* predikát lze nyní použít */ ) { SP [ prdc_num ]. vlajka ++ ; cur_ind_info = ( SPs_indexes [ skutečné_číslo ]) + prdc_num ; if ( cur_ind_info -> Sel ) { /* tento predikát je SP pro aktuální tabulku */ ColNum = cur_ind_info -> ColNum ; if ( col_stat [ ColNum ]. Sel > cur_ind_info -> Sel ) { col_stat [ ColNum ]. Sel = cur_ind_info -> Sel ; if ( cur_ind_info -> IndExists /* existuje index pro sloupec tohoto SP */ && col_stat [ ColNum ]. Sel < ind_best_sel ) ind_best_sel = col_stat [ ColNum ]. Sel ; } } } /* nalezení společné selektivity všech jednoduchých predikátů pro aktuální tabulku */ for ( i = 0 , sel = 1,0 ; i < tab_col_num [ skutečné_číslo ]; i ++ ) sel *= col_stat [ i ]. Sel ; /* přidání výchozí selektivity pro zbytek predikátů */ for ( prdc_num = počet_SP ; prdc_num < počet_disjunktů ; prdc_num ++ ) if ( ! ( SPs [ prdc_num ]. příznak ) /* tento predikát ještě nebyl použit */ && CAN_BE_USED ( SPs [ prdc_num ]. Depend , Depend ) /* predikát lze nyní použít */ ) { SP [ prdc_num ]. vlajka ++ ; sel *= DEFAULT_SEL ; } počet_naskenovaných_řádků [ tbl_num ] = počet_řádků [ skutečné_číslo ] * ind_best_sel * číslo_řádku ; /* number_of_scanned_rows [i] - odhadovaný počet řádků přečtených z i-té tabulky */ cena_vše += počet_naskenovaných_řádků [ číslo_tbl ] + OPEN_SCAN_COST * počet_řádku ; číslo_řádku *= počet_řádků [ skutečné_číslo ] * sel ; } /* pro tbl_num: zpracování tabulek */ for ( prdc_num = 0 ; prdc_num < počet_disjunktů ; prdc_num ++ ) SP [ prdc_num ]. příznak = 0 ; /* přičtení ceny všech poddotazů */ for ( prdc_num = 0 ; prdc_num < počet_disjunktů ; prdc_num ++ ) { for ( tbl_num = 0 ; tbl_num < počet_tabulek ; tbl_num ++ ) if ( CAN_BE_USED ( SPs [ prdc_num ]. SQ_deps , TblAllBits [ tbl_num ])) zlomit ; tvrdit ( tbl_num < počet_tabulek ); /* tbl_num - číslo poslední (v pořadí) tabulky * *, na kterou se odkazuje v predikátu */ cost_all += SPs [ prdc_num ]. SQ_cost * počet_naskenovaných_řádků [ tbl_num ]; } * res_row_num = ( row_num < 1,0 ) ? 1 : (( číslo_řádku < FLT_MAX_LNG ) ? ( i4_t ) číslo_řádku : MAX_LNG ); vrátit náklady_vše ; } /* est_cost_order */Zde je cur_tbl_order vektor známý z předchozího příkladu obsahující aktuální pořadí tabulky.
S rostoucím počtem tabulek v dotazu roste počet možných permutací jako n! , proto se proporcionálně prodlužuje i doba vyhodnocení u každého z nich . Díky tomu je problematické optimalizovat dotazy založené na velkém počtu tabulek. Při hledání řešení tohoto problému v roce 1991 Kristin Bennett, Michael Ferris a Yannis Ioannidis navrhli použití genetického algoritmu pro optimalizaci dotazů, který poskytuje suboptimální řešení v lineárním čase.
Při použití genetického algoritmu se zkoumá pouze část permutačního prostoru. Tabulky účastnící se dotazu jsou zakódovány do chromozomů. Jsou zmutované a zkřížené. Při každé iteraci se provádí obnova chromozomů, aby se získala smysluplná permutace tabulek a výběr chromozomů, který poskytuje minimální odhady nákladů. V důsledku selekce zůstanou pouze ty chromozomy, které dávají nižší hodnotu nákladové funkce ve srovnání s předchozí iterací. Probíhá tedy výzkum a hledání lokálních minim nákladové funkce. Předpokládá se, že globální minimum neposkytuje významné výhody oproti nejlepšímu lokálnímu minimu. Algoritmus se opakuje po několik iterací, po kterých se vybere nejefektivnější řešení.
Při vyhodnocování plánů provádění dotazů se zkoumají alternativní způsoby provádění relačních spojení. Metody vytváření spojení se liší účinností, ale mají omezení v aplikaci.
V případě vnořených smyček vnější smyčka načte všechny řádky z vnější tabulky a zavolá vnitřní smyčku pro každý nalezený řádek. Vnitřní smyčka vyhledává řádky ve vnitřní tabulce na základě podmínek spojení a dat vnější smyčky. Smyčky mohou být vnořeny libovolně kolikrát. V tomto případě se vnitřní smyčka stane vnější smyčkou pro další smyčku a tak dále.
Při vyhodnocování různých pořadí provádění vnořených smyček, aby se minimalizovala režie volání vnitřní smyčky, je vhodnější, aby vnější smyčka skenovala méně řádků než vnitřní smyčka.
Pro výběr indexu pro každou tabulku se nejprve najdou všechny potenciální indexy, které lze použít ve zkoumaném dotazu. Protože jsou klíče v indexu uspořádány, efektivní načítání z něj lze provádět pouze v lexikografickém pořadí . V tomto ohledu je výběr indexu založen na přítomnosti omezení pro sloupce zahrnuté v indexu, počínaje prvním.
Pro každý sloupec zahrnutý v indexu, počínaje prvním, se prohledají omezení z celé sady omezení pro danou tabulku, včetně podmínek spojení. Pokud nelze najít žádná omezení pro první sloupec indexu, pak se index nepoužije (jinak by se musel skenovat celý index). Pokud nelze najít žádná omezení pro další sloupec, hledání skončí a index je přijat.
Při vyhodnocování prováděcích plánů se zkoumají alternativní sady indexů, které lze použít pro vzorkování. V případě vnořených smyček nemůže nejvzdálenější smyčka používat žádný index, který je omezen alespoň jednou podmínkou spojení, protože žádná z podmínek spojení není při spuštění smyčky plně definována. Vnitřní smyčka nemůže používat žádný index s omezeními, která nejsou kompatibilní s podmínkami spojení.
Zbývající indexy jsou seřazeny podle počtu načtených řádků a délky klíče. Je zřejmé, že počet načtených řádků závisí na limitech. Čím menší je počet načtených řádků a čím kratší je délka klíče, tím vyšší je pořadí.
Pro vzorkování se používá index s nejvyšším hodnocením.
U některých agregačních dotazů lze skenovat celý index. Zejména:
Pokud požadované pořadí načtení odpovídá pořadí jednoho nebo více indexů , vyhodnotí se, zda lze jeden z těchto indexů naskenovat celý.
Pokud index obsahuje všechny sloupce potřebné k vytvoření výsledku , neproběhne žádná kontrola tabulky. Pokud optimalizátor tento faktor využívá, pak je možné u specializovaných dotazů urychlit načítání z tabulky zahrnutím redundantních sloupců do indexu, které budou načteny přímo při vyhledávání podle klíče. Tento způsob urychlení dotazů by měl být používán opatrně.
Pokud mají spojované tabulky indexy na porovnávaných polích nebo pokud jsou jedna nebo obě tabulky dostatečně malé na to, aby mohly být seřazeny v paměti, lze spojení provést pomocí sloučení. Oba seřazené datové sady jsou naskenovány a vyhledány stejné hodnoty. Kvůli třídění je sloučení efektivnější než vnořené smyčky u velkých objemů dat, ale plán provádění nemůže začít sloučením.
Odhad počtu řádků načtených z tabulky se používá k rozhodnutí, zda provést úplné prohledávání tabulky namísto přístupu k indexu. Rozhodnutí je učiněno na základě toho, že každá listová stránka indexu čtená z disku znamená 1 nebo více umístění a 1 nebo více čtení stránky tabulky. Vzhledem k tomu, že index obsahuje také stránky bez listů, extrahování více než 0,1–1 % řádků z tabulky je obvykle efektivnější pro provedení úplného prohledání tabulky.
Přesnější hodnocení bude získáno na základě následujících ukazatelů:
DBMS se snaží organizovat ukládání datových bloků jedné tabulky sekvenčně, aby se eliminovala režie polohování při úplném skenování ( Oracle DBMS používá předběžné přidělení místa na disku pro datové soubory). Efektivitu úplného skenování zvyšuje také čtení napřed . S předčítáním DBMS současně vydává příkazy pro čtení několika blokům do externí paměti. Skenování se spustí, když je přečten některý z bloků. Současně pokračuje čtení zbývajících bloků. Efektivity je dosaženo díky paralelismu čtení a skenování.
Pokud DBMS běží na více procesorech, lze řazení provádět paralelně, aby se zkrátila doba odezvy. Předpokladem k tomu je možnost umístit všechna načtená data do paměti RAM. Pro provedení třídění jsou extrahovaná data rozdělena na fragmenty, jejichž počet se rovná počtu procesorů. Každý z procesorů provádí třídění na jednom z fragmentů nezávisle na ostatních. V posledním kroku se setříděné fragmenty sloučí nebo se sloučení spojí s vydáním dat klientovi DBMS.
Pokud DBMS běží na několika uzlech, pak třídění provádí paralelně každý z uzlů zapojených do provádění dotazu. Poté každý z uzlů odešle svůj fragment do uzlu odpovědného za vydávání dat klientovi, kde se přijaté fragmenty sloučí.
RDBMS používá statistiky k odhadu potenciálního počtu řádků, které mají být načteny z tabulky . Statistika má podobu histogramů pro každý sloupec tabulky, kde je stupnice hodnot umístěna vodorovně a výška sloupce udává odhad počtu řádků v procentech z celkového počtu řádků.
Pokud jsou tedy z tabulky načteny řádky s hodnotou sloupce C s omezením [V1, V2], pak můžeme odhadnout počet řádků, které spadají do tohoto intervalu. Algoritmus pro odhad počtu řádků, které mají být extrahovány, je následující:
DBMS zpravidla nezná a nemůže znát přesný počet řádků v tabulce (i u dotazu SELECT COUNT(*) FROM TABLE se skenuje primární index), protože databáze může ukládat několik obrázků stejné tabulky. s různým počtem řádků současně. . K odhadu počtu řádků se používají následující údaje:
Statistiky lze také ukládat na akruální bázi. V tomto případě každý interval obsahuje celkové skóre všech předchozích intervalů plus své vlastní skóre. Pro získání odhadu počtu řádků pro omezení [V1, V2] stačí od odhadu intervalu, do kterého spadá V2, odečíst odhad intervalu, do kterého spadá V1.
Sběr statistik pro vykreslování histogramů se provádí buď speciálními příkazy DBMS nebo procesy na pozadí DBMS . Zároveň s ohledem na skutečnost, že databáze může obsahovat značné množství dat, je vytvořen menší vzorek z celé obecné populace řádků. Posouzení reprezentativnosti (spolehlivosti) vzorku lze provést např. podle kritéria Kolmogorovovy shody .
Pokud se data v tabulce během krátké doby výrazně změní, statistika přestane být relevantní a optimalizátor provede nesprávná rozhodnutí o úplném prohledání tabulky. Chování databáze by mělo být naplánováno tak, aby statistiky byly aktuální, nebo aby se nepoužívala optimalizace na základě statistik.
| Databáze | |
|---|---|
| Koncepty |
|
| Objekty |
|
| Klíče | |
| SQL | |
| Komponenty | |