Alternatives to Oracle Fine Grained Access Control Bitmap join indexes   Donald K. Burleson

Oracle9i has introduced a new method to create speed join queries against very large data warehouse tables.  This new method is called the bitmap join index, and this new table access method required the creation of an index that performs the join at index creation time and creates a bitmap index of the keys that are used in the join.

For our example, we will use a many-to-many relationship where we have parts and suppliers.  Each part has many suppliers and each supplier provides many parts

In this example, the database has 200 types of parts and the suppliers provide parts in all 50 states. The idea behind a bitmap join index is to pre-join the low cardinality columns together, thereby making the overall join faster:

To create a bitmap join index we issue the following SQL.  Note the inclusion of the FROM and WHERE clauses inside the CREATE INDEX syntax.

create bitmap index

   part_suppliers_state
on

   inventory( parts.part_type, supplier.state)
from

   inventory i,

   parts     p,

   supplier  s
where

   i.part_id = p.part_id

and
   i.supplier_id = p.part_id;

While b-tree indexes are used in the standard junction records, we can improve the performance of Oracle9i queries where the predicates involve the low cardinality columns.  For example, look at the query below where we want a list of all suppliers of pistons in North Carolina:

select

   supplier_name

from

   parts

natural join

   inventory

natural join

   suppliers

where

   part_type = ‘piston’

and

   state = ‘nc’

;

Prior to Oracle9i, this query would require a nested loop join or hash join of all three tables.  In Oracle9i, we can pre-join these tables based on the low cardinality columns.

For queries that have additional criteria in the WHERE clause that does not appear in the bitmap join index, Oracle9i will be unable to use this index to service the query. 

While Oracle markets this new feature with great fanfare, the bitmap join index is only useful for table joins that involve low-cardinality columns (e.g. columns with less than 300 distinct values).  Bitmap join indexes are also not useful for OLTP databases because of the high overhead associated with updating bitmap indexes.

Oracle claims that this indexing method results in more than 8x improvement in table joins in cases where all of the query data resides inside the index.  However, this claim is dependent upon many factors, and the bitmap join is not a panacea.  In many cases the traditional hash join or nested loop join may out-perform a bitmap join.  Some limitations of the bitmap join index join include:

• The indexed columns must be of low cardinality – usually with less than 300 distinct values

• The query must not have any references in the WHERE clause to data columns that are not contained in the index.

• The overhead when updating bitmap join indexes is substantial.  For practical use, bitmap join indexes are dropped and re-built each evening about the daily batch load jobs.  Hence bitmap join indexes are only useful for Oracle data warehouses that remain read-only during the processing day.

In sum, bitmap join indexes will tremendously speed-up specific data warehouse queries, but at the expense of pre-joining the tables at bitmap index creation time.

If you like Oracle tuning, you might enjoy my latest book “Oracle Tuning: The Definitive Reference” by Rampant TechPress.  It’s only $41.95 (I don’t think it is right to charge a fortune for books!) and you can buy it right now at this link:

Copyright © 1996 -  2009 by Burleson Enterprises, Inc. All rights reserved.

Oracle® is the registered trademark of Oracle Corporation.