Optimalizace dotazu - Query optimization
Optimalizace dotazů je funkcí mnoha systémů pro správu relačních databází a dalších databází, například databází grafů . Optimalizace dotazů pokusy určit nejefektivnější způsob vykonání daného dotazu tím, že zvažuje možné plány dotazů .
K optimalizátoru dotazů obecně nelze přistupovat přímo ze strany uživatelů: jakmile jsou dotazy odeslány na databázový server a analyzovány analyzátorem, jsou poté předány optimalizátoru dotazů, kde dochází k optimalizaci. Některé databázové stroje však umožňují vést optimalizátor dotazů pomocí rad .
Dotaz je požadavek na informace z databáze. Může to být tak jednoduché jako „najít adresu osoby s číslem sociálního zabezpečení 123-45-6789“, nebo složitější jako „najít průměrný plat všech zaměstnaných ženatých mužů v Kalifornii ve věku od 30 do 39 let, kteří vydělávají méně než jejich manželé “. Výsledek dotazu je generován zpracováním řádků v databázi způsobem, který poskytne požadované informace. Vzhledem k tomu, že databázové struktury jsou ve většině případů složité, a zvláště u ne příliš jednoduchých dotazů, lze potřebná data pro dotaz shromažďovat z databáze různými způsoby, prostřednictvím různých datových struktur a v různých objednávkách. Každý jiný způsob obvykle vyžaduje jinou dobu zpracování. Časy zpracování stejného dotazu mohou mít velkou odchylku, od zlomku sekundy do hodin, v závislosti na zvolené metodě. Účelem optimalizace dotazu, což je automatizovaný proces, je najít způsob, jak zpracovat daný dotaz v minimálním čase. Velké možné časové odchylky odůvodňují provádění optimalizace dotazů, přestože nalezení přesného optimálního plánu dotazů je mezi všemi možnostmi obvykle velmi složité, časově náročné, samo o sobě může být příliš nákladné a často prakticky nemožné. Optimalizace dotazů se tedy obvykle pokouší aproximovat optimum porovnáním několika alternativ zdravého rozumu, aby v rozumném čase poskytla „dostatečně dobrý“ plán, který se obvykle příliš neliší od nejlepšího možného výsledku.
Obecné úvahy
Existuje kompromis mezi množstvím času stráveného vymýšlením nejlepšího plánu dotazů a kvalitou volby; optimalizátor nemusí sám vybrat nejlepší odpověď. Různé kvality systémů správy databází mají různé způsoby vyvažování těchto dvou. Optimalizátory dotazů na základě nákladů vyhodnotí stopu zdrojů různých plánů dotazů a použijí to jako základ pro výběr plánu. Ty každému případnému plánu dotazů přiřadí odhadovanou „cenu“ a zvolí plán s nejmenšími náklady. Náklady se používají k odhadu nákladů za běhu na vyhodnocení dotazu, pokud jde o počet požadovaných I/O operací, délku cesty procesoru , množství místa na vyrovnávací paměti disku, čas služby úložiště disku a využití propojení mezi jednotkami paralelismu a další faktory určené ze slovníku dat . Sada plánů dotazů zkoumaných je tvořen tím, že zkoumá možné přístupové cesty k (například primární přístup index, sekundární přístup index, plná skenování souborů) a různé relační tabulky spojit techniky (např merge připojit , hash , výrobek připojit ). V závislosti na složitosti dotazu SQL může být vyhledávací prostor poměrně velký . Existují dva typy optimalizace. Ty sestávají z logické optimalizace - která generuje sekvenci relační algebry k vyřešení dotazu - a fyzické optimalizace - která se používá k určení prostředků pro provádění každé operace.
Implementace
Většina optimalizátorů dotazů představuje plány dotazů jako strom „uzlů plánu“. Uzel plánu zapouzdřuje jednu operaci, která je nutná k provedení dotazu. Uzly jsou uspořádány jako strom, ve kterém průběžné výsledky proudí ze spodní části stromu nahoru. Každý uzel má nula nebo více podřízených uzlů - jedná se o uzly, jejichž výstup je přiváděn jako vstup do nadřazeného uzlu. Například spojovací uzel bude mít dva podřízené uzly, které představují dva spojovací operandy, zatímco třídicí uzel by měl jeden podřízený uzel (vstup, který má být seřazen). Listy stromu jsou uzly, které vytvářejí výsledky skenováním disku, například prováděním indexové kontroly nebo sekvenční kontroly.
Připojte se k objednávce
Výkon plánu dotazů je do značné míry určen pořadím, ve kterém jsou tabulky spojeny. Například při spojování 3 tabulek A, B, C o velikosti 10 řádků, 10 000 řádků a 1 000 000 řádků může dotazovací plán, který spojuje nejprve B a C, trvat několik řádů více času na provedení než jeden, který spojuje A a C jako první. Většina optimalizátorů dotazů určuje pořadí spojení pomocí algoritmu dynamického programování propagovaného databázovým projektem IBM System R. Tento algoritmus funguje ve dvou fázích:
- Nejprve se vypočítají všechny způsoby přístupu ke každému vztahu v dotazu. Ke každému vztahu v dotazu lze přistupovat prostřednictvím sekvenčního skenování. Existuje-li index o vztahu, který může být použit k zodpovězení predikát v dotazu, může být také použita procházení indexu. Pro každý vztah zaznamenává optimalizátor nejlevnější způsob skenování relace a také nejlevnější způsob skenování relace, která vytváří záznamy v konkrétním seřazeném pořadí.
- Optimalizátor poté zváží zkombinování každého páru vztahů, pro které existuje podmínka spojení. U každého páru bude optimalizátor zvažovat dostupné spojovací algoritmy implementované systémem DBMS . Zachová nejlevnější způsob spojování každého páru vztahů, kromě nejlevnějšího způsobu spojování každého páru vztahů, který produkuje svůj výstup podle konkrétního pořadí řazení.
- Poté se vypočítají všechny plány tří relačních dotazů spojením každého plánu dvou relací vytvořeného v předchozí fázi se zbývajícími vztahy v dotazu.
Pořadí řazení může zabránit nadbytečné operaci řazení později při zpracování dotazu. Za druhé, konkrétní pořadí řazení může urychlit následné spojení, protože seskupuje data určitým způsobem.
Plánování dotazů pro vnořené dotazy SQL
Dotaz SQL na moderní relační DBMS dělá víc než jen výběry a spojení. Zejména dotazy SQL často vnořují několik vrstev bloků SPJ (Select-Project-Join) prostřednictvím operátorů seskupení podle , existuje a neexistuje . V některých případech lze takové vnořené dotazy SQL sloučit do dotazu select-project-join, ale ne vždy. Plány dotazů pro vnořené dotazy SQL lze také vybrat pomocí stejného algoritmu dynamického programování, jaký se používá pro řazení spojení, ale to může vést k enormnímu eskalaci času optimalizace dotazů. Některé systémy pro správu databází tedy používají alternativní přístup založený na pravidlech, který používá model grafu dotazů.
Přibližná cena
Jedním z nejtěžších problémů při optimalizaci dotazů je přesný odhad nákladů na alternativní plány dotazů. Plány dotazů optimalizátorů využívají matematický model nákladů na provádění dotazů, který do značné míry závisí na odhadech mohutnosti nebo počtu n -tic, protékajících každou hranou v plánu dotazů. Odhad mohutnosti zase závisí na odhadech faktoru výběru predikátů v dotazu. Databázové systémy tradičně odhadují selektivitu prostřednictvím poměrně podrobných statistik o rozdělení hodnot v každém sloupci, jako jsou histogramy . Tato technika funguje dobře pro odhad selektivit jednotlivých predikátů. Mnoho dotazů však má konjunkce predikátů, jako například . Predikáty dotazů jsou často vysoce korelované (například implikují ) a je velmi těžké odhadnout selektivitu spojivky obecně. Špatné odhady mohutnosti a nezachycená korelace jsou jedním z hlavních důvodů, proč optimalizátoři dotazů vybírají špatné plány dotazů. To je jeden z důvodů, proč by měl správce databáze pravidelně aktualizovat statistiky databáze, zejména po velkém načítání/uvolňování dat.
select count(*) from R where R.make='Honda' and R.model='Accord'model='Accord'make='Honda'
Rozšíření
Klasická optimalizace dotazů předpokládá, že plány dotazů jsou porovnávány podle jediné metriky nákladů, obvykle doby provedení, a že náklady na každý plán dotazů lze vypočítat bez nejistoty. Oba předpoklady jsou v praxi někdy porušovány a ve výzkumné literatuře byla studována více rozšíření klasické optimalizace dotazů, která tato omezení překonávají. Tyto rozšířené varianty problémů se liší v tom, jak modelují náklady na plány jednoho dotazu, a ve smyslu jejich cíle optimalizace.
Parametrická optimalizace dotazů
Klasická optimalizace dotazů spojuje každý plán dotazů s jednou skalární hodnotou nákladů. Parametrická optimalizace dotazů předpokládá, že cena plánu dotazů závisí na parametrech, jejichž hodnoty jsou v době optimalizace neznámé. Takové parametry mohou například představovat selektivitu predikátů dotazů, které nejsou plně specifikovány v době optimalizace, ale budou poskytnuty v době provádění. Parametrická optimalizace dotazů proto spojuje každý plán dotazů s nákladovou funkcí, která mapuje z vícerozměrného prostoru parametrů do jednorozměrného nákladového prostoru.
Cílem optimalizace je obvykle vygenerovat všechny plány dotazů, které by mohly být optimální pro kteroukoli z možných kombinací hodnot parametrů. Tím se získá sada příslušných plánů dotazů. Za běhu je z této sady vybrán nejlepší plán, jakmile budou známy skutečné hodnoty parametrů. Výhodou parametrické optimalizace dotazů je, že se za běhu vyhýbá optimalizaci (což je obecně velmi nákladná operace).
Optimalizace víceúčelových dotazů
Kromě doby provádění často existují další metriky nákladů, které jsou relevantní pro porovnání plánů dotazů. V případě cloud computingu je třeba například porovnat plány dotazů nejen z hlediska toho, kolik času zabere jejich provedení, ale také z hlediska toho, kolik peněz stojí jejich provedení. Nebo v kontextu optimalizace přibližných dotazů je možné spouštět plány dotazů na náhodně vybraných vzorcích vstupních dat za účelem získání přibližných výsledků se sníženou režií provádění. V takových případech musí být alternativní plány dotazů porovnány z hlediska doby jejich provedení, ale také z hlediska přesnosti nebo spolehlivosti generovaných dat.
Víceobjektová optimalizace dotazů modeluje náklady plánu dotazů jako nákladový vektor, kde každá vektorová komponenta představuje náklady podle jiné nákladové metriky. Klasickou optimalizaci dotazů lze považovat za speciální případ víceobjektové optimalizace dotazů, kde je dimenze nákladového prostoru (tj. Počet komponent vektoru nákladů) jedna.
Různé metriky nákladů mohou být ve vzájemném konfliktu (např. Ve scénáři cloud computingu může existovat jeden plán s minimální dobou provedení a jiný plán s minimálními peněžitými poplatky za provedení). Cílem optimalizace tedy nemůže být najít plán dotazů, který minimalizuje všechny metriky nákladů, ale musí být najít plán dotazů, který realizuje nejlepší kompromis mezi různými metrikami nákladů. Jaký je nejlepší kompromis, závisí na uživatelských preferencích (např. Někteří uživatelé mohou preferovat levnější plán, zatímco jiní dávají přednost rychlejšímu plánu v cloudovém scénáři). Cílem optimalizace je tedy buď najít nejlepší plán dotazů na základě určité specifikace uživatelských preferencí poskytovaných jako vstup do optimalizátoru (např. Uživatelé mohou definovat váhy mezi různými metrikami nákladů, aby vyjádřili relativní důležitost, nebo definovat pevné hranice nákladů na určité metriky) nebo generovat aproximaci sady Pareto-optimálních plánů dotazů (tj. plány takové, že žádný jiný plán nemá lepší náklady podle všech metrik) tak, aby si uživatel mohl vybrat preferovaný kompromis nákladů z této sady plánů.
Víceúčelová parametrická optimalizace dotazů
Víceobjektová parametrická optimalizace dotazů zobecňuje parametrickou a víceobjektovou optimalizaci dotazů. Plány jsou porovnávány podle více metrik nákladů a náklady plánu mohou záviset na parametrech, jejichž hodnoty nejsou v době optimalizace známy. Náklady na plán dotazů jsou proto modelovány jako funkce z vícerozměrného prostoru parametrů do vícerozměrného nákladového prostoru. Cílem optimalizace je vygenerovat sadu plánů dotazů, které mohou být optimální pro každou možnou kombinaci hodnot parametrů a uživatelských preferencí.
Řada nástrojů zobrazuje plány provádění dotazů, které ukazují, které operace mají nejvyšší náklady na zpracování. Microsoft SMS, ApexSQLPlan, Hana a Tableau jsou některé příklady. Oprava těchto problémů nalezených v těchto plánech může oholit desítky procent času na provedení a v některých případech může snížit dvojrozměrná vyhledávání na lineární.
Jedním z primárních a nejjednodušších kontrolních seznamů optimalizace je použití operací, pro jejichž efektivní výkon je navržena většina RDMS. Viz Sargable .
