Zobrazení zdroje stránky Používání indexů v PostgreSQL - krátce a pro začátečníky

[[Category:Články]]
''Autor: Pavel Stěhule, 2012''

V relačních databázích se běžně setkáváme s dvěma typy databázových relací (lišících se svou strukturou a chováním). Nejčastějším typem je halda (heap) a index.
V haldě jsou záznamy v nedefinovaném pořadí. V indexu (Btree) pak jsou záznamy uspořádané podle vybraného klíče a je tedy možné určitým mechanismem efektivně vybrat hledanou 
podmnožinu relace. Pro haldu takový mechanismus nemáme - výběr podmnožiny z haldy znamená zpracování kompletní haldy. Na druhou stranu, operace INSERT je pro haldu velice rychlý
(laciný) a pro indexy o poznání pomalejší (dražší), protože po každé operaci může dojít  k přeuspořádání indexu. Na implementaci indexů
stojí každá klasická relační SQL databáze - indexy ovlivňují rychlost všech SQL příkazů a to ať pozitivně (SELECT) nebo negativně (všechny ostatní příkazy). A proto
jejich implementace je "rodinné stříbro" každé databáze.

==Úvod==

V relačních databázích se nejčastěji setkáváme s [http://cs.wikipedia.org/wiki/B-strom Btree indexy] (v různých variantách). Nejedná se o jediný podporovaný typ indexů 
- v PostgreSQL se setkáme s indexy typu Hash, GiST, GiN a v jiných databázích zase s jinými typy. Nicméně Btree indexy jsou nejpoužívanější a nejdůležitější pro 
typické OLTP použití relačních databází (pozn. uživatelé PostGISu by zajisté nesouhlasili). 

Ve stávajích relačních databázích jsou relace uložené v datových souborech (jednom či více (nebo naopak relace mohou sdílet tentýž soubor)) - 
a k těmto soborům přistupujeme sekvenčně (čteme soubor od začátku do konce) nebo
náhodně (čteme vybrané části souborů). Na klasických pevných discích je sekvenční čtení a zápis několikanásobně rychlejší než čtení a zápis s náhodným přístupem.
Rozdílná rychlost čtení se bere do úvahy při optimalizaci dotazu - kdy se zvažuje, zda-li je rychlejší přečíst sekvenčně celou tabulku nebo nahodným přístupem
přečíst jen části tabulky, které vyhovují filtrovacím kritériím. Typický index většinou obsahuje dvojice - klíč a adresu záznamu v haldě - většinou
číslo datové stránky a pozice (offset) v datové stránce. Výsledkem výběru indexu je seznam datových stránek a adres haldy, které je třeba načíst - ty se
čtou náhodně (a aby se zabránilo opakovanému čtení z disku, tak se používá cache datových stránek (kterou si udržuje PostgreSQL ve sdílené paměti - ''shared_buffers'').
Z datových stránek haldy se získávají vlastní data, která tvoří výsledek dotazu.

Pokud budu mít tabulku zaměstnanci:
<pre>
CREATE TABLE zamestnanci(id int PRIMARY KEY, jmeno text, prijmeni text)
</pre>
a index
<pre>
CREATE INDEX zamestnanci_prijmeni ON zamestnanci(prijmeni)
</pre>
tak mám dvě relace - jednu typu halda (zamestnanci) a druhou typu index - (zamesntnanci_prijmeni). Halda obsahuje relaci (id, jmeno, prijmeni), Index pak
relaci (prijmeni, (datová_stránka, offset). Pokud předpokládám, že je Nováků více než 10% (někdy se udává 5-10%), tak pro dotaz:
<pre>
SELECT * FROM zamestnanci WHERE prijmeni = 'Novák' 
</pre>
se použije sekvenční čtení datového souboru relace zamestnanci a nevyhovující záznamy se zahodí. Naopak Stěhulů je určitě méně než 10%, takže má smysl použít
pomalejší čtení s náhodným přístupem (protože se s disku přečte málo dat), kdy se napřed musí načíst z disku část datového souboru indexu zamestnanci_prijmeni 
a následně část datového souboru haldy zamestananci.
<pre>
SELECT * FROM zamestanci WHERE prijmeni = 'Stehule'
</pre>
Pokud by tabulka zamestnanci byla malá (tisíce záznamů), tak se sekvenční čtení použije i pro Stěhulu - pro malé relace se nevyplatí režie spojená s načtením
indexů a náhodným přístupem k datovým stránkám haldy. Na to, zda-li optimalizátor použije nebo nepoužije index mají vliv dva základní faktory: poměr rychlosti
sekvenčního čtení a čtení s náhodným přístupem, a selektivita predikátu. 

Většina relačních databází podporuje příkaz EXPLAIN (nebo jeho analogii), který zobrazí prováděcí plán dotazu, z kterého můžeme vyčíst, která metoda přístupu k relaci 
se uplatní při zpracování dotazu:
<pre>
postgres=> EXPLAIN SELECT * FROM zamestnanci WHERE prijmeni = 'Novák';
                                    QUERY PLAN                                     
───────────────────────────────────────────────────────────────────────────────────
 Bitmap Heap Scan on zamestnanci  (cost=4.28..12.74 rows=4 width=68)
   Recheck Cond: (prijmeni = 'Novák'::text)
   ->  Bitmap Index Scan on zamestnanci_prijmeni  (cost=0.00..4.28 rows=4 width=0)
         Index Cond: (prijmeni = 'Novák'::text)
(4 rows)
</pre>
Bitmap Heap Scan je varianta Index Scanu - na základě indexu se vytvoří bitová mapa datových stránek a podle této bitmapy se sekvenčně (s přeskočením nezajímavých stránek)
čtou datové stránky haldy (do cache datových stránek) a dále ve výpočtu se pracuje jen s vybranými datovými stránkami.

Pokud si pohraji s optimalizátorem - nastavím cenu za načtení náhodné stránky na 1 (stejné jako za cena za stránku načtenou sekvenčně), tak optimalizátor
zvolí index scan:
<pre>
postgres=> SET random_page_cost TO 1; -- treba pokud by bylo k dispozici Fusion-IO
SET
postgres=> EXPLAIN SELECT * FROM zamestnanci WHERE prijmeni = 'Novák' ORDER BY prijmeni;
                                       QUERY PLAN                                        
─────────────────────────────────────────────────────────────────────────────────────────
 Index Scan using zamestnanci_prijmeni on zamestnanci  (cost=0.00..5.32 rows=4 width=68)
   Index Cond: (prijmeni = 'Novák'::text)
(2 rows)
</pre>
V tomto dotazu je pak ještě další důvod pro použití indexu - klauzule ORDER BY. Tato klauzule sama o sobě nemusí znamenat, že se použije index. Pokud máte dostatek
paměťi - (v PostgreSQL hodnota konfigurační proměnné ''work_mem''), tak je možné, že optimalizátor bude preferovat rychlejší sekvenční čtení haldy a následné řazení
v paměti (quick sort).

V případě, že existuje vhodný index, tak jej optimalizátor může využít i pro spojování tabulek, pro optimalizaci poddotazů a korelovaných poddotazů, pro optimalizaci
agregací (typickou operací je Merge join, kdy se slučují dvě seřazené seznamy záznamů, a nested loop, kdy se ke každému záznamu jedné relace dohledávají záznamy z druhé
relace).
<pre>
-- klasické nejjednodušší použití
SELECT *
   FROM tabulka
  WHERE sloupec = konstanta

-- nested loop - akcelerace korelovaného poddotazu
SELECT prijmeni, 
                (SELECT prijmeni 
                    FROM zamestnanci 
                   WHERE id = z.nadrizeny) AS nadrizeny
   FROM zamestnanci z

-- Merge Join, index může být na primárním či cizím klíči, připadně na obou  
SELECT *
   FROM tabulka1 t1
        JOIN tabulka2 t2
        ON t1.pk = t2.pk;

postgres=> EXPLAIN SELECT * FROM b1 JOIN b2 ON b1.a = b2.a;
                                 QUERY PLAN                                  
─────────────────────────────────────────────────────────────────────────────
 Merge Join  (cost=168.75..687.00 rows=28800 width=8)
   Merge Cond: (b1.a = b2.a)
   ->  Index Scan using b1_a_idx on b1  (cost=0.00..80.25 rows=2400 width=4)
   ->  Sort  (cost=168.75..174.75 rows=2400 width=4)
         Sort Key: b2.a
         ->  Seq Scan on b2  (cost=0.00..34.00 rows=2400 width=4)
(6 rows)
</pre>
==Techniky používané k minimalizaci IO (minimalizace operace seek)==
V případě sekvenčního čtení haldy se čte kompletní halda. V případě použití indexu a následného náhodného čtení haldy záleží, jak šikovně jsou hledaná data
rozhozený po datových stránkách. Při troše štěstí se může načíst několik málo stránek, kdy každá stránka obsahuje několik záznamů, která hledáme. Při troše 
smůly se musí načíst hodně stránek, kdy každá stránka bude obsahovat pouze jeden námi hledaný záznam. Tato "hustota" je důležitá - zvláště v případech, kdy
se datové stránky haldy neudrží v cache. 

Nejstarším trikem je sloučení haldy a indexu do jednoho souboru - datové stránky obsahují jak data indexu, tak data haldy - tím se z neuspořádané haldy stává
částečně uspořádaná halda - na úrovni datových stránek a pro jeden vybraný index. Variací je udržení indexy a haldy v oddělených souborech, nicméně halda do jisté
míry kopíruje organizaci indexu. Pro takový objekt se používá termín ''klastrovaný index'' nebo ''klastrovaná tabulka''.
Výsledkem je zrychlení přístupu k datům podle klastrovaného indexu a mírné zpomalení přístupu podle případných dalších indexů. U některých databází se klastrovaný
index vytváří explicitně (Oracle), u jiných implicitně (MySQL - InnoDB, MS SQL) pro primární klíč tabulky. Z principu - ke každé tabulce může být pouze jeden
klastrovaný index - protože halda může být fyzicky uspořádána pouze jedním způsobem. Zde PostgreSQL nijak zvlášť neexceluje - umožňuje pouze jednorázové seřazení
haldy příkazem <i>CLUSTER</i> - což se hodí spíš pro stabilní málo měněné tabulky - např. číselníky.

Dalším docela starým trikem jsou tzv ''coverage indexy''. Tyto indexy obsahují všechny potřebné sloupce a při jejich zpracování se vůbec do haldy nepřistupuje. 
<pre>
CREATE NONCLUSTERED INDEX polozka_faktury(faktura_id) INCLUDE (pocet, cena); -- T-SQL syntaxe Microsoft SQL Server
</pre>
I tady PostgreSQL dohání konkurenci - jako důsledek návrhu multigenerační architektury nebyla implementace coverage indexů možná. Teprve s implementací tzv 
visibility maps, které se původně implementovali pro urychlení provádění VACUUM, se něco ve stylu coverage indexů mohlo implementovat. A tím něčím je podpora
přístupu k indexu nazvaná <i>index only scan</i>.

Nejnovějším - nikoliv ale novým je použití bitmap pro přístup k haldě - ''bitmap heap scan''. V tomto případě se na základě indexu vytvoří bitová mapa zajímavých
stránek - a touto bitmapou se řídí zpracování haldy, které je pseudo sekvenční (dochází k přeskakování nezajímavých datových stránek, každá zajímavá datová
stránka se zpracuje pouze jednou). "bitmap heap scan" se může použít i v případech, kdy je možné při filtrování využít více indexů (nebo opakovaně jeden index s různými
filtry). Bitová mapa haldy je posloupnost bitů (1bit pro každou datovou stránku (v PostgreSQL 8KB) - 0 přeskočit, 1 zpracovat), kdy 1KB mapy vystačí na 8MB tabulku.

Random I/O minimalizují i další techniky, které ovšem s indexy přímo nesouvisí - např. ''Hash Join'', ''Hash Agg'' - kdy se halda čte sekvenčně a přečtená data se
umisťují do hashovacích tabulek. 

==Techniky používané k minimalizaci velikosti indexu==
Obecně platí, že čím je index menší, tím s ním databáze rychleji pracuje - rychleji se natáhne do paměti, a v paměti zabere méně místa. Jsou dvě základní techniky jak
minimalizovat velikost indexu. První technikou je komprimace indexu - bezztrátovou kompresí (např. prefixová komprimace ve Firebirdu) nebo ztrátovou komprimací, použitou
v GiST indexech v PostgreSQL. Ztrátová komprimace funguje poměrně jednoduše - do indexu se neukládají klíče - index musí vracet všechny adresy, které odpovídají 
filtru, ale také může vrátit adresy, které neodpovídají - a proto je nutné, to co dostaneme z indexu ještě jednou verifikovat vůči filtru. GiST se v Postgresu používá
např. i pro fulltext:

Další možností je podmíněný index. Podmíněný index je index, který je udržován pouze pro podmnožinu relace. 

Dejme tomu, že budeme mít databázi mailů, kde častou operací bude získání seznamu nepřečtených mailů - to je perfektní zadání pro podmíněný index (nepřečtených mailů
je výrazně méně než všech mailů):
<pre>
CREATE TABLE mails(id integer PRIMARY, user_id integer, read boolean, msg text);
</pre>
Získání seznamu nepřečtených mailů by měl zrychlit index:
<pre>
CREATE INDEX ON mails(user_id) WHERE read = false;
</pre>
a pokud se v dotazu <b>použije stejný filtr</b>, pak by se měl použít i podmíněný index:
<pre>
SELECT *
   FROM mails
  WHERE user_id = $1
    AND read = false;
</pre>
Výhodou podmíněných indexů je jejich velikost (resp. malost :)) a s tím související možná vyšší selektivita.

==Obecné zásady používání indexů==
S trochou nadsázky mohu indexy přirovnat k soli - solit se musí, ale nesmí se to přehnat. Vždy musíme mít na paměti, že index urychlí výběr z tabulky - ať už se jedná
primárně o příkaz SELECT nebo o UPDATE či DELETE. Na druhou stranu, každý další index nad tabulkou zpomalí zápis do tabulky - každý index se musí aktualizovat. Sekvenční
čtení je rychlé, ale přesto u větších tabulek může trvat dlouho - a po tu dobu vytěžuje IO. Některé dotazy se ani přes velkou
snahu nepodaří dostatečně zrychlit, aby jejich zpracování nezdržovalo zpracováních ostatních dotazů - v pracovní době by většina dotazů měla být kratší než 200ms u 
vnitropodnikových aplikací nebo 50ms u www aplikací (eshopy) - a pak spíš indexy je nutné přemýšlet o složitějších řešeních - např. preagregace počítané mimo pracovní 
dobu, používání vyhrazených serverů pro analytické dotazy (OLAP), používání speciálních databází navržených pro OLAP jako je např. [http://www.monetdb.org/ MonetDB], 
[https://launchpad.net/stado Stado] nebo moderní array databázi [http://www.scidb.org/ SciDB].

Existují určitá doporučení, na které sloupce umístit index:

<ul>
<li>Sloupce cizích klíčů - některé databáze automaticky vytváří index nad cizím klíčem (PostgreSQL nikoliv),

<li>Sloupce, kde se vypočítává hodnota <i>MIN</i> nebo <i>MAX</i>,

<li>Sloupce podle kterých se filtruje a mají vysokou selektivitu ( počet unikátních hodnot / celkový počet hodnot) - naopak index nemá smysl na sloupci s nízkou selektivitou
(částečně to lze obejít pomocí podmíněných index). Typickou začátečnickou chybou je oindexování každého sloupce bez ohledu na obsah uvnitř sloupce. Indexy, které se málo používají,
lze identifikovat dotazem do systémové tabulky ''pg_stat_user_indexes''. S identifikací zbytečných indexů mohou také pomoci dotazy uvedené na stránce 
http://wiki.postgresql.org/wiki/Index_Maintenance.

<li>Je nutné znát, jaké SQL příkazy posílá aplikace do databáze - a je nutné řešit přednostně ty nejpomalejší (indexy, přepsání) a ty nejčastější (cache) dotazy. V PostgreSQL se používá
logování pomalých dotazů [http://www.postgresql.org/docs/9.1/static/runtime-config-logging.html log_min_duration_statememnt] a analyzátor logu [http://pgfouine.projects.postgresql.org/ pgFouine]. Optimalizace dotazů stojí primárně na [http://pgfouine.projects.postgresql.org/reports/sample_default.html reportech] vygenerovaných pgFouine.
</ul>

Každý index je vhodné po čase  '''reindexovat'''. To je, bohužel, přirozená vlastnost indexů založených na B-tree stromech. Úpravami indexu (dělením datových stránek) dochází
prakticky pouze ke zvyšování hloubky stromu - čímž se zvyšuje počet iterací, které je nutné provést k vyhledání požadovaného záznamu (a také se zvyšuje počet datových stránek,
které se musí přečíst z disku). Tudíž není praktické mít připravené indexy pro strýčka Příhodu - permanentně zdržují a zastarávají (pozn. zde by byla na místě diskuze o vhodnosti
dynamických dotazů - ale to bych viděl někde u piva). V případě Postgresu je k dispozici extenze [http://www.postgresql.org/docs/9.1/static/pgstattuple.html pgstattuple], 
která obsahuje funkci ''pgstatindex'', která může poskytnout informace o tom, zda-li je vhodné index reindexovat nebo nikoliv.

V případě reportů, které se počítají 1x za měsíc - 1x za rok, může být výhodné vytvořit některé indexy těsně před spočítáním reportu a po spočtení je zahodit (pozn. rychlost
vytvoření indexu záleží na nastavení proměnné [http://www.postgresql.org/docs/9.1/static/runtime-config-resource.html ''maintenance_work_mem''], která by
měla být v ideálním případě větší než velikost největší tabulky - ale musíte se vejít do volné RAM). 

Poznámka - je vhodné rozumnět výpisu prováděcího plánu dotazu. V rámci konference [http://2012.pgconf.eu/ PostgreSQL Conference Europe 2012] bude mít
Tomáš Vondra 4 hodinový tréning věnovaný [http://www.postgresql.eu/events/sessions/pgconfeu2012/session/286-cteni-exekucnich-planu/ čtení prováděcích plánů] (v češtině).

==Testování databázových aplikací==
Samotné testování přímo s indexy nesouvisí, ale je to téma navýsost aktuální a věčné. Při vývoji databázových aplikací je nutné pracovat s několika různě velikými databázemi.
S jednou menší, na které je možné rychle ověřit sémantiku dotazu. Neměla by ovšem chybět testovací databáze, která obsahuje data v předpokládaném objemu po zhruba 5 letech provozu.
Na této databázi lze ověřit výkon SQL dotazů a odhadnout jejich náročnost. Bez této databáze se na problémy s výkonem přichází příliš pozdě - navíc věšinou v době, kdy kromě
výkonu řešíte hromadu dalších problémů spojených se startem produkce každého projektu. Navíc v té době už je dost pozdě na případné úpravy databázového schématu a větší úpravy kódu.

Nemá cenu extrémně ladit dotazy nad testovacími daty (pokud pokud používáme generovaná data). Na druhou stranu aplikace musí zvládnout odpovídat v rozumném čase i nad testovacími
daty řádově násobně vyššími než při zahájením reálného provozu. Pozor - syntetické testy zátěže u komplikovanějších systémů ani zdaleka nemusí vygenerovat zátěž podobnou reálnému
multiuživatelskému provozu - je dobré mít pro začátek velkou rezervu výkonu (se zřetelem na předpokládanou zátěž a důležitost aplikace) a neošidit testování v režimu blízkém produkčnímu
nasazení (případně pokud jeden systém nahrazuje jiný, tak je prozíravé oba systémy provozovat po určitou dobu současně - a zátěž ze starého systému tlačit na nový testovaný systém).