What is Bit Mapped Index

Bit Map Indexing is a technique commonly used in relational databases where the application uses binary coding in representing data. This technique was originally used for low cardinality data but recent applications like the Sybase IQ have used this technique efficiently.

The word cardinality is an SQL term to refer to the uniqueness of a data value in a particular column in a database table. Low cardinality means that the values in the data column of the data table are pretty common. These data may include gender, race, age, hair color or status flags and Boolean data. On the other hand, high cardinality data may refer to data in a column which are unique. These data may identification numbers, user names, email addresses, social security number.

A bit mapped index is a special type of index that executes queries by performing logical operations on the bit map. Generally, a bit mapped index is generated for one column of the database's table.

As an example, a let us take a look at the gender field in a students database. This column contains only tow values – male or female. If we use a bit mapped index for this, we may use 0 and 1 to denote the values of male and female. If I want to know all male students in a particular department within a large university with several campuses, I will only try to access the index instead of doing a full table scan. This can greatly speed up my search.

In fact, the three main reasons why professionals use bit mapped indexing technique when dealing with low cardinality data are performance, storage and maintainability.
In a performance test condition, it was found out that bit mapped index did a very impressive performance in execution times of some given queries by orders of magnitude.

Most queries that benefited from bit mapped indexes have WHERE clauses containing multiply predicates on columns with low cardinality. It was also found out that bit mapped indexes are very useful in doing very complex ad hoc queries which contain long WHERE clauses that involve low cardinality data.

In terms of storage, bit mapped index can incur only a small storage cost compared to the needs of the B-indexes and this means a big savings on companies. This can be especially true to many companies maintaining large data warehouses spread across several geographic locations.

But of course there is also a negative to using bit mapped indexing. When doing inserts and deletes on a table, using this indexing technique will automatically results in a wave of updates to all associated indexes. If the number of rows is very large and covered only by a single bitmap index entry, concurrent delete and insert activities can result in massive contention.

There are many other alternatives to bit mapped indexes in dealing with large databases with low cardinality data. A bit mapped index maybe the best alternative to the equally efficient B-Tree index in certain given conditions.

The best things to remember is that bit mapped indexes are typically very quick to build and tend to be small size although the size can dramatically vary with the distribution of data. Bit mapped index are generally beneficial when using queries that use several indexes at once but updating bit mapped columns can dramatically degrade the quality of indexes.

Despites the process and cons of using bit mapped index, some application tools are available to optimize the benefits of using this indexing technique. Some database vendors carry optimizers to improve performance of a database whatever indexing technique is being used.