2008-11-07

Composite Bitmap Indexes

In hist Book Troubleshoot Oracle Performance Christian Antognini wrote also about Composite Bitmap Indexes. (p400)
Unfortunately he only proclaims
Composite bitmap indexes are rarely created. This is because several indexes can be combined efficiently in order to apply a restriction. To see how powerful bitmap indexes are, let’s look at several queries. (p400)
without givin gany evidence. So I grabbed his scripts (thank you for providing them) and run some testcases (on 11.1.0.6):
I just created this additional bitmap index:
CREATE BITMAP INDEX bx_i_n456 on t (n4, n5, n6);

bitmap AND:

index_combine:

SELECT /*+ index_combine(t i_n4 i_n5 i_n6) */ *
FROM t
WHERE n4 = 6 AND n5 = 42 AND n6 = 11

-----------------------------------------------------------------------------------------------
| Id  | Operation                    | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-----------------------------------------------------------------------------------------------
|   1 |  TABLE ACCESS BY INDEX ROWID | T    |      1 |      1 |      1 |00:00:00.01 |       7 |
|   2 |   BITMAP CONVERSION TO ROWIDS|      |      1 |        |      1 |00:00:00.01 |       6 |
|   3 |    BITMAP AND                |      |      1 |        |      1 |00:00:00.01 |       6 |
|*  4 |     BITMAP INDEX SINGLE VALUE| I_N5 |      1 |        |      1 |00:00:00.01 |       2 |
|*  5 |     BITMAP INDEX SINGLE VALUE| I_N6 |      1 |        |      1 |00:00:00.01 |       2 |
|*  6 |     BITMAP INDEX SINGLE VALUE| I_N4 |      1 |        |      1 |00:00:00.01 |       2 |
-----------------------------------------------------------------------------------------------

   4 - access("N5"=42)
   5 - access("N6"=11)
   6 - access("N4"=6)
Cost: 3

composite bitmap index(CIB):

SELECT *
FROM t
WHERE n4 = 6 AND n5 = 42 AND n6 = 11

----------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name      | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------------
|   1 |  TABLE ACCESS BY INDEX ROWID | T         |      1 |      1 |      1 |00:00:00.01 |       4 |
|   2 |   BITMAP CONVERSION TO ROWIDS|           |      1 |        |      1 |00:00:00.01 |       3 |
|*  3 |    BITMAP INDEX SINGLE VALUE | BX_I_N456 |      1 |        |      1 |00:00:00.01 |       3 |
----------------------------------------------------------------------------------------------------

   3 - access("N4"=6 AND "N5"=42 AND "N6"=11)
Cost:1

In this case the CBI wins.

bitmap OR:

index_combine:

SELECT /*+ index_combine(t i_n4 i_n5 i_n6) */ *
FROM t
WHERE n4 = 6 OR n5 = 42 OR n6 = 11

-----------------------------------------------------------------------------------------------
| Id  | Operation                    | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-----------------------------------------------------------------------------------------------
|   1 |  TABLE ACCESS BY INDEX ROWID | T    |      1 |    797 |    767 |00:00:00.01 |     419 |
|   2 |   BITMAP CONVERSION TO ROWIDS|      |      1 |        |    767 |00:00:00.01 |       7 |
|   3 |    BITMAP OR                 |      |      1 |        |      1 |00:00:00.01 |       7 |
|*  4 |     BITMAP INDEX SINGLE VALUE| I_N4 |      1 |        |      1 |00:00:00.01 |       3 |
|*  5 |     BITMAP INDEX SINGLE VALUE| I_N6 |      1 |        |      1 |00:00:00.01 |       2 |
|*  6 |     BITMAP INDEX SINGLE VALUE| I_N5 |      1 |        |      1 |00:00:00.01 |       2 |
-----------------------------------------------------------------------------------------------

   4 - access("N4"=6)
   5 - access("N6"=11)
   6 - access("N5"=42)
 Cost: 135

no hints:

SELECT *
FROM t
WHERE n4 = 6 OR n5 = 42 OR n6 = 11

-----------------------------------------------------------------------------------------------
| Id  | Operation                    | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-----------------------------------------------------------------------------------------------
|   1 |  TABLE ACCESS BY INDEX ROWID | T    |      1 |    797 |    767 |00:00:00.01 |     419 |
|   2 |   BITMAP CONVERSION TO ROWIDS|      |      1 |        |    767 |00:00:00.01 |       7 |
|   3 |    BITMAP OR                 |      |      1 |        |      1 |00:00:00.01 |       7 |
|*  4 |     BITMAP INDEX SINGLE VALUE| I_N4 |      1 |        |      1 |00:00:00.01 |       3 |
|*  5 |     BITMAP INDEX SINGLE VALUE| I_N6 |      1 |        |      1 |00:00:00.01 |       2 |
|*  6 |     BITMAP INDEX SINGLE VALUE| I_N5 |      1 |        |      1 |00:00:00.01 |       2 |
-----------------------------------------------------------------------------------------------

   4 - access("N4"=6)
   5 - access("N6"=11)
   6 - access("N5"=42)
