Bitmap深入研究(一)

4月 3rd, 2015

环境:
ORACLE:
BANNER
—————————————————————-
Oracle Database 10g Enterprise Edition Release 10.2.0.2.0 – Prod
PL/SQL Release 10.2.0.2.0 – Production
CORE    10.2.0.2.0      Production
TNS for Linux: Version 10.2.0.2.0 – Production
NLSRTL Version 10.2.0.2.0 – Production

OS:

LSB Version:    :core-3.1-ia32:core-3.1-noarch:graphics-3.1-ia32:graphics-3.1-noarch
Distributor ID: EnterpriseEnterpriseServer
Description:    Enterprise Linux Enterprise Linux Server release 5.4 (Carthage)
Release:        5.4
Codename:       Carthage
研究Bitmap索引的存储和特性

SQL> conn scott/scott
Connected.
SQL> CREATE TABLE t –创建一张测试表
2  (
3  NAME VARCHAR2(20)
4  );
Table created.

SQL> CREATE BITMAP INDEX idx_b_name ON t(NAME); –创建一个测试的索引

Index created.
SQL> select sid from v$mystat where rownum<2;  –查看自己的sid

SID
———-
159

–查看trace的文件所在
select a.value||b.symbol||c.instance_name||’_ora_’||d.spid||’.trc’ trace_file from
(select value from v$parameter where name=’user_dump_dest’) a,
(select substr(value,-6,1) symbol from v$parameter where name=’user_dump_dest’) b,
(select instance_name from v$instance) c,
(select spid from v$session s,v$process p,v$mystat m where s.paddr=p.addr
and s.sid=m.sid and m.statistic#=0) d;

TRACE_FILE
——————————————————————————–
/u01/app/oracle/admin/orcl/udump/orcl_ora_9707.trc
查看文件内容

*** ACTION NAME:() 2015-03-03 08:25:59.728
*** MODULE NAME:(SQL*Plus) 2015-03-03 08:25:59.728
*** SERVICE NAME:(SYS$USERS) 2015-03-03 08:25:59.728
*** SESSION ID:(159.7) 2015-03-03 08:25:59.728
—– begin tree dump   这个是空的时候
leaf: 0x100018c 16777612 (0: nrow: 0 rrow: 0)
—– end tree dump
*** 2015-03-03 08:28:08.940
—– begin tree dump   insert into t values(‘U’); commit;
leaf: 0x100018c 16777612 (0: nrow: 1 rrow: 1)
—– end tree dump
*** 2015-03-03 08:29:20.359
—– begin tree dump insert into t values(‘c’); commit;
leaf: 0x100018c 16777612 (0: nrow: 2 rrow: 2)
—– end tree dump
*** 2015-03-03 08:30:09.053
—– begin tree dump 又insert into t values(‘U’); commit;
leaf: 0x100018c 16777612 (0: nrow: 2 rrow: 2)
—– end tree dump
*** 2015-03-03 08:38:07.763
—– begin tree dump  delete from t where name=’c’; commit;
leaf: 0x100018c 16777612 (0: nrow: 2 rrow: 1)
—– end tree dump
*** 2015-03-03 08:40:35.384
—– begin tree dump  –insert into t select OBJECT_TYPE from user_objects;
leaf: 0x100018c 16777612 (0: nrow: 3 rrow: 3)
—– end tree dump

—– begin tree dump   insert into t SELECT object_type FROM dba_objects; / commit;
branch: 0x100018c 16777612 (0: nrow: 6, level: 1)
leaf: 0x1000190 16777616 (-1: nrow: 11 rrow: 11)
leaf: 0x100018f 16777615 (0: nrow: 2 rrow: 2)
leaf: 0x100018d 16777613 (1: nrow: 17 rrow: 17)
leaf: 0x100028c 16777868 (2: nrow: 3 rrow: 3)
leaf: 0x100018e 16777614 (3: nrow: 2 rrow: 2)
leaf: 0x100028d 16777869 (4: nrow: 11 rrow: 11)
—– end tree dump 这个时候可以发现整个树的结构都发生了变化 不再是单纯只有一个叶子节点了

仔细观察最后一次dump出来的结构 我们可以得出以下结论
1.原来的叶子节点发生了分裂而不是迁移。(b-tree也是一样) 根节点永远不会变
2.叶子节点从-1开始的顺序不代表在数据文件上也是连续的块

观察倒数第二个的nrow=3 我们去验证是否是这样
SQL> select DISTINCT name from t;

NAME
——————–
U
INDEX
TABLE

第一列中的
1.branch表示分支节点(包括根节点),
2.leaf则表示叶子节点
第二列表示十六进制表示的节点的地址;
第三列表示十进制表示的节点的地址;
第四列表示相对于前一个节点的位置,根节点从0开始计算,其他分支节点和叶子节点从-1开始计算;
第五列的nrow表示当前节点中所含有的索引条目的数量。比如我们可以看到含有的nrow为2,表示节点中含有2个索引条目,
分别指向2个分支节点
第六列中的
1.rrow表示有效的索引条目(因为索引条目如果被删除,不会立即被清除出索引块中。
所以nrow减rrow的数量就表示已经被删除的索引条目数量)的数量,
2.level表示分支节点的层级,对于叶子节点来说level都是0

以种方式以树状形式转储整个索引。同时,我们可以转储一个索引节点来看看其中存放了些什么

从上面我们可以看到索引块(根)的地址为:16777612 .我们先将其转换为文件号以及数据块号

select dbms_utility.data_block_address_file(16777615) “file”,dbms_utility.data_block_address_block(16777615) “BLOCK” from dual;

FILE  BLOCK
—————
4     396

— 注: 反推的话可以使用  select dbms_utility.make_data_block_address(4,396) from dual;
我们首先看一下根节点 然后再看一下叶子节点

SQL> alter system dump datafile 4 block 396;

System altered.
–内容如下

*** 2015-03-03 09:03:48.908
Start dump data blocks tsn: 4 file#: 4 minblk 396 maxblk 396
buffer tsn: 4 rdba: 0x0100018c (4/396)
scn: 0x0000.000739b7 seq: 0x02 flg: 0x04 tail: 0x39b70602
frmt: 0x02 chkval: 0x3905 type: 0x06=trans data
Hex dump of block: st=0, typ_found=1
Dump of memory from 0x0DECE400 to 0x0DED0400
DECE400 0000A206 0100018C 000739B7 04020000  [………9……]
DECE410 00003905 00000002 0000CD53 000739B7  [.9……S….9..]
DECE420 00000000 00320001 01000189 002C0006  [……2…….,.]
DECE430 00000102 00800B8F 00020136 00008000  [……..6…….]
DECE440 000739B7 00000000 00000000 04800001  [.9…………..]
DECE450 00000001 00260005 1F171F3D 01000190  [……&.=…….]
DECE460 00000004 00001F78 1F6C1F4B 1F5D1F44  [….x…K.l.D.].]
。。。
。。。
省略部分内容
。。。
。。。
Block header dump:  0x0100018c
Object id on Block? Y
seg/obj: 0xcd53  csc: 0x00.739b7  itc: 1  flg: E  typ: 2 – INDEX
brn: 0  bdba: 0x1000189 ver: 0x01 opc: 0
inc: 0  exflg: 0

