Re: index rebuilding...

From: Richard Foote <richard.foote_at_bigpond.com>
Date: Mon, 3 Feb 2003 23:54:55 +1000
Message-ID: <ant%9.39604$jM5.100537@newsfeeds.bigpond.com>

"DA Morgan" <damorgan_at_exesolutions.com> wrote in message news:3E3D977E.D31B2DA0_at_exesolutions.com...

>
> Sounds to me like someone is going to be doing some block dumps pretty
> soon.
>
> Or at least I hope so. It would be great to have a definitive answer.
>

Hi Daniel,

• WARNING WARNING WARNING ***
• BLOCK DUMPS BLOCK DUMPS BLOCK DUMPS ***

The following is a very simple but hopefully illustrative demonstration of how Oracle maintains it's indexes. It's not however meant to be a "definitive answer".

So long as one follows the basic principles that once a leaf node is full, it needs to "split" and by doing so the branch node that points to it requires a new entry and if it's full, it needs to split etc., this will show how Oracle puts it all together.

OK, firstly, lets build a simple table and associated index:

SQL> create table bowie_stuff (id number, album_title varchar(30));

Table created.

SQL> create index bowie_stuff_idx on bowie_stuff(album_title);

Index created.

Now let's populate with some data and get the index structure building along. Note the values I'm using, they'll come in handy later.

SQL> insert into bowie_stuff values (1, 'David Bowie');

1 row created.

SQL> insert into bowie_stuff values (2, 'The Man Who Sold The World');

1 row created.

SQL> insert into bowie_stuff values (3, 'Hunky Dory');

1 row created.

SQL> insert into bowie_stuff values (4, 'Ziggy Stardust');

1 row created.

SQL> insert into bowie_stuff values (5, 'Aladdin Sane');

1 row created.

SQL> insert into bowie_stuff values (6, 'Pin Ups');

1 row created.

SQL> insert into bowie_stuff values (7, 'Diamond Dogs');

1 row created.

SQL> insert into bowie_stuff values (8, 'Young Americans');

1 row created.

SQL> insert into bowie_stuff values (9, 'Station To Station');

1 row created.

SQL> insert into bowie_stuff values (10, 'Low');

1 row created.

SQL> commit;

Commit complete.

SQL> insert into bowie_stuff select * from bowie_stuff;

10 rows created.

SQL> / 20 rows created.

SQL> / 40 rows created.

SQL> / 80 rows created.

SQL> / 160 rows created.

SQL> / 320 rows created.

SQL> commit;

Commit complete.

Having played with this table structure for many years now, I know I'm close to having a "full" index structure. Let's see the current state of affairs:

SQL> analyze index bowie_stuff_idx validate structure;

Index analyzed.

SQL> select height, lf_blks, br_blks from index_stats;

    HEIGHT LF_BLKS BR_BLKS
---------- ---------- ----------

         2 2 1

We currently have a nice simple index structure with one branch (root) node pointing to two leaf nodes.

I now check to see which blocks I need to dump.

SQL> select file_id, block_id, blocks from dba_extents where segment_name = 'BOW
IE_STUFF_IDX';    FILE_ID BLOCK_ID BLOCKS
---------- ---------- ----------

         9 1513 8

What I'll do now is take a before and after dump of the branch and leaf node block while inserting a new row. For the record, three further inserts did the trick and caused the first leaf node to "split".

SQL> insert into bowie_stuff values (7, 'Diamond Dogs');

1 row created.

SQL> commit;

Commit complete.

So now I've "captured" what Oracle has done in order to maintain it's index structure after a node split.

First of all, lets look at an extract of the branch node, just *before* the leaf node split. My comments are preceded with a *** :

Start dump data blocks tsn: 9 file#: 9 minblk 1516 maxblk 1516 buffer tsn: 9 rdba: 0x024005ec (9/1516)
scn: 0x0000.01974320 seq: 0x02 flg: 0x02 tail: 0x43200602 frmt: 0x02 chkval: 0x0000 type: 0x06=trans data Block header dump: 0x024005ec
 Object id on Block? Y

 seg/obj: 0x79ab  csc: 0x00.197431c  itc: 1  flg: E  typ: 2 - INDEX
     brn: 0  bdba: 0x24005e9 ver: 0x01
     inc: 0  exflg: 0

• above portion is the block header which includes the last SCN, rdba, object type (2 index), etc. ***

 Itl           Xid                  Uba         Flag  Lck        Scn/Fsc

