Re: index rebuilding...

Richard Foote wrote:

> "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

Thanks. Thanks. Thanks.

So when are you publishing "The Definitive Book On Oracle Indexes"?

Daniel Morgan Received on Mon Feb 03 2003 - 10:37:01 CST