Hlavní navigace

Zákys jménem flattening

Pavel Stěhule

Uživatelé, kteří přechází z MySQL nebo Firebirdu, občas naráží na "inteligenci" PostgreSQL. V PostgreSQL není žádný způsob, jak jej donutit použít konkrétní index, a ještě se to považuje za výhodu. I když má PostgreSQL zřejmě nejpropracovanější optimalizaci ze všech open-source databází, mohou nastat situace, kdy optimalizace selže a sql dotazy trvají příliš dlouho. Kdy se tak stane a jak to řešit?

Flattening představuje jedna z mála nástrah PostgreSQL pro začátečníky (a občas i pro pokročilé uživatele). Inspirací tohoto článku byl rozhovor s kolegou, který se marně snažil přinutit PostgreSQL použít jeden konkrétní index. V tomhle ohledu je PostgreSQL poněkud jankovité stvoření, které si nedá říci. Abychom mohli rozumět důvodům, kdy PostgreSQL přestane nacházet optimální prováděcí plán, musíme alespoň rámcově chápat proces výběru optimálního prováděcího plánu. Ve chvíli, kdy se PostgreSQL dostane do problémů, se obvykle začnou zkoušet variace problematického SQL dotazu (např. použití derivované tabulky), což je už jen krok od seznámení se s tzv. flatteningem. Workaround je více než jednoduchý, musíte si ale uvědomit, že to, co nám působí problém, je právě flattening.

Nejedná se o častý problém, kromě zmínky v diskuzích jsem zatím na něj narazil poprvé v životě. Kdo sleduje diskuze na pg_performance, tak by jej měl okamžitě identifikovat a odstranit. Kdo má ale čas sledovat všechny možné konference, že? Za normálních okolností flattening nepředstavuje problém, naopak jedná se o užitečnou techniku, které urychluje celou řadu dotazů. Je to také technika, bez které by se v PostgreSQL nedaly efektivně používat pohledy.

Když predikce selhává

Základním předpokladem korektního chování optimalizéru je relativně přesný odhad účinnosti predikátů. Ten je založen na tzv. sloupcových statistikách. Ke každému atributu tabulky se udržuje histogram, tj. četnosti jednotlivých tříd hodnot. Pokud dokážu predikát zařadit do konkrétní třídy, pak na základě počtu řádků v tabulce prostým součinem určím dopad predikátu. Sloupcové statistiky se aktualizují příkazem ANALYZE. Dokud se tento příkaz nespustí, PostgreSQL používá výchozí nastavení, kdy se předpokládá, že počet řádek je nepřímo úměrný počtu sloupců (zhruba pro 3 sloupce 1770 řádek). Dalším předpokladem je, že rozdělení hodnot daného atributu je rovnoměrné. Stejně jako v Prachettovi je asi pravděpodobnost 1:1000000, že by oba předpoklady byly splněny. Příkaz ANALYZE aktualizuje statistiky tak, že na jejich základě lze provést věrohodný odhad:

root=# create table t1(a integer, b integer);
CREATE TABLE

root=# explain analyze select * from t1;
                                           QUERY PLAN
------------------------------------------------------------------------------------------------
 Seq Scan on t1  (cost=0.00..29.40 rows=1940 width=8) (actual time=0.004..0.004 rows=0 loops=1)
 Total runtime: 0.055 ms
(2 rows)

root=# insert into t1 values(10,20);
INSERT 0 1

root=# ANALYZE t1;
ANALYZE

root=# explain analyze select * from t1;
                                         QUERY PLAN
--------------------------------------------------------------------------------------------
 Seq Scan on t1  (cost=0.00..1.01 rows=1 width=8) (actual time=0.009..0.012 rows=1 loops=1)
 Total runtime: 0.066 ms
(2 rows)

To, že se rozchází odhad počtu řádků (1940) od skutečného počtu řádků (0), signalizuje, že něco je špatně. Po příkazu ANALYZE odhad souhlasí se skutečným počtem řádků.

K celkem zajímavým statistickým údajům se dostanete, pokud si zobrazíte obsah tabulky pg_stats (po přidání deseti náhodných záznamů do t2 a provedení ANALYZE):

root=# select * from pg_stats where tablename = 't1';
 schemaname | tablename | attname | null_frac | avg_width | n_distinct | most_common_vals |    most_common_freqs    | histogram_bounds | correlation
------------+-----------+---------+-----------+-----------+------------+------------------+-------------------------+------------------+-------------
 root       | t1        | a       |         0 |         4 |       -0.4 | {13,10,30}       | {0.466667,0.2,0.133333} | {11,12,20}       |    0.803571
 root       | t1        | b       |         0 |         4 |  -0.533333 | {30,20,91}       | {0.4,0.133333,0.133333} | {40,45,66,87,90} |    0.996429
