jump to navigation

Updates and Indexes Part I (Fashion) January 17, 2009

Posted by Richard Foote in Index Delete Operations, Oracle Indexes, Oracle Myths, Update Indexes.
trackback

Let’s start with a few basic concepts.

Simplistically, Oracle doesn’t generally care where or in what order data is stored in heap tables, unless the table is partitioned or clustered. Therefore, when an update operation is performed on a column value, Oracle can basically make the change “in place” within the table block. If the value of a name column changes from say “BOWIE” to a new value of “FOOTE”, Oracle can simply just make the necessary change to the specific table block. Only if the new value is larger and there’s not sufficient space within the current table block for the new value does the picture get a little more complicated, with Oracle having to migrate the row.

However, the story isn’t quite so simple for corresponding changes to index column values. The key difference (no pun intended) is that unlike most heap tables, the location and order of the data within the index is very much an issue. All index entries must be and must always be in the order of the indexed columns. Otherwise, it would be impossible for Oracle to efficiently navigate down the index structure to find within the index all the  necessary indexed values required for an index range scan. Imagine for one moment how difficult it would be to find someones phone details if the telephone book wasn’t ordered on names or to use an index in the back of a reference book if the index wasn’t ordered.

The order of an index is crucial and must always be in the order of the indexed column values. Therefore, if a specific indexed value of  say “BOWIE” is updated to a new value of “FOOTE”, Oracle can’t simply make the change “in place” within the leaf block as this would result in the index order no longer being maintained. The new value of “FOOTE” would be surrounded by index values starting with “B” and there would be no easy way to subsequently find it within the index. It would likely not even be in the same index leaf block as those other index entries beginning with “F” where the new value should actually reside.

Therefore, Oracle doesn’t actually “update” an index value. The old index entry is marked as deleted and the a new index entry is inserted in the appropriate location within the index to ensure the index order is maintained. So the update of an index value is effectively a delete operation followed by an insert.

Simple example to demonstrate. Let’s first create a little table and index.

SQL> create table test_update (id number, name varchar2(10));

Table created.

SQL> create index test_update_idx on test_update (name);

Index created.

Now, let’s insert one row.

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

1 row created.

SQL> commit;

Commit complete.

Let’s have a quick look at a block dump of our little index. As the index only contains the one index entry, the index will only consist of a single leaf block. This specific block is located next to the segment header of the index.

SQL> select header_file, header_block from dba_segments where segment_name = ‘TEST_UPDATE_IDX';

HEADER_FILE HEADER_BLOCK
----------- ------------
          7       118537

We just need to add 1 to the header_block to get us the specific block id we need to dump.

SQL> alter system dump datafile 7 block 118538;

System altered.

Following is the portion of interest from the index block dump:

Leaf block dump
===============
header address 425361500=0x195a805c
kdxcolev 0
KDXCOLEV Flags = – – -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 1
kdxcofbo 38=0x26
kdxcofeo 8021=0x1f55
kdxcoavs 7983
kdxlespl 0
kdxlende 0
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 8036
row#0[8021] flag: ——, lock: 2, len=15
col 0; len 5; (5):  42 4f 57 49 45
col 1; len 6; (6):  01 c1 ce 8a 00 00

—– end of leaf block dump —–

