Hadoop组件之-HIVE(位图索引)

索引概述

 

• 什么是索引？

 

索引是Oracle数据库中提供的一种可选的数据结构，用于关联一个表。

 

•  为什么要使用索引？

 

索引在有些情况下可以加快访问速度，减少磁盘IO。

 

• 通常情况下时候使用索引？

 

 

1. 表中的某列经常会在查询中使用，并且经常用返回占表中数据总量比例较少的row set。
2. 引用完整性约束列。
3. unique key 。

 

 

下面我们来简述一下两种常见的索引类型：B-Tree索引以及BitMap索引。

B-Tree 索引

B*Tree索引，这是OracleDatabase中最常用的索引类型，在各种Oracle各种数据库类型中都得到了广泛的使用。原理上来讲，它的逻辑结构就像一个B-树，一种多路搜索树（非二叉树），并且不管在Oracle数据库在维护索引的过程中，branch block 和 leaf block 如何分裂，或者收缩，它一直保持平衡状态（平衡树），这意味着我们需要的数据也就是leaf block都存放在相同的level上面（height-1）。

逻辑结构

逻辑结构如下图所示：

如上图所示，每个branch block 都拥有其child block的指针。每个indexentry都只指向一单一的row。如下所示：

 

row#0[8024] flag: ------, lock: 0, len=12
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  01 10 7a 5300 00
row#1[7796] flag: ------, lock: 0, len=12
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  01 10 7a 5500 00
row#2[7676] flag: ------, lock: 0, len=12
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  01 10 7a 5500 0a
row#3[7556] flag: ------, lock: 2, len=12
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  01 10 7a 5500 14
row#4[7436] flag: ------, lock: 2, len=12
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  01 10 7a 5500 1e
row#5[8012] flag: ------, lock: 0, len=12
col 0; len 2; (2):  c1 03
col 1; len 6; (6):  01 10 7a 5300 01

 

 

可以看到，每一个index entry都指向单一的rowid，相同index key value下的行按照rowid asc排列。

我觉得，它不像是树，更像是一个森林。

B-tree索引维护要点

计算要创建索引的大小

可以使用dbms_space.create_index_cost存储过程来预估创建index需要的存储空间。这个操作比较依赖于数据字典中的表统计信息，所以在使用之前需要执行dbms_stats.gather_table_stats。

相关说明：

 

DBMS_SPACE.CREATE_INDEX_COST (
  ddl             IN    VARCHAR2,
  used_bytes      OUT   NUMBER,
  alloc_bytes     OUT   NUMBER,
  plan_table      IN    VARCHAR2 DEFAULT NULL);

 

Parameter	Description
ddl	The create index DDL statement
used_bytes	The number of bytes representing the actual index data
alloc_bytes	Size of the index when created in the tablespace
plan_table	Which plan table to use, default NULL

Usage Notes

• The table on which the index is created must already exist.
• The computation of the index size depends on statistics gathered on the segment.
• It is imperative that the table must have been analyzed recently.
• In the absence of correct statistics, the results may be inaccurate, although the procedure will not raise any errors.

考虑分离索引段到专用的表空间

以下几个情况，可以考虑分离索引段：

1.     对于表和索引，制定不同的备份策略。对于索引数据和表中数据，可以适当的根据重要性来调整备份的周期。甚至可以选择不备份索引数据。

2.     分离索引和表的数据到不同的表空间，可以针对两者给予不同的存储选项。比如说，对于索引表空间，可以适当的调整extent 的大小和 logging选项等。

何时重建索引

 

ANALYZE INDEX &&index_name VALIDATESTRUCTURE;
col name        heading 'Index Name'          format a30
col del_lf_rows  heading 'Deleted|LeafRows'   format 99999999
col lf_rows_used heading 'Used|Leaf Rows'     format 99999999
col ibadness     heading '%Deleted|Leaf Rows' format 999.99999
SELECT name,
del_lf_rows,
lf_rows - del_lf_rows lf_rows_used,
to_char(del_lf_rows /(lf_rows)*100,'999.99999') ibadness
FROM index_stats
where name = upper('&&index_name');

 

 

当10%-15%索引数据更改的时候，就可以考虑重建索引了。

 

BitMap索引

 

Bitmap索引不像B-Tree索引，它的一个index entry可以指向更多的rows。通常它比较适用于以下两种情况：

1.     索引列拥有较低的基数，重复值较少。

2.     表是read only 模式，或者极少更改其中的数据。

不管是OLTP 或者 OLAP ，只要满足上面的情况，都可以使用BitMap索引（当然适用于OLAP比较多）。

