Part 1  |  Part 2  |  Part 3

In recent articles, I have described the functionality of bitmap indexes, and the bitmap star transformation. In this article we move on to the bitmap join index an option just introduced in Oracle 9.

In the previous article in this short series on bitmap indexes, I described how ordinary bitmap indexes are used in the bitmap star transformation. In this article we look at the effect, and costs, of using the new bitmap join index in an attempt to make the process even more efficient.

Figure 1 shows us a simple example of the way in which several tables might be related in a query that Oracle would address through the bitmap star transformation.

Figure 1: Simple snowflake schema.

As we saw in my last article, the query represented by Figure 1 would be addressed by a two-stage process. First, Oracle would visit all the necessary outlying tables (the dimension tables and their parents) to collect a set of primary keys from each of the dimensions, which it could use to access the four bitmap indexes into the fact table.

After ANDing the four bitmaps, to locate the minimum set of relevant fact rows, Oracle would 'turn around' to revisit the dimension tables and their parents — possibly using a nested loop access path through the primary keys on the outlying tables.

Apparently, according to a whitepaper I found recently on Metalink, Oracle actually owns the copyright to some aspects of this extremely cute strategy.

It's fantastic - What's the Problem?

There are three possible inefficiencies in this strategy (which, I have to add, seem to be very small compared to the massive benefit that the technology can introduce).

First — if the queries reaching the system are typically about some attribute of a dimension, but never acquire data about that dimension, then we are adding work by travelling through the dimension and perhaps merging many bitmap index sections corresponding to the selected primary keys from that dimension.

Secondly — if the queries reaching the system are typically aimed at the parent tables (the outer layers of the snowflake), then we are doing a lot of work tracking back and forth through the dimension tables.

Finally — bitmap indexes on columns of higher "distinct cardinality" can be relatively large; which leads to a waste of buffer space loading them, and a waste of memory and CPU if we have to merge lots of small bitmap ranges (see my first article on bitmap indexes to find out why the myth about "bitmaps for low-cardinality columns is misleading").

So — what has Oracle got to offer those of us whose systems are described by the conditions above? The answer is bitmap join indexes.

What Is a Bitmap Join Index?

As its name suggests, this is a bitmap index, but an index that is described through a join query.

Amazingly, it is an index where the indexed values come from one table, but the bitmaps point to another table.

Let's clarify this with a simple concrete example. Figure 2 reproduces the SQL I used to build my first demonstration of a star transformation:

Figure 2: Part of a star (snowflake) schema.

Imagine now that I have observed that all the queries are about people who work in particular towns, and these towns are always referenced by name and not acquired by searching through attributes of the town. I may decide that the bitmap index on column (id_town_work) is sub-optimal, and should be replaced by a bitmap join index that allows a query to jump straight into the people table, bypassing the towns table completely. Figure 3 shows how I would define this index.

Figure 3: Creating a basic bitmap join index.

Imagine that I have also noticed that queries about where people live are always based on the name of the state they live in, and not on the name of the town they live in. So the bitmap index on column (id_town_home) is even less appropriate, and could be replaced by a bitmap join index that allows a query to jump straight into the people table, bypassing both the states and the towns tables completely. Figure 4 gives the definition for this index:

Figure 4: Creating a more subtle bitmap join index.

You will probably find that the index pe_work_id is the same size as the index it has replaced, but there is a chance that the PE_home_st_idx will be significantly smaller than the original PE_home_idx. However, the amount of space saved is extremely dependent on the data distribution and the typical number of (in this case) towns per state.

In a test case with 4,000,000 rows, 500 towns, and 17 states, with maximum scattering of data, the PE_home_st_idx index dropped from 12MB to 9MB so the saving was not tremendous. On the other hand, when I rigged the distribution of data to emulate the scenario of loading data one state at a time, the index sizes were 8MB and 700K respectively.

These tests, however, revealed an important issue. Even in the more dramatic space-saving case, the time to create the bitmap join index was much greater than the time taken to create the simple bitmap index.

The index creation statements took 12 minutes 24 seconds in one case, and four minutes 30 seconds in the other; compared to a base time of one minute 10 seconds for the simple index.

Remember, after all, that the index definition is a join of three tables. The execution path Oracle used to create the index appears in Figure 5.

Figure 5: Execution path for create index.

As you can see, this example hashes the two small tables and passes the larger table through them. We are not writing an intermediate hash result to disc and rehashing it, so most of the work must be due to the sort that takes place before the bitmap construction. Presumably this could be optimised somewhat by using larger amounts of memory, but it is an important point to test before you go live on a full-scale system.

At the end of the day, though, the most important question is whether or not these indexes work. So let's execute a query for people, searching on home state, and work town (refer to Figure 6 for the test query, and its execution plan).