Itl           Xid                  Uba         Flag  Lck        Scn/Fsc
0x01   0x0006.02c.00000102  0x00800b8f.0136.02  C—    0  scn 0x0000.000739b7

Branch block dump
=================
header address 233628748=0xdece44c
kdxcolev 1
KDXCOLEV Flags = – – –
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=— is converted=Y
kdxconco 4
kdxcosdc 1
kdxconro 5
kdxcofbo 38=0x26
kdxcofeo 7997=0x1f3d
kdxcoavs 7959
kdxbrlmc 16777616=0x1000190
kdxbrsno 4
kdxbrbksz 8056
kdxbr2urrc 0
row#0[8011] dba: 16777615=0x100018f
col 0; len 10; (10):  4a 41 56 41 20 43 4c 41 53 53
col 1; len 1; (1):  01
col 2; TERM
row#1[8044] dba: 16777613=0x100018d
col 0; len 6; (6):  4a 41 56 41 20 44
col 1; TERM
row#2[8004] dba: 16777868=0x100028c
col 0; len 1; (1):  53
col 1; TERM
row#3[8029] dba: 16777614=0x100018e
col 0; len 7; (7):  53 59 4e 4f 4e 59 4d
col 1; len 1; (1):  01
col 2; TERM
row#4[7997] dba: 16777869=0x100028d
col 0; len 1; (1):  54
col 1; TERM
—– end of branch block dump —–
End dump data blocks tsn: 4 file#: 4 minblk 396 maxblk 396

