Oracle Database Tips by Donald Burleson

Bitmapped Index

The bit mapped index  uses a bitmap instead of a b-tree to represent the data/rowid pairs.  A bit mapped index is very fast at locating data; however, it is very slow at updating or inserting index values.  For this reason, bitmapped indexes are used mostly on static data such as in a data warehouse.  A bitmapped index functions best on low cardinality columns, columns with a small number of distinct values.  The bitmap created for the index is as wide as the cardinality and as long and the number of rows. 

If our publishing company divided its operations into regions, East, West, North, and South, the regions column would have four distinct values or a cardinality of four.  If the table contained 100 rows, then a bitmap on region would be four wide and 100 long.  But since we are talking about computer bits that are very small, this index would be very small also.  Remember, a kilobyte is a 1028 bytes or 8224 bits. 

Let's look at what the bitmapped index would look like.  Each value is a TRUE or FALSE.  So, if the bit map was set up as E, W, N, S, then an East value would be 1,0,0,0.  A North value would be 0,0,1,0.  Notice that the correct value is a one and the incorrect values are zeroes.  With the corresponding rowid, our bit map would look like Table 5.1 below.

The rowids I used are just examples.  rowids are actually large alphanumeric numbers.  This example looks simple enough.  If I had 1000 rows, then my bitmap would be five columns wide and 1000 rows long.  What makes bitmaps so fast is that comparing ones and zeroes is what microprocessors do best.  In fact, they can compare multiple values at the same time, some as many as 64 values at a time.  To search the bitmap, the database uses the WHERE clause filters to create a mask.  In the query below, I want all rows from region West.

select
  office_num,
  sales
from
  year_2005_sales
where
  region = 'WEST'; 

Since I am looking for West, the database creates the mask 1,0,0,0.  Now, I can use the mask and run down the bitmap using the AND/OR function to compare the mask with the row values.  Those that return TRUE, we grab the rowids (00100) and access the table, retrieving the rows.  One of the unique abilities of the bitmapped index is that multiple indexes can be used by one query.  It is the only type of index that the Oracle database will use more that one index to access a table in a single query.  The reason is that the bitmapped indexes can be combined, and one mask used to scan multiple indexes at the same time.  

select
  office_num,
  sales
from
  all_year_sales
where
  region = "WEST"
and
  year   = 2005; 

Here, we have two columns to filter by, and both have a bitmapped index.  Since the bitmaps have the same number of rows, they can be compared directly.  In the first example, comparing the value mask to the index resulted in a one or zero (TRUE or FALSE).  I can compare multiple indexes, place the results side by side, and compare them to produce a final result. 

Lastly, bitmapped indexes can be created on the join of two tables.  Queries that join the same tables can use the index to filter both tables at the join.

create bitmap index store_sales on
  sales (store_key)
from
  sales join store using (store_key); 

This creates a bitmap of the table join.  It is the same as building an index on the store_key of the two tables and then joining them.

So, bitmap indexes have two real advantages; they are very fast, and more than one can be used to satisfy a query.  But, they also have problems, INSERTs/UPDATEs take a performance hit when bitmap indexes are used, and they need to be used on low cardinality columns.  So, bitmapped indexes are most useful with static data or data warehouses.

Get the Complete Oracle SQL Tuning Information  The landmark book "Advanced Oracle SQL Tuning  The Definitive Reference"  is filled with valuable information on Oracle SQL Tuning. This book includes scripts and tools to hypercharge Oracle 11g performance and you can buy it for 30% off directly from the publisher.