Part 3 - The Bitmap Dominion

Bitmap Execution Plans

This is Part 3 of The Bitmap Conspiracy, a four part epic on Bitmap Indexes.

In Part 1 we touched briefly on how Oracle can use Bitmap Indexes to resolve queries by translating equality and range predicates into bitmap retrievals. Now that we know more about how they are stored (see Part 2), let’s look closer at some of the operations that Oracle uses to access Bitmap Indexes and manipulate bitmaps.

1. Bitmap Execution Plans
2. Bitmap Index Access – Single Value
3. Bitmap Index Access – Range Scan and Bitmap Merge
4. Bitmap Index Access – Full Scan
5. Bitmap Operation – Bitmap Conversion Count
6. Bitmap Operation - Count Distinct
7. Bitmap Operation – AND and OR
8. Bitmap Operation – Minus
9. Bitmap Operation – Bitmap Conversion From ROWID
10. So now what?

Bitmap Index Access – Single Value

This one is simple: when you write a SQL statement that includes a predicate of the form WHERE COLUMN = ‘VALUE’ (or COLUMN IS NULL) – and the column is bitmap indexed – then Oracle will retrieve the bitmap for that column value and then pass it to the next step in the plan (possibly conversion to ROWIDs and row retrieval).

SQL> SELECT name
  2  FROM bradys
  3  WHERE birthorder IS NULL;

NAME
------
MIKE
CAROL
ALICE

-------------------------------------------------------------
| Id  | Operation                    | Name                 |
-------------------------------------------------------------
|   0 | SELECT STATEMENT             |                      |
|   1 |  TABLE ACCESS BY INDEX ROWID | BRADYS               |
|   2 |   BITMAP CONVERSION TO ROWIDS|                      |
|*  3 |    BITMAP INDEX SINGLE VALUE | BRADYS_BIRTHORDER_IX |
-------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   3 - access("BIRTHORDER" IS NULL)

Bitmap Index Access – Range Scan and Bitmap Merge

Another simple one: when you write a SQL statement that includes a predicate of the form WHERE COLUMN >= ‘VALUE’ – and the column is bitmap indexed – then Oracle will retrieve the bitmaps for the matching range of values. Supported operators include >[=], <[=], BETWEEN and LIKE.

SQL> SELECT name
  2  FROM bradys
  3  WHERE agegrp >= 'CHILD';

NAME
------
JAN
CINDY
PETER
BOBBY
MARCIA
GREG

6 rows selected.

---------------------------------------------------------
| Id  | Operation                    | Name             |
---------------------------------------------------------
|   0 | SELECT STATEMENT             |                  |
|   1 |  TABLE ACCESS BY INDEX ROWID | BRADYS           |
|   2 |   BITMAP CONVERSION TO ROWIDS|                  |
|*  3 |    BITMAP INDEX RANGE SCAN   | BRADYS_AGEGRP_IX |
---------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   3 - access("AGEGRP">='CHILD')
       filter("AGEGRP">='CHILD')

Interestingly the Explain Plan does not list any operation to combine the bitmaps returned by the Range Scan; each separate bitmap is individually converted to ROWIDs without the need to create a single “master” bitmap result set. This is made possible by the knowledge that no two bitmaps from the one index will have the same bit set. Eg. The bitmaps for AGEGRP = ‘CHILD’ and AGEGRP = ‘TEEN’ will never point to the same rows.

Note that this behaviour changes when a Bitmap Index Range Scan is combined with another bitmap predicate on a different column. In these cases it is necessary to merge the bitmaps from the Range Scan into a single bitmap so that it can be combined (AND/OR) with the bitmap from the other column. This operation is known as a Bitmap Merge – see Step 5 in the example below.

SQL> SELECT count(*)
  2  FROM bradys
  3  WHERE agegrp >= 'CHILD'
  4  and birthorder = 'YOUNGEST';

  COUNT(*)
----------
         2