The query very specifically selects columns only from the people table. Note how the execution plan doesn't reference the towns table or the states table at all. It factors these out completely and resolves the rows required by the query purely through the two bitmap join indexes.

The query:

Figure 6: Querying through a bitmap join index.

There is a little oddity that may cause confusion when you run your favourite bit of SQL to describe these indexes. Try executing:

select table_name, column_name
from user_ind_columns
where index_name = 'PE_WORK_IDX';

The results come back as:

Oracle is telling you the truth - the index on the people table is an index on the towns.name column. But if you've got code that assumes the table_name in user_ind_columns always matches the table_name in user_indexes, you will find that your reports 'lose" bitmap join indexes. (In passing, the view user_indexes will have the value YES in the column join_index for any bitmap join indexes).

Issues

The mechanism is not perfect — even though it may offer significant benefits in special cases.

"Join back" still takes place — even if you think it should be unnecessary. For example, if you changed the query in Figure 6 to select the home state, and the work town, (the two columns actually stored in the index, and supplied in the where clause) Oracle would still join back through all the tables to report these values. Of course, since the main benefit comes from reducing the cost of getting into the fact (people) table, it is possible that this little excess will be pretty irrelevant in most cases.

More importantly, you will recall my warning in the previous articles about the dangers of mixing bitmap indexes and data updates. This problem is even more significant in the case of bitmap join indexes. Try inserting a single row into the people table with sql_trace set to true, and you will find some surprising recursive SQL going on behind the scenes — refer to Figure 7 for one of the two strange SQL statements that take place as part of this single row insert.

Figure 7: A recursive update to a bitmap join indexes.

There are three new things in this one statement alone. First, the command upd_joinindex, which explain plan cannot yet cope with but which is known to Oracle as the operation "bitmap join index update." Second, the undocumented hint cardinality(), which is telling the cost based-optimizer to assume that the table aliased as T26763 will return exactly one row. And finally, you will notice that this SQL is nearly a copy of our definition of index PE_home_st_idx, but with the addition of table called SYS.L$15 — what is this strange table?

A little digging (with the help of SQL_trace) demonstrates the fact that every time you create a bitmap join index, Oracle needs at least a couple of global temporary tables in the SYS schema to support that index. In fact, there will be one global temporary table for each table referenced in the query that defines the index.

These global temporary tables appear with names like L$nnn, and are declared as "on commit preserve rows." You don't have to worry about space being used in system tablespace, of course, as global temporary tables allocate space in the user's temporary tablespace only as needed. Unfortunately, if you drop the index (as you may decide to do whenever applying a batch update), Oracle does not seem to drop all the global temporary table definitions. On the surface, this seems to be merely a bit of a nuisance, and not much of a threat - however, you may, like me, wonder what impact this might have on the data dictionary if you are dropping and recreating bitmap join indexes on numerous tables on a daily basis.

If you pursue bitmap join indexes further through the use of SQL_trace — and it is a good idea to do so before you put them into production — you will also see accesses to tables sys.log$, sys.jijoin$, sys.jifrefreshsql$, and sequence sys.log$sequence. These are objects that are part of the infrastructure for maintaining the bitmap indexes. jirefreshsql$, for example, holds all the pieces of SQL text that might be used to update a bitmap join index when you change data in the underlying tables (you need a different piece of SQL for each table referenced in the index definition). Be warned every time that Oracle gives you a new, subtle, piece of functionality: there is usually a price to pay somewhere. It is best to know something about the price before you adopt the functionality.

Conclusion

This article only scratches the surface of how you may make use of bitmap join indexes. It hasn't touched on issues with partitioned tables, or on indexes that include columns from multiple tables, or many of the other areas which are worthy of careful investigation. However, it has highlighted four key points.

• Bitmap join indexes may, in special cases, reduce index sizes and CPU consumption quite significantly at query time.
• Bitmap join indexes may take much more time to build than similar simple bitmap indexes. Make sure it's worth the cost.
• The overheads involved when you modify data covered by bitmap join indexes can be very large — the indexes should almost certainly be dropped/invalidated and recreated/rebuilt as part of any update process — but watch out for the problem in the previous paragraph.
• There are still some anomalies related to Oracle's handling of bitmap join indexes, particularly the clean-up process after they have been dropped.

References

Oracle 9i Release 2 Datawarehousing Guide, Chapter 6.

--

Jonathan Lewis is a freelance consultant with more than 17 years' experience in Oracle. He specialises in physical database design and the strategic use of the Oracle database engine, is author of Practical Oracle 8i - Building Efficient Databases published by Addison-Wesley, and is one of the best-known speakers on the UK Oracle circuit. Further details of his published papers, tutorials, and seminars can be found at www.jlcomp.demon.co.uk, which also hosts The Co-operative Oracle Users' FAQ for the Oracle-related Usenet newsgroups.