Bitmap Index – when to use it?

I will cover how Bitmap index work, when to use it and how to use it in this article.

How does it work?

The bitmap index stores the column values in bits. Each bit represents a single value. For example, the gender column has two possible values: Male and Female. three bit will be used in the bitmap to capture the index on the gender column. A good example can be seen in reference 1. So the more distinct value is, the more space is required to store the bitmap.

Internally, the database engine, like Oracle, uses a map function to converts the bit location to the distinct value. (See reference #2) Many bitmap indexes can be used together since database can merge it, so this can improve the response time. (See Reference #3 for the example of merging the index on Marital Status and Region)

When to use it?

1. Low cardinality – Some dabase vendor, like Oracle, provides very practical suggestion -(See Reference #3 and 4)

• If the number of distinct values of a column is less than 1% of the number of rows in the table, or if the values in a column are repeated more than 100 times, then the column is a candidate for a bitmap index.
• B-tree indexes are most effective for high-cardinality data: that is, data with many possible values, such as CUSTOMER_NAME or PHONE_NUMBER.
• There are 100 or more rows for each distinct value in the indexed column. When this limit is met, the bitmap index will be much smaller than a regular index, and you will be able to create the index much faster than a regular index.

2. No or little insert/update –

Updating bitmap indexes take a lot of resources. Here are the suggestions: (See Reference 5)

• Building and maintaining an index structure can be expensive, and it can consume resources such as disk space, CPU, and I/O capacity. Designers must ensure that the benefits of any index outweigh the negatives of index maintenance.
  
• Use this simple estimation guide for the cost of index maintenance: each index maintained by an INSERT, DELETE, or UPDATE of the indexed keys requires about three times as much resource as the actual DML operation on the table. What this means is that if you INSERT into a table with three indexes, then it will be approximately 10 times slower than an INSERT into a table with no indexes. For DML, and particularly for INSERT-heavy applications, the index design should be seriously reviewed, which might require a compromise between the query and INSERT performance.

3. Multiple Columns

One of the advantage is that multiple bitmap indexes can be merged and the column does not have to selective!

• More than one column in the table has an index that the optimizer can use to improve performance on a table scan. (See reference 6)
• Combining bitmap indexes on non-selective columns allows efficient AND and OR operations with a great number of rowids with minimal I/O. (Reference 5)
  

References

1. Bitmap Index – Wikipedia
2. Oracle Database Performance Tuning Guide – Index Scan – Bitmap Index
3. Oracle Database Concept – Overview of Indexes – Bitmap Index
4. Oracle Database Data Warehousing Guide – Using Bitmap Indexin Data Warehousing
5. Oracle Database Performance Tuning guide – Designing and Developing for Performance
6. IBM Informix Database Design and Implementation Guide
7. Siebel Analytics Performance Tuning Guide
8. Practical Data Warehousing in Oracle, Part 4 from DBAsupport.com

Other Reading:

• Bitmap Indexes – Part 1: Understanding Bitmap Indexes from DBZine.com
• Bitmap Indexes – Part 2: Star Transformations from DBZine.com
• Bitmap Indexes – Part 3: Bitmap Join Indexes from DBZine.com