–kdxcolev表示索引层级号,这里由于我们转储的是根节点所以其层级号为1(当非叶子节点时层级也有可能为2 3 4递增)对叶子节点来说该值为0
–kdxcolok表示该索引上是否正在发生修改块结构的事务;
–kdxcoopc表示内部操作代码;
–kdxconco表示索引条目中列的数量;
–kdxcosdc表示索引结构发生变化的数量,当你修改表里的某个索引键值时,该值增加;
–kdxconro表示当前索引节点中索引条目的数量,但是注意,不包括kdxbrlmc指针;
–kdxcofbo表示当前索引节点中可用空间的起始点相对当前块的位移量;
–kdxcofeo表示当前索引节点中可用空间的最尾端的相对当前块的位移量;
–kdxcoavs表示当前索引块中的可用空间总量,也就是用kdxcofeo减去kdxcofbo得到的。
–kdxbrlmc表示分支节点的地址,该分支节点存放了索引键值小于row#0(在转储文档后半部分显示)所含有的最小值的所有节点信息;
–kdxbrsno表示最后一个被修改的索引条目号,这里看到是0,表示该索引是新建的索引;
–kdxbrbksz表示可用数据块的空间大小。实际从这里已经可以看到,即便是PCTFREE设置为0,也不能用足8192字节。
接下去看到的是row#0的内容
这部分内容就是在根节点中所记录的索引条目,总共是5个[0-4]条目。再加上kdxbrlmc所指向的第一个分支节点,
我们知道该根节点中总共存放了6个分支节点的索引条目 也对应了树形结构里nrow的值

每个索引条目都指向一个分支节点。
其中col 1表示所链接的分支节点的地址,该值经过一定的转换以后实际就是row#所在行的dba的值。
如果根节点下没有其他的分支节点,则col 1为TERM 比如上面的dba: 16777613=0x100018d的col 1; TERM

col 0表示该分支节点所链接的最小键值。其转换方式非常复杂 是要从十六进制转换为十进制
我们可以做下试验

row#0[8011] dba: 16777615=0x100018f
col 0; len 10; (10):  4a 41 56 41 20 43 4c 41 53 53
SELECT to_number(‘4a’,’XX’) FROM dual; –74
SELECT to_number(’41’,’XX’) FROM dual;–65
SELECT to_number(’56’,’XX’) FROM dual;–86
SELECT to_number(’41’,’XX’) FROM dual;–65
SELECT to_number(’20’,’XX’) FROM dual;–32
SELECT to_number(’43’,’XX’) FROM dual;–67
SELECT to_number(‘4c’,’XX’) FROM dual;–76
SELECT to_number(’41’,’XX’) FROM dual;–65
SELECT to_number(’53’,’XX’) FROM dual;–83
SELECT to_number(’53’,’XX’) FROM dual;–83
索引键值是char类型的,所以对每个值都运用chr函数就可以得到被索引键值为:
SELECT CHR(74) FROM dual;  –J
SELECT CHR(65) FROM dual;  –A
SELECT CHR(86) FROM dual;  –V
SELECT CHR(65) FROM dual;  –A
SELECT CHR(32) FROM dual;  — (空格)
SELECT CHR(67) FROM dual;  –C
SELECT CHR(76) FROM dual;  –L
SELECT CHR(65) FROM dual;  –A
SELECT CHR(83) FROM dual;  –S
SELECT CHR(83) FROM dual;  –S
–我擦 竟然是JAVA CLASS , JAVA CLASS就是dba为16777615的索引块所链接的最小键值

然后再dump一下看到结果就是我们要的10进制还没转成16进制的值
select dump(‘JAVA CLASS’) from dual;
Typ=96 Len=10: 74,65,86,65,32,67,76,65,83,83

那么我们上面dump出来了根节点 接下来继续dump叶子节点  我们就dump刚刚的16777615这个块吧。

select dbms_utility.data_block_address_file(16777615) “file”,dbms_utility.data_block_address_block(16777615) “BLOCK” from dual;
file      BLOCK
———- ———-
4        399

alter system dump datafile 4 block 399;
文件如下:
*** 2015-03-03 10:26:29.354
Start dump data blocks tsn: 4 file#: 4 minblk 399 maxblk 399
buffer tsn: 4 rdba: 0x0100018f (4/399)
scn: 0x0000.00073fd7 seq: 0x01 flg: 0x04 tail: 0x3fd70601
frmt: 0x02 chkval: 0x0703 type: 0x06=trans data
Hex dump of block: st=0, typ_found=1
Dump of memory from 0x0DECE400 to 0x0DED0400
DECE400 0000A206 0100018F 00073FD7 04010000  [………?……]
DECE410 00000703 00000002 0000CD53 00073FD7  [……..S….?..]
DECE420 00000000 00320002 01000189 00080004  [……2………]
…..
Block header dump:  0x0100018f
Object id on Block? Y
seg/obj: 0xcd53  csc: 0x00.73fd7  itc: 2  flg: E  typ: 2 – INDEX
brn: 0  bdba: 0x1000189 ver: 0x01 opc: 0
inc: 0  exflg: 0

