Následující text rozhodně nemá být vyčerpávajícím popisem implementace indexů v libovolném relačním databázovém systému - jedná se spíše o shrnutí základních principů společných pro indexy obecně. Jsem přesvědčen - a několik let poměrně intenzivní práce s různými relačními databázemi (MySQL, PortgreSQL, Oracle, Sybase) mi to potvrzuje - že základy práce s indexy jsou na všech databázových systémech v podstatě totožné. Jednotlivé systémy se od sebe samozřejmě liší podporovanými vlastnostmi, chováním pod zátěží, ale základní principy se nemění. Zdrojové kódy uvedené v příkladech jsou čistě ilustrační, jejich cílem není nic jiného než velmi stručně naznačit "jak to funguje" - konec konců často jsou napsány v jazyce vzdáleně připomínajícím Javu ;-)

Zajímají-li vás implementační detaily indexů v konkrétním databázovém systému, hledejte prosím v jeho dokumentaci (nicméně v případě komerčních systémů budete mít nejspíše smůlu).

Indexy jsou bezesporu jedním z nejdůležitějších témat návrhu schématu a optimalizace databáze, neboť právě ony jsou neocenitelným pomocníkem při efektivním třídění, slučování a čtení tabulek a vyhledávání  záznamů v nich. Mnoho programátorů pracujících s databázovými systémy (a nejsou to vždy jen začátečníci) bohužel indexy považuje tak trochu za magii, a nemá příliš jasnou představu o tom co to indexy vlastně jsou a jak pracují, o tom že indexů je více druhů ani nemluvě.

Než se budeme věnovat indexům samotným se ale musíme alespoň stručně podívat na to co to vlastně je tabulka v databázi.

Co je to databázová tabulka?

Definic databázové tabulky existuje spousta, ale suše řečeno je to prostě datový soubor (případně sada souborů) ve kterých jsou uloženy dva typy dat:

• metadata tj. popis struktury tabulky (názvy a typy sloupců, statistiky tabulky, apod.)
• data tj. jednotlivé řádky tabulky (n-tice dat), seřazené jedna za druhou

Toto je samozřejmě velmi zjednodušený model - v moderních systémech jsou metadata většinou oddělena od vlastních dat, uložena v samostatných souborech a dostupná přes systémové katalogy apod. - ale pro účely tohoto článku je toto naprosto dostačující.

Pro ilustraci uvažujme tabulku osob s následujcí strukturou

CREATE TABLE Osoby (
    id       INTEGER,
    jmeno    VARCHAR(64),
    prijmeni VARCHAR(64),
    vek      INTEGER,
    email    VARCHAR(64),
    vyska    INTEGER,
    vaha     INTEGER
);

Data uložená v této tabulce mohou být například

id	jmeno	prijmeni	vek	email	vyska	vaha
1	Franta	Vopička	29	franta.vopicka@example.com	185	78
17	Jaroslav	Modrý	43	jarda.modry@example.com	171	65
65	Jitka	Novotná	19	jitka.novotna@example.com	175	60
44	Radek	Volek	25	radek.volek@example.com	165	65
...	...	...	...	...	...	...

Pokud si jako oddělovač sloupců zvolíme "|" a jako oddělovač řádek "|n" potom by tato tabulka po uložení do souboru mohla vypadat například takto (pomiňme skutečnost že tabulky jsou většinou ukládány do binárních souborů a uložme data v ASCII):

1|Franta|Vopička|29|franta.vopicka@example.com|185|78\n
17|Jaroslav|Modrý|43|jarda.modry@example.com|171|65\n
65|Jitka|Novotná|19|jitka.novotna@example.com|175|60\n
44|Radek|Volek|25|radek.volek@example.com|165|65\n

To nevypadá špatně, ale problém nastává pokud je záznamů hodně a je třeba v tabulce vyhledávat něco dle hodnoty v některém ze sloupců. To totiž znamená nutnost projít celý soubor řádek po řádku (a pokud není načten v paměti tak načíst z disku, což může klidně znamenat nutnost načtení několika GB dat), a pro každý řádek zkontrolovat hodnotu v daném sloupci.

Princip indexů