(2 rows)

Nepřímým důkazem kvalit tohoto řešení je implementace podobného algoritmu v RDBMS Firebird 2.x a MySQL5.x. Nicméně odhad na statistikách není takzvaně košer v případě:

  • použití funkce LIKE (použitelný odhad je zabudován až ve verzi 8.2)
  • použití tabulkových funkcí (SRF), kdy se předpokládá, že každá funkce vrátí 1000 řádek (opraveno v 8.3, kdy lze alespoň rámcově nastavit náročnost funkce (atribut COST) a předpokládaný počet vrácených řádek (atribut ROWS)).
root=# create or replace function foo() returns setof t1 as $$begin return; end; $$ language plpgsql rows 100;
CREATE FUNCTION
root=# explain select * from foo();
                        QUERY PLAN
-----------------------------------------------------------
 Function Scan on foo  (cost=0.00..26.00 rows=100 width=8)
(1 řádka)
  • že data mají charakter, který nelze dostatečně přesně aproximovat histogramem o n třídách, kdy n je ve výchozím nastavení rovno deseti. Představte si, že máte 1000 sběrných míst. 80 % jich je ve městech, kde minimálně jednou denně každé sběrné místo generuje alespoň jeden záznam. Zbylých 20% je umístěno v zapadákovech, výspách a koutech, kde lišky dávají dobrou noc, a těchto 20 % dohromady generuje jeden záznam za měsíc. Nemůžeme se divit, že se nám v histogramu o deseti třídách těchto 20 % rozpustí. Důsledkem jsou optimální dotazy na 80% majoritních sběrných míst a neoptimální dotazy na 20 % minoritních sběrných míst. Nejde o chybu PostgreSQL. Prostě s nastavenou rozlišovací úrovní nejsme schopní dostatečně přesně zachytit skutečnost. Můžeme doufat, že nám pomůže zvednutí počtu tříd. Technicky je počet tříd omezen na tisíc. Reálný limit je +/- tři sta tříd. Potřeba více tříd signalizuje něco shnilého ve vstupních datech a je potřeba spíše vyčistit data nebo změnit datový model.

Dejme tomu, že budu náhodně generovat dvojice z prostoru [1..800, 1..100]. To odpovídá osmi seti sběrným místům, kde mohu naměřit hodnotu 1..100. Abych simuloval nerovnoměrnost v datech, pro interval 50–100 odstraním 90 % záznamů.

root=# insert into t1 select (random()*800)::int, (random()*100)::int from generate_series(1,15000);
INSERT 0 15000
root=# delete from t1 where a between 50 and 100 and b between 10 and 100;
DELETE 827
root=# analyze t1;
ANALYZE
root=# explain analyze select * from t1 where a = 120; -- skoro zasah
                                           QUERY PLAN
-------------------------------------------------------------------------------------------------
 Seq Scan on t1  (cost=0.00..244.16 rows=18 width=8) (actual time=0.799..11.135 rows=20 loops=1)
   Filter: (a = 120)
 Total runtime: 11.250 ms
(3 rows)

root=# explain analyze select * from t1 where a = 55; -- tady je PostgreSQL mimo
                                           QUERY PLAN
------------------------------------------------------------------------------------------------
 Seq Scan on t1  (cost=0.00..244.16 rows=18 width=8) (actual time=6.151..11.145 rows=1 loops=1)
   Filter: (a = 55)
 Total runtime: 11.218 ms
(3 rows)

root=# ALTER TABLE t1 ALTER a SET statistics 1000;
ALTER TABLE
root=# analyze t1;
ANALYZE
root=# explain analyze select * from t1 where a = 120;
                                           QUERY PLAN
-------------------------------------------------------------------------------------------------
 Seq Scan on t1  (cost=0.00..244.16 rows=20 width=8) (actual time=0.771..12.432 rows=20 loops=1)
   Filter: (a = 120)
 Total runtime: 12.546 ms
(3 rows)

root=# explain analyze select * from t1 where a = 55; -- uz je to lepsi, ale jsem na maximu
                                           QUERY PLAN
------------------------------------------------------------------------------------------------
 Seq Scan on t1  (cost=0.00..244.16 rows=10 width=8) (actual time=6.081..10.537 rows=1 loops=1)
   Filter: (a = 55)
 Total runtime: 10.611 ms
(3 rows)

root=# explain analyze select * from t1 where a  between 130 and 150 and b between 0 and 10;
                                           QUERY PLAN
-------------------------------------------------------------------------------------------------
 Seq Scan on t1  (cost=0.00..350.46 rows=46 width=8) (actual time=1.106..15.428 rows=47 loops=1)
   Filter: ((a >= 130) AND (a <= 150) AND (b >= 0) AND (b <= 10))
 Total runtime: 15.605 ms