We note for now that the index indeed just has the one index entry (with a row# 0).

Let’s now update this indexed column and see what impact this has in the index.

SQL> update test_update set name = ‘ZIGGY’ where id = 1;

1 row updated.

SQL> commit;

Commit complete.

SQL> alter system dump datafile 7 block 118538;

System altered.

New block dump follows:

Leaf block dump
===============
header address 425361500=0x195a805c
kdxcolev 0
KDXCOLEV Flags = – – -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 2
kdxcofbo 40=0x28
kdxcofeo 8006=0x1f46
kdxcoavs 7966
kdxlespl 0
kdxlende 1
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 8036
row#0[8021] flag: —D–, lock: 2, len=15
col 0; len 5; (5):  42 4f 57 49 45
col 1; len 6; (6):  01 c1 ce 8a 00 00
row#1[8006] flag: ——, lock: 2, len=15
col 0; len 5; (5):  5a 49 47 47 59
col 1; len 6; (6):  01 c1 ce 8a 00 00
—– end of leaf block dump —–

We notice of few interesting things. Firstly, even though we’ve only ever inserted the one row in the table, the index now actually has two index entries (note the index row count kdxconro value has increased from 1 to 2 and we can see two actual index entries, row#0 and row#1).

Another interesting point is that the initial index entry has been marked as deleted (via the “D” flag highlighted in blue) and that the deleted row count kdxlende value has gone up to 1.

So yes indeed, an update index operation actually consists of a delete operation followed by an insert, even if the new index value were to reside in the same index leaf block as the previous value. Note the deleted index entry isn’t actually physically deleted, it’s only marked as deleted and so continues to consume space within the index leaf block.

If we look at the index_stats for this index:

SQL> analyze index test_update_idx validate structure;

Index analyzed.

SQL> select del_lf_rows from index_stats …

DEL_LF_ROWS
-----------
          1

We notice that we do indeed have a deleted index entry listed in the statistics.

Now it’s at this point of the story when some people go “Aaah haa !! So if we have lots of updates, we effectively have lots deletes and we therefore have lots of deleted space that wastes space within the index. Therefore we would need to periodically rebuild such an index as the deleted space will just continue to grow, making the index larger and less efficient over time”.

Not necessarily.

The point that many don’t quite understand is that this “wasted” delete space can be subsequently reused by Oracle. It’s just free space that in the vast majority of indexes is automatically cleaned out and reused by Oracle.

To illustrate, let’s now insert a second row into this table. Notice the new row has an indexed value that is completely different to the previous values but because we still have available space in our current index leaf block, Oracle will simply insert the new value in this leaf block as well.

SQL> insert into test_update values (2, ‘PINK FLOYD’);

1 row created.

SQL> commit;

Commit complete.

SQL> alter system dump datafile 7 block 118538;

System altered.

Let’s have a look at our block dump now …

Leaf block dump
===============
header address 425361500=0x195a805c
kdxcolev 0
KDXCOLEV Flags = – – -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 2
kdxcofbo 40=0x28
kdxcofeo 7986=0x1f32
kdxcoavs 7961
kdxlespl 0
kdxlende 0
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 8036
row#0[7986] flag: ——, lock: 2, len=20
col 0; len 10; (10):  50 49 4e 4b 20 46 4c 4f 59 44
col 1; len 6; (6):  01 c1 ce 8a 00 01
row#1[8006] flag: ——, lock: 0, len=15
col 0; len 5; (5):  5a 49 47 47 59
col 1; len 6; (6):  01 c1 ce 8a 00 00
—– end of leaf block dump —–

Now isn’t that interesting. The previously marked deleted index entry has disappeared. It’s been automatically cleaned out by Oracle and the deleted row count value kdxlende is now back to 0

We only have an index row count  kdxconro value of 2 for the two actual index entries corresponding to the two rows in the table. The previously deleted index entry is no longer recorded or stored in any way within the index.

When the new index entry was inserted, Oracle basically needed to reorganise the index leaf block to accommodate for the new index entry and automatically cleaned out any deleted index entries there may have been in the leaf block in the process. That’s all it takes to clean out deleted index entries from an index leaf block, just one subsequent insert in the leaf block.

If we now look at the index_stats …

SQL> analyze index test_update_idx validate structure;

Index analyzed.

SQL> select del_lf_rows from index_stats;

DEL_LF_ROWS
-----------
          0

We note that indeed, no deleted index entries are now stored within the index. Periodically rebuilding such an index may not be necessary after all …

Regular readers will recall I’ve previously discussed how deleted index entries are generally cleaned out by Oracle automatically. Sometimes, it’s worth hammering the point a few times ;)

More on the topic of update operations and indexes to come …

About these ads

Comments»

1. Surachart - January 18, 2009

Hi Richard,

That’s a good job. But I’m not understand yet.
I tried to dump block, but my result didn’t the same your result.
I only understand:

insert… no deleted index entries.

Anyway, Your article help me more about index.

Thank You
surachart

2. Richard Foote - January 18, 2009

Hi Surachart

Glad you think it’s a good job but you might want to expand a little on why your results differ because if all you understand is that an insert doesn’t generate deleted results, then perhaps I didn’t do such a good job after all ;)

It might help if perhaps you at least mention how your results differ.

3. Surachart - January 18, 2009

Hi Richard,

My result didn’t show … like you.

