Oracle9i has added the bitmap join index to its mind-boggling array of table join methods. This new table access method requires that you create an index that performs the join at index creation time and that creates a bitmap index of the keys used in the join. But unlike most relational database indexes, the indexed columns don’t reside in the table. Oracle has revolutionized index creation by allowing a WHERE clause to be included in the index creation syntax. This feature revolutionizes the way relational tables are accessed via SQL.

The bitmap join index is extremely useful for table joins that involve low-cardinality columns (e.g., columns with less than 300 distinct values). However, bitmap join indexes aren’t useful in all cases. You shouldn’t use them for OLTP databases because of the high overhead associated with updating bitmap indexes. Let’s take a closer look at how this type of index works.

How bitmap join indexes work
To illustrate bitmap join indexes, I’ll use a simple example, a many-to-many relationship where we have parts and suppliers with an inventory table serving as the junction for the many-to-many relationship. Each part has many suppliers and each supplier provides many parts (Figure A).

Figure A
A many-to-many Oracle table relationship

For this example, I’ll assume the database has 300 types of parts and the suppliers provide parts in all 50 states. So there are 50 distinct values in the State column and only 300 distinct values in the Part_type column.

Note in Figure A that we create an index on the Inventory using columns contained in the Supplier and Part tables. The idea behind a bitmap join index is to pre-join the low cardinality columns, making the overall join faster.

It is well known that bitmap indexes can improve the performance of Oracle9i queries where the predicates involve the low cardinality columns, but this technique has never been employed in cases where the low cardinality columns reside in a foreign table.

To create a bitmap join index, issue the following Oracle DDL: (Note the inclusion of the FROM and WHERE clauses inside the CREATE INDEX syntax.)
create bitmap index
inventory( parts.part_type, supplier.state)
inventory i,parts p,supplier s
i.part_id=p.part_id and i.supplier_id=p.part_id;

Bitmap join indexes in action
To see how bitmap join indexes work, look at this example of a SQL query. Let’s suppose you want a list of all suppliers of pistons in North Carolina. To get that list, you would use this query:
Select supplier_name
From parts
natural join inventory
natural join suppliers
where part_type = ‘piston’ and state=’nc’;

Prior to Oracle9i, this SQL query would be serviced by a nested loop join or hash join of all three tables. With a bitmap join index, the index has pre-joined the tables, and the query can quickly retrieve a row ID list of matching table rows in all three tables.

Note that this bitmap join index specified the join criteria for the three tables and created a bitmap index on the junction table (Inventory) with the Part_type and State keys (Figure A).

Oracle benchmarks claim that bitmap join indexes can run a query more than eight times faster than traditional indexing methods. However, this speed improvement is dependent upon many factors, and the bitmap join is not a panacea. Some restrictions on using the bitmap join index 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 rebuilt each evening about the daily batch load jobs. This means that bitmap join indexes are useful only for Oracle data warehouses that remain read-only during the processing day.

Remember: Bitmap join indexes can tremendously speed up specific data warehouse queries but at the expense of pre-joining the tables at bitmap index creation time. You must also be concerned about high-volume updates. Bitmap indexes are notoriously slow to change when the table data changes, and this can severely slow down INSERT and UPDATE DML against the target tables.

Exclusions for bitmap join indexes
There are also restrictions on when the SQL optimizer is allowed to invoke a bitmap join index. For queries that have additional criteria in the WHERE clause that doesn’t appear in the bitmap join index, Oracle9i will be unable to use this index to service the query. For example, the following query will not use the bitmap join index:
Select supplier_name
From parts
natural join inventory
natural join suppliers
where part_type = ‘piston’and state = ‘nc’ and part_color = ‘yellow’;

Using bitmap join indexes requires planning
Oracle9i has introduced extremely sophisticated execution plan features that can dramatically improve query performance, but these features cannot be used automatically. The Oracle9i professional’s challenge is to understand these new indexing features, analyze the trade-offs of additional indexing, and judge when the new features can be used to speed queries.