jump to navigation

Deleted Index Entries Part II (V-2 Schneider) June 18, 2008

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

I’m back !!

In Part I, we looked at how index entries are only marked as deleted during delete/update operations. This means the DML operation and resultant transaction doesn’t have to concern itself with physically cleaning out the deleted entries.

The question is therefore, are these deleted index entries “deadwood”, wasted space that makes the index less compact and less efficient over time requiring a potential periodic index rebuild, or can this deleted space be subsequently reused by Oracle ?

There’s a common perception that deleted space within an index is indeed “deadwood” or can only be reused in very specific circumstances, such as when an identical index value is subsequently re-inserted.

However, this is just another of Oracle’s infamous urban myths. In the vast majority of cases, deleted space within an index can indeed be recycled and can indeed be subsequently reused. Today, I’m just going to begin by focusing on the most common method by which deleted index entries are generally cleaned up.

All it takes to clean out all the deleted index entries within a specific index leaf block is a subsequent insert in the block. That’s it, that’s all it takes. Just one new index entry in a leaf block will automatically clean out all associated deleted index entries that may currently exist within the block. Even if there are hundreds of deleted entries with the leaf block, just the one new index entry will clean them all out. Note the new index value doesn’t have to be the same as any of the deleted index entries, it doesn’t even have to be within the range of any of the deleted index entries within the block. Any new index entry within the leaf block will do the job quite nicely.

A very simple demonstration I use to highlight this point. First, create a simple table and associated index with 10 rows.

SQL> CREATE TABLE del_stuff (id NUMBER, name VARCHAR2(30));

Table created.

SQL> CREATE INDEX del_stuff_i ON del_stuff(id);

Index created.

SQL> INSERT INTO del_stuff SELECT rownum, ‘Bowie’ FROM dual CONNECT BY level <=10;

10 rows created.

SQL> COMMIT;

Commit complete.

Next, deleted say 4 of the rows from the table.

SQL> DELETE del_stuff WHERE id in (2,4,6,8);

4 rows deleted.

SQL> COMMIT;

Commit complete.

A view of INDEX_STATS after a ANALYZE … VALIDATE STRUCTURE command will show the following:

LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN U_SPACE
------- ----------- --------------- -------
     10           4              56     140

 

Note: It clearly shows 4 index entries are indeed currently marked as deleted.

 

A treedump will show the following:

 

—– begin tree dump

leaf: 0x1402e3a 20983354 (0: nrow: 10 rrow: 6)

—– end tree dump

 

Note: It only shows 6 rrow but 10 nrow values, clearly suggesting there are currently 4 deleted index entries.

 

A partial index block dump will show the following:

 

kdxlende 4

 

row#1[7928] flag: —D–,lock: 2, len=12
col 0; len 2; (2): c1 03
col 1; len 6; (6): 01 40 2e 32 00 01

 

That indeed there are currently 4 index entries marked as deleted with the ‘D’ flag within the index block.

 

However, just a single subsequent insert will clean out all 4 of these deleted index entries. Note the new value (100) is not the same value as any of the previously deleted entries and is not even within the range of previously deleted index entries:

 

SQL> INSERT INTO del_stuff VALUES (100, ‘New Row’);

 

1 row created.

 

SQL> COMMIT;

 

Commit complete.

 

Now, if we look at the same leaf block, we find:

 

LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN U_SPACE
------- ----------- --------------- -------
      7           0               0      98

 

That indeed, INDEX_STATS no longer has any statistics of deleted index entries.

 

—– begin tree dump
leaf: 0x1402e3a 20983354 (0: nrow: 7 rrow:  7)
—– end tree dump

 

That the Index Tree dump no longer has any record of the deleted index entries.

 

That the index block dump no longer has any record of the deleted index entries and that:

 

kdxlende 0

 

the count of deleted index entries within the block has been reset to 0.

 

For most randomly inserted indexes, this means deleted entries will be eventually automatically cleaned out and the freed space reused by subsequent insert operations. Worrying about deleted space and rebuilding such indexes is typically unnecessarily.

 

I’ll next discuss another method by which Oracle will clean out and remove deleted index entries from its indexes …

 

About these ads

Comments»

1. Mohamed - June 18, 2008

Hi Richard,

Do you obtain this
— ———————
Now, if we look at the same leaf block, we find:
LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN U_SPACE
——- ———– ————— ——-
7 0 0 98
— —————————————
Without doing again and analyze validate structure of the index???
and if so, do this means that the deleted space is really cleaned up after an analyze validate structure or just after the insert??

Regards