Základní princip indexů je vlastně celkem jednoduchý - pomocí "vhodných datových struktur" (strom, hash tabulka, bitmapa a další) urychlit přístup k řádkům tabulky vyhovujícím dané podmínce (nejčastějí s danou hodnotou v určitém sloupci) oproti prostému sekvenčnímu čtení.

Typy indexů

Kromě tří základních typů indexů (b-tree, bitmapových a hash indexů) existuje samozřejmě mnoho specializovaných typů (GIST, GIN, fulltextové, R-Tree, apod.).

B-tree indexy

Jak již název napovídá, tento typ indexů je založen na stromech (konkrétně na B-stromech). Pokud nevíte jaké vlastnosti tato datová struktura má, zejména co se vyhledávání a třídění dat týká, podívejte se například na články o binárních stromech, binárních vyhledávacích stromech a B-stromech na české wikipedii, případně o něco rozsáhlejší záznamy o stromech jako datové struktuře, binárních stromech a B-stromech z anglické wikipedie.

Na tomto místě uveďme alespoň dvě hlavní vlastnosti stromů:

• Průměrná hloubka binárního stromu obsahujícího N hodnot je log₂N, v případě B-stromu řádu m je průměrná hloubka stromu přinejhorším log_m/2N. Díky tomu jsou stromy extrémně vhodné pro vyhledávání.
• Máme-li data uložena ve stromu, lze je velmi jednoduše setřídit, neboť strom ji vlastně v setříděném stavu udržuje. Stačí pouze provést pre-order resp. post-order zpracování stromu a dostaneme hodnoty ve vzestupném resp. sestupném pořadí.

Jak tedy stromy zapadají do tématu databázových indexů? Máme-li vytvořit index nad sloupcem tabulky, sestavíme pro každou unikátní hodnotu v daném sloupci množinu "adres" řádků s touto hodnotou, přičemž adresou je míněn například index nebo offset (počet bytů od začátku souboru) začátku daného řádku. Tyto dvojice (hodnota v indexovaném sloupci, množina řádek) uspořádáme do stromu, s tím že poloha ve stromu bude záležet čistě na hodnotě (nikoliv na množině).

V Javě by primitivní index nad textovým sloupcem mohl být definován například takto:

Map<String, List<Long>> index = new TreeMap<String, List<Long>>();

Algoritmus vytvoření indexu by mohl vypadat zhruba takto:

BufferedReader reader = new BufferedReader(new FileReader(filename));

Map<String, List<Long>> index = new TreeMap<String, List<Long>>();

long offset = 0;

while ((String line = reader.readLine()) != null) {

    // rozděl řádky na sloupce
    String[] fields = String.split("|");

    // načti hodnotu ve sloupci
    String field = fields[3];

    // zjisti zda už je v indexu
    List<Long> element = index.get(field);

    // pokud není tak záznam vytvoř a přidej ho do indexu
    if (element == null) {
        element = new ArrayList<Long>();
        index.put(field, element);
    }

    // přidej do indexu aktuální záznam
    element.add(new Long(offset));

    // aktualizuj offset (přičti délku řádky a znak konce řádky)
    offset += line.length() + 1;
}

Díky stromové struktuře jsme schopni při dotazu na řádky s touto hodnotou velmi rychle najít množinu adres odpovídajících řádků, a tedy velmi rychle přistoupit k relevantním řádkům bez nutnosti procházet tabulku (tj. soubor) řádek po řádce.

B-Tree indexy a LIKE podmínky

Za zmínku stojí také možnost využití B-Tree indexů pro vyhodnocení některých typů LIKE podmínek, často využívaných například pro implementaci jednoduchého textového vyhledávání. V případě obecných LIKE dotazů tvaru

sloupec LIKE '%řetězec%'

nejsou B-Tree indexy nic platné, nicméně v případě tzv. prefixových resp. postfixových podmínek, tj. podmínek tvaru

sloupec LIKE 'prefix%'

resp. tvaru

sloupec LIKE '%prefix'

je využít lze. V případě prefixové podmínky je využití B-Tree indexů celkem přímočaré - jedná se totiž v podstatě o podmínku tvaru

sloupec >= 'prefix' AND sloupec < 'prefiy'

(neboť první "větší" řetězec který nezačíná "prefix" je řetězec "prefiy"). Tuto podmínku tak stačí  aplikovat přímo na kliče ve větvích stromu, a současně využít jejich přirozeného uspořádání.

