位图索引

位图索引区别于传统B*树索引有两个结构特点：其一是叶子节点上是一个可能的索引列取值对应一个叶子节点。另一个就是叶子节点上通过一个位图向量表示对应行是否取定这个索引值。

 

使用位图向量记录对应行的取值情况不仅可以带来存储空间上的节省，而且可以借助计算机位图运算的快速特性来提高索引结果利用率。下面我们通过模拟情况来进行分析。

 

Bitmap Index模拟说明

 

假设存在数据表T，有两个数据列A和B，取值如下。

 

序号	A	B
1	L	1
2	T	2
3	L	2
4	M	1

 

对两个数据列A、B分别建立位图索引：idx_t_bita和idx_t_bitb。两个索引对应的存储逻辑结构如下：

 

Idx_t_bita索引结构，对应的是叶子节点：

 

索引键值	起始rowid	结束rowid	位图向量
L	xxx	ttt	1010
T	xxx	ttt	0100
M	xxx	ttt	0001

 

Idx_t_bitb索引结构，对应的是叶子节点：

 

索引键值	起始rowid	结束rowid	位图向量
1	xxx	ttt	1001
2	xxx	ttt	0110

 

对查询“select * from t where b=1 and (a=’L’ or a=’M’)”

 

分析：位图索引使用方面，和B*索引有很大的不同。B*索引的使用，通常是从根节点开始，经过不断的分支节点比较到最近的符合条件叶子节点。通过叶子节点上的不断Scan操作，“扫描”出结果集合rowid。

 

而位图索引的工作方式截然不同。通过不同位图取值直接的位运算（与或），来获取到结果集合向量（计算出的结果）。

 

针对实例SQL，可以拆分成如下的操作：

 

1、a=’L’ or a=’M’

 

a=L：向量：1010

a=M：向量：0001

 

or操作的结果，就是两个向量的或操作：结果为1011。

 

2、结合b=1的向量

 

中间结果向量：1011

B=1：向量：1001

 

and操作的结果，1001。翻译过来就是第一和第四行是查询结果。

 

3、获取到结果rowid

 

目前知道了起始rowid和终止rowid，以及第一行和第四行为操作结果。可以通过试算的方法获取到结果集合rowid。

 

上面的操作演算过程，说明了两个问题：

 

位图索引是可以多索引共同合作操作的，不像B*树索引只有一个会加入结果集合；

位图索引的工作是通过位逻辑运算，非扫描操作；

 

 

实际试验

 

下面我们通过一系列的实验，来进一步观察结果。

 

实验环境构建

 

 

SQL> create table t as select owner owner1, object_type type1, owner owner2, object_type type2 from dba_objects;

Table created

 

SQL> desc t;

Name  Type        Nullable Default Comments

------ ------------ -------- ------- --------

OWNER1 VARCHAR2(30) Y                        

TYPE1 VARCHAR2(19) Y                        

OWNER2 VARCHAR2(30) Y                        

TYPE2 VARCHAR2(19) Y                        

 

SQL> create index idx_t_owner1 on t(owner1);

Index created

 

SQL> create index idx_t_type1 on t(type1);

Index created

 

SQL> create bitmap index idx_t_owner2bit on t(owner2);

Index created

 

SQL> create bitmap index idx_t_type2bit on t(type2);

Index created

 

SQL> exec dbms_stats.gather_table_stats(user,'T',cascade => true);

PL/SQL procedure successfully completed

 

 

 

常规索引实验

 

我们构建的环境中，字段和类型完全相同。区别就在于使用的索引类型差异。下面我们先进行常规索引实验。

 

//为防止影响执行计划，先禁用Bitmap Index

SQL> alter index idx_t_owner2bit unusable;

Index altered

 

SQL> alter index idx_t_type2bit unusable;

Index altered

 

SQL> set pagesize 1000;

SQL> set linesize 1000;

SQL> explain plan for select * from t where owner1='SCOTT' and type1='TABLE';

已解释。

 

SQL> select * from table(dbms_xplan.display);

PLAN_TABLE_OUTPUT

----------------------------------------------------------------------------------------------

Plan hash value: 2154532428

 

--------------------------------------------------------------------------------------------

| Id | Operation                  | Name        | Rows | Bytes | Cost (%CPU)| Time|

--------------------------------------------------------------------------------------------