0x01 0x0001.00b.00006e99 0x00800888.02ca.01 -BU- 1 fsc 0x0000.01974320

• above is the transaction slot (used by Oracle to maintain branch node structure) ***

Branch block dump

---

header address 99815500=0x5f3104c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 1
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y kdxconco 2
kdxcosdc 1
kdxconro 1
kdxcofbo 30=0x1e
kdxcofeo 8041=0x1f69
kdxcoavs 8011
kdxbrlmc 37750255=0x24005ef *** An error with my previous post to Don (which Jonathan Lewis kindly pointed out) is that this actually marks the first "pointer" to the leaf nodes. The logic being that values > null but less than the next pointer go to this leaf node. So 0x24005ef marks the first rdba of the first leaf node ***
kdxbrsno 0
kdxbrbksz 8060

• above section is the index (branch) header details, more on this later

row#0[8041] dba: 37750256=0x24005f0 *** This therefore marks the pointer to the second leaf node in the index, all values greater than or equal to col 0 belong in this leaf node. As there are only currently 2 leaf nodes in this index, that's about it for now ***
col 0; len 7; (7): 50 69 6e 20 55 70 73 *** values greater than or equal to PIN UPS go here ***
col 1; len 6; (6): 02 40 05 e8 00 eb
----- end of branch block dump -----
End dump data blocks tsn: 9 file#: 9 minblk 1516 maxblk 1516

Next, let's look at the poor index block in "desperate need of a bucket", ie. she's about to blow (split) ;)

Start dump data blocks tsn: 9 file#: 9 minblk 1519 maxblk 1519 buffer tsn: 9 rdba: 0x024005ef (9/1519)
scn: 0x0000.01975306 seq: 0x01 flg: 0x02 tail: 0x53060601 frmt: 0x02 chkval: 0x0000 type: 0x06=trans data Block header dump: 0x024005ef
 Object id on Block? Y

 seg/obj: 0x79ab  csc: 0x00.1975305  itc: 2  flg: E  typ: 2 - INDEX
     brn: 0  bdba: 0x24005e9 ver: 0x01
     inc: 0  exflg: 0

• above, block header details. Note that I can confirm this is the "first" index node by the rdba list above which we noted was the first "pointed" to block in the branch node ***

 Itl           Xid                  Uba         Flag  Lck        Scn/Fsc

0x01 0x0001.02c.00006e97 0x00800489.02cb.04 C--- 0 scn 0x0000.01974321
0x02 0x0008.029.00006d59 0x0080025d.0264.33 --U- 1 fsc 0x0000.01975306

• Above, the index transaction slots ***

Leaf block dump

---

header address 99815524=0x5f31064
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y kdxconco 2
kdxcosdc 0
kdxconro 376
kdxcofbo 788=0x314
kdxcofeo 802=0x322
kdxcoavs 14
kdxlespl 0
kdxlende 0
kdxlenxt 37750256=0x24005f0 *** This points to the "next" leaf node in the index structure. Oracle uses this when performing index range scans *** kdxleprv 0=0x0 *** As this is the first leaf node, there is no pointer the other way, that is, there is no previous leaf node (again used by Oracle when performing range scans, especially when avoiding a DESC sort) *** kdxledsz 0
kdxlebksz 8036
row#0[8014] flag: -----, lock: 0 *** Header for the first index entry *** col 0; len 12; (12): 41 6c 61 64 64 69 6e 20 53 61 6e 65 *** This represent the first index entry (ALADDIN SANE) *** col 1; len 6; (6): 02 40 05 e4 00 02 *** and it's associated row id *** row#1[7992] flag: -----, lock: 0 *** and this is the second index entry, and so on ... ***
col 0; len 12; (12): 41 6c 61 64 64 69 6e 20 53 61 6e 65 col 1; len 6; (6): 02 40 05 e4 00 0c
row#2[7970] flag: -----, lock: 0
col 0; len 12; (12): 41 6c 61 64 64 69 6e 20 53 61 6e 65 col 1; len 6; (6): 02 40 05 e4 00 16

.
. <snip>
.
row#374[841] flag: -----, lock: 0
col 0; len 7; (7):  50 69 6e 20 55 70 73