Aplikace na postfixové podmínky je tak trochu podvod, neboť vlastně převádí dotaz na prefixový (právě popsaný) za použití indexů nad výrazy. Namísto indexu přímo nad sloupcem je vytvořen index nad výrazem

revert(sloupec)

kde funkce "revert" vrací zadaný řetězec pozpátku. Vlastní dotaz je následně upraven na tvar

revert(sloupec) LIKE revert('%postfix')

čímž vlastně vzniká prefixový dotaz, jehož vyhodnocení za použití B-Tree indexů již bylo popsáno.

Obecně vzato jsou LIKE podmínky dosti problematické - setkal jsem se s několika aplikacemi ve kterých bylo vyhledávání implementováno právě přes LIKE podmínky, a plně vytěžovalo I/O subsystém serveru (datový tok dlouhodobě dosahoval limitů disků, tj. 80 MB/s) a brzdil tak veškeré další aplikace. Situace se zlepšila až po nasazení fulltextového vyhledávání umožňujícího využití indexů. Proto si velmi rozmyslete zda není rozumnější pro vyhledávání v textech nasadit například Lucene.

Kdy B-Tree indexy nefungují dobře

Kromě obecných LIKE podmínek samozřejmě existuje i další situace kdy tento typ indexů nefunguje dobře, tj. jeho použití buď vůbec není možné nebo dokonce může výrazně zhoršit výkon. Jednou z takových situací je například indexace sloupce s nízkou variabilitou, tj. s nízkým počtem různých hodnot, případně situace kdy je velmi častá konkrétní hodnota užitá v dotazu. V takovém případě totiž (některé) elementy stromu obsahují velký počet řádků (resp. jejich offsetů), a náhodný přístup k velkému počtu jednotlivých řádků (přičemž náhodný přístup je důsledkem užití indexu) je výrazně pomalejší než přečtení celé tabulky a průběžné filtrování řádků.

Nejen že čtení velké části tabulky s využitím indexu představuje potenciální výkonnostní problém, ale v případě složitějších dotazů (například pokud je několik podmínek spojeno logickými spojkami AND / OR) přichází v úvahu kombinace více indexů (pro jednotlivé podmínky). To ale není v případě B-Tree indexů příliš triviální - jak uvidíme v následující sekci, bitmapové indexy jsou k tomuto účelu výrazně vhodnější.

Bitmapové indexy

Bitmapové indexy jsou navrženy tak aby pokud možno dobře fungovaly tam kde B-Tree indexy selhávají, tj. zejména v případě sloupců s malým počtem různých hodnot. Namísto stromové struktury jsou založeny na tzv. bitových polích (bit arrays, resp. bitmaps).

Pro indexovaný sloupec jsou získány unikátní hodnoty v daném sloupci, a pro každou z těchto hodnot je vytvořeno bitové pole jehož délka v bitech odpovídá počtu řádek tabulky. Ponechme stranou technické detaily tupu "alokace po bytech" a optimalizace typu "předalokace" a jednotlivé bity v bitmapě nastavme tak aby na i-tém bitu byla hodnota "1" právě když v i-tém řádku je hodnota pro kterou byla daná bitmapa alokována.

Rozšíříme-li tabulku uvedenou v příkladech výše o sloupec "pohlaví" se třemi možnými hodnotami ("m" - muž, "ž" - žena, "n" - nevím), jedná se o typický příklad sloupce s nízkou variabilitou.

id	jmeno	prijmeni	vek	email	vyska	vaha	pohlavi
1	Franta	Vopička	29	franta.vopicka@example.com	185	78	m
17	Jaroslav	Modrý	43	jarda.modry@example.com	171	65	m
65	Jitka	Novotná	19	jitka.novotna@example.com	175	60	ž
44	Radek	Volek	25	radek.volek@example.com	165	65	n
...	...	...	...	...	...	...

Pro každou z těchto hodnot bude vytvořena bitmapa, a jejich hodnota bude zhruba takováto:

m => '1100...'
ž => '0010...'
n => '0001...'

