[20150204]关于位图索引3.txt

[20150204]关于位图索引3.txt

--许多人知道在oltp系统不适合使用位图索引.它的索引的记录结构如下是:
字段0:键值
字段1:开始rowid
字段2:结束rowid
字段3:位图信息,指示那行记录,位图1=>表示存在.位图0=>表示不存在.

--但是字段4的位图信息,介绍的资料太少,我自己看了链接http://juliandyke.com/Presentations/BitmapIndexInternals.ppt,做一个简单探究.
--昨天讲了Single-Byte Groups,再总结如下:

1.Byte represents the number of zero bits followed by a one bit
2.Maximum of 191 zero bits
3.Range of byte values is 0x00 to 0xBF

--如果仔细看可以发现Single-Byte Groups,仅仅出现1个1,如果8位里面包含两个1,这种方式就无法表示.而且还受到前导0的限制最多191个0.
--这样就出现Multi-Byte Groups.还是参考http://juliandyke.com/Presentations/BitmapIndexInternals.ppt文档:

Multi-Byte Groups
. Multi-byte groups allow more than 192 bits to be skipped
. First byte is a control byte 11
. First two bits indicate this is a control byte (always 11)

. Next three bits indicate number of zero bytes to skip

. If all three bits are set then number overflows to second byte
. If top bit of second byte is set then number of zero bytes overflows to third byte
. Last three bits indicate number of bytes following control  block (minimum 1, maximum 8)

--上面的表述不是很好理解.至少我看了很久都无法理解,我自己总结如下(现在才觉得自己的语文没学好,但愿我能描述清楚):
--第1字节大于等于192,使用Multi-Byte Groups.但愿我能讲清楚里面的一些细节,也可能讲的不对.希望知道能指正谢谢!!!

1.首先前面2位一定是11,只有这样才能大于192.也叫控制位.
2.下面3位表示0字节的数量.
         字节数量      0bit的数量 
=================================
001         0               0
010         1               8
011         2              16 
100         3              24
101         4              32
110         5              40
==================================

其中3位=111,必须扩展到下一字节.

                          字节数量      0bit的数量 
==================================================
111000 00000000                  6            48
111000 00000001                  7            56
111000 00000010                  8            64
....
111000 01111111                133      133*8=1064
111000 10000000 00000001       134      134*8=1072
111000 10000001 00000001       135      135*8=1080
==================================================

. Last three bits indicate number of bytes following control block (minimum 1, maximum 8)
--最后3位是表示位图信息的长度,这里注意000,表示后面占用1个字节. ... 111表示占用8个字节.

1.建立测试环境:
SCOTT@test> @ver1
PORT_STRING                    VERSION        BANNER
------------------------------ -------------- --------------------------------------------------------------------------------
x86_64/Linux 2.4.xx            11.2.0.3.0     Oracle Database 11g Enterprise Edition Release 11.2.0.3.0 - 64bit Production

--drop table t purge;
create table t(id number , name varchar2(10), status varchar2(1));
insert into t select rownum-1 id,dbms_random.string('X',10) c20,decode(mod((rownum-1),8),0,'Y','N') c1 from dual connect by levelcommit ;
create bitmap index ib_t_status on t(status);

SCOTT@test> select owner,segment_name,header_file,header_block  from dba_segments where owner=user and segment_name='IB_T_STATUS';

OWNER  SEGMENT_NAME         HEADER_FILE HEADER_BLOCK
------ -------------------- ----------- ------------
SCOTT  IB_T_STATUS                    4          530

SCOTT@test> select rowid,t.* from t where rownumROWID                      ID NAME                 S
------------------ ---------- -------------------- -
AABI+0AAEAAAACnAAA          0 1DDKXFS06B           Y
AABI+0AAEAAAACnAAB          1 MD5WQEJ31X           N
AABI+0AAEAAAACnAAC          2 UEPVVKFJR0           N
AABI+0AAEAAAACnAAD          3 X5AYXHD6YH           N
AABI+0AAEAAAACnAAE          4 1UX5F7CB7O           N

SCOTT@test> @lookup_rowid AABI+0AAEAAAACnAAA
    OBJECT       FILE      BLOCK        ROW DBA                  TEXT