col 1; len 6; (6): 02 40 05 e8 00 d7
row#375[824] flag: -----, lock: 0 *** last index entry in this leaf node ***
col 0; len 7; (7): 50 69 6e 20 55 70 73 col 1; len 6; (6): 02 40 05 e8 00 e1
----- end of leaf block dump -----
End dump data blocks tsn: 9 file#: 9 minblk 1519 maxblk 1519

Now let's see how Oracle has "documented" the additional leaf node in the branch node:

Start dump data blocks tsn: 9 file#: 9 minblk 1516 maxblk 1516 buffer tsn: 9 rdba: 0x024005ec (9/1516)
scn: 0x0000.01975359 seq: 0x01 flg: 0x02 tail: 0x53590601 frmt: 0x02 chkval: 0x0000 type: 0x06=trans data Block header dump: 0x024005ec
 Object id on Block? Y

 seg/obj: 0x79ab  csc: 0x00.1975358  itc: 1  flg: E  typ: 2 - INDEX
     brn: 0  bdba: 0x24005e9 ver: 0x01
     inc: 0  exflg: 0

 Itl           Xid                  Uba         Flag  Lck        Scn/Fsc

0x01 0x0004.01e.00006ed7 0x00800a31.024b.03 --U- 1 fsc 0x0000.01975359

Branch block dump

---

header address 99618892=0x5f0104c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 1
kdxcoopc 0x81: opcode=1: iot flags=--- is converted=Y kdxconco 2
kdxcosdc 1
kdxconro 2
kdxcofbo 32=0x20
kdxcofeo 8017=0x1f51
kdxcoavs 7985
kdxbrlmc 37750255=0x24005ef *** The first leaf pointer remains unchanged, values greater than null go here ***
kdxbrsno 0
kdxbrbksz 8060
row#0[8017] dba: 37750253=0x24005ed *** But we now have a new leaf pointer inserted between the previous two. This points to the new leaf node that has been added as a result of the leaf node split *** col 0; len 12; (12): 44 69 61 6d 6f 6e 64 20 44 6f 67 73 *** values greater or equal to DIAMOND DOGS go here ***
col 1; len 6; (6): 02 40 05 e8 00 88
row#1[8041] dba: 37750256=0x24005f0 *** and this entry now points to the third, or last leaf node ***
col 0; len 7; (7): 50 69 6e 20 55 70 73 *** values greater or equal to PIN UPS go here ***
col 1; len 6; (6): 02 40 05 e8 00 eb
----- end of branch block dump -----
End dump data blocks tsn: 9 file#: 9 minblk 1516 maxblk 1516

So Oracle has simply added in an appropriate pointer for the new leaf node and values from which are to go into it.

Let's see how our poor "splitted" leaf node looks like:

Start dump data blocks tsn: 9 file#: 9 minblk 1519 maxblk 1519 buffer tsn: 9 rdba: 0x024005ef (9/1519)
scn: 0x0000.0197535a seq: 0x01 flg: 0x02 tail: 0x535a0601 frmt: 0x02 chkval: 0x0000 type: 0x06=trans data Block header dump: 0x024005ef
 Object id on Block? Y

 seg/obj: 0x79ab  csc: 0x00.1975359  itc: 2  flg: E  typ: 2 - INDEX
     brn: 0  bdba: 0x24005e9 ver: 0x01
     inc: 0  exflg: 0

 Itl           Xid                  Uba         Flag  Lck        Scn/Fsc

0x01 0x0004.01e.00006ed7 0x00800a30.024b.01 CB-- 0 scn 0x0000.01975359
0x02 0x0004.02c.00006ed7 0x00800a2e.024b.3c --U- 1 fsc 0x0000.0197535a

Leaf block dump

---

header address 99815524=0x5f31064
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y kdxconco 2
kdxcosdc 1
kdxconro 175
kdxcofbo 386=0x182
kdxcofeo 4250=0x109a
kdxcoavs 3864
kdxlespl 0
kdxlende 0
kdxlenxt 37750253=0x24005ed *** note that this has now changed and points to the newly added leaf node as it logically is the next node in the index structure ***
kdxleprv 0=0x0 *** still no previous pointer as this node is still the first leaf node in the index structure *** kdxledsz 0
kdxlebksz 8036
row#0[4272] flag: -----, lock: 0
col 0; len 12; (12): 41 6c 61 64 64 69 6e 20 53 61 6e 65 col 1; len 6; (6): 02 40 05 e4 00 02
row#1[4294] flag: -----, lock: 0
col 0; len 12; (12): 41 6c 61 64 64 69 6e 20 53 61 6e 65 col 1; len 6; (6): 02 40 05 e4 00 0c
row#2[4316] flag: -----, lock: 0
col 0; len 12; (12): 41 6c 61 64 64 69 6e 20 53 61 6e 65 col 1; len 6; (6): 02 40 05 e4 00 16