Pro výše uvedenou tabulku osob by v případě indexu nad sloupcem "pohlaví" byla někde bokem naalokována bitová pole pro hodnoty "m", "ž" a "n". Ve srovnání s B-Tree indexy představuje problém že bitmapy obsahují pouze informaci o indexu řádku a nikoliv přímo offsety - pro tabulku je tak třeba vytvořit "mapování" indexů na offsety, například prostřednictvím pole offsetů. Vytvoření bitmapového indexu lze implementovat přibližně takto:

BufferedReader reader = new BufferedReader(new FileReader(filename));

// hodnoty ve slupci
Set<String> values = new HashSet<String>();

// počet řádek
long pocetRadek = 0;

// v prvním průchodu zjistíme různé hodnoty ve sloupci a počet řádek
while ((String line = reader.readLine()) != null) {

    // rozděl řádky na sloupce
    String[] fields = String.split("|");

    // načti hodnotu ve sloupci
    String field = fields[3];

    // přidej do množiny
    values.add(field);

    // aktualizuj počet řádek
    ++pocetRadek;

}

// skoč na začátek souboru
reader.reset();

// převeď množinu hodnot na pole (rychlejší přístup)
String[] valuesArray = values.toArray();

// index - mapa bitmap tvaru hodnota -> bitmapa
Map<String, boolean[]> index = new HashMap<String, boolean[]>();

// vytvoř bitmapy potřebné délky pro všechny hodnoty
for (int i = 0; i < valuesArray.length; i++) {
    index.put(valuesArray[i], new boolean[pocetRadek]);
}

// číslo a offset aktuální řádky
int radka = 0;
long offset = 0;

// pole offsetů řádek
long offsetyRadek = new long[pocetRadek];

// vytvoř bitmapy
while ((String line = reader.readLine()) != null) {

    // ulož offset řádky
    offsetyRadek[radka] = offset;

    // rozděl řádky na sloupce
    String[] fields = String.split("|");

    // načti hodnotu ve sloupci
    String field = fields[3];

    // doplň do bitmap pro jednotlivé hodnoty tento řádek
    for (int i = 0; i < valuesArray.length; i++) {
        boolean[] bitmap = index.get(valuesArray[i]);
        bitmap[radka++] = valuesArray[i].equals(field);
    }

    // aktualizuj offset
    offset += line.length() + 1;

}

Jak už bylo několikrát řečeno na konci odstavce o B-Tree indexech, některé operace jsou s bitmapovými indexy daleko jednodušší - ukázkovým příkladem jsou logické spojky (AND, OR, XOR, NOT) neboť je lze provádět přímo na odpovídajících bitmapách. Například vyhodnocení podmínky

(pohlavi = 'm' OR pohlavi = 'n')

je otázka spojení aplikace podmínky OR na bitmapy po elementech. To je pochopitelně výrazně rychlejší než procházení tabulky, neboť bitmapy jsou podstatně menší a aplikace logických spojek přímo na jednotlivé bity (resp. boolean proměnné) je velmi rychlá.

Obdobně lze při vyhodnocování dotazu samozřejmě využít více bitmapových indexů. Dokonce pokud je v databázovém systému implementována možnost využití více indexů při vyhodnocování jedné části dotazu, je toto většinou realizováno tak že s výsledků získaných pomocí B-Tree indexů jsou vytvořeny dočasné bitmapy a dále se pracuje s nimi (právě kvůli jejich jednoduché kombinaci).

Nevýhody bitmapových indexů

Určitou nevýhodou při práci s bitmapovými indexy je samozřejmě v tom že se vždy nutno iterovat přes všechny řádky (resp. indexy bitmapy) a kontrolovat zda na daném místě je či není 1, ale i to je většinou výrazně efektivnější než čtení a zpracovávání celé tabulky. I zde však platí že použití bitmapových indexů má určitou režii a tudíž v některých situacích může být výhodnější pracovat přímo s řádky tabulky (zejména pokud výsledný počet řádků tvoří velkou část tabulky).

Co se týká dalších možností použití bitmapových indexů jako je například třídění nebo vynucení unikátnosti hodnot, tak zatímco pro vynucení uníkátnosti jsou bitmapové indexy dosti nevhodné (znamenalo by to vytvoření tolika bitmap kolik je řádků tabulky), třídění lze s jejich použitím provést poměrně efektivně. Stačí totiž setřídit hodnoty pro které byly vytvořeny bitmapy (a jsou tedy uloženy u indexu), a následně načítat jednotlivé bitmapy a řádky z nich.

