An Adequate Design for Large Data Warehouse Systems: Bitmap index versus B-tree index
Morteza Zaker, Somnuk Phon-Amnuaisuk, Su-Cheng Haw · 2008
Abstract—Although creating indexes on database is usually regarded as a common issue, it plays a key role in the query performance, particularly in the case of huge databases like a Data Warehouse where the queries are of complicated and ad hoc nature. Should an appropriate index structure be selected, the time required for query response will decrease extensively. To best of our knowledge, to date no comprehensive guideline has been provided for Data Warehouse analysts to opt for suitable indices. Conventionally, most experts go for the Bitmap index as a preferred indexing technique for cases where the indexed attributes are of few distinct values (i.e., low cardinality). Once the index size is huge, the cardinality of indexed columns increases causing the query response time to rise. On the other hand, owing to its indexing and retrieving mechanisms, B-tree index is assumed to be the adequate technique as the column values increase in cardinality. The paper seeks to illustrate how such assumptions mentioned above may not be true under certain circumstances. Empirical evidence is provided to confirm that even though the level of column cardinality may be determined by the index file size, the query processing time is not necessarily set by the level of column cardinality. Surprisingly, the results also indicate how the Bitmap index can be more expeditious than B-tree index on a large dataset with multi-billion records. Index Terms—Data warehouse, Bitmap index, B-tree index, Query processing