(3 rows)

-- pro oba atributy take PostgreSQL take neni v pohode (statistiky na maximu)
root=# explain analyze select * from t1 where a  between 65 and 85 and b between 0 and 10;
                                           QUERY PLAN
------------------------------------------------------------------------------------------------
 Seq Scan on t1  (cost=0.00..350.46 rows=5 width=8) (actual time=0.066..14.882 rows=51 loops=1)
   Filter: ((a >= 65) AND (a <= 85) AND (b >= 0) AND (b <= 10))
 Total runtime: 15.076 ms
(3 rows)

Jeden z důvodů, proč odhad je „mimo“, je, že se jedná o náhodně generovaná data, která jsou na sobě nezávislá. Také testovací množina není příliš velká. Skutečná data mívají, naštěstí, většinou jiný charakter.

Pokud ani změna počtu tříd nepomůže, musíme předepsat dotaz a mít připraveny dvě varianty dotazu, případně dotaz rozbít a napsat uloženou proceduru (v našem příkladě vyhýbat se predikátům obsahujícím atribut „a“, jak je to jen možné). Znamená to, že máme automaticky zvýšit statistiky na stovky tříd? Určitě ne. Stejně tak, jako dopředu nevytváříme nové indexy. Jednalo by se o tzv. předčasnou optimalizaci (použil bych spíš přívlastek zbrklou). V SQL bychom problémy měli řešit ve chvíli, kdy nastanou. Nikoliv dříve, nikoliv později. K tomu máme k dispozici logování pomalých dotazů. Kontrola tohoto logu patří k dennímu chlebu každého správného dba.

Nyní by mělo být jasné, kdy může selhat optimalizace provádění dotazů. A jak jsem zmínil, flattening nám může překážet jedině v těchto případech. Logicky, když všechno funguje, jak má, tak se nezajímáme o detaily. Skutečně se jedná o netypické případy. To, že optimalizace výjimečně „hapruje“, je známo. Bohužel, co v tuto chvíli není známé, je dostatečně rychlé robustní řešení, které by se dokázalo řešit bez výjimek odhad efektu predikátu.

Flattening

Co je flattening? Flattening je metoda, kdy se snažíme SQL dotaz obsahující derivovanou tabulku transformovat do ekvivalentního SQL dotazu bez derivované tabulky. Uvedu příklad:

select * from (select * from data where a = 10) s where s.b = 20; --> select * from data where a = 10 and b = 20;

důkaz:

root=# explain select * from (select * from t1 where a = 20) s where s.b =  20;
                     QUERY PLAN
----------------------------------------------------
 Seq Scan on t1  (cost=0.00..279.60 rows=1 width=8)
   Filter: ((a = 20) AND (b = 20))
(2 rows)

root=# explain select * from t1 where a = 20 and b = 20;
                     QUERY PLAN
----------------------------------------------------
 Seq Scan on t1  (cost=0.00..279.60 rows=1 width=8)
   Filter: ((a = 20) AND (b = 20))
(2 rows)

V čem je problém? V chápání závorek. V klasických programovacích jazycích závorky mění pořadí vyhodnocování. Takže čekáme, že napřed se vyhodnotí predikát a = 10 (a adekvátně se použije index nad a), a poté se nad výsledkem vyhodnotí predikát b = 20. Tak to ale není. V tomto případě závorky slouží pouze ke korektnímu syntaktickému zápisu a s pořadím vyhodnocování nemají nic společného. Pokud PostgreSQL preferuje index b, můžeme dotaz vnořovat tisíckrát a PostgreSQL stejně bude preferovat index b. Díky flatteningu se vnořený dotaz vynoří a Pg si mezi indexy nad a a b opět vybere b. Jednoduše PostgreSQL index nevnutíme. Ještě o krok zpět. Proč vnořený dotaz? Často vnořený dotaz použijeme v marné naději, že PostgreSQL vnutíme korektní index ve chvíli, kdy PostgreSQL, díky chybným statistikám, ztratil kontrolu nad situací. Všimněte si, jednoduše to nepůjde.

Ještě k příkladu. Kdo by psal tak okatě náročný dotaz? Nikdo. A přece ho použivá každý, kdo pracuje s pohledy. Dotaz z příkladu odpovídá dotazu

select * from pohled where b = 20
create view pohled as select * from data where a = 10.

Proto hraje flattening v PostgreSQL tak významnou roli. Díky němu používání pohledů nepřináší žádnou režii navíc vůči přímému dotazu do tabulky.