Hash indexy

Posledním poměrně běžným typem indexu jsou takzvané hash indexy. Jak už název napodívá, budou mít cosi společného s hashi, resp. s hashovými tabulkami. Pokud nevíte přesně co to hash tabulka je, je nejvyšší čas si tuto poměrně zásadní díru v programátorském vzdělání doplnit!

V podstatě se jedná o to že pro každou hodnotu vhodným algoritmem spočítáte hash, přičemž předpokládejme že výsledkem hash funkce je celé číslo například z intervalu 1 až 1024. Hodnoty tak vlastně třídíte do 1024 "přihrádek" s tím že

• stejné hodnoty jsou vždy v jedné přihrádce (mají stejný hash)
• v jedné přihrádce může být více různých hodnot (ale se stejným hashem)
• různé hodnoty by měly mít různé hodnoty (ideální hash funkce by měla hodnoty distribuovat pokud možno rovnoměrně do všech přihrádek)

Vytvoření jednoduchého hash indexu lze implementovat například takto:

BufferedReader reader = new BufferedReader(new FileReader(filename));

// index: hash -> seznam dvojic [hodnota, offset]
Map<Long, List<Object[]>> index = new HashMap<Long, List<Object[]>>();

long offset = 0;

while ((String line = reader.readLine()) != null) {

    // rozděl řádky na sloupce
    String[] fields = String.split("|");

    // načti hodnotu ve sloupci
    String field = fields[3];

    // zjisti zda už je v indexu
    List<Object[]> bin = index.get(field);

    // pokud není tak záznam vytvoř a přidej ho do indexu
    if (bin == null) {
        bin = new ArrayList<Object[]>();
        index.put(field.hashCode(), bin);
    }

    // přidej do indexu aktuální záznam
    bin.add(new Object[] {field, new Long(offset)});

    // aktualizuj offset (přičti délku řádky a znak konce řádky)
    offset += line.length() + 1;
}

Toto třídění do přihrádek je sice pěkné, ale k čemu to vlastně je? Inu, zjednodušeně řečeno není při vyhledávání nebo joinování tabulek nutno tolik porovnání (a jak už je u indexů zvykem, není nutno číst celou tabulku).

Uvažujme například tabulku s 1.000.000 řádek, a zkusme vyhledat řádek s danou hodnotou ve sloupci nad kterým je vytvořen hash index - zatímco bez hash indexu by bylo nutno přečíst všech 1.000.000 řádek, s hash indexem stačí

1. spočítat hash hledané hodnoty
2. skočit do příslušné přihrádky indexu
3. prohledat řádky v dané přihrádce (v ideálním případě jen 1.000 řádek)

V případě joinování dvou tabulek je efekt podobný - pokud budeme joinovat dvě tabulky, každou s 1.000.000 řádek, znamená to bez indexů (i když s dosti naivní implementací) celkem 1.000.000.000.000 porovnání. Použijí-li se hash indexy na obou stranách, stačí porovnávat řádky v odpovídajících přihrádkách - těch je cca 1000, a v každé z nich je v průměru 1000 hodnot, což dává 1.000.000 porovnání na přihrádku, a tedy 100.000.000 porovnání celkem.

Nevýhody hash indexů

Bohužel hash indexy mají oproti B-Tree indexům několik podstatných nevýhod. První nevýhodou je že je z principu lze použít pouze ve spojení s operátorem "=" a vyhledávání pomocí jiných operátorů (například "<", ">" a podobně) není podporováno. To ale ve svém důsledku znamená že je nelze využít ani při třídění tabulky.

Kdy lze indexy použít

Dost bylo teorie - podívejme se na několik základních typů dotazů, při jejichž vyhodnocování mohou být indexy užitečné. Schopnosti jednotlivých databázových systémů se však ohledně využití indexů dosti liší - tam kde jeden systém dokáže index dokonale využít se jiný systém musí obejít bez indexu. Proto následující odstavce berte spíše jako výchozí bod pro zkoumání možností využití indexu ve vašem databázovém systému.

WHERE podmínky

Základním a nejčastějším způsobem využití indexů je zcela jistě jejich použití pro vyhodnocení podmínek ve WHERE části dotazu. Vzhledem k tomu že základní typy WHERE podmínek a vhodnost či nevhodnost jednotlivých typů indexů pro jejich vyhodnocení byly rozebrány v předchozích odstavcích (u jednotlivých typů indexů), podívejme se na některá důležitá související témata.

