Oracle Database - Bitmap Indexes

Normally in a B*Tree indexes, 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.

They are :

• appropriate for highly repetitive data (data with a few distinct values relative to the total number of rows in the table) that is mostly read-only.
• inappropriate for OLTP system cause of the concurrency-related issue (where data is frequently updated by many concurrent sessions)

Consider :

• a column that takes on three possible value Y, N, and null
• in a table of 1 million rows.

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.

Example :

The last example probably would not be candidates for a having B*Tree indexes indexes, as each of the values would tend to retrieve an extremely large percentage of the table.

nico@ORCL>create BITMAP INDEX job_idx ON emp(job);
 
INDEX created.

We can see that :

• rows 8, 10 and 13 have the value ANALYST
• rows 4, 6 and 7 have the value MANAGER
• ….
• no rows are null (bitmap index store null entries)

If we wanted to count the rows that have the value MANAGER, the bitmap index would do this very rapidly.

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 |       |            |          |
---------------------------------------------------------------------------------

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.

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 |       |       |            |          |
-----------------------------------------------------------------------------------------

nico@ORCL>select * FROM emp WHERE job = 'CLERK' OR job = 'MANAGER';
 
Execution Plan
-----------------------------------------------------------------------------------------
| Id  | Operation                     | Name    | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT              |         |     7 |   609 |     2   (0)| 00:00:01 |
|   1 |  INLIST ITERATOR              |         |       |       |            |          |
|   2 |   TABLE ACCESS BY INDEX ROWID | EMP     |     7 |   609 |     2   (0)| 00:00:01 |
|   3 |    BITMAP CONVERSION TO ROWIDS|         |       |       |            |          |  <-------- Here
|*  4 |     BITMAP INDEX SINGLE VALUE | JOB_IDX |       |       |            |          |
-----------------------------------------------------------------------------------------

We need for this query to get to the table. Here, Oracle will apply a function to turn the fact that i'th bit is on in a bitmap, into a rowid that can be used to access the table.

Bitmap indexes are useful when you have query :

• that reference many columns in an ad hoc fashion
• produce aggregation such as COUNT

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 B*Tree indexes, you will need large concatenated B*Tree indexes indexes on :

• GENDER, LOCATION, AGE_GROUP for queries that use all three, or GENDER WITH LOCATION, or GENDER alone
• LOCATION, AGE_GROUP for queries that use LOCATION and AGE_GROUP or LOCATION alone
• …

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 B*Tree indexes index on such low cardinality data is not a good idea.

Above 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 functions as :

• AND
• OR
• and NOT

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  |       |       |            |          |
------------------------------------------------------------------------------------------------

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.