jump to navigation

Differences Between Unique and Non-Unique Indexes Part IV (Take It Back) March 25, 2009

Posted by Richard Foote in Index Internals, Non-Unique Indexes, Oracle Indexes, Unique Indexes.
trackback

I’ve previously discussed various differences between Unique and Non-Unique indexes (Part I, Part II and Part III) and why I have a preference to implement Unique indexes whenever possible and practical.

Various recent discussions on the OTN forums and on Ask Tom reminded me that I hadn’t yet discussed on this blog another subtle, but potentially significant difference between Unique and Non-Unique indexes.

As I’ve previously discussed, there’s actually no such thing as a Non-Unique index entry as such as Oracle ensures all index entries are effectively unique by adding the rowid to the index key for all Non-Unique indexes. Fundamentally, this is essential because Oracle needs some way of efficiently finding the precise index entry associated with an update or delete operation. Without having the rowid as part of the index key, Oracle would be forced to navigate to the first occurrence of an index value and search through all occurrences of the index value until it finds the specific entry containing the rowid of interest. This could potentially result in visiting many leaf blocks if the index value spans multiple leaf blocks. By including the rowid as the last index key column, non-unique index values are further ordered based on the corresponding rowid within the same indexed values. Oracle can therefore always navigate directly to the leaf block containing the exact index entry of interest as the rowid can be included in the branch blocks to determine both the index entry and rowid ranges found in specific leaf blocks.

If we look at a simple example by creating a one row table with a Non-unique index:

SQL> create table bowie (id number, name varchar2(20));

Table created.

SQL> insert into bowie values (1, ‘BOWIE’);

1 row created.

SQL> commit;

Commit complete.

SQL> create index bowie_idx on bowie(id);

Index created.

SQL> select header_file, header_block from dba_segments where segment_name = ‘BOWIE_IDX’;

HEADER_FILE HEADER_BLOCK
----------- ------------
          7       124937

Let’s dump the index block …

SQL> alter system dump datafile 7 block 124938;

System altered.
Leaf block dump
===============
header address 425713756=0x195fe05c
kdxcolev 0
KDXCOLEV Flags = – - -
kdxcolok 0
kdxcoopc 0×80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 1
kdxcofbo 38=0×26
kdxcofeo 8024=0x1f58
kdxcoavs 7986
kdxlespl 0
kdxlende 0
kdxlenxt 0=0×0
kdxleprv 0=0×0
kdxledsz 0
kdxlebksz 8036
row#0[8024] flag: ——, lock: 0, len=12
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  01 c1 e7 8a 00 00

Notice how the rowid is an additional index column within the index entry for the Non-Unique index.

Now if we were to delete and subsequently re-insert a row in the table with same index value within a single transaction, note the rowid of the new row by definition will differ from the deleted row. Therefore, we would need a different index entry for the new index row because if the rowids differ, then the associated index entries must differ as well. Note also (and this is critical) that because we would have a different rowid, if we had multiple index entries with the same key, this new index entry might not be in the same logical order as that of the deleted index entry. In fact, it’s quite possible that the new index entry might actually need to be stored in a totally different leaf block if this specific index value spanned multiple index leaf blocks because the index entries, including the rowids must always be logically ordered.

Therefore, if we were to delete and re-insert the same index value within a single transaction, Oracle is forced to create a new index entry and will not reuse the existing, deleted index entry.

So continuing with the demo, let’s delete the row:

SQL> delete bowie;

1 row deleted.

and now re-insert a row with the same indexed value within the same transaction:

SQL> insert into bowie values (1, ‘THIN WHITE DUKE’);

1 row created.

SQL> commit;

Commit complete.

If we look at a block dump now …

Leaf block dump
===============
header address 425713756=0x195fe05c
kdxcolev 0
KDXCOLEV Flags = – - -
kdxcolok 0
kdxcoopc 0×80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 2
kdxcofbo 40=0×28
kdxcofeo 8012=0x1f4c
kdxcoavs 7972
kdxlespl 0
kdxlende 1
kdxlenxt 0=0×0
kdxleprv 0=0×0
kdxledsz 0
kdxlebksz 8036
row#0[8024] flag: —D–, lock: 2, len=12
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  01 c1 e7 8a 00 00
row#1[8012] flag: ——, lock: 2, len=12
col 0; len 2; (2):  c1 02
col 1; len 6; (6):  01 c1 e7 8a 00 01
—– end of leaf block dump —–