FOREIGN KEY a JOIN

Mezi dotazy s WHERE podmínkou víceméně spadají i dotazy užívané pro kontrolu vazeb mezi tabulkami - cizích klíčů. Tyto dotazy jsou sice spouštěny DB systémy interně, ale platí pro ně naprosto stejné zákonitosti jako pro běžné dotazy.

S cizími klíči nastávají problémy pokud je závislá tabulka "příliš" velká. Uvažujme následující tabulky:

CREATE TABLE A (
    id INT PRIMARY KEY,
    ...
);

CREATE TABLE B (
    ...
    a_id INT REFERENCES A(id),
    ...
);

Při mazání záznamů z tabulky "A" musí databázový systém zkontrolovat zda náhodou v závislé tabulce "B" neexistuje záznam odkazující právě mazaný řádek - to znamená že je spouštěn zhruba následující dotaz:

SELECT COUNT(*) FROM B WHERE a_id = #id#

kde #id# je ID mazaného řádku z tabulky "A". Pokud nad sloupcem "B.a_id" není definován vhodný index, bude sekvenčně prohledávána celá tabulka B, což samozřejmě pro velké tabulky může znamenat značné výkonnostní problémy.

S právě popsaným problémem souvisí i joinování tabulek - ty jsou totiž většinou joinovány přes cizí klíče. Pokud by byly joinovány tabulky bez indexu nad sloupcem "B.a_id" znamená to opět potenciální nebezpečí pro výkon.

Z toho plynou následující doporučení:

1. Indexujte sloupce velkých tabulek přes které často joinujete, a to nejlépe na obou stranách JOINu (na jedné straně to většinou není problém, neboť se v dané tabulce jedná o PRIMARY KEY nebo UNIQUE INDEX).
2. Indexujte všechny cizí klíče (zejména) ve velkých tabulkách.

ORDER BY, min / max, first / last

Dalším celkem tradičním použitím indexů je třídění řádků tabulky - některé typy indexů totiž buď přímo udržují řádky v setříděném stavu (což je případ B-tree indexů), případně je možné z nich jednoduše třídění odvodit (což je případ bitmapových indexů). Existují pochopitelně i indexy pro třídění zcela nevhodné - sem patří hash indexy.

Obecně vzato platí následující pravidla

• Pokud podle sloupce často třídíde, měl by být oindexován.
• Při třídění dle více sloupců, je vhodné vytvořit složený index (a sloupce by v něm měly být uvedeny ve stejném pořadí jako v klauzuli ORDER BY).

Se tříděním souvisí i dva typy dotazů, a to hledání extrémů (minim a maxim) v daném sloupci, a načítání prvních / posledních záznamů výsledku.

GROUP BY

Vyhodnocení GROUP BY může být rychlejší v případě že sloupce v GROUP BY klauzuli jsou indexovány (ve vícesloupcovém indexu), ale je to nutno odzkoušet.

unikátnost

V databázích je často třeba vynucovat unikátnost hodnot v určitém sloupci - jedná se o tzv. "UNIQUE constraint," a k jeho implementaci jsou často využívány indexy. S úspěchem lze použít například hash indexy s tím že během modifikace indexu (vkládání / mazání hodnot) je kontrolována unikátnost hodnoty v rámci dané přihrádky.

Proč se indexy nepoužily ...

Poměrně často se na mne lidé obracejí s problémy typu "Mám nad tabulkou definovaný index ale on se nepoužije. Proč?" Odpovědět na tuto otázku není jednoduché, ale v zásadě existuje několik hlavních možností proč se index nepoužije:

Bylo by to pomalejší

Mnoho vývojářů bohužel žije v iluzi že použití indexu automaticky znamená zvýšení výkonu, a to není pravda. Je tedy možné že databáze se při plánování dotazu rozhodla správně index nepoužít. Ostatně v některých databázích je možné si použití indexu vynutit (například přes hinty v Oracle, nebo přes "SET enable_seqscan = off" v PostgreSQL).

Databáze si myslí že by to bylo pomalejší

