Oracle9i 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
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=s.supplier_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).
Testing shows 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.