Relation - Bitmap Indexes

> (Data|State) Management and Processing > (Data Type|Data Structure) > (Relation|Table) - Tabular data > Relation - Index

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

Advertising

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

Advertising

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

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

4 - 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>
[email protected]>CREATE BITMAP INDEX job_idx ON emp(job);
 
INDEX created.
 
[email protected]>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 |       |            |          |
---------------------------------------------------------------------------------
Advertising

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

[email protected]>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  |       |       |            |          |
------------------------------------------------------------------------------------------------

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

[email protected]>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 |       |       |            |          |
-----------------------------------------------------------------------------------------
data/type/relation/index/bitmap.txt · Last modified: 2017/09/13 16:16 by gerardnico