---------- ---------- ---------- ---------- -------------------- ----------------------------------------
    298932          4        167          0 4,167                alter system dump datafile 4 block 167 ;

--注:我每次删除除了data_OBJECT_id发生变化,其它基本不变.

row#0[8003] flag: ------, lock: 0, len=29
col 0; len 1; (1):  4e
col 1; len 6; (6):  01 00 00 a7 00 00
col 2; len 6; (6):  01 00 00 a7 00 47
col 3; len 10; (10):  cf fe fe fe fe fe fe fe fe 01
row#1[7974] flag: ------, lock: 0, len=29
col 0; len 1; (1):  59
col 1; len 6; (6):  01 00 00 a7 00 00
col 2; len 6; (6):  01 00 00 a7 00 47
col 3; len 10; (10):  cf 01 01 01 01 01 01 01 01 00
----- end of leaf block dump -----
End dump data blocks tsn: 4 file#: 4 minblk 531 maxblk 531

--0x47=71,我仅仅插入66条,可以发现结束rowid是补齐8位整除的.
--看看键值status='Y'的col3:,其它前面已经介绍,这里不在说明了.
cf 01 01 01 01 01 01 01 01 00

cf 拆开二进制 11 001 111
-- 11 大于192.表示Multi-Byte Groups
-- 001 表示 0个字节0
-- 111 表示8个字节长度.我的例子是0,8,16..的位置出现.
-- 注意后面还有1个00,这个前面讲的单字节组,表示10000000,也就是row=64的记录是status.
-- 从另外一个侧面也说明单字节组与多字节组可以混合编码的.

SCOTT@test> select * from t where status='Y';
        ID NAME                 S
---------- -------------------- -
         0 1DDKXFS06B           Y
         8 9FKXWZ29S1           Y
        16 S3A7A96RJD           Y
        24 J30XPHSFIN           Y
        32 N7DBOGUDNZ           Y
        40 0QDGDKADFY           Y
        48 09VWEEWBJN           Y
        56 2HB0AV0TX2           Y
        64 NTO2X2PP12           Y
9 rows selected.

2.做1个修改测试:
update t set status='N' where id=64;
commit ;
alter system checkpoint ;
alter system dump datafile 4 block 531 ;

row#0[7944] flag: ------, lock: 2, len=30
col 0; len 1; (1):  4e
col 1; len 6; (6):  01 00 00 a7 00 00
col 2; len 6; (6):  01 00 00 a7 00 47
col 3; len 11; (11):  cf fe fe fe fe fe fe fe fe c8 03
row#1[7915] flag: -----R, lock: 2, len=28, rsl=1
col 0; len 1; (1):  59
col 1; len 6; (6):  01 00 00 a7 00 00
col 2; len 6; (6):  01 00 00 a7 00 3f
col 3; len 9; (9):  cf 01 01 01 01 01 01 01 01
----- end of leaf block dump -----
End dump data blocks tsn: 4 file#: 4 minblk 531 maxblk 531

-- 可以发现行地址发生了变化,col3长度发生了变化,减少1个字节.注意看还改变了结束rowid.

3.看看自己能否造一个col3的值是否正确.

DA 03 04 05

--DA 拆开
--11 011 010
-- 11 大于192.表示Multi-Byte Groups
-- 011 表示 2个字节 0
-- 010 表示3个字节长度.

--也就是前面16个0, 00000011 00000100 00000101
--drop table t purge;
create table t(id number , name varchar2(10), status varchar2(1));
insert into t select rownum-1 id,dbms_random.string('X',10) c20,'N' c1 from dual connect by levelcommit ;

--注意如果前面开始是8个0的话,开始rowid不会是0000 (开始rowid的后2个字节),从id=24(8_2*8=24)开始构造.

update t set status='Y' where id=0;
update t set status='Y' where id=24;
update t set status='Y' where id=25;
update t set status='Y' where id=34;
update t set status='Y' where id=40;
update t set status='Y' where id=42;
commit ;

create bitmap index ib_t_status on t(status);

alter system checkpoint ;
alter system dump datafile 4 block 531 ;

row#0[8002] flag: ------, lock: 0, len=30
col 0; len 1; (1):  4e
col 1; len 6; (6):  01 00 00 a7 00 00
col 2; len 6; (6):  01 00 00 a7 00 47
col 3; len 11; (11):  cf fe ff ff fc fb fa ff ff c8 03
row#1[7978] flag: ------, lock: 0, len=24
col 0; len 1; (1):  59
col 1; len 6; (6):  01 00 00 a7 00 00
col 2; len 6; (6):  01 00 00 a7 00 2f
col 3; len 5; (5):  00 da 03 04 05
----- end of leaf block dump -----
End dump data blocks tsn: 4 file#: 4 minblk 531 maxblk 531

--这里再次验证我的猜测是正确的.
--再来展开status='N'的情况:

col 3; len 11; (11):  cf fe ff ff fc fb fa ff ff c8 03

-- cf 拆开
-- 11 001 111
-- 11 大于192.表示Multi-Byte Groups
-- 001 表示 0个字节 0
-- 111 表示8个字节长度.
   fe       ff       ff       fc        fb        fa        ff       ff
   11111110 11111111 11111111 11111100  11111011  11111010  11111111 11111111
--为了对着方便我左右置换看看.
   01111111 11111111  11111111 00111111  11011111  01011111  11111111 11111111
--再连在一起. 
0111111111111111111111110011111111011111010111111111111111111111
--简单检查使用vim移到开头,执行24l,看看是否可以定位的是0.

--还没有完成.剩下C803
-- c8 拆开
-- 11 001 000
-- 11 大于192.表示Multi-Byte Groups
-- 001 表示 0个字节 0
-- 000 表示1个字节长度.
00000011

--再从右往左看,前面已经占了8*8=64位,这样剩下的11就是对用id=65,66的记录了.

--我这里仅仅讲解了在1个数据块的情况,如果开始rowid与结束rowid在不同数据块的情况呢?自己再做一些验证.
--且看下一篇blog.也许不再写了^_^.

--实际上我写第1篇时一直有一个疑问:
create table t(id number , name varchar2(10), status varchar2(1));
insert into t select rownum-1 id,dbms_random.string('X',10) c20,decode(mod((rownum-1),8),0,'Y','N') c1 from dual connect by levelcommit ;
create bitmap index ib_t_status on t(status);

--status='Y'的col3对应的是
col 3; len 9; (9):  cf 01 01 01 01 01 01 01 01
--为什么不使用单字节组 00 00 00 00 00 00 00 00 表示,而使用多字节组来表示,后面的编码更短,难道不能全是0吗?

--再做一个测试:
--drop table t purge;
create table t(id number , name varchar2(10), status varchar2(1));
insert into t select rownum-1 id,dbms_random.string('X',10) c20,decode(mod((rownum-1),8),1,'Y','N') c1 from dual connect by levelcommit ;
SCOTT@test> select * from t where status='Y';
        ID NAME                 S
---------- -------------------- -
         1 1H2YD3EUJG           Y
         9 LTHF8GKDUP           Y
        17 0XK5EGWLZF           Y
        25 PONO8HR4KX           Y
        33 OVEF0K35C8           Y
        41 L23DBSZ5IC           Y
        49 DK18XVX8J4           Y
        57 IB6XNM5Z8W           Y
8 rows selected.

create bitmap index ib_t_status on t(status);
alter system checkpoint ;
alter system dump datafile 4 block 531 ;

row#0[8004] flag: ------, lock: 0, len=28
col 0; len 1; (1):  4e
col 1; len 6; (6):  01 00 00 a7 00 00
col 2; len 6; (6):  01 00 00 a7 00 3f
col 3; len 9; (9):  cf fd fd fd fd fd fd fd fd
row#1[7976] flag: ------, lock: 0, len=28
col 0; len 1; (1):  59
col 1; len 6; (6):  01 00 00 a7 00 00
col 2; len 6; (6):  01 00 00 a7 00 3f
col 3; len 9; (9):  cf 02 02 02 02 02 02 02 02

-- 搞不懂oracle内部如何处理,为什么选择这种编码模式.....