逻辑结构

BitMap Index使用B-Tree的索引结构去存储索引数据。这里不再列出。

下面给出一个简单示例：

 

create table tb_test ( id number , gendervarchar2(1),level int) ;
insert into tb_test select level , ‘F’ , 1from dual connect by level<=3 ;
insert into tb_test select level , ‘M’,2 fromdual connect by level <=2 ;
create bitmap index tb_test_btidx1 ontb_test(gender) ;
create bitmap index tb_test_btidx2 ontb_test(level) ;

 

那么它的bitmap示意表如下：

键值	row#1	row#2	row#3	row#4	row#5
F	1	1	1	0	0
M	0	0	0	1	1
1	1	1	1	0	0
2	0	0	0	1	1
1 and F	1	1	1	0	0
2 or F	1	1	1	1	1

使用BitMap索引的性能提升（建立在low cardinality前提下）：

1.     相对于传统的B-Tree索引消耗更少的存储空间。

2.     查询更快，尤其是在拥有很多and、or 查询条件的时候。

3.     创建时间短（相对于B-Treeindex）。

 

缺点：

DML锁的代价非常昂贵。更新一个带有bitmap index 的数据的时候，会锁定拥有该indexkey value的所有行。这也是为什么它只适用在拥有非常少的DML或者根本没有DML操作的表上面。详细测试请见附录1.

 

相关介绍先介绍到这里，下面我们来简单比较一下B-Tree索引和BitMap 索引在不同情况下的性能。

B-Tree和BitMap索引性能比较

场景1

在拥有较低基数的列上创建索引

 

--create table
create table tb_btree2(idnumber , name varchar2(20)) ;
create table tb_bitmap2(idnumber , name varchar2(20)) ;

--init data
insert into tb_btree2 selecttrunc(dbms_random.value(1,100001)) , 'name'||level from dual connect by level<= 100000;
insert into tb_bitmap2 select* from tb_btree2 ;


--create index
create index tb_btree2_idx1on tb_btree2(id) ;
create bitmap indextb_bitmap2_btidx1 on tb_bitmap2(id) ;


--gather statistics
execdbms_stats.gather_table_stats ('dexter','tb_btree2',cascade=> true) ;
execdbms_stats.gather_table_stats ('dexter','tb_bitmap2',cascade=> true) ;

 

 

测试语句1

单值查询

select * from tb_btree2 where id = 10 ;

两种索引性能对比如下表所示，详细执行计划请见附录2

 

select * from table where where id = 10 ;
	consistent gets	scan operation
B-Tree index	5	index range scan
BitMap index	5	bitmap index single value

 

 

测试语句2

范围查询

select * from tb_btree2 where id < 100 ;

两种索引性能对比如下表所示，详细执行计划请见附录3

select * from table where where id < 10 ;
	consistent gets	scan operation
B-Tree index	101	index range scan
BitMap index	101	bitmap index range scan

 

总结：在基数较大的情况下BitMap也能发挥较好的作用。

场景2

在拥有较高基数的列上创建索引：

 

--create table
create table tb_btree3(id number , namevarchar2(20)) ;
create table tb_bitmap3(id number , namevarchar2(20)) ;

--init data
insert into tb_btree3 select trunc(dbms_random.value(1,100)), 'name'||level from dual connect by level <= 100000;
insert into tb_bitmap3 select * from tb_btree3;


--create index
create index tb_btree3_idx1 on tb_btree3(id) ;
create bitmap index tb_bitmap3_btidx1 ontb_bitmap3(id) ;


--gather statistics
exec dbms_stats.gather_table_stats('dexter','tb_btree3',cascade=> true) ;
exec dbms_stats.gather_table_stats('dexter','tb_bitmap3',cascade=> true) ;

 

测试语句1

单值查询

select * from tb_btree3 where id = 10

两种索引性能对比如下表所示，详细执行计划请见附录4

select * from table where where id = 10 ;
	consistent gets	scan operation
B-Tree index	365	table access full
BitMap index	289	bitmap index single value

 

可以看到，在基数较高的时候，表甚至都不再使用B-Tree索引来检索数据，而BitMap这个时候能够发挥较好的性能。

测试语句2

范围查询

select * from tb_btree3 where id < 10 ;

两种索引性能对比如下表所示，详细执行计划请见附录5

select * from table where where id < 10 ;
	consistent gets	scan operation
B-Tree index	917	table access full
BitMap index	916	table access full

 

由于检索的数据量太多，所以都使用了全表扫描。

 

总结