.
. <snip>
.

row#173[7992] flag: -----, lock: 0
col 0; len 12; (12): 44 69 61 6d 6f 6e 64 20 44 6f 67 73 col 1; len 6; (6): 02 40 05 e8 00 74
row#174[8014] flag: -----, lock: 0 *** we now only have 175 leaf entries in this leaf node (when previously we had 376. The other index entries have been "moved" to the new leaf node. Now wait a minute, 376 divided by 2 is not 175, what about the 50/50 split. Well the 50/50 split is based on "volume", not number of index entries. Both split nodes are approximately 50% full, this one happens to have larger index values on average*** col 0; len 12; (12): 44 69 61 6d 6f 6e 64 20 44 6f 67 73 col 1; len 6; (6): 02 40 05 e8 00 7e
----- end of leaf block dump -----
End dump data blocks tsn: 9 file#: 9 minblk 1519 maxblk 1519

And finally, an extract of the new leaf node dump and how it "slots" into the index structure:

Start dump data blocks tsn: 9 file#: 9 minblk 1517 maxblk 1517 buffer tsn: 9 rdba: 0x024005ed (9/1517)
scn: 0x0000.0197535b seq: 0x01 flg: 0x00 tail: 0x535b0601 frmt: 0x02 chkval: 0x0000 type: 0x06=trans data Block header dump: 0x024005ed
 Object id on Block? Y

 seg/obj: 0x79ab  csc: 0x00.197535b  itc: 2  flg: E  typ: 2 - INDEX
     brn: 0  bdba: 0x24005e9 ver: 0x01
     inc: 0  exflg: 0

• note above in the block header that this indeed is the new index leaf node as pointed to in the branch node ***

 Itl           Xid                  Uba         Flag  Lck        Scn/Fsc

0x01 0x0004.01e.00006ed7 0x00800a31.024b.01 CB-- 0 scn 0x0000.01975359
0x02 0x0008.029.00006d59 0x0080025d.0264.33 C--- 0 scn 0x0000.01975306

Leaf block dump

---

header address 99618916=0x5f01064
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y kdxconco 2
kdxcosdc 0
kdxconro 202
kdxcofbo 440=0x1b8
kdxcofeo 4566=0x11d6
kdxcoavs 4126
kdxlespl 0
kdxlende 0
kdxlenxt 37750256=0x24005f0 *** note that the "next" leaf node is the third node as pointed to in the branch node *** kdxleprv 37750255=0x24005ef *** and the previous node is the first node we previously looked at ***
kdxledsz 0
kdxlebksz 8036
row#0[4566] flag: -----, lock: 0
col 0; len 12; (12): 44 69 61 6d 6f 6e 64 20 44 6f 67 73 *** and as recorded in the branch node, entires in this now second leaf node start with DIAMOND DOGS values ***
col 1; len 6; (6): 02 40 05 e8 00 88
row#1[4588] flag: -----, lock: 0
col 0; len 12; (12): 44 69 61 6d 6f 6e 64 20 44 6f 67 73 col 1; len 6; (6): 02 40 05 e8 00 92
row#2[4610] flag: -----, lock: 0
col 0; len 12; (12): 44 69 61 6d 6f 6e 64 20 44 6f 67 73 col 1; len 6; (6): 02 40 05 e8 00 9c

.
. <snip>
.

row#200[8002] flag: -----, lock: 0
col 0; len 7; (7): 50 69 6e 20 55 70 73 col 1; len 6; (6): 02 40 05 e8 00 d7
row#201[8019] flag: -----, lock: 0 *** and the other 202 index entires (including the new one inserted that caused the leaf node split) are all found in this new leaf node ***
col 0; len 7; (7): 50 69 6e 20 55 70 73 col 1; len 6; (6): 02 40 05 e8 00 e1
----- end of leaf block dump -----
End dump data blocks tsn: 9 file#: 9 minblk 1517 maxblk 1517

So what does all this show ?

Well hopefully anyone that may have been a bit unsure how indexes hang together, especially when a block split occurs, will be a bit more cluey on what's going on.

Cheers

Richard Received on Mon Feb 03 2003 - 07:54:55 CST