SQL> create table test_update (id number, name varchar2(10));

Table created.

SQL> create index test_update_idx on test_update (name);

Index created.

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

1 row created.

SQL> commit;

Commit complete.

SQL> select file_id, block_id from dba_extents where segment_name =’TEST_UPDATE_IDX';

FILE_ID BLOCK_ID
———- ———-
7 33

SQL> alter system dump datafile 7 block 34;

System altered.

Start dump data blocks tsn: 7 file#: 7 minblk 34 maxblk 34
buffer tsn: 7 rdba: 0x01c00022 (7/34)
scn: 0x0794.2fd9292e seq: 0x01 flg: 0x00 tail: 0x292e2101
frmt: 0x02 chkval: 0x0000 type: 0x21=SECOND LEVEL BITMAP BLOCK
Hex dump of block: st=0, typ_found=1
Dump of memory from 0x00000000066F0C00 to 0x00000000066F2C00
0066F0C00 0000A221 01C00022 2FD9292E 00010794 [!..."....)./....]
0066F0C10 00000000 00000000 00000000 00000000 [................]
Repeat 2 times
0066F0C40 00000000 00000000 00000000 01C00023 [............#...]
0066F0C50 00000001 00000001 00000000 00000000 [................]
0066F0C60 00000000 00000000 0004DB2A 00000001 [........*.......]
0066F0C70 00000000 01C00021 00010005 00000000 [....!...........]
0066F0C80 00000000 00000000 00000000 00000000 [................]
Repeat 502 times
0066F2BF0 00000000 00000000 00000000 292E2101 [.............!.)]
Dump of Second Level Bitmap Block
number: 1 nfree: 1 ffree: 0 pdba: 0x01c00023
Inc #: 0 Objd: 318250
opcode:0
xid:
L1 Ranges :
——————————————————–
0x01c00021 Free: 5 Inst: 1

——————————————————–
End dump data blocks tsn: 7 file#: 7 minblk 34 maxblk 34

Thank You

4. Surachart - January 18, 2009

About “INSERT”… No deleted index entries.
I mean when insert data “del_lf_rows” on index_stats no change…

SQL1> analyze index test_update_idx validate structure;

Index analyzed.

SQL1> select del_lf_rows from index_stats;

DEL_LF_ROWS
———–
0

SQL1> insert into test_update values (2, ‘BOWIE2′);

1 row created.

SQL1> commit;

Commit complete.

SQL1> analyze index test_update_idx validate structure;

Index analyzed.

SQL1> select del_lf_rows from index_stats;

DEL_LF_ROWS
———–
0

When test update….

SQL1> update test_update set name=’BOWIE3′ where id=2;

1 row updated.

SQL1> commit;

Commit complete.

SQL1> analyze index test_update_idx validate structure;

Index analyzed.

SQL1> select del_lf_rows from index_stats;

DEL_LF_ROWS
———–
1

Thank You

5. Richard Foote - January 18, 2009

Hi Surachart

The problem with the index block dump is that you’re using an Automatic Segment Space Management (ASSM) tablespace and so you’ll likely need to add 3, not 1 to the first block in the segment. Thanks for mentioning this, it’s probably safer if I had simply used the header_block from dba_segments as it’s always 1 after this block regardless of type of tablespace. I’ve now amended my post.

In your second demo, you’ve previously added a row, so no deleted index entries. You then insert a second row and so still no deleted entries, as you’ve yet to perferm an update or delete operation.

You then finally perform an update and you now have a deleted index entry because of the update operation.

So I don’t understand your question/demo, it’s all extactly as I’ve explained ?

If you were to now perform another insert, you’ll find the deleted index entry will be automatically cleaned out by Oracle. You haven’t yet gone through my demo (or not done so in the correct order).

It’s the insert AFTER the delete/update that cleans out the deleted entry. An insert BEFORE the delete/update can’t do the same as there’s nothing yet for it to clean out …

6. Surachart - January 18, 2009

Hi Richard,

Thank you for your suggestion.;)
I got result…(dump).

Leaf block dump
===============
header address 107940964=0x66f0c64
kdxcolev 0
KDXCOLEV Flags = – – –
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=— is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 1
kdxcofbo 38=0x26
kdxcofeo 8017=0x1f51
kdxcoavs 7979
kdxlespl 0
kdxlende 0
kdxlenxt 0=0x0
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 8032
row#0[8017] flag: ——, lock: 2, len=15
col 0; len 5; (5): 42 4f 57 49 45
col 1; len 6; (6): 01 c0 00 17 00 00
—– end of leaf block dump —–

