Normally in a btree, there is a one-to-one relationship between an index entry and a row: an entry points to a row. Indexes should be selective in general.
With Bitmap Indexes, a single entry uses a bitmap to point to many rows simultaneously. Bitmap indexes should not be selective.
Values that have fewer than three distinct values can see dramatic performance improvements by utilizing the bitmapped index technique.
Bitmap indexes provide set-based processing within the database, allowing to use very fast methods for set operations such as AND, OR, MINUS and COUNT.
They are :
Consider :
This might be a good candidate for a bitmap index if, for example, you need to frequently count how many rows have a value of Y.
That is not to say that a bitmap index on a column with 1,000 distinct values in that same table would not be valid. It certainly can be !
Bitmap indexes are most appropriate on low distinct cardinality data, i.e. data with relatively few discrete values when compared to the cardinality of the entire set.
Example :
Number of records in the resultset | Distinct Number | Percent | Low Cardinality |
---|---|---|---|
100 | 2 | 0.02 | YES |
2 | 2 | 1.00 | NO |
10,000,000 | 100,000 | 0.01 | YES |
The last example probably would not be candidates for a having Index - Btree structure (Balanced Tree) indexes, as each of the values would tend to retrieve an extremely large percentage of the table.
The reason is that a single bitmap index key entry points to many rows.
If a session modifies the indexed data, then all of the rows that index entry points are effectively locked in most case. Oracle cannot lock an individual bit in a bitmap index entry; it locks the entire bitmap index entry. Any other modifications that need to update the same bitmap index entry will be locked out.
Bitmap indexes are useful when you have query :
select count(*)
from T
where gender = 'M'
and location in ( 1, 10, 30 )
and age_group = '41 and over';
select *
from T
where
( ( gender = 'M' and location = 20 )
or ( gender = 'F' and location = 22 ) )
and age_group = '18 and under';
select count(*) from t where location in (11,20,30);
select count(*) from t where age_group = '41' and gender = 'F';
With btree, you will need large concatenated btree indexes on :
To reduce the amount of data being searched, other permutations might be reasonable as well to decrease the size of the index structure being scanned but this is ignoring the fact that a btree index on such low cardinality data is not a good idea.
Value/Row | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
ANALYST | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
CLERK | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
MANAGER | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
PRESIDENT | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
SALESMAN | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
We can see that :
If we wanted to count the rows that have the value MANAGER, the bitmap index would do this very rapidly.
Example on Oracle.
<code sql>
nico@ORCL>create BITMAP index job_idx on emp(job);
Index created.
nico@ORCL>select count(*) from emp;
Execution Plan
---------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Cost (%CPU)| Time |
---------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 1 (0)| 00:00:01 |
| 1 | SORT AGGREGATE | | 1 | | |
| 2 | BITMAP CONVERSION COUNT | | 14 | 1 (0)| 00:00:01 |
| 3 | BITMAP INDEX FAST FULL SCAN| JOB_IDX | | | |
---------------------------------------------------------------------------------
Below the bitmap index comes into play. With three small indexes, one on each of the individual columns, you will be able to satisfy all the previous predicates with the use of Bitwise operation such as :
Example Oracle
nico@ORCL>select *
2 from t
3 where ( ( gender = 'M' and location = 20 )
4 or ( gender = 'F' and location = 22 ))
5 and age_group = '18 and under';
Execution Plan
------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 501 | 16533 | 79 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID | T | 501 | 16533 | 79 (0)| 00:00:01 |
| 2 | BITMAP CONVERSION TO ROWIDS | | | | | |
| 3 | BITMAP AND | | | | | | <-----Here, BITMAP AND
|* 4 | BITMAP INDEX SINGLE VALUE | AGE_GROUP_IDX | | | | |
| 5 | BITMAP OR | | | | | | <-----Here, BITMAP OR
| 6 | BITMAP AND | | | | | | <-----Here, BITMAP AND
|* 7 | BITMAP INDEX SINGLE VALUE| LOCATION_IDX | | | | |
|* 8 | BITMAP INDEX SINGLE VALUE| GENDER_IDX | | | | |
| 9 | BITMAP AND | | | | | | <-----Here, BITMAP AND
|* 10 | BITMAP INDEX SINGLE VALUE| GENDER_IDX | | | | |
|* 11 | BITMAP INDEX SINGLE VALUE| LOCATION_IDX | | | | |
------------------------------------------------------------------------------------------------
Even if we wanted to find all the rows such that the JOB was CLERK or MANAGER, we would simply combine their bitmaps from the index.
Value/Row | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
ANALYST | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
CLERK | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
CLERK or MANAGER | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
Example on Oracle:
nico@ORCL>select count(*) from emp where job = 'CLERK' or job = 'MANAGER';
Execution Plan
-----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 6 | 1 (0)| 00:00:01 |
| 1 | SORT AGGREGATE | | 1 | 6 | | |
| 2 | BITMAP CONVERSION COUNT | | 7 | 42 | 1 (0)| 00:00:01 |
|* 3 | BITMAP INDEX FAST FULL SCAN| JOB_IDX | | | | |
-----------------------------------------------------------------------------------------