Indexy (InterBase a Firebird)

Alexey Kovyazin, poslední aktualizace 07-Sep-2005

Koncept, který je základem indexů, je jednoduchý a názorný a patří k nejdůležitějším základům návrhu databází. Na základě indexů je postaveno mnoho základních databázových objektů a správné použití indexů je klíčem ke zlepšení výkonnosti databázových aplikací. Co je to ale index? Index je uspořádaný ukazatel na záznamy v tabulce. Ukazatel znamená, že index obsahuje hodnoty jednoho nebo několika polí v tabulce a adresy datových stránek, kde se tyto hodnoty nacházejí (podrobnosti o datových stránkách viz kapitola „Struktura databáze InterBase") (část 4). Jinými slovy, index se skládá z dvojic hodnot „hodnota pole" - „fyzické umístění tohoto pole".

Takže podle hodnoty pole (nebo polí) zahrnutých v indexu můžeme pomocí indexu rychle najít místo v tabulce, kde je záznam obsahující tuto hodnotu uložen. Uspořádaný znamená, že hodnoty polí uložených v indexu jsou seřazeny. Velmi často je index přirovnáván k knihovnímu katalogu, ve kterém jsou všechny knihy zaznamenány na kartách a seřazeny nějakým způsobem: podle abecedy nebo témat, a každá karta obsahuje informaci o tom, kde přesně je daná kniha ve skladu umístěna.

Proč potřebujeme indexy?

Jediné, k čemu indexy přispívají, je zrychlení vyhledávání záznamů podle indexovaného pole (indexovaný - znamená zahrnutý v indexu). Hlavní funkcí indexů je zajistit rychlé vyhledávání záznamů v tabulce. K tomu se scvrkává jakékoli použití indexu.

Jak je tato vyhledávací funkce realizována? Na vstupu této funkce máme hodnotu indexovaného pole (nebo několika polí). Výsledkem vyhledávání bychom měli obdržet celý záznam, ve kterém má indexované pole přednastavenou hodnotu. Nejprve se v indexu (přesněji řečeno v uspořádaném poli hodnot indexovaného pole) hledá požadovaná hodnota, poté se vezme adresa datové stránky, kde se požadovaný záznam nachází, server přejde na tuto stránku a přečte nalezený záznam. Vypadá to poněkud nepohodlně, avšak vyhledávání pomocí indexu je mnohonásobně rychlejší než sekvenční procházení všech hodnot z tabulky.

Pokud budeme pokračovat v analogii mezi indexem a knihovním katalogem, uvidíme, že vyhledávání záznamů pomocí indexu je velmi podobné vyhledávání knihy pomocí karty. Když najdeme knihu v poměrně malém katalogu (ve srovnání s celým knihovním skladem), okamžitě obdržíme informaci o tom, kde přesně je kniha uložena, a můžeme jít přímo tam. Vyhledávání bez použití indexu lze přirovnat k sekvenčnímu procházení všech knih v knihovně!

Procházení všech záznamů v tabulce se nazývá přímé nebo přirozené. Měli bychom říci, že navzdory výkonu moderních počítačů může být přirozené procházení velmi dlouhé, pokud tabulka obsahuje velký počet záznamů.

Jak jsou organizovány?

Index není součástí tabulky, je to samostatný objekt spojený s tabulkou a dalšími databázovými objekty. Toto je velmi důležitý bod implementace DBMS, který umožňuje oddělit ukládání informací od jejich reprezentace.

InterBase, stejně jako jakákoli jiná relační databáze, ukládá záznamy v tabulkách neuspořádaným způsobem, tj. vůbec se nestará o to, jak jsou záznamy fyzicky rozmístěny v tabulce. Neuspořádané ukládání znamená, že dva záznamy přidané do tabulky jeden po druhém nemusí být vedle sebe. Navíc data extrahovaná z tabulky také nemají žádné pořadí kromě toho, které by mělo být explicitně specifikováno uživatelem provádějícím vyhledávací dotaz.

Nicméně se neobejdeme bez uspořádání uložených dat: koncoví uživatelé aplikací chtějí vidět data v definovaném pořadí - například příjmení lidí podle abecedy. Indexy řeší problém reprezentace dat uspořádaným způsobem. Hodnoty polí zahrnutých v indexu jsou seřazeny a reprezentovány ve speciálním pohledu, optimalizovaném pro vyhledávání požadovaných hodnot (konkrétně to je podstatné pro vytváření uspořádaných sekvencí).

Oddělení ukládání dat od jejich reprezentace poskytuje další výhody ve srovnání s přímým řazením - možná budete potřebovat seřadit původní tabulku různými způsoby. Pak vám pomohou indexy - pro každou tabulku může být až 64 indexů!

Pokud mluvíme o implementaci indexů na fyzické úrovni, představují binární strom, jehož uzly představují dvojice „hodnota pole v indexu" - „umístění dat v tabulce". Vyhledání požadovaného záznamu v indexu se provádí pomocí mechanismu hash-vyhledávání - jednoho z nejrychlejších vyhledávacích algoritmů.

Použití indexů

Nyní, když je jasné, co můžeme od indexů požadovat, je čas dozvědět se o jejich funkci v databázi. Indexy se používají ve třech hlavních případech:

Zrychlení provádění dotazů. Indexy se vytvářejí pro pole použitá v podmínkách vyhledávání SQL-dotazů.
Podpora jedinečnosti hodnot v polích; omezení primárního klíče (o kterém bylo řečeno v kapitole „Tabulky. Primární klíče") vyžaduje, aby v tabulce nebyly dvě identické hodnoty polí zahrnutých v primárním klíči. Aby byla tato podmínka splněna, při vkládání nového záznamu byste měli vyhledat stejnou hodnotu, která bude vložena. Pro vyhledávání záznamů se používá speciální druh indexu - jedinečný index (viz níže).
Podpora referenční integrity. Omezení cizích klíčů (která jsou zvažována v kapitole „Databázová omezení") se používají ke kontrole, že hodnoty vložené do tabulky nutně existují v jiné tabulce. Při vytváření cizího klíče je automaticky vytvořen index. Tento index se používá pro zrychlení dotazů používajících spojení tabulek, stejně jako pro kontrolu podmínek cizího klíče. Stručně jsme pokryli všechna možná použití indexů. Nyní zvážíme zvláštnosti každého případu podrobněji a odpovíme na nejčastěji vznikající otázky týkající se použití indexů.

Zrychlení provádění dotazů pomocí indexů

Výše bylo popsáno, že použití indexů může výrazně zrychlit provádění dotazů. Ve většině případů to tak skutečně je, ale existují určité výhrady. Nejprve odpovíme na otázku, která často vzniká u těch, kdo se s indexy seznámili. Pokud indexy zrychlují vyhledávání v databázi, proč bychom neindexovali všechna pole v tabulce? Existují dva momenty, které brání obecnému indexování, - místo na disku a náklady při úpravě dat v tabulce. Každý vytvořený index má velikost rovnou velikosti dat v indexovaném poli plus velikost dat umístění záznamů. Pokud vytvoříme indexy pro každé pole v tabulce, jejich celková velikost bude větší než velikost dat v tabulce! Proto vytvoření velkého počtu indexů vede k obrovské spotřebě místa na disku.

Druhý moment je důležitější. Jsou to náklady při úpravě dat v tabulce. V relačním DBMS, jak víte, jsou záznamy v tabulkách neuspořádané, a proto přidávání/mazání záznamů probíhá bez významných nákladů na zdroje serveru. I když je záznam smazán z prostředku databáze, nedochází k přesouvání dat, aby se vyplnilo toto prázdné místo, - není to nutné: server jednoduše označí prázdné místo a zapíše tam něco, když to bude nutné. Pokud jde o přidávání, ve většině případů se provádí na konci tabulky. Avšak i když server při úpravě nepřesouvá hlavní data v tabulce, data uložená v indexech se při každém přidání/mazání záznamů znovu uspořádávají! Jinými slovy, server musí znovu vytvořit index při přidání záznamu do prostředku tabulky. Implementace indexu je samozřejmě nějakým způsobem určena pro časté reorganizace, ale tyto operace přesto zabírají čas a zdroje procesoru, a když je v tabulce velký počet indexů, úprava dat v ní může být mnohem pomalejší než ve stejné tabulce bez indexů!

To jsou dva hlavní důvody, které brání obecnému indexování. Kromě nich existuje ještě několik poznámek omezujících použití indexů. První je pravidlo 20 %. Říká, že pokud vyhledávací dotaz vrací více než 20 % záznamů z tabulky, použití indexu může zpomalit vyhledávání dat! Situace samozřejmě závisí na konkrétním dotazu a podmínkách nastavených pro vyhledávání, ale měli bychom si pamatovat, že 20 % záznamů je hranice, kdy se účinnost použití indexů stává pochybnou. Druhá poznámka není formulována tak jasně. Souvisí s prací optimalizátoru InterBase.

Optimalizátor je soubor mechanismů, které vytvářejí plán provádění dotazu. Když uživatel zadá InterBase jakýkoli SQL dotaz, specifikuje, co by měl server po provedení dotazu vrátit, ale nedefinuje, JAK by měl server dotaz provést. Optimalizátor na základě daného dotazu vytvoří plán jeho provádění, tj. odkud a v jakém pořadí budou data pro provedení dotazu brána, jaké indexy se při tom použijí. Když server analyzuje podmínky vyhledávání (to jsou hlavně části výrazů WHERE, ORDER BY atd.) pro každé pole zahrnuté v podmínce, server se snaží použít index. Bohužel algoritmus vytváření plánu je neúplný a optimalizátor často používá indexy, které nejsou pro konkrétní dotaz příliš účinné, kvůli čemuž se může doba provádění výrazně zpomalit. Proto vytváření zbytečných indexů může vést k vytváření neoptimálních plánů.

Mělo by být poznamenáno, že v klonu Yaffil je tento problém vyřešen díky použití moderních algoritmů vytváření plánů. Třetí případ, kdy index není nutný, jsou pole s omezenou sadou hodnot - například pole ukládající informaci o pohlaví osoby a obsahující pouze dvě možné hodnoty - „F" a „M"; nemá smysl toto pole indexovat. Takže jsme zvážili hlavní omezení vytváření indexů. Nyní bychom měli pokrýt problém, kdy je nutné použít indexy k dosažení zlepšení výkonnosti. Existují 3 hlavní případy, kdy pole musí být indexováno:

Když je toto pole použito v podmínkách vyhledávání v dotazech
Když spojení tabulek používají toto pole
Když je toto pole použito v příkazu řazení ORDER BY Pokud je pole použito výše uvedeným způsobem, vytvoření indexu pro něj může vést ke zlepšení výkonnosti dotazů.

Podívejme se na syntaxi vytváření indexů. Zde je úplný formát příkazu DDL, který umožňuje vytvářet indexy:

CREATE [UNIQUE] [ASC[ENDING] | DESC[ENDING]] INDEX index ON table (col [, col …]);

Minimální výraz vytvářející index je následující:

CREATE INDEX my_index ON Table_example(ID)

V tomto příkladu je index s názvem my_index vytvořen pro tabulku Table_example a pole ID je indexovaným polem. Index je vzestupný, tj. hodnoty v něm jsou seřazeny vzestupně, stejně jako nejedinečný, což znamená, že pole ID může mít několik identických hodnot. To je samozřejmě nejjednodušší příklad indexu - nejběžnější. Jak vidíme z popisu syntaxe, index může obsahovat ne jedno, ale několik polí. Takový index se používá, když jsou dotazy často prováděny a obsahují kombinaci indexovaných polí v podmínkách vyhledávání nebo řazení. Například pokud máme tabulku obsahující pole Příjmení, Jméno, Patronymikum, takový index se použije při vytváření dotazu, který používá řazení podle Příjmení, Jména a Patronymika. Obecně není nutné specifikovat podmínky pro všechna 3 pole použitá v indexu, abychom využili jeho výhod. Pokud chceme seřadit výsledek dotazu, index se použije v případě, že první pole v podmínce řazení se shoduje s prvním polem v indexu. Například náš index se použije v případě řazení podle Příjmení a Jména.

Podle dokumentace pro optimalizaci provádění dotazů obsahujících v příkazu WHERE spojení polí s podmínkou OR bychom měli použít ne souhrnný index, ale několik jednotlivých pro všechna pole zahrnutá v podmínce OR.

Pokud jde o otázku pořadí řazení indexu, může být buď vzestupné, nebo sestupné. Proč potřebujeme různá pořadí řazení? Samozřejmě, pro různá třídění! Pokud chceme třídit osoby podle příjmení vzestupně, vytvoříme vzestupný index (ASC), a pokud sestupně (od Z do A) - pak sestupný! Pokud chceme obojí, musíme vytvořit oba indexy.

Podpora referenční integrity pomocí indexů

V definici indexu je ještě jedna možnost - UNIQUE. Pokud ji zadáme, index umožní vložit do tabulky pouze jedinečné hodnoty. Ve skutečnosti je to základ pro implementaci jedinečných klíčů. Jedinečné klíče jsou v databázích široce používány. To znamená, že РК je jedinečný klíč-index, ale ne každý UK je РК. Výše jsme hovořili pouze o РК. Primární klíč je nejčastěji používaným typem jedinečného klíče. Při vytváření primárního klíče pro tabulku je automaticky vytvořen jedinečný index. Je mu přidělen název složený z RDB$PRIMARYNNN, kde NNN je sekvenční jedinečné číslo v rámci databáze. Tím jsou dvě hlavní omezení referenční integrity - jedinečný klíč a primární klíč - realizována pomocí jedinečného indexu. Je zřejmé, že pojem jedinečnosti je neslučitelný s pojmem nedefinované hodnoty. Jinými slovy, v polích obsažených v jedinečných indexech by neměly být žádné hodnoty typu NULL. Před vytvořením jedinečného indexu pro pole je nutné nastavit omezení NOT NULL. Pokud je index vytvořen pro data, která již existují, pak při vytváření bude indexované pole zkontrolováno na výskyt opakujících se hodnot. Pokud obsahuje, bude vám vytvoření indexu zakázáno.

Kromě omezení jedinečného a primárního klíče je mechanismus indexů základem pro implementaci dalšího omezení referenční integrity - cizího klíče. Omezení cizího klíče je nastaveno pro jedno nebo několik polí libovolné tabulky a zabraňuje vkládání hodnot do těchto polí, které nejsou zahrnuty v primárním klíči jiné, nadřazené tabulky. Pro implementaci cizího klíče, tj. pro provedení kontroly, zda existuje hodnota v nadřazené tabulce, je automaticky vytvořen speciální index. Jeho název je RDB$FOREIGNNN, kde NNN je sekvenční jedinečné číslo v rámci databáze.

Proč se mechanismus indexů používá pro implementaci omezení referenční integrity? Jde o to, že indexy v InterBase jsou ve zvláštním, preferovaném postavení - říká se, že jsou prováděny mimo kontext transakcí. To je velmi důležitá vlastnost. O transakcích budeme hovořit později, v kapitole jim věnované. Nyní pouze zmíníme, že když jsou indexy mimo transakce, znamená to, že všichni uživatelé pracující současně s daty ve stejné tabulce musí dodržovat omezení referenční integrity.

Optimalizace výkonnosti indexů

V názvu této části můžeme najít určitý paradox - indexy, jak bylo uvedeno výše, mají urychlit provádění dotazů, a ukazuje se, že i ony by měly být optimalizovány! Ale co se dá dělat (takový je život) - někdo se musí o indexy starat. Co se s indexy děje? Proč “ztrácejí formu”? Budeme muset znovu říci, že indexy jsou realizovány jako binární strom. A když je do tabulky přidán nový záznam (aktualizován, smazán - jak chcete), je do stromu přidána nová větev. Tyto větve nejsou přidávány doprostřed stromu, ale na vrcholy jiných větví. Postupně se strom stává stále více rozvětveným (nebo nevyváženým) a vyhledávání - méně efektivním. Přestavba stromu nebo (v některých případech) přepočet statistik může situaci zlepšit.

Periodicky je nutné index znovu vytvořit, aby se obnovila jeho výkonnost. K rekreaci indexu dochází v následujících případech:

Při přestavbě indexu pomocí příkazu ALTER INDEX.
Při smazání a znovuvytvoření indexu pomocí příkazů DROP INDEX a CREATE INDEX.
Při zálohování a obnově ze záložní kopie pomocí nástroje gbak.

Také můžete použít přepočet statistik. Musíte však pochopit, že tato operace nemění stav indexu, pouze informuje optimalizátor o přesných informacích o jeho stavu, což umožňuje správně používat tento index. Jinými slovy, přepočet statistik není “lék” pro index, ale pouze přesná diagnostika jeho stavu. Podívejme se na všechny tyto způsoby optimalizace indexů podrobněji. Použití příkazu ALTER INDEX má následující formát:

ALTER INDEX name {ACTIVE | INACTIVE};

Zde name je název indexu a ACTIVE a INACTIVE - dva stavy indexu, do kterých může být převeden pomocí příkazu ALTER INDEX. Parametr ACTIVE znamená, že index je aktivní a může být použit ve všech dotazech a procedurách. Pokud nastavíte index na INACTIVE, povede to k odpojení jeho používání. Pro přeskupení stromu by měly být sekvenčně provedeny dva příkazy:

ALTER INDEX name INACTIVE; ALTER INDEX name ACTIVE;

Tím bude index přestavěn. Použití ALTER INDEX má řadu omezení: nemůžete přestavět indexy použité v primárních, jedinečných a cizích klíčích; nemůžete přestavět index, pokud je v současné době používán nějakým dotazem; a také pro změnu indexu je nutné mít práva administrátora (SYSDBA) nebo být tvůrcem daného indexu.

Rekreace indexu pomocí příkazů DROP INDEX a CREATE INDEX vede k úplnému smazání indexu z databáze a poté k jeho vytvoření od začátku. Syntaxe příkazu DROP INDEX je zřejmá:

DROP INDEX jméno_indexu;

Po smazání je nutné vytvořit index se stejným názvem a parametry pomocí příkazu CREATE INDEX, jehož syntaxi jsme již probrali. Způsob přestavby indexu jeho úplnou rekreací má omezení podobná omezením pro použití ALTER INDEX.

Třetí způsob přestavby indexu je založen na vlastnosti záložních kopií databází InterBase vytvořených utilitou gbak. Jde o to, že při zálohování nejsou data obsažená v indexu uložena do záložní kopie, je uložena pouze definice indexu. Při obnově ze záložní kopie je index znovu vytvořen. Pokud se chcete dozvědět více o zálohování, podívejte se do kapitoly “Zálohování a obnova ze záložní kopie” (část 4).

Čtvrtým způsobem, jak zlepšit výkonnost indexů, je shromažďování statistik o indexech pomocí příkazu SET STATISTICS. Statistika tabulky je hodnota v rozsahu od 0 do 1, jejíž hodnota závisí na počtu různých záznamů v tabulce. Optimalizátor InterBase používá statistiku pro určení efektivity použití toho či onoho indexu v dotazu. Když se počet záznamů v tabulce může výrazně změnit (například kvůli velkému počtu vložení nebo odstranění), může přepočet statistik výrazně zlepšit výkonnost. Příkaz pro přepočet statistik je následující:

SET STATISTICS INDEX name;

Zde name je název indexu, pro který je statistika přepočítána. Přepočet statistik nepřestavuje index, a proto je prost většiny omezení stanovených pro výše popsané způsoby zlepšení výkonnosti, kromě toho, že pouze tvůrce indexu nebo systémový administrátor (uživatel se jménem SYSDBA) může přepočítat statistiku. Správná statistika umožňuje optimalizátoru učinit správné rozhodnutí o použití či nepoužití jakéhokoli indexu.

Probrali jsme několik způsobů zlepšení výkonnosti indexů. Pomocí příkazů ALTER INDEX a DROP/CREATE INDEX můžeme přestavět jakékoli indexy kromě systémových indexů vytvořených automaticky, určených k zajištění referenční integrity. Pokud chcete tyto indexy přestavět, měli byste použít příkazy pro změnu a vytváření tabulek - ALTER TABLE a CREATE TABLE, protože tyto indexy jsou nedílnou součástí tabulkových klíčů.