Hoe werkt de bitmap join index

September 2003 - Donald K. Burleson

Oracle9i heeft de bitmap join index aan de reeks van nieuwe tabel functies toegevoegd. Deze nieuwe tabel toegangsmethode vereist dat een index wordt gecreëerd die bestaat uit het resultaat van een join en dat vervolgens een bitmap index wordt samengesteld met alle kolommen uit deze index. In tegenstelling tot andere relationele database indexen worden de geïndexeerde kolommen niet in de tabel zelf vastgelegd. Oracle heeft hiervoor de index creatie aangepast door nu een Where clause toe te staan in de index creatie syntax. Deze optie heeft grote invloed op de wijze waarop tabellen kunnen worden benaderd vanuit SQL.

De bitmap join index is erg bruikbaar voor tabel joins met een lage cardinaliteit (bijv. kolommen met minder dan 300 distincte waarden). Bitmap join indexen zijn echter niet bruikbaar in alle gevallen. Je kunt ze niet gebruiken voor OLTP databases omdat het bijwerken van deze indexen redelijk wat overhead vraagt. Laten we eens wat nader kijken hoe dit type index werkt. 

Hoe werkt de bitmap join index

In onderstaande figuur wordt een eenvoudig voorbeeld gegeven hoe bitmap join indexen werken. We zien een many-to-many relatie tussen onderdelen en toeleveranciers met een inventaris tabel die als join tabel functioneert. Ieder onderdeel heeft meerdere toeleveranciers en iedere toeleverancier biedt meerdere onderdelen (Figuur A).

Figuur A: een many-to-many relatie

In dit voorbeeld nemen we aan dat de database 300 verschillende soorten onderdelen heeft en dat de toeleveranciers in alle landen van Europa leveren. Hierdoor zijn er 300 distincte waarden in de soort kolom van de onderdelen tabel en bijv. 20 distincte waarden in de land kolom van de toeleveranciers tabel. 

Merk nu op dat we in Figuur A een index aangemaakt hebben op de inventaris tabel met kolommen uit de onderdelen en toeleveranciers tabel. Het idee achter een bitmap join index is om de lage cardinaliteit kolommen vooral te 'join'-en om zodoende de algehele join sneller te maken.

Het is bekend dat bitmap indexen de performance van Oracle9i queries verbeteren bij gevallen waar de Where clause betrekking heeft op lage cardinaliteit kolommen. Maar deze techniek was tot dus ver nog niet gebruikt in gevallen waar de lage cardinaliteit kolommen in een andere tabel zitten.

Om een bitmap join index te creëren kan de volgende DDL gebruikt worden (let op het gebruik van de FROM en de WHERE clause in de CREATE INDEX syntax):

create bitmap index
   onderdeel_toelev_land 
on     
   inventaris ( onderdeel.soort, toeleverancier.land) 
from
          inventaris i
,         onderdeel o
,         toeleverancier t 
where
   i.onderdeel_id = o.onderdeel_id 
and    
   i.toelev_id      = t.toelev_id;

Bitmap join indexen in gebruik

Om nu te zien hoe bitmap join indexen werken kijken naar een voorbeeld van een SQL query. Stel dat we een lijst van alle toeleveranciers van bouten willen hebben in Duitsland. Hiervoor schrijven we de volgende query:

select
   toelev_naam 
from 
   onderdelen 
natural join
   inventaris 
natural join
   toeleveranciers 
where 
   soort = 'bout' 
and     
   land='Duitsland';

Voor Oracle9i werd deze SQL query uitgevoerd middels een nested loop join of hash join op alle drie tabellen. Met een bitmap join index - waarbij de index de drie tabellen vooraf ge-joined heeft - kan de query heel snel de lijst met row ID's ophalen van de corresponderende records in de drie tabellen.

Merk op dat deze bitmap join index de join criteria voor de drie tabellen specificeerde en een bitmap index op de tussentabel (inventaris) creëerde inclusief Soort en Land (Figuur A).

Oracle benchmarks tonen aan (beweren) dat bitmap join indexen een query meer dan 8x sneller uitvoeren dan traditionele index methoden. Deze verbetering is echter wel afhankelijk van veel factoren en een bitmap join is een oplossing voor alle problemen. Enkele beperkingen op het gebruik van de bitmap join index zijn:

• De geïndexeerde kolommen moet een lage cardinaliteit hebben — veelal minder dan 300 distincte waarden.
   

• De query moet in de Where clause geen verwijzingen hebben naar kolommen die niet in index zitten. 
   

• De overhead tijdens het bijwerken van de bitmap join indexen is substantieel. Veelal worden daarom de bitmap join indexen eerst verwijderd voordat veel records in de onderliggende tabellen worden bijgewerkt , om vervolgens weer herbouwd te worden. Dit probleem speelt bijvoorbeeld voor data warehouses waar tabellen 'en masse' worden bijgewerkt.

Onthoud daarom dat bitmap join indexen de performance van bepaalde queries enorm kunnen verbeteren - maar wel tegen de kosten van het vooraf join-en van de tabellen tijdens de index creatie. 

Denk eerst goed na... 

Oracle9i heeft nu de mogelijkheden voor een zeer verfijnd executieplan waarmee de query snelheid enorm kan verbeteren. Maar deze functies kunnen niet zo maar automatisch worden gebruikt. Het is daarom belangrijk voor de Oracle9i professional om deze nieuwe technieken goed te begrijpen, te bepalen wat de kosten zijn en te oordelen wanneer de nieuwe functies echt gebruikt kunnen worden om de snelheid van bepaalde queries te vergroten.