Itl           Xid                  Uba         Flag  Lck        Scn/Fsc
0x01   0x0004.008.000000d0  0x00800041.009e.01  CB–    0  scn 0x0000.000739b2
0x02   0x0001.009.000000db  0x008002da.00be.09  C—    0  scn 0x0000.000739ba

Leaf block dump
===============
header address 233628772=0xdece464
kdxcolev 0
KDXCOLEV Flags = – – –
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=— is converted=Y
kdxconco 4
kdxcosdc 1
kdxconro 2
kdxcofbo 40=0x28
kdxcofeo 2853=0xb25
kdxcoavs 3233
kdxlespl 0
kdxlende 0
kdxlenxt 16777613=0x100018d
kdxleprv 16777616=0x1000190
kdxledsz 0
kdxlebksz 8032
row#0[3667] flag: ——, lock: 0, len=3945
col 0; len 10; (10):  4a 41 56 41 20 43 4c 41 53 53
col 1; len 6; (6):  01 00 01 db 00 b0
….
row#1[2853] flag: ——, lock: 0, len=814
col 0; len 10; (10):  4a 41 56 41 20 43 4c 41 53 53
col 1; len 6; (6):  01 00 02 3e 01 00
col 2; len 6; (6):  01 00 02 80 01 4f
col 3; len 785; (785):
cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55
55 55 ce 55 55 55 55 55 55 05 ff 18 55 55 55 55 55 55 55 55 cf 55 55 55 55
55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55
55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 ce
55 55 55 55 55 55 05 ff 18 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55
55 cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55
55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 ce 55 55 55
55 55 55 05 ff 18 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55
55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55
c9 55 05 ff 2d 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55
55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf
55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 ce 55 55 55 55 55 55 05
ff 18 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55
55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55 55
55 55 55 55 55 cf 55 55 55 55 55 55 55 55 ce 55 55 55 55 55 55 05 ff 18 55
—– end of leaf block dump —–
End dump data blocks tsn: 4 file#: 4 minblk 399 maxblk 399

发现内容与根节点完全类似,只不过该索引块中所包含的索引条目(指向叶子节点)的数量只有两个

我们再拿其中一个叶子来分析一下
row#1[2853] flag: ——, lock: 0, len=814
col 0; len 10; (10):  4a 41 56 41 20 43 4c 41 53 53
col 1; len 6; (6):  01 00 02 3e 01 00
col 2; len 6; (6):  01 00 02 80 01 4f
col 3; len 785; (785):
cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55 55 55 cf 55 55 55 55 55 55

其中flag表示标记,比如删除标记等;
而lock表示锁定信息。col 0表示索引键值,其算法与我们在前面介绍分支节点时所说的算法一致。

继续转化进制后使用chr
4a 41 56 41 20 43 4c 41 53 53
74 65 86 65 32 67 76 65 83 83
J  A  V  A     C  L  A  S  S

col 1
在b-tree的时候表示rowid
在bitmap的时候表示rowid的起始位置
01 00 01 db 00 b0
010001db00b0

SELECT to_number(‘010001db00b0′,’xxxxxxxxxxxx’) FROM dual;
select dbms_utility.data_block_address_file(to_number(‘010001DB’,’xxxxxxxxxxxx’)) “file”,
dbms_utility.data_block_address_block(to_number(‘010001DB’,’xxxxxxxxxxxx’)) “BLOCK” from dual;

4        475
col 2
在b-tree的时候没有
在bitmap中表示rowid的结束位置
01000280014f

col3表示位图编码 在b-tree里一样也没有
select to_number(‘0180001c’,’xxxxxxxxxxxx’) from dual;

中间的ca和开头的cf,不是索引的bitmap,而是类似数据头之类的东西,具体数值代表什么我还不清楚,不过似乎每64位就会出现一个数据头
SELECT
sys.pkg_number_trans.f_hex_to_bin(’55’) as c2,
from dual;

1010101

其中不足8位的前面用0补齐
–连接起来全是二进制的数据  也就代表了是不是JAVA CLASS

SELECT SYS.pkg_number_trans.f_oct_to_hex(‘01000280014f’) FROM dual;

在数据很少的时候单一块的时候很容易验证 但是数据多了之后怎么在块与块之间进行

