再上一篇:11.1 Oracle索引概述
上一篇:11.2 B*树索引
主页
下一篇:11.4基于函数的索引
再下一篇:11.5应用域索引
文章列表

11.3位图索引

Oracle 9i 10g编程艺术:深入数据库体系结构

位图索引(bitmap index)是从Oracle7.3版本开始引入的。目前Oracle企业版和个人版都支持位 图索引,但标准版不支持。位图索引是为数据仓库/即席查询环境设计的,在此所有查询要求的数据在系统 实现时根本不知道。位图索引特别不适用于OLTP系统,如果系统中的数据会由多个并发会话频繁地更新,
这种系统也不适用位图索引。 位图索引是这样一种结构,其中用一个索引键条目存储指向多行的指针;这与B*树结构不同,在B*
树结构中,索引键和表中的行存在着对应关系。在位图索引中,可能只有很少的索引条目,每个索引条目
指向多行。而在传统的B*树中,一个索引条目就指向一行。

下面假设我们要在EMP表的JOB列上创建一个位图索引,如下:
Ops$tkyte@ORA10G> create BITMAP index job_idx on emp(job);
Index created.
Oracle在索引中存储的内容如表11.-6所示。
表11.-6 Oracle如何存储JOB-IDX位图索引
值/行 1 2 3 4 5 6 7 8 9 11. 11. 11. 11. 11. ANALYST 0 0 0 0 0 0 0 1 0 1 0 0 1 0
CLERK 1 0 0 0 0 0 0 0 0 0 1 1 0 1
MANAGER 0 0 0 1 0 1 1 0 0 0 0 0 0 0
PRESIDENT 0 0 0 0 0 0 0 0 1 0 0 0 0 0
SALESMAN 0 1 1 0 1 0 0 0 0 0 0 0 0 0
表11.-6显示了第8、11.和11.行的值为ANALYST,而第4、6和7行的值为MANAGER。在此还显示了 所有行都不为null(位图索引可以存储null条目;如果索引中没有null条目,这说明表中没有null行)。 如果我们想统计值为MANAGER的行数,位图索引就能很快地完成这个任务。如果我们想找出JOB为CLERK 或MANAGER的所有行,只需根据索引合并它们的位图,如表11.-7 所示。
表 11.-7 位OR的表示
值/行 1 2 3 4 5 6 7 8 9 11. 11. 11. 11. 11. CLERK 1 0 0 0 0 0 0 0 0 0 1 1 0 1
MANAGER 0 0 0 1 0 1 1 0 0 0 0 0 0 0
CLERK 或 1 0 0 1 0 1 1 0 0 0 1 1 0 1
MANAGER
表 11.-7清楚地显示出,第1、4、6、7、11.、11.还11.行满足我们的要求。Oracle如下为每个键 值存储位图,使得每个位置表示底层表中的一个rowid,以后如果确实需要访问行时,可以利用这个rowid 进行处理。对于以下查询:

select count(*) from emp where job = 'CLERK' or job = 'MANAGER'

用位图索引就能直接得出答案。另一方面,对于以下查询:
select * from emp where job = 'CLERK' or job = 'MANAGER'
则需要访问表。在此Oracle会应用一个函数把位图中的第i位转换为一个rowid,从而可用于访问
表。

11.3.1什么情况下应该使用位图索引?

位图索引对于相异基数(distinct cardinality)低的数据最为合适(也就是说,与职工数据集的基 数相比,这个数据只有很少几个不同的值)。对此做出量化是不太可能的——换句话说,很难定义低相异基 数到底是多大。在一个有几千条记录的数据集中,2就是一个低相异基数,但是在一个只有两行的表中,2 就不能算是低相异基数了。而在一个有上千万或上亿条记录的表中,甚至100,000都能作为一个低相异基 数。所以,多大才算是低相异基数,这要相对于结果集的大小来说。这是指,行集中不同项的个数除以行 数应该是一个很小的数(接近于0)。例如,GENDER 列可能取值为M、F 和NULL。如果一个表中有20,000 条员工记录,那么3/20000=0.00015。类似地,如果有100,000个不同的值,与11.,000,000条结果相比, 比值为0.01,同样这也很小(可算是低相异基数)。这些列就可以建立位图索引。它们可能不适合建立B* 树索引,因为每个值可能会获取表中的大量数据(占很大百分比)。如前所述,B*树索引一般来讲应当是选 择性的。与之相反,位图索引不应是选择性的,一般来讲它们应该“没有选择性“。