Když databáze vytváří execution plan, tj, když rozhoduje v jakém pořadí a jakým způsobem joinovat tabulky, které indexy použít apod., používají většinou "cost based" odhady pro porovnání který z potenciálních plánů je nejlepší. Přitom ale musí zkombinovat několik více či méně nepřesných hodnot, zejména statistiky tabulek a sloupců (počet řádků, histogramy hodnot ve sloupcích, nejčastější hodnoty ve sloupcích, apod.), odhady nákladů při náhodném resp. sekvenčním čtení, a v neposlední řadě informace o systému (velikost diskové cache apod.).

Pokud jsou kombinované hodnoty příliš nepřesné, může se stát že výsledné odhady náročnosti plánu jsou natolik nepřesné že se databáze chybně rozhodne pro nevýhodný plán. Důvodů pro tyto nepřesnosti může být mnoho, například:

• statistiky tabulek / sloupců jsou nepřesné - Statistiky mohou být zastaralé nebo nedostatečně podrobné, takže si databáze mylně myslí že tabulka má výrazně méně či více řádků než ve skutečnosti.

• odhady nákladů na náhodné / sekvenční čtení neodpovídají realitě - Toto závisí zejména na použitém HW (typu pevných disků, použitém řadiči, apod.) - například na SSD discích jsou oba typy přístupu zhruba stejně náročné, zatímco na starých IDE discích může být náhodný přístup výrazně pomalejší než sekvenční čtení.

• databáze při plánování nemá potřebné informace - Jsou případy kdy při plánování dotazu prostě některé informace nejsou dostupné - například při plánování "prepared" dotazů nejsou k dispozici konkrétní hodnoty parametrů a databáze tak nemůže odhadnout kolik řádků z tabulky bude načítáno (čím větší část tabulky je načítána tím nevýhodnější použití indexů je). Databáze v takových případech většinou volí "bezpečnější" plán namísto "riskantního" plánu který je sice v některých případech o něco rychlejší ale v některých případech výkon výrazně degraduje.

• dotaz je nevhodně zformulovaný - Často je problém v dotaze samotném, který je zformulován tak nešťastně že databáze nemůže index použít, přičemž oprava je většinou otázkou drobné změny dotazu. Způsobů jak zmršit dotaz je celá řada, ale obzvláště oblíbeným je aplikace funkcí na sloupce ve WHERE podmínkách, přičemž dotaz je vytvořen přímo nad sloupcem.

  Například pokud je index vytvořen nad sloupcem "a", potom ho nebude možno použít na vyhodnocení podmínky "WHERE a*a >= 12492" protože ten zahrnuje druhou mocninu sloupce.  Tuto chybu je možno napravit buď vytvořením indexu nad výrazem (funkce aplikovaná na sloupec, v tomto případě nad výrazem "a*a"), nebo taková úprava dotazu aby se index použít dal - například přesunem funkce na druhou stranu podmínky, v tomto případě "WHERE a >= sqrt(12492)".

Čemu se vyhnout

Indexy samozřejmě nejsou zadarmo a přinášejí i potenciální problémy. Při navrhování schématu databáze se proto snažte vyhnout:

• příliš mnoha indexům - Jejich aktualizace není zadarmo a zpomaluje operace modifikující data v indexovaných sloupcích (INSERT, UPDATE, DELETE). Toto platí zejména pro tabulky s výrazně vyšším počtem zápisů než čtení, jako jsou například logovací tabulky apod.
• zbytečně redundantním indexům - Toto doporučení vlastně souvisí s tím předchozím, protože zbytečně redundantní indexy zvyšují počet indexů nad tabulkou.
• indexům nad sloupci s malou variabilitou - Malá variabilita implikuje malou selektivitu podmínek nad tímto sloupcem (tj. podmínce odpovídá velká část tabulky), což ale znamená nevýhodnost indexu a výhodnost prostého sekvenčního přečtení celé tabulky. Tento problém lze do jisté míry obejít použitím indexů nad více sloupci.
• indexům nad malými tabulkami - Pokud tabulka zabírá jen několik diskových stránek, je její kompletní načtení výhodnější než náhodný přístup s využitím indexů. Toto neplatí pro indexy sloužící k vynucení unikátnosti apod.
• pro obecné LIKE podmínky a regulární výrazy - Obecné podmínky tvaru LIKE '%text%' a ~* '%text%' nelze pomocí indexů urychlit (viz. výše). Navíc vytváření a údržba indexů nad textovými sloupci s dlouhými hodnotami je poměrně nákladná.