我们来做一个单一的吧
DROP TABLE t1 PURGE;
CREATE TABLE t1
(
ID NUMBER
);
INSERT INTO t1 VALUES(1);
INSERT INTO t1 VALUES(2);
INSERT INTO t1 VALUES(3);
INSERT INTO t1 VALUES(4);
INSERT INTO t1 VALUES(3);
INSERT INTO t1 VALUES(2);
INSERT INTO t1 VALUES(1);
COMMIT;
select dbms_rowid.rowid_relative_fno(rowid)file_id, dbms_rowid.rowid_block_number(rowid)block_id,
dbms_rowid.rowid_row_number(rowid) row# from t1;

FILE_ID   BLOCK_ID       ROW#
———- ———- ———-
4        664          0
4        664          1
4        664          2
4        664          3
4        664          4
4        664          5
4        664          6

在同一个数据块上
alter session set events ‘10608 trace name context forever, level 10608’;

CREATE BITMAP INDEX IDX_B_T1 ON T1(ID);

alter session set events ‘10608 trace name context off’;

10608事件用来跟踪创建bitmap索引的过程

内容如下:
qerbiARwo: bitmap size is 8168
qerbiIPI default pctfree=10
qerbiIPI length=0
qerbiAllocate pfree=127 space=8168
qerbiStart first start
qerbiRop: rid=01000298.0000, new=Y , key: (2):  c1 02   –表示这是一个新值 产生一个的新的位图表示
qerbiCmpSz notfound pctfree=10
qerbiCmpSz adjblksize=7351 length=0
qerbiRop keysize=4 maxbm=3529
kdibcoinit(b7ddb044): srid=01000298.0000
qerbiRop: rid=01000298.0001, new=Y , key: (2):  c1 03
kdibcoinit(b7ddafc8): srid=01000298.0001
qerbiRop: rid=01000298.0002, new=Y , key: (2):  c1 04
kdibcoinit(b7ddaf4c): srid=01000298.0002
qerbiRop: rid=01000298.0003, new=Y , key: (2):  c1 05
kdibcoinit(b7ddaed0): srid=01000298.0003
qerbiRop: rid=01000298.0004, new=N, key: (2):  c1 04  –不是新值
qerbiRop: rid=01000298.0005, new=N, key: (2):  c1 03
qerbiRop: rid=01000298.0006, new=N, key: (2):  c1 02
kdibcoend(b7ddb044): erid=01000298.0007status=3
qerbiCon: key: (2):  c1 02
srid=01000298.0 erid=01000298.7 bitmap: (2):  c8 41
kdibcoend(b7ddafc8): erid=01000298.0007status=3
qerbiCon: key: (2):  c1 03
srid=01000298.0 erid=01000298.7 bitmap: (2):  c8 22
kdibcoend(b7ddaf4c): erid=01000298.0007status=3
qerbiCon: key: (2):  c1 04
srid=01000298.0 erid=01000298.7 bitmap: (2):  c8 14
kdibcoend(b7ddaed0): erid=01000298.0007status=3
qerbiCon: key: (2):  c1 05
srid=01000298.0 erid=01000298.7 bitmap: (1):  03
qerbiFreeMemory: Work heap is used.

上面是创建bitmap索引的过程。我们先把被索引的列的值换算成十六进制:

select dump(4),dump(3),dump(2),dump(1) from dual;
Typ=96 Len=2: 85,99 Typ=96 Len=3: 74,109,104
1 Typ=2 Len=2: 193,5 Typ=2 Len=2: 193,4 Typ=2 Len=2: 193,3 Typ=2 Len=2: 193,2
5 4 3 2的16进制是05 04 03 02 同时对应了上面的生成key部分的值
qerbiCon: key: (2):  c1 02
srid=01000298.0 erid=01000298.7 bitmap: (2):  c8 41    从上面的推论我们得出02表示1
start rowid和end rowid的格式分两部分,中间用点隔开,
点左边的表示文件号(从左边第一个字节开始的4个字节表示)和数据块号(从左边第五个字节开始的4个字节表示),
点右边表示数据块里的行号。这里的显示可以看到,
这几条记录都位于相同的数据块里。这里的0100表示文件号
select dbms_utility.data_block_address_file(to_number(‘01000298′,’xxxxxxxxxxxx’)) “file”,
dbms_utility.data_block_address_block(to_number(‘01000298′,’xxxxxxxxxxxx’)) “BLOCK” from dual;

4 664
根据我们刚刚的插入按照预想的应该是:1000001

得到结果果然是:
SELECT
sys.pkg_number_trans.f_hex_to_bin(’41’) as c2
from dual;
1000001

目前还没有任何评论.