bitmapindex及其执行计划简介

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<1%)、又少量更新的列上，位图索引的物理存储结构和b tree索引的物理结构类似，有些许区别的就是位图索引的索引条目不再仅仅存储索引键值和rowid，而是变为了被存储的键值、对应的rowid上下限和位图段三部分，位图段是被压缩存储的，解压缩后就是一连串0和1的二进制位图序列，其中1表示索引键值的一个有效的rowid，0表示不存在，oracle通过转换函数（mapping function)将解压缩后的位图段中的1结合对应的rowid上下限，转换为索引键值的有效的rowid。

这个结构描述确实有些复杂难懂，简单来说就是原来的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<'LOB_INDEX';

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"<'LOB_INDEX')

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


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<2)
3 - filter(ROWNUM<2)


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


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


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

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<2)
3 - filter(ROWNUM<2)


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及其执行计划简介, 感谢原作者分享。