We notice the previous index entry has been logically deleted and Oracle has created a new index entry with the new associated rowid.

 

Let’s now run exactly the same demo again, but this time with a Unique index instead of the Non-Unique index …

SQL> drop table bowie;

Table dropped.

SQL> create table bowie (id number, name varchar2(20));

Table created.

SQL> insert into bowie values (1, ‘BOWIE’);

1 row created.

SQL> commit;

Commit complete.

SQL> create unique index bowie_idx on bowie(id);

Index created.

SQL> select header_file, header_block from dba_segments where segment_name = ‘BOWIE_IDX’;

HEADER_FILE HEADER_BLOCK
----------- ------------
          7       125193

SQL> alter system dump datafile 7 block 125194;

System altered.

Leaf block dump
===============
header address 371859548=0x162a205c
kdxcolev 0
KDXCOLEV Flags = – - -
kdxcolok 0
kdxcoopc 0×80: opcode=0: iot flags=— is converted=Y
kdxconco 1
kdxcosdc 0
kdxconro 1
kdxcofbo 38=0×26
kdxcofeo 8025=0x1f59
kdxcoavs 7987
kdxlespl 0
kdxlende 0
kdxlenxt 0=0×0
kdxleprv 0=0×0
kdxledsz 6
kdxlebksz 8036
row#0[8025] flag: ——, lock: 0, len=11, data:(6):  01 c1 e8 8a 00 00
col 0; len 2; (2):  c1 02
—– end of leaf block dump —–

 

Notice the big difference here. Because the index has been defined as Unique, all the associated index entries must be unique. It’s simply not possible to have duplicate index entries within a Unique index structure. Therefore, it’s not necessary to have the rowid as a separate column of the index entry as the index values themselves are sufficient to uniquely identify each and every index entry. The rowid is basically just another piece of overhead associated with the index entry rather than a separate index column. The length of this unique index entry is just 11 bytes, where it was previously 12 bytes, because we no longer need to store the length byte associated with the second index column necessary in the Non-unique index for the rowid.

And now comes the subtle difference …

If we were to now delete and re-insert the same index value within a single transaction, Oracle can now reuse the same, deleted index entry, because the index entry is effectively identical to the deleted one. The only possible difference is the rowid but the rowid is no longer a part of the index column list and so can just be updated as necessary. Note also (and this is the critical bit for Unique indexes), because the actual index value remains the same, the order of the index entry within the index must also remain the same. There is no need to move the re-inserted index entry to another part of the index structure because deleting and re-inserting the same index entry does not logically alter the order of where the index entry must reside.

Therefore, if we were to delete and re-insert the same index value within a single transaction, Oracle does not need to create a new index entry and can simply reuse the existing, deleted index entry.

So continuing with the demo, let’s delete the row:

SQL> delete bowie;

1 row deleted.

and now re-insert a row with the same indexed value within the same transaction:

SQL> insert into bowie values (1, ‘THIN WHITE DUKE’);

1 row created.

SQL> commit;

Commit complete.

If we look at a block dump now …

Leaf block dump
===============
header address 371859548=0x162a205c
kdxcolev 0
KDXCOLEV Flags = – - -
kdxcolok 0
kdxcoopc 0×80: opcode=0: iot flags=— is converted=Y
kdxconco 1
kdxcosdc 0
kdxconro 1
kdxcofbo 38=0×26
kdxcofeo 8025=0x1f59
kdxcoavs 7987
kdxlespl 0
kdxlende 0
kdxlenxt 0=0×0
kdxleprv 0=0×0
kdxledsz 6
kdxlebksz 8036
row#0[8025] flag: ——, lock: 2, len=11, data:(6):  01 c1 e8 8a 00 01
col 0; len 2; (2):  c1 02
—– end of leaf block dump —–