7. Karthick - January 21, 2009

Dear Richard,

If I have an index block that is full. And now I perform a delete that deletes all the data in that block. So now all the data in that block is marked as deleted. So a subsequent insert can’t happen in that block correct? In that case when the deleted index space is freed>

Thanks,
Karthick

8. Karthick - January 21, 2009

Sorry i mean to say i perform an UPDATE and not DELETE.

Thanks,
Karthick

9. illiyaz mohammad - January 21, 2009

Thnks a lot Richard for the nice article….I ve leartn something new today courtesy your blog….

10. Bunditj - January 23, 2009

Richard,

From each dump, why does it always use 4 additional bytes of each leaf block ? For example a first leaf block uses 11 bytes (5+6) of those 2 columns, but total length is 15 bytes.

row#0[8021] flag: ——, lock: 2, len=15
col 0; len 5; (5): 42 4f 57 49 45
col 1; len 6; (6): 01 00 60 3c 00 00

Secondly, after first deletion or before second insert, I wonder why INDEX_STATS.DEL_LF_ROWS_LEN (total length of all deleted rows in index, but only 1 row now) show 17 bytes, but the demarkation of “D” line only show 15 ?

Lastly, you are always the best of index guru, so do you plan to write an Oracle book soon ?

Best regards

11. Vyacheslav Kryuchkov - January 28, 2009

Richard,

First – thank you! Many things became clear due to your articles.
I have a question about PCTFREE for indexes. I thought: if my PK is never updated, so ahhaa, I can rebuild it with PCTFREE 0 and win 10% of space. But if really indexes are never updated, what means PCTFREE for indexes?

Thanks,
Vyacheslav

12. Vyacheslav Kryuchkov - January 28, 2009

I found answer on asktom:

PCTFREE isn’t considered in an index after the index is built. PCTFREE is only meaningful during an index build — then we will reserve x% of the block for furture updates. After that — we stuff those blocks as full as we can.

Richard, sorry for disturb you for nothing.

Best regards,
Vyacheslav

13. Brian Tkatch - February 5, 2009

Richard, thanx for the informative article. I love these step by steps.

14. Richard Foote - February 5, 2009

Hi Karthick

Incorrect. The leaf block, although containing nothing but deleted entries remains in the index structure until a new block is required elsewhere within the index (due to block split) and gets recycled. Therefore a subsequent insert could potentially be reinserted into the block if appropriate.

15. Richard Foote - February 5, 2009

Hi Bunditj

The four byes consist of 2 bytes for general flags and lock bytes, and 1 byte each to store the length of each indexed column.

I think if you print out all my posts, you’ll likely have enough for a book !!

16. Richard Foote - February 5, 2009

Hi Vyacheslav

Exactly !! PCTFREE has a different meaning with indexes than it does with tables precisely because there are no updates as such. Also, there’s no such thing as a PCTUSED option for indexes precisely because index blocks are always considered for inserts if there’s sufficient space.

Ask Tom is one of the very very best places to look for Oracle related information.

17. Richard Foote - February 5, 2009

Hi Illiayaz and Brian

Thank you for your kind comments, much appreciated.

I try my best (when I’m not soaking up the sun by a pool) !!

18. Karthick - February 6, 2009

Oh index block split. Dint think about that. Thanks once again Richard.

19. suresh - April 26, 2009

Hi Richard,

Thanks for the excellent blog. Understanding a little bit about indexes now.

a) But had a confusion over index split. Can you please explain with examples.

b) As far as the previous posts i understand that indexes spaces will be reused when subsequent inserts. If so, how the BTREE leaf will be mapped.

My case is like this

I had 100 rows with btree index which was a sequence column generating a sequence of numbers.

So the range of root, branch ,leaf looks like this.

Root block
Branch1 Branch2
(Leafs 0-50 ) (Leafs 50-100)

If i delete the first 25 rows the index entries would be marked as deleted. If i reinsert the 25 rows again (so now the sequence number would be 101-125) they will insert at branch1 at place of leafs (1-25). Right. If so how the reading would be occur. So what exactly this situation is.

