Bitmap indexes

Buy the ticket, take the ride --Hunter S. Thompson

The star schema and bitmap indexes are a marriage made in heaven. The bitmap indexes and their use in accelerating star schema joins is currently available in commercial databases only. Corollary: never buy a database for data warehousing that does not support star schema joins using bitmap indexes.

The advantages of bitmap indexes compared to b-tree indexes are:

1. Small
   
2. Extremely fast AND operations on individual indexes created for each low cardinality attribute
   
3. Fast creation, no sorts required
   

The following bitmap indexes are created on the star schema example shown, to optimize the star schema join:

1. With Oracle, one bitmap index is created for each foreign key on the fact table: sales_transaction (calendar_key), sales_transaction (transaction_detail_key), sales_transaction (product_key), sales_organization (sales_org_key). With DB2, regular b-tree indexes are created instead. DB2 does not support direct creation of bitmap indexes, the bitmaps are created dynamically during runtime from the regular indexes and show up on the explain plan as the IXAND operator
   
2. In addition some indexes may be created on the dimension attributes that are frequently queried: transaction_details (transaction_type), product (category), sales_organization (store), etc. With Oracle, these indexes are also bitmap indexes
   

Consider the typical query shown that executes against the star schema. The explain plan will look very similar to this:

5.HASH JOIN
4.  TABLE ACCESS BY INDEX ROWID              SALES_TRANSACTION
3.    BITMAP AND
2.      BITMAP MERGE
.         BITMAP KEY ITERATION
1.          TABLE ACCESS BY INDEX ROWID      TRANSACTION_DETAILS
.             BITMAP INDEX RANGE SCAN        TRANS_DET_TRANS_TYP_BIX
.         BITMAP INDEX RANGE SCAN            SALES_TRANS_TRANS_DET_KEY_BIX
2.      BITMAP MERGE
.         BITMAP KEY ITERATION
1.          TABLE ACCESS BY INDEX ROWID      PRODUCT
.             BITMAP INDEX RANGE SCAN        PRODUCT_CATEGORY_BIX
.         BITMAP INDEX RANGE SCAN            SALES_TRANS_PROD_KEY_BIX
2.      BITMAP MERGE
.         BITMAP KEY ITERATION
1.          TABLE ACCESS BY INDEX ROWID      SALES_ORGANIZATION
.             BITMAP INDEX RANGE SCAN        SALES_ORG_STORE_BIX
.         BITMAP INDEX RANGE SCAN            SALES_TRANS_SALES_ORG_KEY_BIX
2.      BITMAP MERGE
.         BITMAP KEY ITERATION
.           BUFFER SORT
1.            TABLE ACCESS FULL              CALENDAR
.         BITMAP INDEX RANGE SCAN            SALES_TRANS_CALENDAR_KEY_BIX

The explain plan for the star join shown above executes these steps:

1. Filter dimension rows using bitmap index if present. Bitmap is not required here. B-tree index is used if present or full table scan is done if no indexes are viable
   
2. BITMAP MERGE - create a new bitmap by performing intersection of: the limited row set returned by the dimension WHERE clause and the full bitmap index present on the fact foreign key for the dimension
   
3. BITMAP AND - execute AND operation on all the bitmaps returned by step 2 after completion of all the respective dimension joins with fact bitmaps
   
4. Fact lookup - get only the fact rows for the rowids returned by the result of step 3
   
5. Hash join only the fact rows filtered in step 4 with the dimension rows
   

Note that the large fact table is not touched till the bitmap MERGE and AND operations are complete, only the small bitmap indexes created for each foreign key attribute on the fact are used. The fact table is then accessed using rowids only. This is what makes this approach so powerful and provides almost unlimited scalability on the fact table size, at least from the join performance perspective. 10 billion rows in the fact table? Bring it on! Compare this to the nested fact join approach where fact table is operated upon as many times as there are dimensions in the query.

So far so good, the biggest disadvantage with using bitmaps is that they are not amenable to updates. In a data warehousing environment this is not a big concern as the indexes are preferably dropped before data load and created once the load is complete.