如果有大量即席查询,特别是查询以一种即席方式引用了多列或者会生成诸如 COUNT之类的聚合,在 这样的环境中,位图索引就特别有用。例如,假设你有一个很大的表,其中有3列:GENDER、LOCATION和 AGE_GROUP。在这个表中,GENDER只有两个可取值:M或F,LOCATION可取值为11.50,AGE_GROUP是一个 代码,分别表示11. and under(11.及以下)、11.-25、26-30、31-40和41 and over(41及以上)。你必 须支持大量即席查询,形式如下:
Select count(*)
from T
where gender = 'M'
and location in ( 1, 11., 30 )
and age_group = '41 and over';
select *
from t
where ( ( gender = 'M' and location = 20 )
or ( gender = 'F' and location = 22 ))
and age_group = '11. and under';
select count(*) from t where location in (11.,20,30);
select count(*) from t where age_group = '41 and over' and gender = 'F';

你会发现,这里使用传统的B*树索引机制是不行的。如果你想使用一个索引来得到答案,就需要组
合至少 3~6 个可能的 B*树索引,才能通过索引访问数据。由于这 3列或它们的任何子集都有可能出现, 所以需要在以下列上建立很大的串联B*树索引:
GENDER、LOCATION和 AGE_GROUP:对应使用了这3列、使用了GENDER和 LOCATION或者仅 使用GENDER的查询。
LOCATION、AGE_GROUP:对应使用了LOCATION和AGE_GROUP或者仅使用LOCATION的查询。 AGE_GROUP、GENDER:对应使用了AGE_GROUP和GENDER或者仅使用LOCATION的查询。
要减少搜索的数据量,还可以有其他排列,以减少所扫描索引结构的大小。这是因为在此忽略了这样 一个重要事实:对这种低基数数据建立B*树索引并不明智。

这里位图索引就能派上用场了。利用分别建立在各个列上的 3个较小的位图索引,就能高效地满足前 面的所有谓词条件。对于引用了这3列(其中任何一例及任何子集)的任何谓词,Oracle只需对3个索引 的位图使用函数AND、OR和NOT,就能得到相应的结果集。它会得到合并后的位图,如果必要还可以将位 图中的“1”转换为rowid来访问数据(如果只是统计与条件匹配的行数,Oracle就只会统计“1”位的个 数)。下面来看一个例子。首先,生成一些测试数据(满足我们指定的相异基数),建立索引,并收集统计。 我们将利用DBMS_RANDOM包来生成满足我们的分布要求的随机数据:
ops$tkyte@ORA10G> create table t
2 ( gender not null,
3 location not null,
4 age_group not null,
5 data
6 )
7 as
8 select decode( ceil(dbms_random.value(11.2)),
9 1, 'M',
11. 2, 'F' ) gender,
11. ceil(dbms_random.value(11.50)) location,

11. decode( ceil(dbms_random.value(11.5)),
11. 1,'11. and under',
11. 2,'11.-25',
11. 3,'26-30',
11. 4,'31-40',
11. 5,'41 and over'),
11. rpad( '*', 20, '*')
11. from big_table.big_table
20 where rownum <= 100000; Table created.
ops$tkyte@ORA10G> create bitmap index gender_idx on t(gender); Index created.
ops$tkyte@ORA10G> create bitmap index location_idx on t(location); Index created.
ops$tkyte@ORA10G> create bitmap index age_group_idx on t(age_group); Index created.
ops$tkyte@ORA10G> exec dbms_stats.gather_table_stats( user, 'T', cascade=>true ); PL/SQL procedure successfully completed.

现在来看前面各个即席查询的相应查询计划:
ops$tkyte@ORA10G> Select count(*)

2 from T
3 where gender = 'M'
4 and location in ( 1, 11., 30 )
5 and age_group = '41 and over';
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=5 Card=11.Bytes=11.)
11.0 SORT (AGGREGATE)
2 1 BITMAP CONVERSION (COUNT) (Cost=5 Card=11.Bytes=11.)
3 2 BITMAP AND
4 3 BITMAP INDEX (SINGLE VALUE) OF 'GENDER_IDX' (INDEX (BITMAP))
5 3 BITMAP OR
6 5 BITMAP INDEX (SINGLE VALUE) OF 'LOCATION_IDX' (INDEX (BITMAP))
7 5 BITMAP INDEX (SINGLE VALUE) OF 'LOCATION_IDX' (INDEX (BITMAP))
8 5 BITMAP INDEX (SINGLE VALUE) OF 'LOCATION_IDX' (INDEX (BITMAP))
9 3 BITMAP INDEX (SINGLE VALUE) OF 'AGE_GROUP_IDX' (INDEX (BITMAP))
这个例子展示出了位图索引的强大能力。Oracle能看到location in (11.11.,30),知道要读取这3

个位置(对于这3个值的位置)上的索引,并在位图中对这些“位”执行逻辑OR。然后将得到的位图与 AGE_GROUP=’41 AND OVER’和GENDER=’M’的相应位图执行逻辑AND。再统计”1”的个数,这就得到了 答案:
ops$tkyte@ORA10G> select *
2 from t
3 where ( ( gender = 'M' and location = 20 )
4 or ( gender = 'F' and location = 22 ))
5 and age_group = '11. and under';
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=77 Card=507 Bytes=16731)
11.0 TABLE ACCESS (BY INDEX ROWID) OF 'T' (TABLE) (Cost=77 Card=507 ...
2 1 BITMAP CONVERSION (TO ROWIDS)
3 2 BITMAP AND
4 3 BITMAP INDEX (SINGLE VALUE) OF 'AGE_GROUP_IDX' (INDEX (BITMAP))
5 3 BITMAP OR
6 5 BITMAP AND
7 6 BITMAP INDEX (SINGLE VALUE) OF 'LOCATION_IDX' (INDEX (BITMAP))
8 6 BITMAP INDEX (SINGLE VALUE) OF 'GENDER_IDX' (INDEX (BITMAP))
9 5 BITMAP AND
11. 9 BITMAP INDEX (SINGLE VALUE) OF 'GENDER_IDX' (INDEX (BITMAP))
11. 9 BITMAP INDEX (SINGLE VALUE) OF 'LOCATION_IDX' (INDEX (BITMAP))

这个逻辑与前面是类似的,由计划显示:这里执行逻辑OR的两个条件是通过AND适当的位图逻辑计
算得到的,然后再对这些结果执行逻辑OR 得到一个位图。再加上另一个AND条件(以满足AGE_GROUP=’
11.’ AND UNDER),我们就找到了满足所有条件的结果。由于这一次要请求具体的行,所以Oracle会把位 图中的各个“1“和”0“转换为rowid,来获取源数据。
在一个数据仓库或支持多个即席SQL查询的大型报告系统中,能同时合理地使用尽可能多的索引确实 非常有用。这里不常使用传统的B*树索引,甚至不能使用B*树索引,随着即席查询要搜索的列数的增加, 需要的B*树索引的组合也会飞速增长。
不过,在某些情况下,位图并不合适。位图索引在读密集的环境中能很好地工作,但是对于写密集的 环境则极不适用。原因在于,一个位图索引键条目指向多行。如果一个会话修改了所索引的数据,那么在 大多数情况下,这个索引条目指向的所有行都会被锁定。Oracle无 法锁定一个位图索引条目中的单独一 位;而是会锁定这个位图索引条目。倘若其他修改也需要更新同样的这个位图索引条目,就会被“关在门 外“。这样将大大影响 并发性,因为每个更新都有可能锁定数百行,不允许并发地更新它们的位图列。在
此不是像你所想的那样锁定每一行,而是会锁定很多行。位图存储在块(chunk)中,所以,使用前面的 EMP例子就可以看到,索引键ANALYST在索引中出现了多次,每一次都指向数百行。更新一行时,如果修 改了JOB列,则需要独占地访问其中两个索引键条目:对应老值的索引键条目和对应新值的索引键条目。 这两个条目指向的数百行就不允许其他会话修改,直到UPDATE提交。

11.3.2位图联结索引

Oracle9i引入了一个新的索引类型:位图联结索引(bitmap join index)。通常都是在一个表上创 建索引,而且只使用这个表的列。位图联结索引则打破了这个规则,它允许使用另外某个表的列对一个给 定表建立索引。实际上,这就允许对一个索引结构(而不是表本身)中的数据进行逆规范化。
考虑简单的EMP表和DEPT表。EMP有指向DEPT的一个外键(DEPTNO列)。DEPT表有一个DNAME属性

(部门名)。最终用户会频繁地问这样的问题:“销售部门有多少人?“”谁在销售部门工作?“”可以告 诉我销售部门中业绩最好的前N个人吗?“注意他们没有这样问:”DEPTNO为30的部门中有多少人?“他 们没有用这些键值;而是用了人可读的部门名。因此,最后运行的查询如下所示:
select count(*)
from emp, dept
where emp.deptno = dept.deptno and dept.dname = 'SALES'
/
select emp.*
from emp, dept
where emp.deptno = dept.deptno and dept.dname = 'SALES'
/
使用传统索引的话,这些查询中 DEPT表和EMP表都必须访问。我们可以使用DEPT.DNAME上的一个索
引来查找SALES 行,并获取SALES 的DEPTNO值,然后使用EMP.DEPTNO上的一个索引来查找匹配的行,但 是如果使用一个位图联结索引,就不需要这些了。利用位图联结索引,我们能对DEPT.DNAME列建立索引, 但这个索引不是指向DEPT表,而是指向EMP表。这是一个全新的概念:能从其他表对某个表的属性建立索 引,而这可能会改变你的报告系统中实现数据模型的方式。实际上,可以鱼和熊掌兼得,一方面保持规范 化数据结构不变,与此同时还能得到逆规范化的好处。

以下是我们为这个例子创建的索引:
ops$tkyte@ORA10G> create bitmap index emp_bm_idx

2 on emp( d.dname )
3 from emp e, dept d
4 where e.deptno = d.deptno
5 /
Index created.
注意,这个CREATE INDEX开始看上去很“正常“,它会在表上创建索引INDEX_NAME。但之后就不那

么”正常“了。可以看到在此引用了DEPT表中的一列:D.DNAME。这里有一个FROM子句。使这个CREATE INDEX 语句有些像查询。另外,多个表之间有一个联结条件。这个CREATE INDEX语句对DEPT.DNAME列建立了索 引,但这在EMP表的上下文中。对于前面提到的那些问题,我们会发现数据库根本不会访问DEPT,而且也 不需要访问DEPT,因为 DNAME列现在是在指向EMP表中的行的索引中。为了便于说明,我们把 EMP表和DEPT 表制作得看上去很”大“(以避免CBO认为它们很小,以至于选择执行全面扫描,而不是使用索引):
ops$tkyte@ORA10G> begin
2 dbms_stats.set_table_stats( user, 'EMP',
3 numrows => 1000000, numblks => 300000 );
4 dbms_stats.set_table_stats( user, 'DEPT',
5 numrows => 100000, numblks => 30000 );
6 end;
7 /
PL/SQL procedure successfully completed.
然后再执行查询:
ops$tkyte@ORA10G> set autotrace traceonly explain
ops$tkyte@ORA10G> select count(*)
2 from emp, dept
3 where emp.deptno = dept.deptno
4 and dept.dname = 'SALES'

5 / Execution Plan

----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=11.Card=11.Bytes=11.)
11.0 SORT (AGGREGATE)
2 1 BITMAP CONVERSION (COUNT) (Cost=11.Card=10000 Bytes=130000)
3 2 BITMAP INDEX (SINGLE VALUE) OF 'EMP_BM_IDX' (INDEX (BITMAP))
可以看到,要回答这个特定的问题,我们不必真正去访问 EMP表或DEPT表,答案全部来自索引本身。
回答这个问题所需的全部信息都能在索引结构中找到。