-------------------------------------------------------------
| Id  | Operation                    | Name                 |
-------------------------------------------------------------
|   0 | SELECT STATEMENT             |                      |
|   1 |  SORT AGGREGATE              |                      |
|   2 |   BITMAP CONVERSION COUNT    |                      |
|   3 |    BITMAP AND                |                      |
|*  4 |     BITMAP INDEX SINGLE VALUE| BRADYS_BIRTHORDER_IX |
|   5 |     BITMAP MERGE             |                      |
|*  6 |      BITMAP INDEX RANGE SCAN | BRADYS_AGEGRP_IX     |
-------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("BIRTHORDER"='YOUNGEST')
   6 - access("AGEGRP">='CHILD')
       filter("AGEGRP">='CHILD')

Bitmap Index Access – Full Scan

All other comparison operators will result in a Full Scan, except for a special case of Bitmap Minus (see below). This includes all NOT style predicates: <>, IS NOT NULL, NOT LIKE. A Full Scan reads the entire index and discards bitmaps for non-matching keys.

Note that although NOT is an operator that could be easily applied to a bitmap to return the bitwise complement, Oracle does not do this. Presumably the reason is related to the fact that the bitmap contains bits that do not map to actual rows in the table (see Bitmap Conversion to ROWIDs in Part 2 of this series). If we took the logical complement of a Bitmap Index bitmap, then bits would be set that correspond to missing rows and the conversion to ROWIDs would fail.

In the following example, Oracle uses a BITMAP INDEX FULL SCAN to satisfy the inequality condition, but then looks up the NAME from a B-Tree index rather than from the table.

SQL> SELECT name
  2  FROM bradys
  3  WHERE agegrp <> 'CHILD';

NAME
------
ALICE
CAROL
GREG
MARCIA
MIKE

----------------------------------------------------------
| Id  | Operation                     | Name             |
----------------------------------------------------------
|   0 | SELECT STATEMENT              |                  |
|   1 |  VIEW                         | index$_join$_001 |
|*  2 |   HASH JOIN                   |                  |
|   3 |    BITMAP CONVERSION TO ROWIDS|                  |
|*  4 |     BITMAP INDEX FULL SCAN    | BRADYS_AGEGRP_IX |
|   5 |    INDEX FAST FULL SCAN       | BRADYS_NAME_UX   |
----------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access(ROWID=ROWID)
   4 - filter("AGEGRP"<>'CHILD')

Bitmap Operation – Bitmap Conversion Count

When Oracle can satisfy all of the filter predicates of a query using bitmap indexes, then it can very efficiently compute a simple COUNT(*) by counting the set bits in the final bitmap. There is no need to convert the bitmap into ROWIDs or to lookup the rows in the table.

The compressed storage of Bitmap Indexes allows COUNT(*) to execute with very little IO; typically several times faster than a COUNT(*) without Bitmap Indexes.

SQL> SELECT count(*)
  2  FROM bradys
  3  WHERE agegrp = 'CHILD';

  COUNT(*)
----------
         4

----------------------------------------------------------
| Id  | Operation                     | Name             |
----------------------------------------------------------
|   0 | SELECT STATEMENT              |                  |
|   1 |  SORT AGGREGATE               |                  |
|   2 |   BITMAP CONVERSION COUNT     |                  |
|*  3 |    BITMAP INDEX FAST FULL SCAN| BRADYS_AGEGRP_IX |
----------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   3 - filter("AGEGRP"='CHILD')

Bitmap Operation - Count Distinct

Counting the distinct values of a non-bitmap-indexed column is quite inefficient because of the de-duplication process. If the COUNT(DISTINCT …) uses a bitmap indexed column, then the bitmap index already contains a distinct list of column values so it can return a result incredibly fast.

Since long bitmaps are broken into pieces (multiple index entries per distinct key), Oracle still needs to de-duplicate the keys, but it can do so very quickly because the B-Tree architecture of the Bitmap Index means the pieces are pre-sorted. Note how the GROUP BY NOSORT operation in the following example performs the count without having to sort the result set.

Also note that there is no Bitmap Conversion. In fact, the bitmaps are ignored completely because the query is resolved entirely with the index keys.

SQL> SELECT count(distinct agegrp)
  2  FROM bradys;

COUNT(DISTINCTAGEGRP)
---------------------
                    3

------------------------------------------------------
| Id  | Operation                 | Name             |
------------------------------------------------------
|   0 | SELECT STATEMENT          |                  |
|   1 |  SORT AGGREGATE           |                  |
|   2 |   VIEW                    | VW_DAG_0         |
|   3 |    SORT GROUP BY NOSORT   |                  |
|   4 |     BITMAP INDEX FULL SCAN| BRADYS_AGEGRP_IX |
------------------------------------------------------

Bitmap Operation – AND and OR

The above examples mostly show Bitmap Indexes performing the same type of operations as B-Tree Indexes: find and retrieve the rows matching a certain condition.

Bitmap Indexes really begin to shine when you start using them in combinations, like AND and OR conditions. B-tree indexes can support these types of operations in a limited way; concatenated (multi-column) B-Tree indexes can help resolve some types of AND predicates, and the Optimizer can rewrite some types of OR predicates as UNION queries that will use B-tree indexes.

Bitmap indexes can be applied to AND and OR predicates with far more versatility. Quite simply, if individual predicates can use a Bitmap Index, then the individual bitmaps can be combined with AND and OR operations.

Here are some simple examples:

SQL> SELECT COUNT(*)
  2  FROM bradys
  3  WHERE birthorder IS NULL
  4  AND HAIR = 'BROWN';

  COUNT(*)
----------
         2

-------------------------------------------------------------
| Id  | Operation                    | Name                 |
-------------------------------------------------------------
|   0 | SELECT STATEMENT             |                      |
|   1 |  SORT AGGREGATE              |                      |
|   2 |   BITMAP CONVERSION COUNT    |                      |
|   3 |    BITMAP AND                |                      |
|*  4 |     BITMAP INDEX SINGLE VALUE| BRADYS_HAIR_IX       |
|*  5 |     BITMAP INDEX SINGLE VALUE| BRADYS_BIRTHORDER_IX |
-------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("HAIR"='BROWN')
   5 - access("BIRTHORDER" IS NULL)


SQL> SELECT COUNT(*)
  2  FROM bradys
  3  WHERE birthorder IS NULL
  4  OR agegrp = 'TEEN';

  COUNT(*)
----------
         5

-------------------------------------------------------------
| Id  | Operation                    | Name                 |
-------------------------------------------------------------
|   0 | SELECT STATEMENT             |                      |
|   1 |  SORT AGGREGATE              |                      |
|   2 |   BITMAP CONVERSION COUNT    |                      |
|   3 |    BITMAP OR                 |                      |
|*  4 |     BITMAP INDEX SINGLE VALUE| BRADYS_BIRTHORDER_IX |
|*  5 |     BITMAP INDEX SINGLE VALUE| BRADYS_AGEGRP_IX     |
-------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("BIRTHORDER" IS NULL)
   5 - access("AGEGRP"='TEEN')

Bitmap Operation – Minus

The Full Scan operation above demonstrated how a negative (NOT) condition can still use a Bitmap Index, albeit with a potentially costly Full Scan. Surprisingly, there are cases where negative conditions can be satisfied with Single Value scans. If a negative condition is combined (using AND) with a positive condition, then Oracle can use a Single Value or Range Scan to find the bitmap for the positive condition and then subtract the bitmap for the negative condition.

For example consider the following SQL and bitmaps

SELECT COUNT(*)
FROM bradys
WHERE hair = 'BLONDE'
AND birthorder IS NOT NULL;

    M
  C A   C   P B A
M A R   I G E O L
I R C J N R T B I
K O I A D E E B C
E L A N Y G R Y E
- - - - - - - - -
0 1 1 1 1 0 0 0 0 - HAIR = ‘BLONDE’
1 1 0 0 0 0 0 0 1 - BIRTHORDER IS NULL
-----------------
0 0 1 1 1 0 0 0 0 – Bitmap MINUS

Oracle applies a “Bitmap Minus” operation to turn the BIRTHORDER IS NULL bitmap into an operation that applies BIRTHODER IS NOT NULL. A Bitmap MINUS is different to an arithmetic minus:

• Bitmap 0 – 0 = 0 (same as arithmetic minus)
• Bitmap 1 – 1 = 0 (same as arithmetic minus)
• Bitmap 1 – 0 = 1 (same as arithmetic minus)
• Bitmap 0 – 1 = 0 (!!!!)

Let’s look at it in action. Note that the negative condition (IS NOT NULL) is translated into a positive condition (IS NULL) in line 5 of the plan. It is the Minus operation that converts its behaviour back to IS NOT NULL.