2. Asif Momen - June 18, 2008

Hi,

>> do this means that the deleted space is really cleaned up after an >> analyze validate structure or just after the insert??

Deleted space is cleaned after the insert, we use “analyze validate structure” to confirm the same.

3. karthick - June 19, 2008

So does that mean when there is lot of deleted index entry in a block then a new insert will be more expencive as it has to do the clean up work.

Thanks,

Karthick.

http://www.karthickarp.blogspot.com/

4. laurentschneider - June 19, 2008

Hi Rich,
I was in your session in OOW when you talked about index rebuild.

I have a primary key index (2 numeric columns) that is 50% bigger than the table. I suppose there is no DELETE and no UPDATE on this table, only inserts. Does this makes sense?

Regards
Laurent


desc AUDITDETAIL
Name Null? Type
----------------------- -------- ----------------
AUDITMASTERIK NOT NULL NUMBER(14)
PTRVALUE NOT NULL NUMBER(5)
SQLNAME VARCHAR2(40)
DBTYPENO NUMBER(5)
INTWID NUMBER(10)
DECIMALS NUMBER(5)
VALOLD VARCHAR2(4000)
VALNEW VARCHAR2(4000)

select segment_name, segment_type,BYTES,EXTENTS from dba_segments where segment_name like '%AUDITDETAIL';

SEGMENT_NAME SEGMENT_TYPE BYTES EXTENTS
--------------- ------------------ ------------- ----------
AUDITDETAIL TABLE 97669611520 93145
P_AUDITDETAIL INDEX 143687417856 137031

select num_rows from dba_tables where table_name='AUDITDETAIL';

NUM_ROWS
----------
1996805942

5. Richard Foote - June 19, 2008

Hi Mohamed

It’s as stated by Asif, yes you need to analyze the index with validate structure to populate index_stats, no magic there.

Whether or not the analyze clears the deleted entries, try it out yourself and dump the block after the insert but before the analyze.

6. Richard Foote - June 19, 2008

Hi Karthick

As Oracle is already going to the trouble of reading the leaf block into memory and adding a new index entry, clearing out the deleted stuff is only going to add a relatively minor amount of additional overhead.

7. Richard Foote - June 19, 2008

Hi Laurent

This index would certainly be worth some further investigation. Assuming you use all the digits for the numeric columns, that’s approximately 12 byes + 6 bytes for the rowid, + 2 bytes for the column length bytes + 2 bytes additional overhead for a max of say 22 bytes per index entry. Smaller numbers may only need around 2 bytes each so 22 bytes is pushing it.

Now looking at your numbers, if you divide the bytes in the index by the rows in the table, that’s roughly 72 bytes per index entry. Even allowing for block overheads, branch blocks, free space, etc. it does appear your index has lots of potential free space.

Even allowing for 50-50 block splits, it’s still very excessive so something doesn’t appear right here. Are you sure there have been no deletes ? How are rows inserted into the table ? When was the index created and what was the pctfree value ?

Certainly an index with unusual characteristics and worthy of some investigation.

8. laurentschneider - June 19, 2008

Thanks for your answer,

Looking in dbms_metadata I can get the following ddl.

CREATE UNIQUE INDEX “SCDAT”.”P_AUDITDETAIL” ON “SCDAT”.”AUDITDETAIL” (“AUDITMASTERIK”, “PTRVALUE”)
PCTFREE 10 INITRANS 2 MAXTRANS 255 COMPUTE STATISTICS
STORAGE(INITIAL 1048576 NEXT 1048576 MINEXTENTS 1 MAXEXTENTS 2147483645
PCTINCREASE 0 FREELISTS 1 FREELIST GROUPS 1 BUFFER_POOL DEFAULT)
TABLESPACE “SCAUDIX”

The rows are inserted with
INSERT INTO AUDITDETAIL VALUES (:B1 ,:B2 ,:B3 ,:B4 ,:B5 ,:B6 ,:B7 ,:B8 )

According to dba objects, the index was created in 2006. Note the table is never selected, the index is there only to enforce primary key.

I cannot exclude a former dba did some reorg on the table and/or delete some rows, but surely not this year.

If I look in history (I have many copies of this db), the 1/1.5 ratio is still there. In the oldest copy I have 71Gb/107Gb and in the newest I have 100Gb/148Gb.

9. Richard Foote - June 20, 2008

Hi Laurent

Something odd is happening…

My suspicion based on what info I have is that the index is generally performing 50-50 block splits but the free space is not being utilised as would normally be expected.

