bitmap index及其执行计划简介

oracle的位图索引多用于数据仓库和DSS系统，这些年维护的系统也都是OLTP的系统，基本都是在和b tree索引打交道，对于bitmap也很少接触，查阅了一些书籍和自己的测试来简单学习下bitmap index。 位图索引一般创建在distinct value很小(num_distinct/num_rows

oracle的位图索引多用于数据仓库和DSS系统，这些年维护的系统也都是OLTP的系统，基本都是在和b tree索引打交道，对于bitmap也很少接触，查阅了一些书籍和自己的测试来简单学习下bitmap index。

位图索引一般创建在distinct value很小(num_distinct/num_rows

这个结构描述确实有些复杂难懂，简单来说就是原来的b tree索引的键值和rowid被修改为了键值、rowid上下限、位图段，当通过位图索引查找数据时，oracle同样的先根据root到branch再到leaf block，然后根据键值过滤，但是由于bitmap index下索引键值并不是和rowid一一对应，而是记录一系列的rowid上下限，bitmap index下找到键值后会将这个键值的位图段解压缩，获取到位图是1的，然后结合rowid的上下限通过转换函数得到最终的rowid然后回表，同样由于位图段是被压缩的，索引键值对应一个rowid上下限，bitmap index往往比b tree索引小很多。

位图索引的结构图：

位图索引的并发局限性：
由于位图索引是用一个位图段来记录，dml时候就没有行锁的概念，要锁就锁住了整个位图段，位图索引也不建议在OLTP这类高并发的事务处理系统中使用。

SESSION A:
SQL> create table tab_bitmap01(id number,name varchar2(10));

Table created.

SQL> create bitmap index ind_bitmap_name on tab_bitmap01(name);

Index created.


SQL> insert into tab_bitmap01 values(1,'ss');

1 row created.

SESSION A不提交事务

SESSION B:
SQL> insert into tab_bitmap01 values(1,'ss’);

SESSION B被阻塞

SESSION C:
SQL> insert into tab_bitmap01 values(1,'st');

1 row created.

SQL> insert into tab_bitmap01 values(1,'sr');

1 row created.

SESSION C的dml事务可以正常执行

由于等于ss的数据较少，bitmap index中键值等于ss都在同一个索引条目中也就是同一个位图段中，由于每次dml都是锁住对应的位图段，那么插入到同一个位图段的相关dml语句全部被阻塞，但是别的索引键值插入会重新生成一个索引条目也就是生成另一个位图段，由于不共用相同的位图段，对应的dml语句将不会被阻塞。

位图索引的优点：
1 根据存储结构而言，位图索引会更加节省空间
2 位图索引能够显示某些复杂的and和or查询条件的sql语句，这主要是因为位图索引能够实现快捷的按位运算

下面我们来看有关bitmap index的执行计划,bitmap index有关的执行计划有BITMAP INDEX SINGLE VALUE、BITMAP INDEX RANGE SCAN、BITMAP INDEX FULL SCAN、BITMAP INDEX FAST FULL SCAN、BITMAP AND、BITMAP OR和BITMAP CONVERSION TO ROWIDS等，下面只简单的列出常见的几种。

SQL> create table tab_bitmap02 as select * from dba_objects;

Table created.

SQL> create bitmap index ind_bitmap_type on tab_bitmap02(object_type);

Index created.
SQL> exec dbms_stats.gather_table_stats(ownname=>USER,tabname=>'TAB_BITMAP02',cascade=>true);

PL/SQL procedure successfully completed.

SQL> select * from tab_bitmap02 where object_type='TABLE';


2898 rows selected.


Execution Plan
----------------------------------------------------------
Plan hash value: 2735916582

------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name            | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                 |  2726 |   260K|   281   (1)| 00:00:04 |
|   1 |  TABLE ACCESS BY INDEX ROWID | TAB_BITMAP02    |  2726 |   260K|   281   (1)| 00:00:04 |
|   2 |   BITMAP CONVERSION TO ROWIDS|                 |       |       |            |          |
|*  3 |    BITMAP INDEX SINGLE VALUE | IND_BITMAP_TYPE |       |       |            |          |
------------------------------------------------------------------------------------------------

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

   3 - access("OBJECT_TYPE"='TABLE')

Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
        389  consistent gets
          0  physical reads
          0  redo size
     322090  bytes sent via SQL*Net to client
       2646  bytes received via SQL*Net from client
        195  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
       2898  rows processed

比较常见的bitmap index single value先进行键值筛选，然后bitmap conversion to rowids转换为rowid

SQL> select * from tab_bitmap02 where object_type>'LOB' and object_type
Execution Plan
----------------------------------------------------------
Plan hash value: 1977456414

------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name            | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                 |     8 |   784 |     3   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | TAB_BITMAP02    |     8 |   784 |     3   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS|                 |       |       |            |          |
|*  3 |    BITMAP INDEX RANGE SCAN   | IND_BITMAP_TYPE |       |       |            |          |
------------------------------------------------------------------------------------------------

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

   3 - access("OBJECT_TYPE">'LOB' AND "OBJECT_TYPE"
Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
          4  consistent gets
          0  physical reads
          0  redo size
       1651  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

这里是范围的bitmap index range scan扫描。

SQL> select object_type from tab_bitmap02;

86304 rows selected.


Execution Plan
----------------------------------------------------------
Plan hash value: 45367078

------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name            | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                 | 86304 |   758K|     5   (0)| 00:00:01 |
|   1 |  BITMAP CONVERSION TO ROWIDS |                 | 86304 |   758K|     5   (0)| 00:00:01 |
|   2 |   BITMAP INDEX FAST FULL SCAN| IND_BITMAP_TYPE |       |       |            |          |
------------------------------------------------------------------------------------------------

Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
         46  consistent gets
          0  physical reads
          0  redo size
    1485341  bytes sent via SQL*Net to client
      63806  bytes received via SQL*Net from client
       5755  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
      86304  rows processed

bitmap index fast full scan的执行计划类似于b tree的index fast full scan

SQL>  select * from (select * from tab_bitmap02 order by object_type) where rownum

Execution Plan
----------------------------------------------------------
Plan hash value: 3339180245

------------------------------------------------------------------------------------------------
| Id  | Operation               | Name         | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |              |     1 |   207 |       |  2271   (1)| 00:00:28 |
|*  1 |  COUNT STOPKEY          |              |       |       |       |            |          |
|   2 |   VIEW                  |              | 86304 |    17M|       |  2271   (1)| 00:00:28 |
|*  3 |    SORT ORDER BY STOPKEY|              | 86304 |  8259K|    11M|  2271   (1)| 00:00:28 |
|   4 |     TABLE ACCESS FULL   | TAB_BITMAP02 | 86304 |  8259K|       |   344   (1)| 00:00:05 |
------------------------------------------------------------------------------------------------

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

   1 - filter(ROWNUM    3 - filter(ROWNUM

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
       1237  consistent gets
          0  physical reads
          0  redo size
       1609  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          1  sorts (memory)
          0  sorts (disk)
          1  rows processed

SQL>  select * from (select /*+index(tab_bitmap02 ind_bitmap_type)*/* from tab_bitmap02 order by object_type) where rownum

Execution Plan
----------------------------------------------------------
Plan hash value: 2399409298

--------------------------------------------------------------------------------------------------
| Id  | Operation                      | Name            | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT               |                 |     1 |   207 |     7   (0)| 00:00:01 |
|*  1 |  COUNT STOPKEY                 |                 |       |       |            |          |
|   2 |   VIEW                         |                 |     1 |   207 |     7   (0)| 00:00:01 |
|   3 |    TABLE ACCESS BY INDEX ROWID | TAB_BITMAP02    |     1 |    98 |     7   (0)| 00:00:01 |
|   4 |     BITMAP CONVERSION TO ROWIDS|                 |       |       |            |          |
|   5 |      BITMAP INDEX FULL SCAN    | IND_BITMAP_TYPE |       |       |            |          |
--------------------------------------------------------------------------------------------------

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

   1 - filter(ROWNUM

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          3  consistent gets
          0  physical reads
          0  redo size
       1609  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed


SQL>  select * from (select /*+index(tab_bitmap02 ind_bitmap_type)*/* from tab_bitmap02 order by object_type desc) where rownum
Execution Plan
----------------------------------------------------------
Plan hash value: 89545540

-----------------------------------------------------------------------------------------------------------
| Id  | Operation                       | Name            | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                |                 |     1 |   207 |       |  3937   (1)| 00:00:48 |
|*  1 |  COUNT STOPKEY                  |                 |       |       |       |            |          |
|   2 |   VIEW                          |                 | 86304 |    17M|       |  3937   (1)| 00:00:48 |
|*  3 |    SORT ORDER BY STOPKEY        |                 | 86304 |  8259K|    11M|  3937   (1)| 00:00:48 |
|   4 |     TABLE ACCESS BY INDEX ROWID | TAB_BITMAP02    | 86304 |  8259K|       |  2011   (1)| 00:00:25 |
|   5 |      BITMAP CONVERSION TO ROWIDS|                 |       |       |       |            |          |
|   6 |       BITMAP INDEX FULL SCAN    | IND_BITMAP_TYPE |       |       |       |            |          |
-----------------------------------------------------------------------------------------------------------

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

   1 - filter(ROWNUM    3 - filter(ROWNUM

Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
       3504  consistent gets
          0  physical reads
          0  redo size
       1631  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          1  sorts (memory)
          0  sorts (disk)
          1  rows processed

这里需要加上hint index,优化器才会考虑走该索引的全扫描然后回表，而如果我们不加hint，上面这个sql会走成本更大的全表扫描，这个大家可以做个10053来看看优化器为什么不选择成本更低的索引回表的方式。

另外更需要我们注意的是如果asc排序的话，bitmap index是可以扫描leaf block的头部块然会回表，但是desc排序bitmap index则要扫描完所有的leaf block后回表排序取出数据，大家有兴趣的可以倒腾下。

SQL> select count(*) from tab_bitmap02 where object_type='TABLE';


Execution Plan
----------------------------------------------------------
Plan hash value: 1775585465

-----------------------------------------------------------------------------------------------
| Id  | Operation                   | Name            | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |                 |     1 |     9 |     1   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE             |                 |     1 |     9 |            |          |
|   2 |   BITMAP CONVERSION COUNT   |                 |  2726 | 24534 |     1   (0)| 00:00:01 |
|*  3 |    BITMAP INDEX SINGLE VALUE| IND_BITMAP_TYPE |       |       |            |          |
-----------------------------------------------------------------------------------------------

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

   3 - access("OBJECT_TYPE"='TABLE')

Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
          2  consistent gets
          0  physical reads
          0  redo size
        527  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

count(*)求总数时bitmap index是会直接走bitmap conversion count，通过解压缩的位图来直接计算count(*)

SQL> create bitmap index ind_bitmap_owner on tab_bitmap02(owner);

Index created.

SQL> select * from tab_bitmap02 where object_type='TABLE' and owner='SYS';

1020 rows selected.


Execution Plan
----------------------------------------------------------
Plan hash value: 3549035508

-------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name             | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                  |   119 | 11662 |    27   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | TAB_BITMAP02     |   119 | 11662 |    27   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS|                  |       |       |            |          |
|   3 |    BITMAP AND                |                  |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE| IND_BITMAP_TYPE  |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE| IND_BITMAP_OWNER |       |       |            |          |
-------------------------------------------------------------------------------------------------

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

   4 - access("OBJECT_TYPE"='TABLE')
   5 - access("OWNER"='SYS')


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
        143  consistent gets
          0  physical reads
          0  redo size
     108064  bytes sent via SQL*Net to client
       1260  bytes received via SQL*Net from client
         69  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
       1020  rows processed

通过两个bitmap index先进行bitmap index single value，然后再进行bitmap and合并

SQL> select * from tab_bitmap02 where object_type='CLUSTER' or owner='ACCOUNT';

10 rows selected.

Execution Plan
----------------------------------------------------------
Plan hash value: 1941447823

-------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name             | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                  |  3759 |   359K|   319   (0)| 00:00:04 |
|   1 |  TABLE ACCESS BY INDEX ROWID | TAB_BITMAP02     |  3759 |   359K|   319   (0)| 00:00:04 |
|   2 |   BITMAP CONVERSION TO ROWIDS|                  |       |       |            |          |
|   3 |    BITMAP OR                 |                  |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE| IND_BITMAP_OWNER |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE| IND_BITMAP_TYPE  |       |       |            |          |
-------------------------------------------------------------------------------------------------

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

   4 - access("OWNER"='ACCOUNT')
   5 - access("OBJECT_TYPE"='CLUSTER')


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
         11  consistent gets
          0  physical reads
          0  redo size
       2449  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
         10  rows processed

将两个bitmap index single value通过bitmap or合并

这里由于是两个过滤条件and或者or运算，而且两个过滤条件都有bitmap index，bitmap这里可以直接通过位图按位合并进行bitmap and或者bitmap or，然后转换为rowid。

bitmap index还可以有bitmap minus这种方式来处理下列的查询

SQL> select /*+index(tab_bitmap02 ind_bitmap_type) index(tab_bitmap02 IND_BITMAP_OWNER)*/* from tab_bitmap02 where object_type='CLUSTER' and owner!='XIAOYU';

10 rows selected.


Execution Plan
----------------------------------------------------------
Plan hash value: 2263546975

-------------------------------------------------------------------------------------------------
| Id  | Operation                     | Name            | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT              |                 |    15 |  1470 |     6   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID  | TAB_BITMAP02    |    15 |  1470 |     6   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS |                 |       |       |            |          |
|   3 |    BITMAP MINUS               |                 |       |       |            |          |
|   4 |     BITMAP MINUS              |                 |       |       |            |          |
|*  5 |      BITMAP INDEX SINGLE VALUE| IND_BITMAP_TYPE |       |       |            |          |
|*  6 |      BITMAP INDEX SINGLE VALUE| IND_BITMAP_OWNER|       |       |            |          |
|*  7 |     BITMAP INDEX SINGLE VALUE | IND_BITMAP_OWNER|       |       |            |          |
-------------------------------------------------------------------------------------------------

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

   5 - access("OBJECT_TYPE"='CLUSTER')
   6 - access("OWNER"='XIAOYU')
   7 - access("OWNER" IS NULL)


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
         13  consistent gets
          1  physical reads
          0  redo size
       2449  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
         10  rows processed

如果是一个复合索引对于下列这种or的查询是怎么样：

SQL> create bitmap index ind_multi_bitmap on tab_bitmap02(object_type,owner);

Index created.

SQL>drop index ind_bitmap_owner ;

SQL> select /*+index(tab_bitmap02 ind_multi_bitmap)*/* from tab_bitmap02 where owner='ACCOUNT' or object_type='CLUSTER';

10 rows selected.


Execution Plan
----------------------------------------------------------
Plan hash value: 4065408901

-------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name             | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                  |  3759 |   359K|  2013   (1)| 00:00:25 |
|   1 |  TABLE ACCESS BY INDEX ROWID | TAB_BITMAP02     |  3759 |   359K|  2013   (1)| 00:00:25 |
|   2 |   BITMAP CONVERSION TO ROWIDS|                  |       |       |            |          |
|*  3 |    BITMAP INDEX FULL SCAN    | IND_MULTI_BITMAP |       |       |            |          |
-------------------------------------------------------------------------------------------------

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

   3 - filter("OWNER"='ACCOUNT' OR "OBJECT_TYPE"='CLUSTER')


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
         16  consistent gets
         13  physical reads
          0  redo size
       2449  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
         10  rows processed

优化器考虑成本一般只能选择全索引扫描来完成.

xiaoyu在测试中没有发现bitmap有b tree的跳跃索引的执行计划,而都是采用的bitmap index single value

SQL> select /*+index(tab_bitmap02 ind_multi_bitmap)*/* from tab_bitmap02 where owner='ACCOUNT';

no rows selected


Execution Plan
----------------------------------------------------------
Plan hash value: 4065408901

-------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name             | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                  |  3744 |   358K|  2013   (1)| 00:00:25 |
|   1 |  TABLE ACCESS BY INDEX ROWID | TAB_BITMAP02     |  3744 |   358K|  2013   (1)| 00:00:25 |
|   2 |   BITMAP CONVERSION TO ROWIDS|                  |       |       |            |          |
|*  3 |    BITMAP INDEX FULL SCAN    | IND_MULTI_BITMAP |       |       |            |          |
-------------------------------------------------------------------------------------------------

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

   3 - filter("OWNER"='ACCOUNT')


Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          8  consistent gets
          0  physical reads
          0  redo size
       1343  bytes sent via SQL*Net to client
        512  bytes received via SQL*Net from client
          1  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          0  rows processed

当然对于上面这些执行计划和索引的创建方式，大家也没有必要去死记这些东西，理解了index的原理，个人觉得对于sql调优是易学难精的，要想在调优上有所建树，肯定得有大量的案例、测试用例和理论知识做铺垫！

原文地址：bitmap index及其执行计划简介, 感谢原作者分享。