SQL> SELECT COUNT(*)
  2  FROM bradys
  3  WHERE hair = 'BLONDE'
  4  AND birthorder IS NOT NULL;

  COUNT(*)
----------
         3

-------------------------------------------------------------
| Id  | Operation                    | Name                 |
-------------------------------------------------------------
|   0 | SELECT STATEMENT             |                      |
|   1 |  SORT AGGREGATE              |                      |
|   2 |   BITMAP CONVERSION COUNT    |                      |
|   3 |    BITMAP MINUS              |                      |
|*  4 |     BITMAP INDEX SINGLE VALUE| BRADYS_HAIR_IX       |
|*  5 |     BITMAP INDEX SINGLE VALUE| BRADYS_BIRTHORDER_IX |
-------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("HAIR"='BLONDE')
   5 - access("BIRTHORDER" IS NULL)

Bitmap Operation – Bitmap Conversion From ROWID

One of the key differences between Bitmap Indexes and B-Tree Indexes that Bitmap Indexes were designed to be used together. They are at their best when they combine bitmaps for two or more non-selective predicates to create a selective result.

B-Tree indexes are at their best when used singly. There are a couple of ways in which B-Tree indexes can be combined (e.g. legacy RBO “AND-Equal” and Fast Full Scan Index Joins) but these are very much exceptions to the rule.

On some occasions we may wish that we could combine B-Tree indexes in the same way that we combine Bitmap Indexes. For example consider a highly selective index on a DATE field that is accurate to the second. Most rows will have a distinct value and we would find that a B-Tree index would produce optimal results for selective queries that scan one day or even one week ranges.

Consider a query that filtered on a bunch of bitmap indexed columns plus a non-selective range of dates (e.g. one month). The bitmap indexed predicates alone may be non-selective (i.e. faster to full table scan) and the date-range alone is non-selective (i.e. faster to full table scan), but if we could combine them somehow then they would produce a selective result that would out-perform a full table scan.

This is precisely what a Bitmap Conversion From ROWID does; it converts the results of a B-Tree index scan into a Bitmap so that it can be combined with other bitmap indexes.

In the example below, we have a selective B-Tree index on BRADYS.NAME from which we are filtering a non-selective range (ALICE to GREG). To this we add another non-selective Bitmap Indexed predicate on HAIR = ‘BROWN’. The result is selective enough that we would like to combine the B-Tree and Bitmap index scans to avoid accessing table rows on one of the criteria which we would then discard based on the other. Note in this example that I used the INDEX_COMBINE hint to force the Bitmap Conversion From ROWID; this is due to the small data volumes in the test case. In reality, this type of access would only make sense on much larger tables; Oracle should choose the Conversion From ROWIDs plan without the need for a hint.

SQL> SELECT /*+ INDEX_COMBINE(bradys) */ count(*)
  2  FROM bradys
  3  WHERE hair = 'BROWN'
  4  AND name BETWEEN 'ALICE' AND 'GREG';

  COUNT(*)
----------
         3

-----------------------------------------------------------
| Id  | Operation                        | Name           |
-----------------------------------------------------------
|   0 | SELECT STATEMENT                 |                |
|   1 |  SORT AGGREGATE                  |                |
|   2 |   BITMAP CONVERSION COUNT        |                |
|   3 |    BITMAP AND                    |                |
|*  4 |     BITMAP INDEX SINGLE VALUE    | BRADYS_HAIR_IX |
|   5 |     BITMAP CONVERSION FROM ROWIDS|                |
|   6 |      SORT ORDER BY               |                |
|*  7 |       INDEX RANGE SCAN           | BRADYS_NAME_UX |
-----------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("HAIR"='BROWN')
   7 - access("NAME">='ALICE' AND "NAME"<='GREG')

So now what?

If you’ve stuck with me this far – through Parts 1, 2 and 3 of this epic – then your patience has just about paid off. Now that we know what a bitmap index is, how it is structured and how it is used; we are in a strong position to revisit some of the things we thought we knew about bitmap indexes. In Part 4 we will apply our current understanding of Bitmap Indexes to some commonly held beliefs and separate the myth from the fact.

Return to main article
Read Part 4 - The Bitmap Legacy