Bitmapové indexování

Bitmapové indexování je speciální způsob indexování databáze. Plné indexování databází tradičním B-stromem může být příliš nákladné, pokud jde o místo, protože indexy mohou být několikanásobně větší než údaje v tabulce. Bitmapové indexy (Indexování pomocí binárních matic) jsou obvykle jen zlomek velikosti indexovaných dat v tabulce. Bitmapové indexy, na rozdíl od klasických indexů, pracují s binárními hodnotami (binární 1 (true) a 0 (false)). Můžeme je chápat jako předem vypočítané odpovědi na jednoduché otázky, které rozdělují záznamy do přehlednějších kategorií. Bitmapový index říká, zda je odpověď na danou otázku pro určitý záznam v databázi pravdivá nebo ne. Bitmapové indexy jsou široce používány v prostředí datových skladů.

Bitmapové indexování a jeho vlastnosti

• Snižuje dobu odezvy u velkých tříd dotazů
• Snížené požadavky na skladování, v porovnání s ostatními technikami indexování
• Dramatický nárůst nároků na výkon i na hardware

Index poskytuje odkazy na řádky v tabulce, které obsahují dané klíčové hodnoty. Každý bit v bitmapu odpovídá možné ROW ID, a je-li bit nastaven, znamená to, že řádek s odpovídajícími ROW ID obsahuje klíčovou hodnotu. Mapovací funkce nezmění skutečné ROW ID, takže bitmapový index poskytuje stejné funkce jako běžný index. Pokud je počet různých klíčových hodnot malý, pak použitím bitmapových indexů šetříme místo.

Bitmapové indexy jsou nejúčinnější pro dotazy, které obsahují více podmínek v klauzuli WHERE. Řádky, které splňují některé, ale ne všechny, jsou podmínkami odfiltrovány. To často dramaticky zlepšuje dobu odezvy.

Bitmapové indexování zná svět poměrně dlouho (první práce na téma bitmapových indexů se objevily již kolem roku 1987), ale praktické využití se pro bitmapové indexy našlo až těsně před rokem 2000.

Jak si to představit

Mějme tabulku Poslední_výskyt_druhu se sloupci datum, místo výskytu, id_druhu, část dne.

datum	místo výskytu	id_druhu	část_dne
23.2.2007	povodí Berounky – oblast Alkazar	300812	AM
14.1.1999	Lidečko – Pulčínské skály	3403412	PM
31.11.2009	Rejvíz – malé mechové jezírko	130045	AM
1.11.2008	Niagarské vodopády	8459712	PM
11.4.2004	Ostrava – Pod Sýkorovým mostem	7239710	PM

V naší tabulce budou hodnoty id_druhu vždy jedinečné. Datum a Místo výskytu bude mít poměrně velký rozptyl hodnot, ale část dne bude nabývat dvou hodnot- AM (dopoledne) a PM (odpoledne). Z toho plyne, že indexovat bitmapově má největší smysl nad sloupcem část dne. V tomto případě se bez ohledu na počet záznamů v tabulce vytvoří pouze dvě bitmapová pole, a to: ” část dne je AM ”,” část dne je PM ”.

datum	místo výskytu	id_druhu	část_dne	BI AM	BI PM
23.2.2007	povodí Berounky – oblast Alkazar	300812	AM	1	0
14.1.1999	Lidečko – Pulčínské skály	3403412	PM	0	1
31.11.2009	Rejvíz – malé mechové jezírko	130045	AM	1	0
1.11.2008	Niagarské vodopády	8459712	PM	0	1
11.4.2004	Ostrava – Pod Sýkorovým mostem	7239710	PM	0	1

Další možnost, jak využít bitmapové indexování u naší tabulky, jsou třeba bitmapová pole BI LEDEN, BI ÚNOR, … apod.

Příklady vytvoření bitmap indexu

Mějme tabulky:

• Prodej (datum, id_zakaznika, mnozstvi, id_typ, …)
• Zakaznik (zakaznik_pohlavi{M,F}, id_zakaznika, rodinny_stav{S,Z}…)
• Zbozi (id_zbozi, typ, …)
• Země (nazev, id_zeme, …)

Vytvoření bitmap indexu 1

Vytvoříme bitmapový index pro tabulku prodej.

CREATE BITMAP INDEX prodej_zakaznik_pohlavi_Bindex
ON prodej(zakaznik.zak_pohlavi)
FROM prodej, zakaznik
WHERE prodej.id_zakaznika = zakaznik.id_zakaznika;

Vytvoření bitmap indexu 2

Můžete vytvořit bitmapový index pro více než jeden sloupec, jako v následujícím příkladu, který používá zakaznik(pohlavi,rodinny_stav)

CREATE BITMAP INDEX prodej_zakaznik_pohlavi_Bindex 
ON prodej(zakaznik.zakaznik_pohlavi, zakaznik.rodinny_stav) 
FROM prodej, zakaznik
WHERE prodej.id_zakaznika=zakaznik.id_zakaznika;

Vytvoření bitmap indexu 3

Můžete vytvořit bitmapový index na více než jednu tabulku, jako v následujícím příkladu, který používá zakaznik(pohlavi) a zbozi(typ)

CREATE BITMAP INDEX prodej_zakaznik_pohlavi_typ_Bindex
ON prodej(zakaznik.pohlavi, zbozi.typ)
FROM prodej, zakaznik, zbozi
WHERE prodej.id_zakaznika = zakaznik.id_zakaznika
AND prodej.id_zbozi = zbozi.id_zbozi;

Vytvoření bitmap indexu 4

Můžete vytvořit bitmapový index na více než jednu tabulku, ve které je indexovaný sloupec připojený k tabulce indexů pomocí jiné tabulky. Například, můžeme používat index zeme.jmeno_zeme i když tabulka zeme není spojena přímo na tabulku prodej. Místo toho se tabulka zeme spojí s tabulkou zakaznik, která je spojená s tabulkou prodej. Tento typ schématu se běžně nazývá snowflake schema.

CREATE BITMAP INDEX prodej_zeme_nazev_Bindex
ON prodej(zeme.nazev)
FROM prodej, zakaznik, zeme
WHERE prodej.id_zakaznika = zakaznik.id_zakaznika
AND zakaznik.id_zeme = zeme.id_zeme

Reference

• WU, John. Annotated References on Bitmap Index [online]. 2007-2013 [cit. 2017-04-08]. Dostupné online.