Root block
Branch1 Branch2
(Leafs 25-50 ) (Leafs 50-100)
(Leafs 101-124)

Does my assumption is correct or wrong. If wrong please correct me…..

Richard Foote - April 27, 2009

Hi Suresh

a) Look at this presentation, it should help to answer your questions regarding block splits:

http://richardfoote.files.wordpress.com/2007/12/index-internals-rebuilding-the-truth.pdf

b) No (if I read your comment correctly), the deleted entries will remain in the first leaf block and the new entries will go into the second leaf block. If they don’t fit in the second leaf block, Oracle will split it and add them in a third leaf block.

The golden rule regarding index entries. Index entries must always be in the logical order of the indexed columns within the index structure, always. The only possible exception being the Reverse key index where they’re in the logical order of the indexed values after the values are reversed.

Else Oracle will have no easy way of finding the location of a specific index entry. Just imagine an index in the back of a book with the index entries not in alphabetic order.

suresh - April 28, 2009

Hi,

Hi Richard,

Thanks much. will read the doc and certainly a great blog.

But you say it will go to the third leaf and subsequent leaf blocks for inserts, if so, when should the deleted entries (space) will be reused and how the space can be reclaimed.

If my understanding is correct Oracle adjusts it automatically. at leaf level, if not so, branch level, if not so, at root level. In such cases manual rebuild can help or what.

-Thanks for your time.
Suresh

20. Richard Foote - April 28, 2009

Hi Suresh

Again, have a read through the presentation in my earlier reply where I discuss all the various scenarios where Oracle may fragment an index. Your scenario where you have a monotonically increasing index but you only perform sparse deletions without totally deleting all index entries from a leaf page is one such scenario.

Note though if you delete all entries from a leaf block, the block becomes available for reuse during a subsequent block split.

And also note that even if you have a fragmented index, it doesn’t necessarily mean performance is impacted if the number of index blocks visited by the database doesn’t reduce substantially. As a typical large range only consists of a small percentage of index block visits, a rebuild may not “help” anything anyways.

But read the presentation to see what I mean …

suresh - April 29, 2009

Hi,

Thanks much for your time. Sure I am reading it.

-Suresh

21. Ashish - February 8, 2010

Hi Richard,

Thanks a lot for a great blog and for all of yr hard work.

God bless u.
Ashish

Richard Foote - February 8, 2010

Hi Ashish

Thanks for the nice feedback, much appreciated :)

22. Rahul - December 11, 2011

Hi Richard,

I want to better understand the reuse of space of deleted/updated records.
In the article above, there is only one index block, so the deleted space within that block was used (or at least this is my understanding).
Lets take a practical example.
There are million records in a table and index on a varchar2 column. I guess, all records where the values of indexed column start with same letter/character will be clubbed together. Now if I delete few records where indexed column starts with ‘A’, will that space will ever be used? I can see if new records where indexed column starts with ‘A’ are inserted, there is a possibility that the space for deleted records will be used. What if no new records starting with ‘A’ are inserted, will the space for deleted records re-used?

Also, for example, there is a NUMBER column, where values are inserted from a sequence (hence, its always increasing). Now I delete some of the older records. In this case, deleted values of indexed column will never come back in the table, will the space re-used?

Your thoughts please.
Thanks again for this really nice article.

– Rahul

Richard Foote - December 19, 2011

Hi Rahul

The same basic principles apply. Whether deleted space gets reused or not depends on a number of factors.

If an index entry is inserted into a leaf block (noting that an index entry must go into a specifc block that retains the logical order of all index entries), all deleted entries within the leaf block are cleaned out and the space potentially reused by later inserts into the leaf block. So in your example with records starting with “A” (say based on a SURNAME column), then yes all future inserts into the leaf block will reuse any deleted entries space.

However, if there are no future inserts into a specific leaf block, then correct, the deleted space within that leaf block will not be reused (as in your second example with a sequence). Unless that is, all the index entries of a leaf block are all deleted. If that’s the case and a leaf block consists of nothing but deleted entries, then the index block is placed on the “freelist” of the index and can be entirely reused by a subsequent index block split operation. The index is logically removed from it’s current location within the logical index structure and reused somewhere else within the index.

Hope this makes sense.

Thanks for the nice feedback.


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,821 other followers

%d bloggers like this: