转帖]bitmap 的一点探究[_MySQL, Oracle及数据库讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  MySQL, Oracle及数据库讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 3728 | 回复: 0   主题: 转帖]bitmap 的一点探究[        下一篇 
kim
注册用户
等级:中校
经验:1729
发帖:222
精华:0
注册:2011-7-21
状态:离线
发送短消息息给kim 加好友    发送短消息息给kim 发消息
发表于: IP:您无权察看 2011-8-1 11:16:09 | [全部帖] [楼主帖] 楼主


bitmap 的一点探究

1:bitmap 索引是分段存储的,也就是说很多条记录可能是分做了N段来存储,也就是有N个begin/end ,当新的记录 insert 而使用以前未曾使用过的物理地址的时候,会产生一个bitmap 段来存储,就算只有一条记录

2: 当删除一条记录的时候,在bitmap 索引上做了一个delete 的标记并用一新的记录来标记了,下面请看具体的演示

3: 当 dml发生的时候,会lock住某个值的存储bit的那一rowid所在的记录,参考下面的 row 中 lock ,这样显然会影响并发

SQL> create table tn(a number, b number);
Table created.
SQL> insert into tn select rownum,mod(rownum,5) from all_objects where rownum < 21;
20 rows created.
SQL> commit;
Commit complete.
SQL> create bitmap index tn_bitmap on tn(b);
Index created.
SQL> exec show_space('tn_bitmap',user,'INDEX');
Free Blocks.............................0
Total Blocks............................16
Total Bytes.............................131072
Unused Blocks...........................14
Unused Bytes............................114688
Last Used Ext FileId....................3
Last Used Ext BlockId...................1954
Last Used Block.........................2
PL/SQL procedure successfully completed.
SQL> select * from tn;
A          B
---------- ----------
1          1
2          2
3          3
4          4
5          0
6          1
7          2
8          3
9          4
10          0
11          1
A          B
---------- ----------
12          2
13          3
14          4
15          0
16          1
17          2
18          3
19          4
20          0
20 rows selected.
SQL> alter system dump datafile 3 block 1955;
System altered.
Block header dump:  0x00c007a3
Object id on Block? Y
seg/obj: 0x66da  csc: 0x00.18a0d77  itc: 2  flg: -  typ: 2 - INDEX
fsl: 0  fnx: 0x0 ver: 0x01
Itl           Xid                  Uba         Flag  Lck        Scn/Fsc
0x01   xid:  0x0000.000.00000000    uba: 0x00000000.0000.00  ----    0  fsc 0x0000.00000000
0x02   xid:  0x0002.040.000000ea    uba: 0x00000000.0000.00  ----    0  fsc 0x0000.00000000
Leaf block dump
===============
header address 125987932=0x7826c5c
kdxcolev 0
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 4
kdxcosdc 0
kdxconro 5
kdxcofbo 46=0x2e
kdxcofeo 7918=0x1eee
kdxcoavs 7872
kdxlespl 0
kdxlende 0
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 8036
row#0[8013] flag: -----, lock: 0
col 0; len 1; (1):  80
---表示值为0
col 1; len 6; (6):  00 c0 7e 03 00 00
---rowid 起点的block和行号
col 2; len 6; (6):  00 c0 7e 03 00 17
---rowid 结束的block和行号,注意17 = 16+7 = 23 ,也就是下面转换后的有效位置截止到23bit
col 3; len 4; (4):  ca 10 42 08
---把该值按照16进制数转化为 11001010 (首字节不表示rowid信息)   00010000 01000010 00001000 ,


凡是从起点到结束点内的1表示该值存在,这里有 一个必须要注意的问题是,这样转化后的位置并不是真实的物理位置,在每个字节内部bit还要颠倒一下顺序,首字节不表示位置信息
也就是说上面的应该转换为 00001000 01000010 00010000 ,发现正好每5个存在一个值为0的记录

row#1[7990] flag: -----, lock: 0
col 0; len 2; (2):  c1 02
---表示值为1
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 0f
---注意这里是f,也就是一共只有16位,因为1是第一条记录开始的,在16的位置就已经有5条了
col 3; len 3; (3):  c9 21 84


注意这里的 21  84 正好16位,根���上面描述的规则转换后就是 10000100 00100001,4个1正好表示记录

row#2[7966] flag: -----, lock: 0
col 0; len 2; (2):  c1 03
---表示值为2
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 17
col 3; len 4; (4):  ca 42 08 01
row#3[7942] flag: -----, lock: 0
col 0; len 2; (2):  c1 04
---表示值为3
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 17
col 3; len 4; (4):  ca 84 10 02
row#4[7918] flag: -----, lock: 0
col 0; len 2; (2):  c1 05
---表示值为4
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 17
col 3; len 4; (4):  ca 08 21 04
----- end of leaf block dump -----
End dump data blocks tsn: 2 file#: 3 minblk 1955 maxblk 1955
SQL> delete from tn where a = 2;
1 row deleted.
SQL> commit;
Commit complete.
SQL> alter system dump datafile 3 block 1955;
System altered.
SQL>
Block header dump:  0x00c007a3
Object id on Block? Y
seg/obj: 0x66da  csc: 0x00.18a0d77  itc: 2  flg: -  typ: 2 - INDEX
fsl: 0  fnx: 0x0 ver: 0x01
Itl           Xid                  Uba         Flag  Lck        Scn/Fsc
0x01   xid:  0x0000.000.00000000    uba: 0x00000000.0000.00  ----    0  fsc 0x0000.00000000
0x02   xid:  0x0003.047.000000e9    uba: 0x00800dba.00d9.1f  --U-    2  fsc 0x001a.018a0d7d
Leaf block dump
===============
header address 125987932=0x7826c5c
kdxcolev 0
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 4
kdxcosdc 0
kdxconro 6
kdxcofbo 48=0x30
kdxcofeo 7894=0x1ed6
kdxcoavs 7846
kdxlespl 0
kdxlende 1
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 8036
row#0[8013] flag: -----, lock: 0
col 0; len 1; (1):  80
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 17
col 3; len 4; (4):  ca 10 42 08
row#1[7990] flag: -----, lock: 0
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 0f
col 3; len 3; (3):  c9 21 84
row#2[7894] flag: -----, lock: 2
---这是删除后的拷贝,我们发现删除的时候该行已经加锁  lock  : 2  
col 0; len 2; (2):  c1 03
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 17
col 3; len 4; (4):  ca 40 08 01
---我们发现 ca 42  已经变成  ca  40 ,也就是已经少掉一位bit了,正好是删除的那一条记录
row#3[7966] flag: ---D-, lock: 2
---这里我们发现值为2的记录已经有删除过的 ---D- ,D表示delete
col 0; len 2; (2):  c1 03
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 17
col 3; len 4; (4):  ca 42 08 01
row#4[7942] flag: -----, lock: 0
col 0; len 2; (2):  c1 04
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 17
col 3; len 4; (4):  ca 84 10 02
row#5[7918] flag: -----, lock: 0
col 0; len 2; (2):  c1 05
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 17
col 3; len 4; (4):  ca 08 21 04
----- end of leaf block dump -----
End dump data blocks tsn: 2 file#: 3 minblk 1955 maxblk 1955


再继续补充

首先truncate 表所有数据

truncate table tn;
SQL> exec show_space('tn_bitmap','i');
Free Blocks.............................0
Total Blocks............................16
Total Bytes.............................131072
Unused Blocks...........................14
Unused Bytes............................114688
Last Used Ext FileId....................3
Last Used Ext BlockId...................1954
Last Used Block.........................2
PL/SQL procedure successfully completed.


可以看出索引是空的

然后插入一条数据

SQL> insert into tn values(1,1);
1 row created.
SQL> commit;
Commit complete.
SQL> alter system dump datafile 3 block 1955;
System altered.
row#0[8009] flag: -----, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 1; (1):  00
row#1[8030] flag: ---D-, lock: 2
col 0; NULL
col 1; NULL
col 2; NULL
col 3; NULL
SQL>  insert into tn values(1,1);
1 row created.
SQL> commit;
Commit complete.
SQL>  alter system dump datafile 3 block 1955;
System altered.
row#0[8009] flag: ---D-, lock: 2
-- 标记删除,下面一份是拷贝
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 1; (1):  00
row#1[7987] flag: -----, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
00---07 正好表示8  rows
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 2; (2):  c8 03
-- 03 正好表示2条记录被插入
SQL>  insert into tn values(1,1);
1 row created.
SQL>  alter system dump datafile 3 block 1955;
System altered.
row#0[7987] flag: ---D-, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 2; (2):  c8 03
row#1[7965] flag: -----, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 2; (2):  c8 07
-- 07 正好表示3条记录被插入
SQL>  insert into tn values(1,1);
1 row created.
SQL>  insert into tn values(1,1);
1 row created.
SQL>  insert into tn values(1,1);
1 row created.
SQL>  insert into tn values(1,1);
1 row created.
SQL>  insert into tn values(1,1);
1 row created.
SQL> commit;
Commit complete.
SQL>  alter system dump datafile 3 block 1955;
System altered.


我们在同一个session中同一个事务连续插入5条记录,发现在bitmap中居然做了5个拷贝

row#0[7987] flag: ---D-, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 2; (2):  c8 03
row#1[7965] flag: ---D-, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 2; (2):  c8 07
row#2[7943] flag: ---D-, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 2; (2):  c8 0f
row#3[7921] flag: ---D-, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 2; (2):  c8 1f
row#4[7899] flag: ---D-, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 2; (2):  c8 3f
row#5[7877] flag: ---D-, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 2; (2):  c8 7f
row#6[7855] flag: -----, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 2; (2):  c8 ff
-- ff 正好表示8条记录被插入
SQL>  insert into tn values(1,1);
1 row created.
SQL> commit;
Commit complete.
SQL>   alter system dump datafile 3 block 1955;
System altered.
SQL>
-- 上一个bitmap段存储表示8条记录,我们再插入第9条记录再来看
row#0[7855] flag: -----, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 00
col 2; len 6; (6):  00 c0 7e 03 00 07
col 3; len 2; (2):  c8 ff
-- 8条记录已满,也把前面的前8条的多拷贝给清除掉了
row#1[7834] flag: -----, lock: 2
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  00 c0 7e 03 00 08
col 2; len 6; (6):  00 c0 7e 03 00 0f
col 3; len 1; (1):  00


新插入的第9条记录被新的从 08 --  0f  这8个字节用来存储


综合上面的实验可以看出,当单条insert发生的时候,会以8条记录为一个bitmap row 来存储,这正好是一个字节的bit,并且就算是
相���事务中的insert也会导致大量的拷贝和lock产生,严重影响性能,甚至可能发生行迁移等严重问题,所以在经常发生变化的表中
我们不应该采用 bitmap index ,当发生update 的时候情形更为复杂,暂时不予讨论了




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论