The table, despite it’s definition appears to have quite a low average row size (the bytes divided by number of rows is around 49 bytes per row, then less block overheads, pctfree etc.) so I would guess many of the fields have null or short values.

So the average index entry length may therefore not too far from say half that of the average table row length.

Therefore, with only 50% of an index block being used, the numbers start to merge somewhat if the 50% of generate free space is not ever used.

Is it possible that the table has some kind of outlier value ? Do most of the PKs monotonically increase but there’s a maximum value in there somewhere already existing that the new monotonically increasing PK entries never hit ?

This could possibly result in 50-50 splits which generates free space that never gets used and makes the index therefore grow at a higher rate than the table.

What is the maximum key value and what are the typical new PK values that get generated ?

10. Mohamed Houri - June 20, 2008

Dear Richard,

I tried the same example but with a partitioned table and a locally partitioned index. It seems for me that I didn’t came to the same result. Do the cleaned index space is also valid for partitioned indexes (oracle 8.1.7.4).

CREATE TABLE del_stuff(ID NUMBER, dat_partition DATE, NAME VARCHAR2(30))
PARTITION BY RANGE (dat_partition)
(PARTITION p_mho_20080630 VALUES LESS THAN …01/07/2008
,PARTITION p_mho_20080930 VALUES LESS THAN …01/10/2008
,PARTITION p_mho_20081231 VALUES LESS THAN… 01/01/2009
)

CREATE INDEX DEL_STUFF_I ON del_stuff
(ID, dat_partition)
LOCAL

insert into del_stuff values (1, ’15/MAY/2008′,’Bowie’);
insert into del_stuff values (2, ’25/MAY/2008′,’Bowie’);
insert into del_stuff values (3, ’30/MAY/2008′,’Bowie’);
insert into del_stuff values (4, ’30/JUNE/2008′,’Bowie’);
insert into del_stuff values (5, ’13/JULY/2008′,’Bowie’);
insert into del_stuff values (6, ’03/AUG/2008′,’Bowie’);
insert into del_stuff values (7, ’23/AUG/2008′,’Bowie’);
insert into del_stuff values (8, ’06/OCT/2008′,’Bowie’);
insert into del_stuff values (9, ’11/NOV/2008′,’Bowie’);
insert into del_stuff values (10, ’30/DEC/2008′,’Bowie’);

commit;

DELETE del_stuff WHERE id in (2,4,6,8);

analyze index DEL_STUFF_I validate structure;

select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE
from index_stats
where name = ‘DEL_STUFF_I’

3 1 22 66

insert into del_stuff values (100, ’30/JULY/2008′,’Bowie’);

commit;

analyze index DEL_STUFF_I validate structure;

select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE
from index_stats
where name = ‘DEL_STUFF_I’

3 1 22 66

Thanks a lot

11. Asif Momen - June 20, 2008

@ Mohamed,

> It seems for me that I didn’t came to the same result. Do the
> cleaned index space is also valid for partitioned indexes (oracle
> 8.1.7.4).

Well, to arrive at the correct result you need to slightly modify your test case.

Instead of issuing “analyze index DEL_STUFF_I validate structure”, you need to validate index structure partition by partition and then query INDEX_STATS view to see the deleted number of rows.

SQL> analyze index DEL_STUFF_I partition (p_mho_20080630) validate structure;

Index analyzed.

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE
2 from index_stats
3 where name = ‘DEL_STUFF_I';

LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE
———- ———– ————— ———-
4 2 44 88

SQL> analyze index DEL_STUFF_I partition (p_mho_20080930) validate structure;

Index analyzed.

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE
2 from index_stats
3 where name = ‘DEL_STUFF_I';

LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE
———- ———– ————— ———-
3 1 22 66

SQL> analyze index DEL_STUFF_I partition (p_mho_20081231) validate structure;

Index analyzed.

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE
2 from index_stats
3 where name = ‘DEL_STUFF_I';

LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE
———- ———– ————— ———-
3 1 22 66

Now, when we sum DEL_LF_ROWS column for all the partitions, Oracle reports that 4 rows are deleted.

SQL> insert into del_stuff values (100, ’30/JULY/2008′,’Bowie’);

1 row created.

SQL>
SQL> commit;

Commit complete.

SQL> analyze index DEL_STUFF_I partition (p_mho_20080630) validate structure;

Index analyzed.

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE
2 from index_stats
3 where name = ‘DEL_STUFF_I';

LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE
———- ———– ————— ———-
4 2 44 88

SQL> analyze index DEL_STUFF_I partition (p_mho_20080930) validate structure;

Index analyzed.

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE
2 from index_stats
3 where name = ‘DEL_STUFF_I';

LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE
———- ———– ————— ———-
3 0 0 66

A block belonging to partition “p_mho_20080930″ has been cleaned.

SQL> analyze index DEL_STUFF_I partition (p_mho_20081231) validate structure;

Index analyzed.

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE
2 from index_stats
3 where name = ‘DEL_STUFF_I';

LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE
———- ———– ————— ———-
3 1 22 66

SQL> analyze index DEL_STUFF_I validate structure;

Index analyzed.

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE
2 from index_stats
3 where name = ‘DEL_STUFF_I';

LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE
———- ———– ————— ———-
3 1 22 66

SQL>

When we issue “analyze index DEL_STUFF_I validate structure;” against the local index, what we see in the INDEX_STATS view is the information about the last local index.

SQL> select LF_ROWS,DEL_LF_ROWS,DEL_LF_ROWS_LEN,USED_SPACE
2 from index_stats
3 where name = ‘DEL_STUFF_I';

LF_ROWS DEL_LF_ROWS DEL_LF_ROWS_LEN USED_SPACE
———- ———– ————— ———-
3 1 22 66

Hope this clarifies your doubt.

Regards

Asif Momen

http://momendba.blogspot.com

12. Mohamed - June 22, 2008

Asif,

Thanks a lot for these clarificationns.

Mohamed

13. Richard Foote - June 23, 2008

Hi Mohamed

Hope your question is answered.

Thanks Asif.

14. Sachin - September 10, 2009

Hi Richard,

Somehow, I’m not able to cleanout the deleted space. Could you answer why ?

SQL> create table rr(r number);

Table created.

Elapsed: 00:00:00.11
SQL> insert into rr values(1);

1 row created.

Elapsed: 00:00:00.11
SQL> /

1 row created.

Elapsed: 00:00:00.10
SQL> /

1 row created.

Elapsed: 00:00:00.10
SQL> /

1 row created.

Elapsed: 00:00:00.10
SQL> insert into rr select 2 from all_tables where rownum commit;

Commit complete.

Elapsed: 00:00:00.11
SQL> create index rr_ix on rr(r);

Index created.

Elapsed: 00:00:00.14
SQL> delete from rr where r=2 and rownum commit;

Commit complete.

Elapsed: 00:00:00.11
SQL> analyze index rr_ix validate structure;

Index analyzed.

Elapsed: 00:00:00.12
SQL> select LF_ROWS,LF_BLKS,DEL_LF_ROWS from index_stats;

LF_ROWS LF_BLKS DEL_LF_ROWS
———- ———- ———–
10004 20 5000

Elapsed: 00:00:00.89
SQL> insert into rr values(100);

1 row created.

Elapsed: 00:00:00.11
SQL> SQL> commit;

Commit complete.

Elapsed: 00:00:00.11
SQL> analyze index rr_ix validate structure;

Index analyzed.

Elapsed: 00:00:00.11
SQL> select LF_ROWS,LF_BLKS,DEL_LF_ROWS from index_stats;

LF_ROWS LF_BLKS DEL_LF_ROWS
———- ———- ———–
10005 20 5000

— Sachiin

15. Richard Foote - September 10, 2009

Hi Sachin

Unfortunately, we lost a little of the formatting in translation.

It looks to me as if you’ve insert a few values 1, a whole bunch of values 2 and then deleted about half of the 2’s but only the first 1/2 of the entries.

That means there are no deleted entries in the last (or right most) leaf block. Correct ?

But you then insert a value of 100 which is the largest yet and it therefore get’s inserted into this last leaf block but there are no deleted entries in there for it to clean out.

Therefore, no deleted entries are removed.

Deleted entries are only removed from the leaf block being inserted into and reorg’ed and because you’ve inserted into a leaf block with no deleted entries, no deleted entries ar removed.

If you delete the rest of the 2’s and insert a few more 100’s, you’ll then see some of the deleted entries being recycled.

16. Rajesh Narkar - March 8, 2011

Hi Richard,

Thanks for your informative posts. Its really helpful!

In a scenario of IOT, when a leaf block is 50% full and one row in the middle of the sorted index key entries in that block is deleted. And then row with same index key values but more row size is inserted again then in that case how will it be stored? Since the row cann’t fit in the same place because of more row size.

Thanks

17. Richard Foote - April 20, 2011

Hi Rajesh

It’s physically stored at the “bottom” of the leaf block where freespace begins but logically referenced and sorted as necessary.

It’s something that’s probably worth a blog post to fully discuss so thanks for the idea.


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

%d bloggers like this: