The Bitmap Conspiracy

(with apologies to Robert Ludlum and Eric Van Lustbader)

The Bitmap Betrayal (Introduction)

Oracle performance tuning is an excellent source of myths. The very best ones have a group of adherents who continue to support the myth even when presented with counter-examples. Who’s heard of these?

• Joins are faster than sub-queries
• Sub-queries are faster than joins
• Full Table Scans are bad

Those ones have been around as long as I can remember. Probably the single greatest concentration of Oracle performance tuning myths centres on Bitmap Indexes. Are these familiar?

• Bitmap indexes are good for low-cardinality columns, whereas B-Tree indexes are good for high-cardinality columns.
• Bitmap indexes are slow to update.
• Bitmap indexes don't support concurrent updates.

As with any good myth, there is an element of truth in these statements that makes them even more powerful. If you were being kind (I’m not), you might just call them “Generalisations” rather than Myths.

Our best defence against myths is the whole truth ... supported by proof. So in this article I will describe what Bitmap Indexes are, how they *actually* work and then set about breaking some of the myths many people hold to be true.

This is a long article, so I have broken it into 4 sections:

Part 1 – The Bitmap Identity (What is a Bitmap Index?)

Without assuming any knowledge of Bitmap Indexes, we start from basics and build up.

Part 2 – The Bitmap Supremacy (What is the structure of a Bitmap Index?)

How do Bitmap Indexes achieve things that B-Tree indexes cannot? Learn about the underlying physical structure of Bitmap Indexes; this allows us to propose and test new hypotheses on their behaviours and capabilities.

Part 3 – The Bitmap Dominion (What can Bitmap Indexes do?)

Discover how Oracle translates WHERE predicates into bitmap access paths to retrieve your data.

Part 4 – The Bitmap Legacy (Bitmap Index myths exposed)

We test some of the common Bitmap Index myths and learn where they are true where they fail.

---

Conclusion

As I draft all 4 parts of this article in MS-Word it runs to 33 pages including appendices. If I knew it would turn out this long I probably wouldn’t have started. It is easily the longest treatment of Bitmap Indexes I have seen, so hopefully it is authoritative and complete if not exactly concise.

If we could summarise the discoveries over the four part journey:

• Bitmap indexes create a bitmap for each distinct value in the indexed column, including NULL.
• The bitmaps are compressed, broken into Pieces and the Pieces arranged in a searchable B-Tree structure.
• A single Bitmap index can be used in isolation (especially for COUNT queries), but they are most powerful when many indexes are combined in AND and OR conditions.
• Bitmap indexes will not improve non-selective queries on low-cardinality columns, although you can bitmap index low-cardinality columns so that queries become selective when used in combination.
• Transactional (single-row) statements on bitmap indexed tables carry performance overheads that make high-volume data loads problematic. These overheads can be mitigated using set-based DML to manipulate many rows in a single statement.
• DML on bitmap indexed will lock many rows, not just those being updated. This leads to locking and deadlocking issues when DML is performed concurrently. The only types of DML concurrency that can be safely achieved are single-row commits (very slow – see previous point) and single-session Parallel DML.