Dylan's BI Study Notes

My notes about Business Intelligence, Data Warehousing, OLAP, and Master Data Management

Bitmap Index – when to use it?

Posted by Dylan Wan on February 1, 2008

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:

Advertisements

5 Responses to “Bitmap Index – when to use it?”

  1. Dylan Wan said

    I just found a very good white paper on oracle.com: Bitmap Index vs. B-tree Index: Which and When?
    http://www.oracle.com/technology/pub/articles/sharma_indexes.html

  2. johnwu said

    Just in case you don’t have to use a database system but want to benefit from the best bitmap index around, you can try something called FastBit .

    Here is a quote from one of their publications:
    “Compared to BBC, a scheme well-known for its operational efficiency, WAH performs logical operations about 12 times faster.”

  3. johnwu said

    Looks like I did not get the url through. The FastBit web site is at http://sdm.lbl.gov/fastbit/ and the paper quoted is http://crd.lbl.gov/%7Ekewu/ps/LBNL-49627.html.
    The software is distributed from https://codeforge.lbl.gov/projects/fastbit/.
    Hope the URL get through this time around.

  4. Please explain Dynamic Bitmap Index in detail or give me some tutorial link.
    Thank You.

  5. which takes less space bitmap index or normal index?????????????????

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s