Jak tedy přinutit PostgreSQL respektovat závorky? Flattening nelze provést, pokud vnořený dotaz obsahuje klauzuli LIMIT nebo OFFSET. Obojí je pro PostgreSQL Limit. LIMIT je poněkud nepraktický a mění sémantiku dotazu. Zato OFFSET 0 je taková nic nedělající vsuvka, a proto se také používá. V jednu chvíli se uvažovalo o zavedení tzv. hintu, což se nakonec neprosadilo, jelikož hint pro zákaz flattingu by znamenal zadní vrátka pro zavedení hintů pro indexy a ty jsou v PostgreSQL tabu. Navíc OFFSET 0 je veřejné tajemství. Pokud se alespoň trochu dostanete mezi komunitu, nemůže vám uniknout. Tak proč vymýšlet a implementovat novou nestandardní syntaxi? Pokud by vás tato tématika zajímala, dopuručuji hledat v pg_performance klíčová slova flattening a „OFFSET 0“. Mimochodem, to je také důvod, proč by pohled neměl obsahovat klauzuli LIMIT.

root=# explain select * from (select * from t1 where a = 20 offset 0) s where s.b =  20;
                           QUERY PLAN
-----------------------------------------------------------------
 Subquery Scan s  (cost=0.00..244.42 rows=1 width=8)
   Filter: (b = 20)
   ->  Limit  (cost=0.00..244.16 rows=21 width=8)
         ->  Seq Scan on t1  (cost=0.00..244.16 rows=21 width=8)
               Filter: (a = 20)
(5 rows)

Přemýšlím, jestli existuje ještě další podobná záludnost a nic mne nenapadá. PostgreSQL prostě funguje a triky nejsou v módě. Zvlášť když zavánějí alchymií. Ale vzpomněl jsem si. V 7.4 pokud chceme, aby PostgreSQL používal indexy, musíme explicitně přetypovávat číselné typy. Na druhou stranu 7.4 je sice spolehlivá databáze, které si své odsloužila, a právě že si své odsloužila (pozn. 7.4 byla patrně první reálně použitelná verze). 8.x verze jsou o generaci dál, což umožňuje programátorům se soustředit víc na svou práci a odbourává to, co označuji jako alchymii.

Když jsem po pár dnech potkal kamaráda a ptal se ho, jak to dopadlo, jestli použil offset nula, odpověděl mi, že to zkoušel, ale deset procent dotazů zrychlil třítisíckrát a zbylých devadesát procent zpomalil o tři sta procent. A tedy, prozatím, si to rozmyslel. Nicméně alespoň nemá pocit, že si z něj PostgreSQL tropí šašky. Občas neexistuje jednoduché řešení.

Anketa

Máte problémy s optimalizátorem PostgreSQL?

Našli jste v článku chybu?

10. 3. 2007 22:28

bbubla (neregistrovaný)
"Nerikam to ustepacne, bohuzel jsme si ve firme take mysleli, ze aspon ty reporty si udelaji ti uzivatele sami, kdyz uz je tu ten standard. Chyby lavky, sef nakupu nas hnal okamzite az k vedeni, ze on a ani jeho podrizeni se nebudou nic ucit, oni jsou tu od nakupu. Znam samozrejme radu instituci (vesmes statnich), kde maji zamestnanci cas na hrani, ale u nasich zakazniku (vyrobni firmy) to nemohu pozorovat."

Jsem uživtelem jedné databáze, kterou tvoří jeden čaroděj již sedmým rokem. J…

10. 3. 2007 22:28

bbubla (neregistrovaný)
"Nerikam to ustepacne, bohuzel jsme si ve firme take mysleli, ze aspon ty reporty si udelaji ti uzivatele sami, kdyz uz je tu ten standard. Chyby lavky, sef nakupu nas hnal okamzite az k vedeni, ze on a ani jeho podrizeni se nebudou nic ucit, oni jsou tu od nakupu. Znam samozrejme radu instituci (vesmes statnich), kde maji zamestnanci cas na hrani, ale u nasich zakazniku (vyrobni firmy) to nemohu pozorovat."

Jsem uživtelem jedné databáze, kterou tvoří jeden čaroděj již sedmým rokem. J…

Vitalia.cz: Vychytané vály a válečky na vánoční cukroví

Vychytané vály a válečky na vánoční cukroví

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

DigiZone.cz: ČRo rozšiřuje DAB do Berouna

ČRo rozšiřuje DAB do Berouna

120na80.cz: 5 nejčastějších mýtů o kondomech

5 nejčastějších mýtů o kondomech

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Vitalia.cz: Taky věříte na pravidlo 5 sekund?

Taky věříte na pravidlo 5 sekund?

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Podnikatel.cz: Udávání a účtenková loterie, hloupá komedie

Udávání a účtenková loterie, hloupá komedie

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Vitalia.cz: Když přijdete o oko, přijdete na rok o řidičák

Když přijdete o oko, přijdete na rok o řidičák

Měšec.cz: Stavební spoření: alternativa i pro seniory

Stavební spoření: alternativa i pro seniory