We note that Oracle has indeed reused the previously deleted index entry and has simply updated the rowid with the new rowid value. There is no deleted index entry, Oracle has simply changed the associated rowid to that of the new row in the table for the existing Unique index entry.

Where an Update of an index entry is actually effectively a delete and an insert of an index entry, notice that by contrast for Unique indexes, a delete and a re-insert operation is effectively an update of an index entry !!

In my next post I’ll highlight how this difference can be critical to the behaviour and efficiency of an index and why it’s important to understand how indexes work to avoid and prevent potential issues.

About these ads

Comments»

1. Statistique - March 26, 2009

Very nice observations, can’t wait for your next post about “how this difference can be critical to the behaviour and efficiency of an index” !

2. coskan - March 26, 2009

Brilliant explanation, for a hidden (for most of us) but very important issue.

Thank you very much

3. Surachart Opun - March 26, 2009

Excellent!
Thank you … knowledge , that make me excited to use INDEX ;)

4. Richard Foote - March 26, 2009

Thanks for the nice feedback folks, much appreciated :)

5. Pythian Group - Blog - March 28, 2009

[...] Richard Foote appeared with a well liked fourth part of his series on the differences between unique and non-unique indexes. [...]

6. Hans-Peter Sloot - April 27, 2009

Hello Richard,

Perhaps it is a silly question: but I do not understand what I quoted below.
>>Now if we were to delete and subsequently re-insert a row in the >>table with same index value within a single transaction, note the >>rowid of the new row by definition will differ from the deleted row.
If a row is deleted, why is the row entry in the table not being reused.
So the rowid could be reused and the corresponding index entry too.

regards Hans-Peter

Richard Foote - April 27, 2009

Hi Hans-Peter

Because in a Non-Unique index, you can’t simply reuse the deleted index entry because the newly inserted index entry must have a different rowid and if we have a different rowid, we must by definition have a different index entry as the rowid is part of the column list of the index entry.

Oracle can’t simply just replace the rowid of an index entry in a Non-Unique index because by doing so, Oracle can’t then guarantee the correct order of the index entries because they must always be in rowid order for all distinct indexed column values. Remember, all index entries must be in the order of the index values and this includes the rowid for non-unique indexes.

7. Hans-Peter Sloot - April 29, 2009

Hi Richard,

I can understand why the index entry cannot be reused when a new rowid comes in.
But why isn’t the rowid in the table reused?
In that case the rowid would be the same.

Regards Hans-Peter

8. Richard Foote - April 29, 2009

Hi Hans-Peter

Because it would make rolling back the changes cumbersome, it would mean changing entirely how Oracle determines a block suitable for inserts, it would mean hoping the new rows will fit in where the old ones used to be, it would mean determining the index values are identical in the new rows, etc.etc.

It just wouldn’t be worth all the additional code paths required.

Yes, you can reuse deleted space in a table block, it’s simply a timing of when.

9. Neeraj Bhatia - September 20, 2010

Hi Richard,

As usual once again nice explanation!

I understand you should be busy with OOW’2010, still once you have some time free, please reply to my questions.

1) I believe data:(6): 01 c1 e8 8a 00 01 entry in case of unique index is rowid entry of table data block, containing respective row. Now, when we say unique indexe doesnt store rowid as columns and thus save 1 byte, isn’t data entry consume additional space. I observe that rowid’s are still there, not as column entry but part of row entry itself.

2) One observation, why you’ve dropped the table bowie, while presenting second test case for unique index. Isnt only recreating the index as unique make the purpose? Stupid question isn’t it?

3) I found your blog post for how to read and interpret treedump/index block dump for non-unique index, do you have similar thing for unique index?

Last night I’ve taken unique index block dump and found data:(6): 01 c1 e8 8a 00 01 and col 1; TERM
type entries, but couldnt understand their meaning.

10. Sorin - July 13, 2012

Hi Richard,

Can u pls explain how to parse this value of the rowid “01 c1 e8 8a 00 00″ to the base64 value I get when selecting rowid from the table. I want to be able to locate the row by it’s rowid(from the dump) in the table.
Thank you!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,808 other followers

%d bloggers like this: