Myths on bitmap indexes

Although bitmap indexes are already available in Oracle 8i or even before (some sources even say 7.3!!!), they are still surrounded by many myths. Time for some clearing up. And believe it or not, every single myth mentioned here I heard many times in several projects.

First, I would like to point out that these are my personal experiences on specific projects and that they everyone’s experience with what is said ‘in the field’ may be different. It possibly is. And that brings me to the second point:

Secondly, in no way I claim to hold all the wisdom on this subject. I noticed that there are a lot of half-true opinions and ‘heard-of’ stories about bitmap index use (and other Oracle features, in fact). I will not pretend to tell the definitive story on Bitmap Indexes. However, my personal experiences can be useful to trigger you to do some investigation
in your specific environment as well; who knows what unexpected pleasure you
can derive from using Bitmap Indexes. At the very least my findings can stir up
some discussion with others bringing their experiences to the table.

Some people (one of them being Jonathan Lewis) pointed out that I was not entirely correct (or thorough) in my statements about bitmap indexes. He is surely right about that. So I took the liberty of rewriting part of this blog. I’m sure that it still doesn’t cover every case, so be warned. The only thing I ‘m trying to say is: check everything you read (including everything I’ve written here) or hear, on the internet, in classroom training events or during  conference presentations . Test it in your own specific case, in your application on your database version. There is no general rule of thumbs. Do not make assumptions, especially not if they are based on bold statements written down on the internet.

Myth 1 – Bitmap indexes take up a lot more space than B-Tree indexes.

mydb&gt; create table bm_test( datum date, ind1 varchar2(1));<br />Tabel is aangemaakt.

mydb&gt; desc bm_test<br />&nbsp;Naam&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Null?&nbsp;&nbsp;&nbsp; Type<br />&nbsp;----------------------------------------- -------- ----------------------------

&nbsp;DATUM&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; DATE<br />&nbsp;IND1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; VARCHAR2(1)

mydb> create index btr1 on bm_test( ind1 );

Index is aangemaakt.

mydb&gt; select segment_name, bytes, blocks, extents<br />&nbsp; 2&nbsp; from user_segments where segment_type = 'INDEX';

SEGMENT_NAME&nbsp;&nbsp;&nbsp;&nbsp; BYTES&nbsp;&nbsp;&nbsp;&nbsp; BLOCKS&nbsp;&nbsp;&nbsp; EXTENTS<br />--------------------------------- ---------- ----------<br />BTR1&nbsp;&nbsp;&nbsp; &nbsp;&nbsp; 1228800&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 150&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 30

mydb> drop index btr1;

Index is verwijderd.<br />

mydb> create bitmap index bmi1 on bm_test( ind1 );

Index is aangemaakt.

mydb&gt; select segment_name, bytes, blocks, extents<br />&nbsp; 2&nbsp; from user_segments where segment_type = 'INDEX';

SEGMENT_NAME&nbsp;&nbsp;&nbsp;&nbsp; BYTES&nbsp;&nbsp;&nbsp;&nbsp; BLOCKS&nbsp;&nbsp;&nbsp; EXTENTS<br /><br />-------------------------- ---------- ----------<br />BMI1&nbsp;&nbsp;&nbsp;&nbsp; 40960&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 5&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1

1 rij is geselecteerd.

There, 41 kB for the bitmap index compared to 1.2 MB for a B-tree, or 5 blocks vs 150 blocks. Keep in mind that the space occupied by bm indexes is related to many factors. In your environment, results may be entirely different.

Myth 2 – Bitmap indexes are only suitable for data warehouses

 I’m still not sure what is the logic behind this thesis, because it is usually not followed by any explanation. I can imagine that for example usage flags are often queried and have extreme poor performance with b-tree indexes. Check the explain plans:

use of btree index on column with values ‘J’ and ‘N’

Execution plan<br />----------------------------------------------------------<br />&nbsp;&nbsp; 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; SELECT STATEMENT Optimizer=CHOOSE (Cost=19 Card=13415 Bytes=<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 134150)

&nbsp;&nbsp; 1&nbsp;&nbsp;&nbsp; 0&nbsp;&nbsp; TABLE ACCESS (FULL) OF 'BM_TEST' (TABLE) (Cost=19 Card=134<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 15 Bytes=134150)

Statistics<br />----------------------------------------------------------<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1&nbsp; recursive calls<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0&nbsp; db block gets<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 65&nbsp; consistent gets<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 59&nbsp; physical reads<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0&nbsp; redo size<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 574&nbsp; bytes sent via SQL*Net to client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 283&nbsp; bytes received via SQL*Net from client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3&nbsp; SQL*Net roundtrips to/from client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0&nbsp; sorts (memory)<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0&nbsp; sorts (disk)<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 22&nbsp; rows processed

use of bitmap index on same column

Execution plan<br />----------------------------------------------------------<br />&nbsp;&nbsp; 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; SELECT STATEMENT Optimizer=CHOOSE (Cost=5 Card=24 Bytes=240)<br />&nbsp;&nbsp; 1&nbsp;&nbsp;&nbsp; 0&nbsp;&nbsp; TABLE ACCESS (BY INDEX ROWID) OF 'BM_TEST' (TABLE) (Cost=5<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Card=24 Bytes=240)

&nbsp;&nbsp; 2&nbsp;&nbsp;&nbsp; 1&nbsp;&nbsp;&nbsp;&nbsp; BITMAP CONVERSION (TO ROWIDS)<br />&nbsp;&nbsp; 3&nbsp;&nbsp;&nbsp; 2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; BITMAP INDEX (SINGLE VALUE) OF 'BMI1' (INDEX (BITMAP))

Statistics<br />----------------------------------------------------------<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 136&nbsp; recursive calls<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0&nbsp; db block gets<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 26&nbsp; consistent gets<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3&nbsp; physical reads<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0&nbsp; redo size<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 595&nbsp; bytes sent via SQL*Net to client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 283&nbsp; bytes received via SQL*Net from client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3&nbsp; SQL*Net roundtrips to/from client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 6&nbsp; sorts (memory)<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0&nbsp; sorts (disk)<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 22&nbsp; rows processed

Myth 3 – Bitmap indexes have slow performance on DML actions

This might me one of the origins for Myth 2. I’ve tried some updates on those 80K records, but found no proof this is a real problem. I did some timing experiments (which are not the most trustworthy, I know!), and in some cases the update on a table with bitmap was even twice as fast as with a b-tree. To be honest, I’m not too surprised with the amount of blocks used in mind. Especially look at the difference in Redo size and recursive calls:

mydb> create index btr1 on bm_tst( ind1) ;

Index is aangemaakt.

mydb> update bm_test set ind1 ='X';

80487 rijen zijn bijgewerkt.

Verstreken: 00:00:19.03

Execution plan<br />----------------------------------------------------------<br />&nbsp;&nbsp; 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; UPDATE STATEMENT Optimizer=CHOOSE (Cost=51 Card=80487 Bytes=<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 160974)

&nbsp;&nbsp; 1&nbsp;&nbsp;&nbsp; 0&nbsp;&nbsp; UPDATE OF 'BM_TEST'<br />&nbsp;&nbsp; 2&nbsp;&nbsp;&nbsp; 1&nbsp;&nbsp;&nbsp;&nbsp; TABLE ACCESS (FULL) OF 'BM_TEST' (TABLE) (Cost=51 Card=8<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0487 Bytes=160974)

Statistics<br />----------------------------------------------------------<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3190&nbsp; recursive calls<br />&nbsp;&nbsp;&nbsp;&nbsp; 410208&nbsp; db block gets<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1319&nbsp; consistent gets<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 365&nbsp; physical reads<br />&nbsp;&nbsp; 57035576&nbsp; redo size<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 475&nbsp; bytes sent via SQL*Net to client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 445&nbsp; bytes received via SQL*Net from client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 4&nbsp; SQL*Net roundtrips to/from client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 42&nbsp; sorts (memory)<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0&nbsp; sorts (disk)<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 80487&nbsp; rows processed

<br />mydb&gt; drop index btr1;

Index is verwijderd.

mydb> create bitmap index bmi1 on bm_test( ind1);

Index is aangemaakt.

mydb> update bm_test set ind1 ='Y';

80487 rijen zijn bijgewerkt.

Verstreken: 00:00:11.18

Execution plan<br />----------------------------------------------------------<br />&nbsp;&nbsp; 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; UPDATE STATEMENT Optimizer=CHOOSE (Cost=3 Card=80487 Bytes=1<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 60974)

&nbsp;&nbsp; 1&nbsp;&nbsp;&nbsp; 0&nbsp;&nbsp; UPDATE OF 'BM_TEST'<br />&nbsp;&nbsp; 2&nbsp;&nbsp;&nbsp; 1&nbsp;&nbsp;&nbsp;&nbsp; TABLE ACCESS (BY INDEX ROWID) OF 'BM_TEST' (TABLE) (Cost<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =3 Card=80487 Bytes=160974)

&nbsp;&nbsp; 3&nbsp;&nbsp;&nbsp; 2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; BITMAP CONVERSION (TO ROWIDS)<br />&nbsp;&nbsp; 4&nbsp;&nbsp;&nbsp; 3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; BITMAP INDEX (FULL SCAN) OF 'BMI1' (INDEX (BITMAP))

Statistics<br />----------------------------------------------------------<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 50&nbsp; recursive calls<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 88282&nbsp; db block gets<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 212&nbsp; consistent gets<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 965&nbsp; physical reads<br />&nbsp;&nbsp; 20102176&nbsp; redo size<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 474&nbsp; bytes sent via SQL*Net to client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 445&nbsp; bytes received via SQL*Net from client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 4&nbsp; SQL*Net roundtrips to/from client<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2&nbsp; sorts (memory)<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1&nbsp; sorts (disk)<br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 80487&nbsp; rows processed

There is a big catch here though, and I think that is exactly where the thesis ‘bm-indexes are slow’ comes from. When you do an update on a bitmap index, all the records in your table which have the same value will be locked untill you commit or rollback. Mind you, only the records that have the same key value. So not the entire table as is sometimes assumed. Also, this will occur only when you update the key value column, not when you update another column in the table.

What does all this say? Again, not much more than that it is crucial to know what your application does to (or with) your data, and what the and benefits and risks of every type of index is (or broader, every feature in the Oracle database). Is there a lot of DML on these low-cardinality columns? Orderstatus fields might be changed often, gender fields probably not (unless you’re writing software for a gender-change clinic). This is something few people can accurately predict beforehand.

Conclusion: test, test, test, do not make assumptions.