Relation - Bitmap Indexes

Data System Architecture

About

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.

When should you use a Bitmap index

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.

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.

Not suitable for write-intensive Environment

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.

Ad hoc query

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 btree, you will need large concatenated btree 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 btree index on such low cardinality data is not a good idea.

Representation

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 :

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

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

Bitmap and bitwise operation (AND, OR,..)

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 :

  • AND
  • OR
  • and NOT

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

Bitwise OR

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





Discover More
Card Puncher Data Processing
Index - Bitmap

in Oracle 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.
Data System Architecture
Index - Btree structure (Balanced Tree)

BTree indexes : has a tree structure provides fast access, by key, to an individual row or range of rows normally requiring few reads to find the correct row are similar in implementation to a...
Data System Architecture
Index - Performance

The impact of index on performance can be resumed as: Too many indexes and the performance of DML will suffer. Too few indexes and the performance of queries (including inserts, updates, and deletes)...
Data System Architecture
Online Analytical Processing (Olap)

Online Analytical Processing (OLAP) refers to: a class of application an approach to quickly answer multi-dimensional analytical queries. The term OLAP was created as a slight modification of...
Card Puncher Data Processing
Oracle - Controlling the Behavior of the Query Optimizer with initialization parameters

This section lists some initialization parameters that can be used to control the behaviour of the query optimizer. These parameters can be used to enable various optimizer features in order to improve...
Card Puncher Data Processing
Oracle Database - Index Scans

The Index Scans is a access path used by the query optimizer to produce the best . In this method, a row is retrieved by traversing the index, using the indexed column values specified by the statement....
Oracle Database Star Transformation
Oracle Database - Star Transformation

This article talk the application of the star query in Oracle which involve a star schema. Star transformation executes the query in two phases: retrieves the necessary rows from the fact table (row...
Data System Architecture
Relation - Index (Indices)

An index is an auxiliary data structure of a relation database to speed up the retrieval of rows. Indexing the data can lead to either performance or degradation of queries, so understanding indexing...



Share this page:
Follow us:
Task Runner