上面的几个测试简单的比较了一下在不同基数情况下，B-Tree索引以及BitMap索引所发挥的作用。可以看到，不管基数如何，BitMap索引都能够发挥较高的性能。而B-Tree索引在基数较高的情况下则无法提升查询的性能。下面附录6提供了BitMap 索引与基数之间的关系，以及一个比较直观线性图。另外，BitMap索引还可以在使用多种谓词 and 、or 的情况下大幅度的提升查询的性能。总结一下：

BitMap 适用范围：虽然BitMap索引能够提供较好的查询性能，但是因为BitMap索引在执行DML语句的时候，会锁定相关的bitmapsegment（dsi 402e p210），代价比较大，并且不支持唯一索引。所以它一般只适用于OLAP系统上的那些不常更新，或者根本不会执行DML语句的表上。

B-Tree 使用范围：对于unique 以及 primary key 一般都使用B-Tree索引，能够提升较高的性能，并且对比与BitMap索引来说，因为每一条Index entry只包含唯一的rowid，所以不需要额外的Lock，经常使用于OLTP系统当中。

 

附录

附录1 BitMap索引，DML锁相关测试

 

--bitmap index test

--create table
create table tb_bitmap_test (id number , gendervarchar2(1)) ;
--init data
insert into tb_bitmap_test select level , 'F'from dual connect by level <= 3 ;
insert into tb_bitmap_test select level , 'M'from dual connect by level <= 2 ;

--create index
create bitmap index tb_bitmap_test_btidx1 ontb_bitmap_test(gender) ;

 

 

 

	Session1	Session2	Description
T1	update tb_bitmap_test set gender='M' where id= 1 ;		session1执行的这个更新语句会将所有的bitmap segemnt锁住。
T2		dexter@ORCL> update tb_bitmap_test set gender='F' where id= 2 ;	因为session1已经将bitmap segment锁住，所以这里无法再执行删除，插入操作
T3		dexter@ORCL> insert into tb_bitmap_test values (6,'M') ;	因为session1已经将bitmap segment锁住，所以这里无法再执行插入操作
T4		dexter@ORCL> insert into tb_bitmap_test values (7,'F') ;	因为session1已经将bitmap segment锁住，所以这里无法再执行插入操作
T5		dexter@ORCL> delete tb_bitmap_test where id= 3 ;	因为session1已经将bitmap segment锁住，所以这里无法再执行删除操作
T6		dexter@ORCL> insert into tb_bitmap_test values (6,'N') ;	因为这里session2的插入操作不涉及index key value=’M’ and ‘F’被锁住的bitmap segment，所以可以正常插入

 

 

dexter@ORCL> insert into tb_bitmap_testvalues (6,'N') ;

 

1 row created.

附录2 select *from tb_btree2 where id = 10 ;

dexter@ORCL> select * from tb_btree2where id = 10 ;

 

 

 

dexter@ORCL> select * from tb_bitmap2where id = 10 ;

 

附录3 select *from tb_btree2 where id < 100 ;

dexter@ORCL> select * from tb_btree2where id < 100 ;

 

 

dexter@ORCL> select * from tb_bitmap2where id < 100 ;

 

附录4 select *from tb_btree3 where id = 10 ;

dexter@ORCL>  select * from tb_btree3 where id = 10 ;

 

dexter@ORCL>  select * from tb_bitmap3 where id = 10 ;

附录5 select *from tb_btree3 where id < 10 ;

dexter@ORCL>  select * from tb_btree3 where id < 10 ;

 

 

dexter@ORCL>  select * from tb_bitmap3 where id < 10 ;

附录6 BITMAPINDEXES AND CARDINALITY

这里引用Oracle®PerformanceSurvival Guide 126页的内容：

BITMAP INDEXES AND CARDINALITY

At what point should we decide that thecolumn has too many unique values to

be suitable for a bitmap index?

Most examples of bitmap indexes (includingthat in Figure 5-7) show multi-ple columns of verylow cardinality, such asgender, marital status, and so on.

When we look at those examples we’d beforgiven for thinking that bitmap in-dexes are not suitable when there are morethan a handful of key values.

In fact, bitmap indexes are capable ofperforming well even when there are

many thousands of unique values. Figure 5-8shows the relative performance of

bitmap and B*-Tree-based queries on amillion row table for columns varying be-tween 5 and 10,000 distinct values. Aswe can see, bitmap indexes are still quite

effective even when the number of distinctvalues is very large.

 

相关文档下载

 Oracle performance survival guide ：

http://download.csdn.net/detail/junegey_kimi/4363090

dsi402e-d12865_Data Types and block structure ：

http://download.csdn.net/detail/renfengjun/4945581