另外,我们还能避免访问 DEPT表,使用EMP上的索引就能从DEPT合并我们需要的数据,直接访问我 们所需的行:
ops$tkyte@ORA10G> select emp.*
2 from emp, dept
3 where emp.deptno = dept.deptno
4 and dept.dname = 'SALES'
5 / Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=6145 Card=10000 Bytes=870000)
11.0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (TABLE) (Cost=6145 Card=10000 ...
2 1 BITMAP CONVERSION (TO ROWIDS)
3 2 BITMAP INDEX (SINGLE VALUE) OF 'EMP_BM_IDX' (INDEX (BITMAP))
位图联结索引确实有一个先决条件。联结条件必须联结到另一个表中的主键或惟一键。在前面的例子

中,DEPT.DEPTNO就是DEPT表的主键,而且这个主键必须合适,否则就会出现一个错误:
ops$tkyte@ORA10G> create bitmap index emp_bm_idx
2 on emp( d.dname )
3 from emp e, dept d
4 where e.deptno = d.deptno

5 /
from emp e, dept d
* ERROR at line 3:
ORA-25954: missing primary key or unique constraint on dimension

11.3.3位图索引小结

如果还犹豫不定,你可以亲自试一试。向一个表(或一组表)增加位图索引很容易,你可以自己看看 位图索引会做些什么。另外,创建位图索引通常比创建B*树索引快得多。要查看位图索引是否适用于你的 环境,最好的办法就是动手实验。经常有人问我:“怎么定义低基数?“对这个问题并没有直截了当的答案 。 有时,在100,000行的表中3 就是一个低基数;而有时在11.000,000行的表中11.,000也是一个低基数。 低基数并不是说不同的值有几位数字。要想知道你的应用中是否适合使用位图,最好做个实验。一般而言, 如果是一个很大的环境,主要是只读操作,并且有大量即席查询,你所需要的可能正是一组位图索引。