What is a bitmap index? Provide a simple, easy to understand explanation and tutorial.

A bitmap index is a special type of index that is primarily used in the Oracle database. Here we will give a detailed explanation and tutorial of bitmap indexes so you can fully understand how they work and when it makes sense to use a bitmap index.

When does it make sense to use a bitmap index?

Bitmap indexes are meant to be used on low cardinality columns. A low cardinality column just means that the column has relatively few unique values. For example, a column called Sex which has only “Male” and “Female” as the two possible values is considered low cardinality because there are only two unique values in the column.

An example of a bitmap index

Let’s go through a more detailed example of a bitmap index. So, let’s say we have a table called People, where each row is a different person, and we have columns like Name, Address, etc. But let’s also say that inside the People table there is a column called SexualOrientation, and the three possible values are heterosexual, homosexual, and bisexual. In this case, if we create a bitmap index on the SexualOrientation column, then what exactly happens? Well, for each unique value in the SexualOrientation column, a separate index record will be created. So, there will be one index record for the “heterosexual” value, another index record for the “homosexual” value, and a third index record for the “bisexual” index record. It’s important to remember that all three of these index records will be a part of the bitmap index – we are not talking about separate bitmap indexes here, but one bitmap index that contains 3 different index records.

What is stored inside a bitmap index?

So, now we have 3 index records – one for each unique value in the SexualOrientation column. But, what’s inside each of those records? Well, each record will have the same number of bits as the number of rows in the table.

How much space does a bitmap index take?

So, let’s say that there are 1,000 rows in the People table. Then, each of these records will have roughly 1,000 bits – one for each row in the table. And the key point to understand here is that every bit corresponds to a row in the table. A binary value of ’1′ means that the particular index record has it’s the corresponding row set to the value that index record represents. A ’0′ means that the value represented by the index record is not set in that row’s column. What does that mean in plain English? Well, let’s go through a more concrete example.

So, let’s say that inside the People table the 10th row has the SexualOrientation column set to “heterosexual” and the 11th row has the SexualOrientation column set to “homosexual”. This means that the index record for “heterosexual” will have it’s 10th bit set to 1 and it’s 10th bit set to “0″, because the 10th row contains the value “heterosexual” – so the “1″ indicates that there is a match. The 0 indicates that there is no match, but the index record for homosexual will have a “1″ in the 11th row, and a 0 in the 10th row.

Why high cardinality columns are not good for bitmap indexes

A high cardinality bitmap index would not work because there would have to be a new data structure/index record for each unique value in the column(s), and if there are a lot of unique values then the index would take up way too much space and it would be very inefficient to have that index.

A bitmap index uses matrix algebra

When dealing with bitmap indexes, the RDBMS will actually use matrix algebra to find the rows that are being looked up.

Example of how to create a bitmap index

Here is the SQL that can be used to create a bitmap index:

CREATE BITMAP INDEX IX_PEOPLE_SEXUAL_ORIENTATION
ON PEOPLE (SEXUALORIENTATION);

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.



FOLLOW Varoon Sahgal, Author of ProgrammerInterviewon