Flattening
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á říct. 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í tak 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ů.
Celkem k 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í tak říkajíc košér 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% jsou umístěny 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 stům sběrným místům, kde mohu naměřit hodnotu 1..100. Abych simuloval nerovnoměrnost v datech, tak 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ěly ř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, tak to 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, tak 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 tematika 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í. 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 a umožňuje programátorům se soustředit víc na svoji 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ři 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í.