Index Techniques   «Prev 

How to use bitmapped Indexes to speed up Queries

The purpose of an index is to provide pointers to the rows in a table that contain a given key value. In a regular index, this is achieved by storing a list of rowids for each key corresponding to the rows with that key value. In a bitmap index, a bitmap for each key value is used instead of a list of rowids. Each bit in the bitmap corresponds to a possible rowid, and if the bit is set, it means that the row with the corresponding rowid contains the key value. A mapping function converts the bit position to an actual rowid, so the bitmap index provides the same functionality as a regular index even though it uses a different representation internally. If the number of different key values is small, bitmap indexes are very space efficient. Bitmap indexes are most effective for queries that contain multiple conditions in the WHERE clause. Rows that satisfy some, but not all conditions are filtered out before the table itself is accessed. This improves response time, often dramatically.

1) The query specifies two low cardinality columns in the WHERE clause, region and type.
SELECT customer_name
FROM CUSTOMER WHERE 
region = 'East'
AND 
type = 'Partnership'

2) Oracle scans the region bitmap, quickly building a list of ROWID's for all rows in the East region.

3) Oracle scans the type bitmapped index and quickly builds a list of ROWID'S for all Partnerships.

4) Oracle then sorts these two lists of ROWID's and returns rows where the ROW ID appears in both ROWID lists.