Celá situace je dále komplikována tím že odstranění indexu v průběhu života aplikace je dosti problematické, neboť je velmi obtížné identifikovat nepoužívané indexy. Některé databáze sice obsahují statistiky využití indexů, které mohou být vodítkem, ale co v případě že je index používán například jen jednou ročně například při účetní uzávěrce? Jeho odstranění na základě statistik může způsobit že účetní uzávěrka neproběhne ...

Příklady ke stažení

V předchozím textu byly u jednotlivých typů indexů uvedeny příklady jejich (naivní) impementace. Pokud chcete, můžete si zde stáhnout jejich poněkud dotaženější a propracovanější variantu. Balíček kromě zdrojových kódů v Javě a vygenerované API dokumentace (javadoc) obsahuje také ukázková data používaná pro benchmark.

Pro orientaci uvádím základní součásti (packages, třídy apod.) obsažené v balíčku

• cz.fuzzy.examples.db.indexes.Index - rozhraní společné pro všechny typy indexů
• cz.fuzzy.examples.db.indexes.BitmapIndex - implementace bitmapového indexu
• cz.fuzzy.examples.db.indexes.HashIndex - implementace hash indexu
• cz.fuzzy.examples.db.indexes.TreeIndex - implementace indexu založeného na stromech (nejedná se o skutečný B-Tree index, ale pro demonstraci stačí)
• cz.fuzzy.examples.db.indexes.IndexException - chyba při práci s indexem (čtení, ...)
• cz.fuzzy.examples.db.tables.Table - rozhraní společné pro všechny tabulky (bez ohledu na způsob uložení dat - v souboru, v paměti, ...)
• cz.fuzzy.examples.db.tables.FileTable - tabulka s daty uloženými v souboru
• cz.fuzzy.examples.db.tables.TableException - chyba při čtení tabulky
• cz.fuzzy.examples.db.IndexBenchmark - třída porovnávající různé způsoby přístupu k datům (bez indexů, s různými typy indexu, ...)
• cz.fuzzy.examples.db.tests - JUnit testy pro jednotlivé třídy
• build.xml - ANTový build skript, umožňující kombilaci a vygenerování JAR archivu
• example.data - ukázková data, používaná při benchmarku (ale nic vám nebrání použít vlastní)

Upozorňuji že tyto příklady jsou poněkud primitivní, soustředí se pouze na demonstraci práce s indexy při vyhodnocování dotazů, a vůbec neřeší problémy které jsou v produkčních databázích velmi důležité, mimo jiné například aktualizaci dat (tabulky umožňují pouze čtení dat z neměnného souboru), víceuživatelský přístup či přístup z více vláken, nebo transakce.

Celý balíček si můžete stáhnout zde - stačí ho rozbalit, zkompilovat do JARu a spustit benchmark

$ unzip examples-indexes.zip
$ cd examples-indexes
$ ant dist
$ java -jar dist/dbindexes-20090425.jar

Příklad výsledků tohoto benchmarku (vyhledání 200 hodnot různými způsoby) může být například:

$ java -jar dist/dbindexes-20090425.jar
==== Preparing table ====
==== Benchmarking plain table (no index) ====
200 searches: 165 ms in average

==== Benchmarking tree index ====
index built: 205 ms
200 searches: 0 ms in average

==== Benchmarking hash index ====
index built: 249 ms
200 searches: 0 ms in average

==== Benchmarking bitmap index ====
index built: 286 ms
200 searches: 0 ms in average

Pokud chcete, můžete si stáhnout i větší verzi zkušebních dat (cca 20MB oproti 1MB souboru zahrnutému v balíčku) - stačí přepsat soubor examples.data.

Odkazy

Z nejdůležitějších zdrojů využitých při psaní tohoto článku bych rád jmenoval alespoň tyto:

• Adventures in PostgreSQL / Episode 2: The Joy of Index
• Adventures in PostgreSQL / Episode 3: The Joy of Index
• PostgreSQL Technical Documentation
• PostgreSQL Internals Through Pictures
• Oracle Documentation Library / Optimizing SQL Statements