Cost:135

index_combine with BX_I_N456

SELECT /*+ index_combine(t BX_I_N456 i_n5 i_n6) */ *
FROM t
WHERE n4 = 6 OR n5 = 42 OR n6 = 11   

----------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name      | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------------
|   1 |  TABLE ACCESS BY INDEX ROWID | T         |      1 |    797 |    767 |00:00:00.04 |     420 |
|   2 |   BITMAP CONVERSION TO ROWIDS|           |      1 |        |    767 |00:00:00.03 |       8 |
|   3 |    BITMAP OR                 |           |      1 |        |      1 |00:00:00.03 |       8 |
|   4 |     BITMAP MERGE             |           |      1 |        |      1 |00:00:00.03 |       4 |
|*  5 |      BITMAP INDEX RANGE SCAN | BX_I_N456 |      1 |        |    527 |00:00:00.01 |       4 |
|*  6 |     BITMAP INDEX SINGLE VALUE| I_N6      |      1 |        |      1 |00:00:00.01 |       2 |
|*  7 |     BITMAP INDEX SINGLE VALUE| I_N5      |      1 |        |      1 |00:00:00.01 |       2 |
----------------------------------------------------------------------------------------------------

   5 - access("N4"=6)
       filter("N4"=6)
   6 - access("N6"=11)
   7 - access("N5"=42)
Cost: 138

index_combine with BX_I_N456 on 2nd place

SELECT /*+ index_combine(t i_n4 BX_I_N456 i_n6) */ *
FROM t
WHERE n4 = 6 OR n5 = 42 OR n6 = 11   

----------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name      | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------------
|   1 |  TABLE ACCESS BY INDEX ROWID | T         |      1 |    797 |    767 |00:00:00.01 |     420 |
|   2 |   BITMAP CONVERSION TO ROWIDS|           |      1 |        |    767 |00:00:00.01 |       8 |
|   3 |    BITMAP OR                 |           |      1 |        |      1 |00:00:00.01 |       8 |
|   4 |     BITMAP MERGE             |           |      1 |        |      1 |00:00:00.01 |       4 |
|*  5 |      BITMAP INDEX RANGE SCAN | BX_I_N456 |      1 |        |    527 |00:00:00.01 |       4 |
|*  6 |     BITMAP INDEX SINGLE VALUE| I_N6      |      1 |        |      1 |00:00:00.01 |       2 |
|*  7 |     BITMAP INDEX SINGLE VALUE| I_N5      |      1 |        |      1 |00:00:00.01 |       2 |
----------------------------------------------------------------------------------------------------

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

   5 - access("N4"=6)
       filter("N4"=6)
   6 - access("N6"=11)
   7 - access("N5"=42)
Costs: 138

in this case, the 3 seperated bitmap indices wins.

NOT EQUAL AND:

index_combine:

SELECT /*+ index_combine(t i_n4 i_n5 i_n6) */ *
FROM t
WHERE n4 != 6 AND n5 = 42 AND n6 = 11   

-----------------------------------------------------------------------------------------------
| Id  | Operation                    | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-----------------------------------------------------------------------------------------------
|*  1 |  TABLE ACCESS BY INDEX ROWID | T    |      1 |      1 |      1 |00:00:00.01 |       6 |
|   2 |   BITMAP CONVERSION TO ROWIDS|      |      1 |        |      2 |00:00:00.01 |       4 |
|   3 |    BITMAP AND                |      |      1 |        |      1 |00:00:00.01 |       4 |
|*  4 |     BITMAP INDEX SINGLE VALUE| I_N5 |      1 |        |      1 |00:00:00.01 |       2 |
|*  5 |     BITMAP INDEX SINGLE VALUE| I_N6 |      1 |        |      1 |00:00:00.01 |       2 |
-----------------------------------------------------------------------------------------------

   1 - filter("N4"<>6)
   4 - access("N5"=42)
   5 - access("N6"=11)
Costs: 2

a different execution plan from Chris' Book, there a BITMAP MINUS was shown in the execution plan.
Maybe a question for a seperated session, where the BITMAP MINUS disappeared.

for some reason, this hint generated the BITMAP MINUS
SELECT /*+ index(t  BX_I_N456) */ *
FROM t
WHERE n4 != 6 AND n5 = 42 AND n6 = 11   

------------------------------------------------------------------------------------------------------
| Id  | Operation                      | Name      | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------------------
|   1 |  TABLE ACCESS BY INDEX ROWID   | T         |      1 |      1 |      1 |00:00:00.01 |      13 |
|   2 |   BITMAP CONVERSION TO ROWIDS  |           |      1 |        |      1 |00:00:00.01 |      12 |
|   3 |    BITMAP MINUS                |           |      1 |        |      1 |00:00:00.01 |      12 |
|   4 |     BITMAP MINUS               |           |      1 |        |      1 |00:00:00.01 |       8 |
|   5 |      BITMAP AND                |           |      1 |        |      1 |00:00:00.01 |       4 |
|*  6 |       BITMAP INDEX SINGLE VALUE| I_N5      |      1 |        |      1 |00:00:00.01 |       2 |
|*  7 |       BITMAP INDEX SINGLE VALUE| I_N6      |      1 |        |      1 |00:00:00.01 |       2 |
|   8 |      BITMAP MERGE              |           |      1 |        |      1 |00:00:00.01 |       4 |
|*  9 |       BITMAP INDEX RANGE SCAN  | BX_I_N456 |      1 |        |    526 |00:00:00.01 |       4 |
|  10 |     BITMAP MERGE               |           |      1 |        |      1 |00:00:00.01 |       4 |
|* 11 |      BITMAP INDEX RANGE SCAN   | BX_I_N456 |      1 |        |    526 |00:00:00.01 |       4 |
------------------------------------------------------------------------------------------------------

   6 - access("N5"=42)
   7 - access("N6"=11)
   9 - access("N4"=6)
  11 - access("N4" IS NULL)
Cost: 4

So I decided to do a slightly different testcase:

index_combine:

SELECT /*+ index_combine(t i_n4 i_n5 i_n6) */ * 
FROM t 
WHERE n4 = 6 and n5 != 42 and n6 = 11

-------------------------------------------------------------------------------------------------
| Id  | Operation                      | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-------------------------------------------------------------------------------------------------
|   1 |  TABLE ACCESS BY INDEX ROWID   | T    |      1 |      8 |      7 |00:00:00.01 |      15 |
|   2 |   BITMAP CONVERSION TO ROWIDS  |      |      1 |        |      7 |00:00:00.01 |       8 |
|   3 |    BITMAP MINUS                |      |      1 |        |      1 |00:00:00.01 |       8 |
|   4 |     BITMAP MINUS               |      |      1 |        |      1 |00:00:00.01 |       6 |
|   5 |      BITMAP AND                |      |      1 |        |      1 |00:00:00.01 |       4 |
|*  6 |       BITMAP INDEX SINGLE VALUE| I_N6 |      1 |        |      1 |00:00:00.01 |       2 |
|*  7 |       BITMAP INDEX SINGLE VALUE| I_N4 |      1 |        |      1 |00:00:00.01 |       2 |
|*  8 |      BITMAP INDEX SINGLE VALUE | I_N5 |      1 |        |      1 |00:00:00.01 |       2 |
|*  9 |     BITMAP INDEX SINGLE VALUE  | I_N5 |      1 |        |      1 |00:00:00.01 |       2 |
-------------------------------------------------------------------------------------------------

   6 - access("N6"=11)
   7 - access("N4"=6)
   8 - access("N5"=42)
   9 - access("N5" IS NULL)
Costs: 6

CIB:

SELECT /*+ index(t BX_I_N456) */ * 
FROM t 
WHERE n4 =6 and n5 != 42 and n6 = 11

----------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name      | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------------
|   1 |  TABLE ACCESS BY INDEX ROWID | T         |      1 |      8 |      7 |00:00:00.01 |      12 |
|   2 |   BITMAP CONVERSION TO ROWIDS|           |      1 |        |      7 |00:00:00.01 |       5 |
|*  3 |    BITMAP INDEX RANGE SCAN   | BX_I_N456 |      1 |        |      7 |00:00:00.01 |       5 |
----------------------------------------------------------------------------------------------------

   3 - access("N4"=6)
       filter(("N6"=11 AND "N5"<>42 AND "N4"=6))
Costs: 107

no hints:

SELECT  * 
FROM t 
WHERE n4 =6 and n5 != 42 and n6 = 11    
    
-----------------------------------------------------------------------------------------------
| Id  | Operation                    | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-----------------------------------------------------------------------------------------------
|*  1 |  TABLE ACCESS BY INDEX ROWID | T    |      1 |      8 |      7 |00:00:00.01 |      12 |
|   2 |   BITMAP CONVERSION TO ROWIDS|      |      1 |        |      8 |00:00:00.01 |       4 |
|   3 |    BITMAP AND                |      |      1 |        |      1 |00:00:00.01 |       4 |
|*  4 |     BITMAP INDEX SINGLE VALUE| I_N6 |      1 |        |      1 |00:00:00.01 |       2 |
|*  5 |     BITMAP INDEX SINGLE VALUE| I_N4 |      1 |        |      1 |00:00:00.01 |       2 |
-----------------------------------------------------------------------------------------------

   1 - filter("N5"<>42)
   4 - access("N6"=11)
   5 - access("N4"=6) 
Costs: 4

My a little bit more explicit view of composite bitmap indexes is:
  • They can be useful in AND statements:
  • even not optimal for OR statements, they can replace the bitmap index which is created only on the first column without high cost increasement
  • in NOT EQUAL AND statements they really kill the performance if enfoced.

Keine Kommentare: