db.dobo.sk

Prehľad a komentár k indexom v Postgrese.

• Všeobecný prehľad o tom, čo je index je dobrý u Pavla Stěhuleho na rootu. Operuje síce len z B-TREE indexom, ale pre obecný prehľad to stačí. Ďalšie dobré zdroje z netu, z ktorých som namudroval:
• Ross Leishman o indexoch, deep dive. Je to síce o Oraclu B-tree, ale naprosto perfektné na pochopenie princípov.
• Lukas Fittl – rozklad o GIN indexoch v Postgrese, pekne vysvetlené

Indexy všeobecne

Index je metódou, ako sa bude pristupovať k datám (k heapu). aktuálne existuje 7 typov indexov: B-tree, hash, GIN, GIST, RUM, SP-GIST, BRIN. Defaultne sa pri vytváraní indexu bytvorí B-tree, pokiaľ nie je explicitne uvedené inak. Systémový katalóg pre indexy je tabuľka pg_index. Pre štatistiky prevádzky indexov (koľkokrát a ako využitý) sú tam 3 kumulatívne štatistické views: pg_stat_[all|user|sys]_indexes. Pre indexy je zaujímavá system info funkcia  pg_get_indexdef(index_oid), ktorá ukazuje, jak bol index vytvorený (a je možné to zopakovať).

Index obecne zvyšuje rýchlosť pri SELECToch, ale znižuje pri INSERToch a UPDATEoch. Tzn. nie vždy má zmysel. Nemá zmysel pri malých tabuľkách (tak do 10 000 recordov) a pokiaľ tabuľky obsahujú veľa NULL záznamov. Taktiež indexy moc nemajú zmysel, pokiaľ je resultset veľký (napr. 40% všetkých záznamov) – vtedy je fullscan table lepší. Pokiaľ je resultset pod 1%, tak je index vždy lepší, pokiaľ je to nad 10%, tak už je to otázne. “Šedá zóna” použitia indexov je teda asi medzi 1%-10% resultsetu.

Postgres neumožňuje hinty, ako napr. Oracle, ale dá sa vynútiť nepoužitie indexu v dotaze (= sekvenčný sken tabuľky): SET enable_indexscan = OFF;

Indexy a NULL value

Pokial stĺpec obsahuje viac NULL values, má sa to indexovať, alebo nie? Od verzie 9 postgres ponúka možnosť parciálneho indexu (len pre vybraný scope hodnot) pomocou predikátu. Ideálne pre hodnoty s nízkou selektivitou (veľké množstvo opekujúcich sa hodnot), takže pre nuly priam ideálne. Ovšem človek musí potom počítať s tým, že nevyslektuje recordy s NULL value…. Dobrá debata k tomu tu.

Reindex

Každý index sa intenzívnym využívaním (deletmi) časom nabloatuje – na datovej page je množstvo “dier” po deletnutých záznamoch z indexu. Množstvo bloatu na indexoch sa dá dohľadať cez túto rutinu. Vysporiadať sa s tým je možné 2 spůsobni: 1. dropnúť a vytvoriť nový index 2. reindexáciou indexu (jeho prebudovaním). Pokiaľ je DB offline, je to jedno, ale v prípade, že sa opravuje index za produkčného behu, je v tom rozdiel:

1. DROP INDEX vynúti ACCESS EXCLUSIVE na tabuľke, ktorej index patrí – až do zmazania indexu. Následný CREATE INDEX vynúti zamknutie tabuľky pre inserty.
2. REINDEX INDEX vynúti ACCESS EXCLUSIVE na indexe, tabuľka sa zavrie pre inserty, ale dá sa z nej čítať (reads). Každopádne len sekvenčne, pretože index nie je k dispozícii. Jedinou rozumnou cestou je REINDEX CONCURRENTLY (alebo pg_repack).

Priebeh reindexu je možné sledovať “online” – pomocou kumulatívneho štatistického view pg_stat_progress_create_index.

Poškodené indexy

Shit sometimes happens a index môže byť koruptnutý, napr. nedobehol celý reindex a pod. V tom prípade je nutné reindexovať, alebo ceý index dropnúť a vytvoriť nanovo. Ako však zistiť, že index je bad? V zásade 2 možnosti:

• pomocou atribútov v pg_index: SELECT indexrelid::regclass AS index_name, indrelid::regclass AS table_name, indisvalid FROM pg_index WHERE NOT indisvalid;
• pomocou extenzie amcheck a jednou z jej funkcií: SELECT indexrelid::regclass, bt_index_check(indexrelid) FROM pg_index WHERE indisvalid;

B-tree

• základný typ indexu, prakticky u všetkých druhov DB. Proste register v knihe.
• nie je to binary search a “B” neznamená balanced, aj keď B-tree je vždy balanced. :)
• root – branches – leaves; Len leaves obsahujú odkazy na heap/records.
• v skutočnosti sú pomerne plytké, tak 4-5 úrovní.
• keď je index plný a je nutné pridať ďalší level, tak sa pridá “nad rootom” – jasné, ak by sa pridával na leves, tak by prestal byť balancovaný
• výhodný pre porvnávacie, intervalové a radiace operácie (<, >, MIN, MAX…) a pod.
• O(log N) zložitosť

Hash index

• používa sa pre rovnostné operácie (=), z princípu fungovania – nad hodnotami v tabuľke vytvorí hash a v indexe porovnáva zhodu, nedokáže vyjadriť rozdiel
• z rovnakého dôvodu nemôže indexovať NULL – hash nad NULL je NULL
• nad indexovanou hodnotou vypočíta hash (výsledkom je číslo) a tieto kľúče rozstrká v indexe do bucketov na základe modula. Pri využívaní indexu (= hľadaní zhody) porovnáva aktuálny hash s hashom v príslušnom buckete. Detailný popis tu.

BRIN

• je “range” index, používa sa hlavne na časové rady, spojité data a pod…
• princíp je ten, že sa predpokladá, že séria dat je zapísaná na jednu pamaťovú stránku a preto stačí indexovať stránky
• komplet vysvetlené tu

GIN

Generalized Inverted Index sa používa na fulltext search a JSONy. Princíp je podobný ako u elasticsearch – rozsekanie súvislého textu na lexémy a indexácia výskytu slov v záznamoch. Resp. je to index, ktorý sa používa na vyhľadávanie častí (rozdeliteľného) záznamu. GIN je možné nasadiť len na column s typom tsvector a na prehľadávanie tohoto indexu je možný len Bitmap Index Scan.

RUM

GIST

Používsa sa v PostGISe. Pritorové fičúry sa nedajú indexovať priamo a preto je to indexácia obálok (bounding boxov). Originálna štúdia R-tree indexovania od Antonina Gutmana v r. 198č je tu (a full text tu).