Tuesday, September 23, 2008

Unique and non-unique indexes

An interesting questions is: what is in fact the difference between unique and non-unique indexes? For a long discussion, see Richard Foote's blog. Here, we look at the on-disk differences.

Let's start with environment setup and block dump creation:
connect system

create user itest identified by itest;

grant dba to itest;

create tablespace ITEST;

alter user itest default tablespace itest;

connect itest/itest

create table TDATA (pk varchar2(20));

begin
for i in 1..10000 loop
insert into TDATA values ('VAL'||i);
end loop;
commit;
end;

create index TIDX1 on TDATA(pk);

(I chose varchar2 type so that the actual characters are clearly seen in the dump. Also, I created a fresh new tablespace so the block numbers are small and probably consecutive.)
Now, find the extents involved:
select * from dba_extents where owner=user;
And dump the blocks (take numbers from the query above - relative_fno, block_id):
alter system dump datafile 14 block min 33 block max 62;
Save the trace, create a unique index, dump it:
drop index TIDX1;
create unique index TIDX2 on TDATA(pk);
select * from dba_extents where owner=user;
alter system dump datafile 14 block min 33 block max 62;
Now, take look at the dumped blocks. For the sake of the explanation flow, let's start with the leaf blocks:

Non-unique:
Leaf block dump
===============
header address 146678372=0x8be2264
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 380
kdxcofbo 796=0x31c
kdxcofeo 1617=0x651
kdxcoavs 821
kdxlespl 0
kdxlende 0
kdxlenxt 58720295=0x3800027
kdxleprv 58720293=0x3800025
kdxledsz 0
kdxlebksz 8036
row#0[8020] flag: ------, lock: 0, len=16
col 0; len 6; (6): 56 41 4c 31 33 34
col 1; len 6; (6): 03 80 00 0d 00 85
row#1[8003] flag: ------, lock: 0, len=17
col 0; len 7; (7): 56 41 4c 31 33 34 30
col 1; len 6; (6): 03 80 00 0f 00 8a
...
What is interesting: the index has 2 colums! This is indicated by kdxconco, and is of course clearly seen in the entries themselves. The second column is the rowid of the table row. So after all, the entries are unique, by considering rowid as an additional column.

Interestingly, the unique index looks a bit differently:
Leaf block dump
===============
header address 152117860=0x9112264
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 1
kdxcosdc 0
kdxconro 401
kdxcofbo 838=0x346
kdxcofeo 1664=0x680
kdxcoavs 826
kdxlespl 0
kdxlende 0
kdxlenxt 58720295=0x3800027
kdxleprv 58720293=0x3800025
kdxledsz 6
kdxlebksz 8036
row#0[8020] flag: ------, lock: 0, len=16, data:(6): 03 80 00 0f 00 9d
col 0; len 7; (7): 56 41 4c 31 33 35 39
row#1[8005] flag: ------, lock: 0, len=15, data:(6): 03 80 00 0d 00 87
col 0; len 6; (6): 56 41 4c 31 33 36
Oracle now does not need to artifically add rowid to column list, as the 1 column suffices to uniquely identify the entry. However, it still needs it to find the row. The difference: 1 byte saved (in fact, the length byte for the rowid).

Now, let's have a look at the branch block (the root, for this small table). First, the non-unique:
Branch block dump
=================
header address 146678348=0x8be224c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 26
kdxcofbo 80=0x50
kdxcofeo 7724=0x1e2c
kdxcoavs 7644
kdxbrlmc 58720293=0x3800025
kdxbrsno 0
kdxbrbksz 8060
kdxbr2urrc 0
row#0[8048] dba: 58720294=0x3800026
col 0; len 6; (6): 56 41 4c 31 33 34
col 1; TERM
row#1[8035] dba: 58720295=0x3800027
col 0; len 7; (7): 56 41 4c 31 36 38 32
col 1; TERM
In the branch blocks, only the information needed to find the correct leaf block is storred. Thus, the column contents is truncated as much as possible (see more below). However, we have two columns in the index - and we have to indicate that the 2nd column (rowid) is not needed - and that's the "col 1; TERM" entry.

Now, for the unique case:
Branch block dump
=================
header address 152117836=0x911224c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 1
kdxcosdc 0
kdxconro 24
kdxcofbo 76=0x4c
kdxcofeo 7775=0x1e5f
kdxcoavs 7699
kdxbrlmc 58720293=0x3800025
kdxbrsno 0
kdxbrbksz 8060
kdxbr2urrc 4
row#0[8048] dba: 58720294=0x3800026
col 0; len 7; (7): 56 41 4c 31 33 35 39
row#1[8037] dba: 58720295=0x3800027
col 0; len 6; (6): 56 41 4c 31 37 32
Here, we have only one column, so no need to write that no other column data is needed. The net difference: 1 bytes per index entry.

Please note, that Oracle fills the blocks end-to-start (so the header can grow), and thus the dump usually starts with high addresses. However, this is only physical location, and does not represent the index ordering. For example, after index block split, it can (and will) change. Just reverse the example order: first create index, then insert data. Then compare first and last leaf block.

One final note regarding the branch blocks and inclusion only of the prefix needed to identify the correct leaf block.
Let's change the example slightly: insert the values 'VAL'||i||'0000000'. Now, the leaf blocks has to contain these values:
row#1[4367] flag: ----S-, lock: 2, len=24
col 0; len 14; (14): 56 41 4c 33 37 35 30 30 30 30 30 30 30 30
col 1; len 6; (6): 03 80 00 0f 00 4f
However, the branch block does not have to:
row#0[7989] dba: 58720300=0x380002c
col 0; len 6; (6): 56 41 4c 31 31 34
col 1; TERM