|  0 | SELECT STATEMENT     |      |    1 |   28 |    2  (0)| 00:00:01 |

|* 1 | TABLE ACCESS BY INDEX ROWID| T |    1 |   28 |    2  (0)| 00:00:01 |

|* 2 |  INDEX RANGE SCAN   | IDX_T_OWNER1 | 28 |   |    1  (0)| 00:00:01 |

--------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):

---------------------------------------------------

  1 - filter("TYPE1"='TABLE')

  2 - access("OWNER1"='SCOTT')

 

已选择15行。

 

 

注意：owner1和type1上均有B*索引，而且均出现在where条件上。结果采用的Scan方式，而且只使用到了一个索引对象。

 

 

Bitmap Index索引实验

 

此次使用Bitmap Index列对应查询条件。

 

//索引处理

SQL> alter index idx_t_type2bit rebuild;

Index altered

 

SQL> alter index idx_t_owner2bit rebuild;

Index altered

 

SQL> alter index idx_t_owner1 unusable;

Index altered

 

SQL> alter index idx_t_type1 unusable;

Index altered

 

SQL> explain plan for select * from t where owner2='SCOTT' and type2='TABLE';

已解释。

 

SQL> select * from table(dbms_xplan.display);

PLAN_TABLE_OUTPUT

-------------------------------------------------------------------------------------------------

Plan hash value: 244872826

 

------------------------------------------------------------------------------------------------

| Id | Operation                   | Name           | Rows | Bytes | Cost (%CPU)| Time    |

------------------------------------------------------------------------------------------------

|  0 | SELECT STATEMENT            |     |   61 | 1708 |   13  (0)| 00:00:01 |

|  1 | TABLE ACCESS BY INDEX ROWID | T |   61 | 1708 |   13  (0)| 00:00:01 |

|  2 |  BITMAP CONVERSION TO ROWIDS|     |  |      |  |         |

|  3 |   BITMAP AND    |   |      |      |           |         |

|* 4 |    BITMAP INDEX SINGLE VALUE| IDX_T_TYPE2BIT | |      | | |

|* 5 |    BITMAP INDEX SINGLE VALUE| IDX_T_OWNER2BIT |      |      | | |

------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):

---------------------------------------------------

  4 - access("TYPE2"='TABLE')

  5 - access("OWNER2"='SCOTT')

 

已选择18行。

 

 

 

在一个SQL中，两个Bitmap索引均使用到。

 

下面实验一个比较复杂的条件。

 

 

SQL> explain plan for select * from t where owner2='SCOTT' and (type2='TABLE' or type2='INDEX');

已解释。

 

SQL> select * from table(dbms_xplan.display);

 

PLAN_TABLE_OUTPUT

--------------------------------------------------------------------------------------------------

Plan hash value: 3499411373

 

-------------------------------------------------------------------------------------------------

| Id | Operation                    | Name           | Rows | Bytes | Cost (%CPU)| Time    |

-------------------------------------------------------------------------------------------------

|  0 | SELECT STATEMENT  |       |  122 | 3416 |   24  (5)| 00:00:01 |

|  1 | TABLE ACCESS BY INDEX ROWID | T  |  122 | 3416 |   24  (5)| 00:00:01 |

|  2 |  BITMAP CONVERSION TO ROWIDS |    |      |      |           |  |

|  3 |   BITMAP AND                |       |      |      |   |         |

|* 4 |    BITMAP INDEX SINGLE VALUE | IDX_T_OWNER2BIT |   |   |   |  |

|  5 |    BITMAP OR    |     |      |      |           |         |

|* 6 |     BITMAP INDEX SINGLE VALUE| IDX_T_TYPE2BIT |  |  | |         |

|* 7 |     BITMAP INDEX SINGLE VALUE| IDX_T_TYPE2BIT |  |  |  |   |

-------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):

---------------------------------------------------

  4 - access("OWNER2"='SCOTT')

  6 - access("TYPE2"='INDEX')

  7 - access("TYPE2"='TABLE')

 

已选择21行。

 

 

请注意Bitmap系列and和or操作，和我们在开篇中做的模拟计算如出一辙。

 

 

Bitmap Index是一种适应范围比较窄，但是特效针对性很强的索引类型。在一些场合下合适使用，可以带来出乎意料的效果。