http://postgres.cz/index.php?title=Pou%C5%BE%C3%ADv%C3%A1n%C3%AD_index%C5%AF_v_PostgreSQL_-_kr%C3%A1tce_a_pro_za%C4%8D%C3%A1te%C4%8Dn%C3%ADky&feed=atom&action=historyPoužívání indexů v PostgreSQL - krátce a pro začátečníky - Historie editací2024-03-28T19:57:04ZHistorie editací této stránkyMediaWiki 1.36.0http://postgres.cz/index.php?title=Pou%C5%BE%C3%ADv%C3%A1n%C3%AD_index%C5%AF_v_PostgreSQL_-_kr%C3%A1tce_a_pro_za%C4%8D%C3%A1te%C4%8Dn%C3%ADky&diff=534&oldid=previmported>Pavel v 4. 9. 2012, 12:432012-09-04T12:43:56Z<p></p>
<p><b>Nová stránka</b></p><div>[[Category:Články]]<br />
''Autor: Pavel Stěhule, 2012''<br />
<br />
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.<br />
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 <br />
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ý<br />
(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ů<br />
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<br />
jejich implementace je "rodinné stříbro" každé databáze.<br />
<br />
==Úvod==<br />
<br />
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ů <br />
- 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 <br />
typické OLTP použití relačních databází (pozn. uživatelé PostGISu by zajisté nesouhlasili). <br />
<br />
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)) - <br />
a k těmto soborům přistupujeme sekvenčně (čteme soubor od začátku do konce) nebo<br />
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.<br />
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<br />
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<br />
čí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<br />
č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'').<br />
Z datových stránek haldy se získávají vlastní data, která tvoří výsledek dotazu.<br />
<br />
Pokud budu mít tabulku zaměstnanci:<br />
<pre><br />
CREATE TABLE zamestnanci(id int PRIMARY KEY, jmeno text, prijmeni text)<br />
</pre><br />
a index<br />
<pre><br />
CREATE INDEX zamestnanci_prijmeni ON zamestnanci(prijmeni)<br />
</pre><br />
tak mám dvě relace - jednu typu halda (zamestnanci) a druhou typu index - (zamesntnanci_prijmeni). Halda obsahuje relaci (id, jmeno, prijmeni), Index pak<br />
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:<br />
<pre><br />
SELECT * FROM zamestnanci WHERE prijmeni = 'Novák' <br />
</pre><br />
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<br />
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 <br />
a následně část datového souboru haldy zamestananci.<br />
<pre><br />
SELECT * FROM zamestanci WHERE prijmeni = 'Stehule'<br />
</pre><br />
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<br />
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<br />
sekvenčního čtení a čtení s náhodným přístupem, a selektivita predikátu. <br />
<br />
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 <br />
se uplatní při zpracování dotazu:<br />
<pre><br />
postgres=> EXPLAIN SELECT * FROM zamestnanci WHERE prijmeni = 'Novák';<br />
QUERY PLAN <br />
───────────────────────────────────────────────────────────────────────────────────<br />
Bitmap Heap Scan on zamestnanci (cost=4.28..12.74 rows=4 width=68)<br />
Recheck Cond: (prijmeni = 'Novák'::text)<br />
-> Bitmap Index Scan on zamestnanci_prijmeni (cost=0.00..4.28 rows=4 width=0)<br />
Index Cond: (prijmeni = 'Novák'::text)<br />
(4 rows)<br />
</pre><br />
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)<br />
č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.<br />
<br />
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<br />
zvolí index scan:<br />
<pre><br />
postgres=> SET random_page_cost TO 1; -- treba pokud by bylo k dispozici Fusion-IO<br />
SET<br />
postgres=> EXPLAIN SELECT * FROM zamestnanci WHERE prijmeni = 'Novák' ORDER BY prijmeni;<br />
QUERY PLAN <br />
─────────────────────────────────────────────────────────────────────────────────────────<br />
Index Scan using zamestnanci_prijmeni on zamestnanci (cost=0.00..5.32 rows=4 width=68)<br />
Index Cond: (prijmeni = 'Novák'::text)<br />
(2 rows)<br />
</pre><br />
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<br />
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í<br />
v paměti (quick sort).<br />
<br />
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<br />
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é<br />
relace).<br />
<pre><br />
-- klasické nejjednodušší použití<br />
SELECT *<br />
FROM tabulka<br />
WHERE sloupec = konstanta<br />
<br />
-- nested loop - akcelerace korelovaného poddotazu<br />
SELECT prijmeni, <br />
(SELECT prijmeni <br />
FROM zamestnanci <br />
WHERE id = z.nadrizeny) AS nadrizeny<br />
FROM zamestnanci z<br />
<br />
-- Merge Join, index může být na primárním či cizím klíči, připadně na obou <br />
SELECT *<br />
FROM tabulka1 t1<br />
JOIN tabulka2 t2<br />
ON t1.pk = t2.pk;<br />
<br />
postgres=> EXPLAIN SELECT * FROM b1 JOIN b2 ON b1.a = b2.a;<br />
QUERY PLAN <br />
─────────────────────────────────────────────────────────────────────────────<br />
Merge Join (cost=168.75..687.00 rows=28800 width=8)<br />
Merge Cond: (b1.a = b2.a)<br />
-> Index Scan using b1_a_idx on b1 (cost=0.00..80.25 rows=2400 width=4)<br />
-> Sort (cost=168.75..174.75 rows=2400 width=4)<br />
Sort Key: b2.a<br />
-> Seq Scan on b2 (cost=0.00..34.00 rows=2400 width=4)<br />
(6 rows)<br />
</pre><br />
==Techniky používané k minimalizaci IO (minimalizace operace seek)==<br />
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<br />
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 <br />
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<br />
se datové stránky haldy neudrží v cache. <br />
<br />
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á<br />
čá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é<br />
míry kopíruje organizaci indexu. Pro takový objekt se používá termín ''klastrovaný index'' nebo ''klastrovaná tabulka''.<br />
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ý<br />
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<br />
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í<br />
haldy příkazem <i>CLUSTER</i> - což se hodí spíš pro stabilní málo měněné tabulky - např. číselníky.<br />
<br />
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. <br />
<pre><br />
CREATE NONCLUSTERED INDEX polozka_faktury(faktura_id) INCLUDE (pocet, cena); -- T-SQL syntaxe Microsoft SQL Server<br />
</pre><br />
I tady PostgreSQL dohání konkurenci - jako důsledek návrhu multigenerační architektury nebyla implementace coverage indexů možná. Teprve s implementací tzv <br />
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<br />
přístupu k indexu nazvaná <i>index only scan</i>.<br />
<br />
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<br />
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á<br />
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<br />
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.<br />
<br />
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<br />
umisťují do hashovacích tabulek. <br />
<br />
==Techniky používané k minimalizaci velikosti indexu==<br />
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<br />
minimalizovat velikost indexu. První technikou je komprimace indexu - bezztrátovou kompresí (např. prefixová komprimace ve Firebirdu) nebo ztrátovou komprimací, použitou<br />
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í <br />
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á<br />
např. i pro fulltext:<br />
<br />
Další možností je podmíněný index. Podmíněný index je index, který je udržován pouze pro podmnožinu relace. <br />
<br />
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ů<br />
je výrazně méně než všech mailů):<br />
<pre><br />
CREATE TABLE mails(id integer PRIMARY, user_id integer, read boolean, msg text);<br />
</pre><br />
Získání seznamu nepřečtených mailů by měl zrychlit index:<br />
<pre><br />
CREATE INDEX ON mails(user_id) WHERE read = false;<br />
</pre><br />
a pokud se v dotazu <b>použije stejný filtr</b>, pak by se měl použít i podmíněný index:<br />
<pre><br />
SELECT *<br />
FROM mails<br />
WHERE user_id = $1<br />
AND read = false;<br />
</pre><br />
Výhodou podmíněných indexů je jejich velikost (resp. malost :)) a s tím související možná vyšší selektivita.<br />
<br />
==Obecné zásady používání indexů==<br />
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á<br />
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í<br />
č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<br />
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 <br />
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í <br />
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], <br />
[https://launchpad.net/stado Stado] nebo moderní array databázi [http://www.scidb.org/ SciDB].<br />
<br />
Existují určitá doporučení, na které sloupce umístit index:<br />
<br />
<ul><br />
<li>Sloupce cizích klíčů - některé databáze automaticky vytváří index nad cizím klíčem (PostgreSQL nikoliv),<br />
<br />
<li>Sloupce, kde se vypočítává hodnota <i>MIN</i> nebo <i>MAX</i>,<br />
<br />
<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<br />
(čá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í,<br />
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 <br />
http://wiki.postgresql.org/wiki/Index_Maintenance.<br />
<br />
<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á<br />
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.<br />
</ul><br />
<br />
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í<br />
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,<br />
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<br />
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], <br />
která obsahuje funkci ''pgstatindex'', která může poskytnout informace o tom, zda-li je vhodné index reindexovat nebo nikoliv.<br />
<br />
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<br />
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<br />
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). <br />
<br />
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<br />
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ě).<br />
<br />
==Testování databázových aplikací==<br />
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.<br />
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.<br />
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ě<br />
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.<br />
<br />
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<br />
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<br />
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<br />
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).</div>imported>Pavel