Dimenzionális modellezés - bitmap indexek
2008. október 12., vasárnap by Zoltan Tanczos
Az előző dimenzionális modellezésről szóló bejegyzésben megemlítettem, hogy a csillag sémának az egyik előnye a jó lekérdezési teljesítmény. Akkor ezt hagytam lógni a levegőben, nem indokoltam meg, hogy miért. Ez a bejegyzés viszont arról szólna, hogy csillag séma esetén milyen technikák léteznek a lekérdezések optimalizálására.
Az indexek a lekérdezésekben szereplő szelekciós feltételek kiértékelésénél használatosak (pl.: WHERE T.A = 1000). Általános esetben egy lekérdezés végrehajtási ideje az indexek feldolgozásának és az adatok kinyerésének ideje. Ha egy lekérdezés eredményhalmazának mérete jelentős a tábla teljes méretéhez viszonyítva, akkor az adatelérés ideje megközelítheti egy teljes "table scan" (amikor a tábla minden során egyesével végigmegyünk) idejét. Ilyen esetekben az indexek használata épphogy lassítaná a lekérdezést.
Erre a problémára az egyik elterjedt megoldás az ún. bitmap indexek, vagy magyarra fordítva bittérképes indexek használata. Bitmap indexekből is többféle létezik, a család legegyszerűbb tagja az egyszerű bitmap indexek (simple bitmap indexes). Például, ha az indexelni kívánt attribútum a nemek (ami tipikusan két értéket vehet fel: Férfi, Nő), akkor az index egy két bitből álló vektor lenne, az egyik bit a férfiak esetén lenne 1-es, a másik pedig nők esetében:
A fenti táblázat minden sora az Ügyfél (Customer) tábla egyik rekordjához tartozik. Az egyszerű bitmap indexek mérete az indexelendő attribútum kardinalitásának és a tábla méretének lineáris függvénye, és az index feldolgozás ideje az index méretének lineáris függvénye. Emiatt rögtön látszódik az egyszerű bitmap indexek egyik hátrányos tulajdonsága: ha az indexelendő attribútum sokféle értéket vehet fel, akkor a táblázat igen ritka lesz (sparsity problem), egy sorhoz tipikusan csak egy darab 1-es fog tartozni, a többi bit értéke 0 lesz. Ez pedig nem nevezhető hatékony tárhely-kihasználásnak. Erre megoldás lehet a bittérképek tömörítése (pl.: futáshossz kódolással), de így elveszítenénk a bitmap indexek egy igen kellemes tulajdonságát: ha több feltétel egyszerre történő teljesülését akarjuk vizsgálni, akkor a bittérképek adott oszlopainak logikai ÉS kapcsolatát kell csak kiszámolnunk:
azaz a 80-as és a 110-es ügyfél tartozik a központi régióban levő férfiak közé. Ming-Chuan Wu a Query Optimization for Selections using Bitmaps című munkájában két olyan bitmap indexet is javasol, amik megőrzik a fent bemutatott előnyöket és mégis hatékonyabb tárhelykihasználtságot tesznek lehetővé.
Bit-sliced indexing
Az első az ún. bit-sliced indexelés (ezt inkább nem próbálom meg magyarra fordítani, úgyis csak valami zagyvaság lenne belőle:) ). Egy attribútum bit-sliced indexe az attribútum értékének bitenkénti leképezése. Például, ha egy A attribútum egy 16-bites egész szám, és értékei 100 és 900 közötti értékeket vehetnek fel, akkor a hozzá tartozó index így nézhet ki:
A bitvektorok száma megegyezik az attribútum típusának méretével, a vektorok hossza pedig az indexelt tábla kardinalitásával.
Egy bit-sliced indexnek nem feltétlen kell bináris alapúnak lennie, elképzelhető például decimális alapú bit-sliced index is. Az előző példában szereplő A attribútum tizes alapú indexe három komponensből állna, a helyiértékeknek megfelelően.
Ilyen típusú indexek esetén a kiválasztás a megfelelő bitvektorok kiolvasásával és össze-ÉS-eléssükkel történik. Például az A=124 szűrőfeltétel esetén a b1 b2 b4 vektorokat olvassuk ki rendre a harmadik, második illetve első komponensekből, és logikai ÉS kapcsolatba hozzuk őket. Az eredmény pedig azon sorokat tartalmazza, ahol az A értéke 124.
Az alap kiválasztása a tárhelykövetelményeket és a feldolgozási sebességet befolyásolja. A fenti példában a bináris alapú index 16 bitvektorból áll, míg a tizes alapú 30-ból. Egy szűrő feltétel kiértékelése (pl.: A=124) bináris alapon 16 bitvektor végigpásztázását jelenti, decimális alapon viszont csak háromét.
Encoded Bitmap Indexing
Egy másik bitmap indexelést kódolt bitmap indexelésnek neveznek (encoded bitmap indexing, EBI). Az EBI az attribútum értelmezési tartományát leképezi egy kódoló függvény segítségével, és a kódolt értékeken felépít egy bináris alapú bit-sliced bittérképet. A bináris alap és kódolás segítségével hatékony tárhelykihasználtságot tesz lehetővé, ugyanakkor viszont megtartja a lekérdezés-optimalizálás lehetőségét jóldefiniált kódolás segítségével (well-defined encoding). Például, ha egy B attribútum értelmezési tartománya {a, b, c, d, e, f, t, u, v, w}, akkor egy M függvényt az alábbi módon definiálhatunk:
a void az adatbázisból törölt, a NULL pedig a NULL értékeket reprezentálja. A fenti táblázathoz tartozó minterm-ek:
EBI segítségével egy szűrés az alábbi módon hajtható végre:
szűrőfeltétel: B eleme {a, b, e, f}
Ezekhez az elemekhez tartozó minterm-ek egy Boole függvényt alkotnak: f_a + f_b + f_e + f_f, amit tovább lehet egyszerűsíteni /b3b1-re. Azaz, azon értékek elégítik ki a szűrőfeltételt, amik b3 bitjét negálva majd b1 bitjükhöz ÉS-elve 1-et kapunk.
Az EBI valójában nem más, mint egy bináris alapú bit-sliced bitmap index egy attribútum kódolt értelmezési tartományán. Az EBI-knek két előnyük van a bit-sliced indexek felett:
Csillag transzformáció bitmap indexekkel
Ezen kitekintő után térjünk vissza a csillag sémánkhoz. Például, egy szokásos értékesítési adatokat tartalmazó "sales" tény-tábla esetén dimenziók lehetnek: idő, ügyfél, termék, értékesítési csatorna.
Tekintsük az alábbi lekérdezést:
Oracle adatbáziskezelő alatt a csillag transzformáció feltétele, hogy minden illesztéshez használt oszlopon definiálva legyen egy bitmap index, ebben az esetben cust_id, time_id, channel_id. A lekérdezést két menetben hajtja végre az adatbáziskezelő motor. Az alábbi lekérdezés végrehajtásával csak azokat a sorokat gyűjti ki a tény táblából, amik valóban szükségesek:
Ebben a lekérdezésben a tény táblán a time_id-re definiált bitmap index segítségével kiválasztjuk azokat a sorokat, amik 1999. első negyedévére vonatkoznak. Ez valójában annyit jelent, hogy azokat a sorokat választjuk ki, amiknél a bittérképben az 1999-Q1 bit értéke 1-es értékű. Hasonlóan történik a második negyedév adatainak kiválasztása. A kettő bitenkénti VAGY kapcsolatba hozásával kapjuk meg a kívánt időszakot.
Ugyanilyen módon történik az ügyfelekre és értékesítési csatornákra történő szűrőfeltételek kiértékelése. A kapott három bittérképet majd logikai ÉS kapcsolatba hozva csupán azon sorok esetén kapunk 1-es értéket, amik az összes feltételt kielégítik.
A második lépésben történik meg a tény tábla kiválasztott sorainak a dimenzió táblákhoz történő illesztése. Mivel a dimenzió táblák relatíve kis méretűek a tény táblákhoz viszonyítva, az Oracle általában teljes "table scan"-t használ az elérésükhöz.
Források:
Az indexek a lekérdezésekben szereplő szelekciós feltételek kiértékelésénél használatosak (pl.: WHERE T.A = 1000). Általános esetben egy lekérdezés végrehajtási ideje az indexek feldolgozásának és az adatok kinyerésének ideje. Ha egy lekérdezés eredményhalmazának mérete jelentős a tábla teljes méretéhez viszonyítva, akkor az adatelérés ideje megközelítheti egy teljes "table scan" (amikor a tábla minden során egyesével végigmegyünk) idejét. Ilyen esetekben az indexek használata épphogy lassítaná a lekérdezést.
Erre a problémára az egyik elterjedt megoldás az ún. bitmap indexek, vagy magyarra fordítva bittérképes indexek használata. Bitmap indexekből is többféle létezik, a család legegyszerűbb tagja az egyszerű bitmap indexek (simple bitmap indexes). Például, ha az indexelni kívánt attribútum a nemek (ami tipikusan két értéket vehet fel: Férfi, Nő), akkor az index egy két bitből álló vektor lenne, az egyik bit a férfiak esetén lenne 1-es, a másik pedig nők esetében:
gender='M' gender='F'
cust_id 70 0 1
cust_id 80 0 1
cust_id 90 1 0
cust_id 100 0 1
cust_id 110 0 1
cust_id 120 1 0
cust_id 130 1 0
cust_id 140 1 0
A fenti táblázat minden sora az Ügyfél (Customer) tábla egyik rekordjához tartozik. Az egyszerű bitmap indexek mérete az indexelendő attribútum kardinalitásának és a tábla méretének lineáris függvénye, és az index feldolgozás ideje az index méretének lineáris függvénye. Emiatt rögtön látszódik az egyszerű bitmap indexek egyik hátrányos tulajdonsága: ha az indexelendő attribútum sokféle értéket vehet fel, akkor a táblázat igen ritka lesz (sparsity problem), egy sorhoz tipikusan csak egy darab 1-es fog tartozni, a többi bit értéke 0 lesz. Ez pedig nem nevezhető hatékony tárhely-kihasználásnak. Erre megoldás lehet a bittérképek tömörítése (pl.: futáshossz kódolással), de így elveszítenénk a bitmap indexek egy igen kellemes tulajdonságát: ha több feltétel egyszerre történő teljesülését akarjuk vizsgálni, akkor a bittérképek adott oszlopainak logikai ÉS kapcsolatát kell csak kiszámolnunk:
gender='M' region='central'
cust_id 70 0 1 0
cust_id 80 1 1 1
cust_id 90 1 AND 0 = 0
cust_id 100 0 0 0
cust_id 110 1 1 1
azaz a 80-as és a 110-es ügyfél tartozik a központi régióban levő férfiak közé. Ming-Chuan Wu a Query Optimization for Selections using Bitmaps című munkájában két olyan bitmap indexet is javasol, amik megőrzik a fent bemutatott előnyöket és mégis hatékonyabb tárhelykihasználtságot tesznek lehetővé.
Bit-sliced indexing
Az első az ún. bit-sliced indexelés (ezt inkább nem próbálom meg magyarra fordítani, úgyis csak valami zagyvaság lenne belőle:) ). Egy attribútum bit-sliced indexe az attribútum értékének bitenkénti leképezése. Például, ha egy A attribútum egy 16-bites egész szám, és értékei 100 és 900 közötti értékeket vehetnek fel, akkor a hozzá tartozó index így nézhet ki:
A b15...b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0
201 0...0 0 0 1 1 0 0 1 0 0 1
100 0...0 0 0 0 1 1 0 0 1 0 0
900 0...0 1 1 1 0 0 0 0 1 0 0
A bitvektorok száma megegyezik az attribútum típusának méretével, a vektorok hossza pedig az indexelt tábla kardinalitásával.
Egy bit-sliced indexnek nem feltétlen kell bináris alapúnak lennie, elképzelhető például decimális alapú bit-sliced index is. Az előző példában szereplő A attribútum tizes alapú indexe három komponensből állna, a helyiértékeknek megfelelően.
A b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0
124 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
harmadik komponens második komponens első komponens
Ilyen típusú indexek esetén a kiválasztás a megfelelő bitvektorok kiolvasásával és össze-ÉS-eléssükkel történik. Például az A=124 szűrőfeltétel esetén a b1 b2 b4 vektorokat olvassuk ki rendre a harmadik, második illetve első komponensekből, és logikai ÉS kapcsolatba hozzuk őket. Az eredmény pedig azon sorokat tartalmazza, ahol az A értéke 124.
Az alap kiválasztása a tárhelykövetelményeket és a feldolgozási sebességet befolyásolja. A fenti példában a bináris alapú index 16 bitvektorból áll, míg a tizes alapú 30-ból. Egy szűrő feltétel kiértékelése (pl.: A=124) bináris alapon 16 bitvektor végigpásztázását jelenti, decimális alapon viszont csak háromét.
Encoded Bitmap Indexing
Egy másik bitmap indexelést kódolt bitmap indexelésnek neveznek (encoded bitmap indexing, EBI). Az EBI az attribútum értelmezési tartományát leképezi egy kódoló függvény segítségével, és a kódolt értékeken felépít egy bináris alapú bit-sliced bittérképet. A bináris alap és kódolás segítségével hatékony tárhelykihasználtságot tesz lehetővé, ugyanakkor viszont megtartja a lekérdezés-optimalizálás lehetőségét jóldefiniált kódolás segítségével (well-defined encoding). Például, ha egy B attribútum értelmezési tartománya {a, b, c, d, e, f, t, u, v, w}, akkor egy M függvényt az alábbi módon definiálhatunk:
B M(B)
void 0000
NULL 0001
a 0010
b 0011
c 0100
d 0101
e 0110
f 0111
t 1000
u 1001
v 1010
w 1011
a void az adatbázisból törölt, a NULL pedig a NULL értékeket reprezentálja. A fenti táblázathoz tartozó minterm-ek:
f_void=/b3/b2/b1/b0 f_b = /b3/b2b1b0
f_null=/b3/b2/b1b0 f_c = /b3b2/b1/b0
f_a =/b3/b2b1/b0 f_d = /b3b2/b1b0
f_e = /b3b2b1/b0 f_u = b3/b2/b1b0
f_f = /b3b2b1b0 f_v = b3/b2b1/b0
f_t = b3/b2/b1/b0 f_w = b3/b2b1b0
EBI segítségével egy szűrés az alábbi módon hajtható végre:
szűrőfeltétel: B eleme {a, b, e, f}
Ezekhez az elemekhez tartozó minterm-ek egy Boole függvényt alkotnak: f_a + f_b + f_e + f_f, amit tovább lehet egyszerűsíteni /b3b1-re. Azaz, azon értékek elégítik ki a szűrőfeltételt, amik b3 bitjét negálva majd b1 bitjükhöz ÉS-elve 1-et kapunk.
Az EBI valójában nem más, mint egy bináris alapú bit-sliced bitmap index egy attribútum kódolt értelmezési tartományán. Az EBI-knek két előnyük van a bit-sliced indexek felett:
- a bitvektorok száma nem több, mint a bit-sliced esetében, hiszen a szükséges bitvektorok száma az adott attribútum számosságának kettes alapú logaritmusa (+2 a törölt és NULL értékek miatt, és ennek a felsőegészrésze).
- EBI esetében több optimalizálási lehetőség van "megfelelő" kódoló függvény kiválasztása esetén. Ilyen függvényeket Wu: Encoded Bitmap Indexing for Data Warehouses című írásában mutat be.
Csillag transzformáció bitmap indexekkel
Ezen kitekintő után térjünk vissza a csillag sémánkhoz. Például, egy szokásos értékesítési adatokat tartalmazó "sales" tény-tábla esetén dimenziók lehetnek: idő, ügyfél, termék, értékesítési csatorna.
Tekintsük az alábbi lekérdezést:
SELECT ch.channel_class, c.cust_city, t.calendar_quarter_desc,
SUM(s.amount_sold) sales_amount
FROM sales s, times t, customers c, channels ch
WHERE s.time_id = t.time_id
AND s.cust_id = c.cust_id
AND s.channel_id = ch.channel_id
AND c.cust_state_province = 'CA'
AND ch.channel_desc in ('Internet','Catalog')
AND t.calendar_quarter_desc IN ('1999-Q1','1999-Q2')
GROUP BY ch.channel_class, c.cust_city, t.calendar_quarter_desc;
Oracle adatbáziskezelő alatt a csillag transzformáció feltétele, hogy minden illesztéshez használt oszlopon definiálva legyen egy bitmap index, ebben az esetben cust_id, time_id, channel_id. A lekérdezést két menetben hajtja végre az adatbáziskezelő motor. Az alábbi lekérdezés végrehajtásával csak azokat a sorokat gyűjti ki a tény táblából, amik valóban szükségesek:
SELECT ... FROM sales
WHERE time_id IN
(SELECT time_id FROM times
WHERE calendar_quarter_desc IN('1999-Q1','1999-Q2'))
AND cust_id IN
(SELECT cust_id FROM customers WHERE cust_state_province='CA')
AND channel_id IN
(SELECT channel_id FROM channels WHERE channel_desc IN('Internet','Catalog'));
Ebben a lekérdezésben a tény táblán a time_id-re definiált bitmap index segítségével kiválasztjuk azokat a sorokat, amik 1999. első negyedévére vonatkoznak. Ez valójában annyit jelent, hogy azokat a sorokat választjuk ki, amiknél a bittérképben az 1999-Q1 bit értéke 1-es értékű. Hasonlóan történik a második negyedév adatainak kiválasztása. A kettő bitenkénti VAGY kapcsolatba hozásával kapjuk meg a kívánt időszakot.
Ugyanilyen módon történik az ügyfelekre és értékesítési csatornákra történő szűrőfeltételek kiértékelése. A kapott három bittérképet majd logikai ÉS kapcsolatba hozva csupán azon sorok esetén kapunk 1-es értéket, amik az összes feltételt kielégítik.
A második lépésben történik meg a tény tábla kiválasztott sorainak a dimenzió táblákhoz történő illesztése. Mivel a dimenzió táblák relatíve kis méretűek a tény táblákhoz viszonyítva, az Oracle általában teljes "table scan"-t használ az elérésükhöz.
Források:
