Problémy optimalizace SQL dotazů a jejich teoretická řešení
Jedním z hlavních rozdílů SQL databází vůči jakýmkoliv jiným databázím je existence planneru (případně optimalizujícího planneru). SQL dotaz definuje výsledek – nikoliv způsob, jak se k žádanému výsledku dostat. Úkolem plánovače dotazů je převod logických operací např. čtení tabulky s filtrem na fyzické operace. V tomto případě na sekvenční čtení nebo čtení indexem.
První optimalizátory byly primitivní, postavené nad jednoduchými heuristikami typu – vždy použij primární klíč, malou tabulku čti přímo, u velkých tabulek používej indexy, tabulky spojuj v pořadí podle velikosti tabulek, atd atd. Těmto tzv rule based optimalizátorům se často muselo ručně pomoci, případně programátoři věděli, jak mají psát dotazy. Rule based optimalizace nebyla moc efektivní, ale byla relativně stabilní a uchopitelná pro běžné programátory.
Další generací optimalizátorů byly tzv cost based optimalizátory, které již pracovaly se statistikami popisujícími obsah tabulek. Prakticky všechny SQL databáze dnes používají tento typ optimalizace. Ačkoliv tyto optimalizátory potřebují hinty v mnohem menší míře a poměrně dobře zvládají velký rozsah moderního SQL jazyka, tak stejně se občas narazí na větší nebo menší problémy.
Důvodem jsou zejména
- špatné odhady výsledku – zejména z důvodu korelace hodnot mezi sloupci nebo neaktuálních statistik (ve větší míře na Oracle než na Postgresu (ale i na Postgresu – např. proces autovacuum nevolá ANALYZE na dočasných tabulkách).
- chybějící statistiky – pro výrazy neexistují statistiky, odhaduje se procentem
- zatím se nepoužívají mezi tabulkové statistiky – předpokládá se, že tabulky se mezi sebou mapují rovnoměrně a úplně, což nebývá pravda.
- použití neoptimálních plánů z cache plánů (Oracle) nebo předpřipravených dotazů (Postgres). Jedná se o poměrně komplikovaný problém opakovaného používání plánů vůči různým vektorům parametrů.
V posledních 20 letech je snaha problémy s optimalizací dotazů nějakým způsobem redukovat. Na dnešních velkých databázích jsou chyby v optimalizaci brutálně vidět. Navíc u cloudových aplikací, u aplikací dodávaných jako služba, u komplexních aplikací nejde z toho či onoho důvodu snadno dělat ruční optimalizace.
a) použitím hrubé síly v případě sloupcových databází – planner u těchto databází je relativně hloupý (stabilní), ale přístup k datům (případně agregace) je velmi rychlá. Vyšší rychlosti je možné dosáhnout distribucí výpočtu. U těchto databází se často pracuje s denormalizovanými (širokými) tabulkami, tudíž není potřeba JOIN a také je výrazně menší riziko nechtěného nested loopu. Pozor – široké tabulky nevadí právě proto, že data jsou uložena po sloupcích. Jinou technikou s podobným výsledkem je použití vektorových executorů případně kompilace dotazů do strojového kódu. Executor většiny SQL databází je interpret se všemi výhody a nevýhodami: rychlý start, nenáročnost, ale pomalý běh v případě extrémního počtu iterací (milióny, případně desítky miliónů iterací). Proto je citlivý na neoptimální optimalizaci, která vede na velký počet iterací. Vektorový executor počítá operace po blocích (stovky, tisíce řádek), čímž se redukuje počet iterací. Klasický executor běží po řádku. Také překladem do strojového kódu můžeme náročnost executoru (a tím i citlivost na neoptimální plán) redukovat. Z open source databází je hezkou ukázkou vektorového zpracování dotazů databáze MonetDB.
b) implementací adaptivních algoritmů.
b.1) Pomocí adaptivních algoritmů (případně algoritmů umělé inteligence (učením)) je možné postupně zpřesňovat odhady a tím vlastně řešit jeden problémů optimalizace.
b.2) Adaptivní algoritmy je možné implementovat i do executoru – např. čtení, které po dosažení určitého počtu řádek přechází z index scanu na seq scan. Join který začína jako nested loop a umí přejít na hash join, případně merge join.
b.3) Další strategií je zahrnutí citlivosti na chybné odhady do optimalizace, a místo nejlepšího plánu, který je optimálním, pouze pokud se povede odhad, tak se hledá plán, který je dostatečně dobrý i při špatných odhadech. Resp hledá se plán, který by nebyl brutálně špatný při špatném nebo horším odhadu.
Aktuálně se hledá nejlepší (nejlevnější plán) přičemž se absolutně věří odhadům kardinalit, počtu unikátních hodnot, atd. Podstřelení odhadu může vést k extrémně pomalým dotazům z důvodu nechtěného použití nested loopu – metoda implementace JOINu – nejrychlejší, kdy je výsledek malý, naopak extrémně pomalá, kdy je výsledek velký. Rozdíly v optimalizaci vedou k rozdílům v době zpracování dotazů z ms na sec (malých dat) nebo z nižších minut na nižší hodiny u tabulek kolem deseti, dvaceti GB.
Ačkoliv výzkum se často provádí nad open source databázemi, do upstreamu se zatím, pokud vím, nedostalo téměř nic. I když to vlastně není tak úplně pravda – Postgres má nyní více sloupcové statistiky a v dohledné době možná bude mít i statistiky nad výrazy. Executor bude mít adaptivní hash agregaci. V této oblasti je dost prostoru pro zlepšení i pro kreativitu.
-
Možná jsem ze staré školy, ale stále dělám nad databází CRUD operace, kde funguje selská logika optimalizaze. Nezpracovávám nějaká našmírovaná data, ani big data (což je možná totéž), ale jen ty, která uživatel zadal.
Proto je řešením to co píšete v úvodu, za prvé, mít v pořádku statistiky. Za druhé, po nějaké době provozu aplikace, dejme tomu po půl roce provozu, je potřeba všechny SQL commandy zrevidovat. Tabulky jsou reálně zaplněné s produkčními záznamy a teď je teprve potřeba se pořádně podívat, co drhne.
Základem jsou samozřejmě správné indexy - pořád stará písnička - a nemít je naopak u sloupců s malou selektivitou. U CRUD pro nějakou běžnou evidenci jsou indexy zpravidla dostačující. Samozřejmě, přepokládám nízke kardinality, jeden zaměstnanec má jednu až dvě adresy, 0 - 3 děti (orientačně cca do čísla 10 je jedno kolik), atd...
Pro mé účely jsou tedy adaptivní algoritmy cestou, kterou nechci jít, neboť si myslím, že je dobré datům rozumět a nechci se dostat do situace, že mi algoritmus již nepomůže a já jako programátor nebudu vědět co s tím. -
Souhlasim s tebou, ale to vse lze poradne delat kdyz je dobre zanalyzovano, dobre udelana normalizace a celkove dobre navrzena databaze. Bohuzel v dnesni uspechane dobe casto DB delaji "programatori" (bohuzel casto z java prostredi), kteri o DB nemaji moc poneti a chteji ji vyuzivat jen jako uloziste ktere se ma samo i vsechno postarat. Tudiz nejake vztahy mezi entitama moc neresi a je z toho chaos. Tam musi nastoupit bud hloubkovy refaktoring (na ktery neni cas, penize a lidi) a nebo ta DB musi umet vestit z kristalove koule (viz techniky z clanku)
Take je to neco jineho u aplikaci ktere vyuzivaji metamodely, tam casto nastupuje i to ze bussiness nedokaze specifikovat pozadavky a tak v prubehu zivota aplikace se rozlozeni a vzathy mohou docela dost lisit. -
To se přeci vůbec nevylučuje. Data máte v databázi normalizovaná (např. tabulka rodičů <-reference tabulka dětí). U dětí máte evidovaný věk, pohlaví.
Když potřebujete zjistit, kteří rodiče mají aspoň jedno dítě pod osmnáct let, je situace ještě triviální.
Ve chvíli, kdy budete potřebovat složitější operace - např. najdi rodiče, kteří mají aspoň tři děti a aspoň jedno je mladší než osmnáct let, tak už se nabízí víc postupů, jak se k výsledku dostat. Např. nejdříve vyhodnotíte podmínku jednoho dítěte <18 a poté zjistíte počet dětí; nebo to vyhodnotíte v opačném pořadí. U složitějších dotazů se začne nabízet násobně více postupů (query plans) vedoucích ke stejnému výsledku.Pokud je v něčem síla moderních SQL databází, tak je to právě v tom, že Vám:
1. umějí odhalit úzká hrdla (EXPLAIN [ANALYZE]),
2. umějí odhalit rozdíl odhadů, které vycházejí ze statistik vs. realita (EXPLAIN vs. EXPLAIN ANALYZE),
3. dají nástroje (INDEX, CLUSTER, PARTITION BY, ...) kterými nastavíte správnou cestu na vykonání dotazuPřesně jak Pavel psal, a do kamene tesat: SQL dotaz definuje výsledek – nikoliv způsob, jak se k žádanému výsledku dostat. Vůbec se to však nevylučuje s tím, že máte v ruce všechny nástroje, jak data v databázi správně nastavit. Úprava dotazů není tou cestou - správný server SQL by měl i odlišné dotazy, ale dávající stejný výsledek vnitřně vykonat totožně.
-
CRUD je v podstatě OLTP a tam jednak se většinou nepracuje s extrémně velkými daty (tabulky - nad desítky GB) a nedělají se ani moc velké analýzy. Tam stávající systémy fungují docela dobře. Popisované problémy jsou primárně na OLAPu případně na větších datech s ORM.
Když máte stovky tisíc různých SQL dotazů, tak tam to ručně nejde dělat. Takových problémových (a takhle velkých) aplikací je ale minimum (a zvlášť, když bych to vztáhl na republiku).
-
Já vám neodporuji (a ani není čemu, neboť neuvádíte, jaký typ úloh řešíte, v článku se nezmiňujete).
Z mého pohledu je i velký počet tabulek v rámci jednolitého systému nesmysl, hovoří se pak o mikroslužbách, kde každá dělá dobře svoji práci nad omezeným množstvím tabulek a tím pádem ani operací není tolik, viz např. https://www.root.cz/clanky/mikrosluzby-zalozene-na-rest-api/
Tady se pohybuji já. -
O adaptivni optimizer se Oracle pokusil v verzi 12c, aby to posleze ve verzi 18c nechali by default vypnute. Ta myslenka ze by se databaze adaptivne prizpusobovala zatezi je hezka ale bohuzel to vede casto k nestabilite celeho systemu.
Takze kdyz shrnu problemy ktere verze 12c prinesla:- adaptivni plany. Ono je hezke za jizdy preklopit nested-loop na hash join. Pokud do ale vyzaduje narocnou udrzbu metadatat, tak ze to casto ani nevyplati
- adaptivni statistiky. background job se snazi analyzovat jiz spustene plany, hledat korelovane sloupce a vytvaret statistiky nad n-ticemi sloupcu. Bohuzel nikomu nedoslo, ze tech n-tic muze byt opravdu hodne a ze prochazeni temito statistikami muze zamestnat optimizer na hodne dlouho.
- adaptivni statistiky (jeste jednou ve 12.1) epicky fail, kdy Oracle nedokaze ulozit extended statistiky v dictionary cache a pokazde je musi behem parsovani nacitat znovu z disku
- cardinality feedback. ono je tezke rozhodnout jestli je lepsi exec plan ktery ma prumerny cas zpracovani 2 sec (a 10 sec v nejhorsim pripade). Zatimto jiny ma prumerny cas zpracovani 3 sec ve vsech pripadech. Muze se stat, ze data skew u jednoho uzivatele rozbije exec plan pro vsechny ostatni. Pokud se exec plan zmeni nekolikrat za hodinu tak se muze stat, ze to nakonec cele dokonverguje k nejakemu uplne pitomemu planu.
- exec plan directives. ono to zni hezky, ze by spusteni exec planu po sobe zanechalo metadata, ktera by se mohla hodit pri dalsi optimalizaci. Proc je to ale v XML formatu a co delat, kdyz je tech direktiv obludne mnozstvi?- Co se povedlo a s cim nejsou problemy je buffered nested loop, kdy si jednotlive casti exec planu nepredavaji jen jednu radku ale buffer s vetsim mnozstim dat.
