Re: index rebuilding...

Hi Don

Comments embedded

"Don Burleson" <don_at_burleson.cc> wrote in message news:998d28f7.0301312045.7ca1d667_at_posting.google.com...
> > "Indexes require rebuilding when deleted leaf nodes appear". I don't
even
> > know what a deleted leaf node is.
>
> Yes, that is very apparent. Despite your delusions of knowledge about
> a "pure" B*Tree, an Oracle index tress cannot be a pure b*tree because
> it is impossible to index 100m rows in only four levels in a b*tree.
> Did you flunk your basic data structures class?

Not sure what you mean here. Are you saying that 100m row index can't fit in a 4 level index ? Well it can, although the block size and index key length would have a say I would think. Or are you suggesting that Oracle indexes can only have 4 levels ?

>
> Oracle maintains many sub-keys within each inode. When the number of
> entries exceeds the internal "index_block_contains" threshold
> (normally 50, depending on the key length), the Oracle index splits
> until it reaches the maximum supported level of its superior node. At
> that point, the index "spawns" into another level. I cannot
> comprehend that you think that Oracle will re-level a whole index tree
> in real-time. Think about it!

Sorry Don, this is incorrect. Although there is some overhead to an index splitting, I've always thought Oracle was rather efficient in the way it maintained the index balance. Worst possible case (assuming a 3 level index about to jump to 4 to keep balanced):

• leaf block splits, extra IO (probably) as Oracle grabs the next free block on the freelist
• if the last 'block' in the index structure then new index entry simply goes to the newly added block, else 50% of the existing entries go into each split block and the new value goes where appropriate
• corresponding branch 'block' needs to be updated to add an entry that points to the newly added block but if full, it too is split, extra IO (probably) as Oracle grabs the next free block on the freelist
• same as the leaf block, existing entires get redistributed and new branch pointer is added
• root block needs to be updated to add an entry that points to the newly add branch block but if full, it too is split, extra IO (probably) as Oracle grabs the next free block on the freelist
• same as the branch block, existing entires get redistributed and the new branch pointer is added
• a new block is required for a new root node, extra IO (probably) as Oracle grabs the next free block on the freelist
• pointers are added to point to the two (now) second level branch nodes

Index rebalance is complete. So in total, we had to split 3 blocks and redistribute (possibly) their contents and perform 4 additional IOs. Now our poor little insert (or possibly update) has had to wait for all this to complete and yes there is some overhead, but such a "total" rebalance would occur once in a blue moon and isn't "that" huge a one (IMHO).

>
> > Oracle re-uses deleted leaf row space, all on its own.
>
> Yes, Einstein, in your simplistic example Oracle will re-use an
> adjacent deleted node that rarely happens in the real-world. In most
> cases, indexes with significant DML will have large amounts of dead
> leaf nodes.

Now I'm confused. If you mean leaf "rows", then note these are completely reusable by subsequent inserts. If you mean leaf "blocks" then these are no longer part of the index structure and except for fast full index scans, have no effect on the performance of the index. These dead "things" are only a concern if:

1. The table has "shrunk" and the same volume of rows is not expect to be reinserted. In which case, a table rebuild as well as an index rebuild is in order
2. The index has incremental entries and the deleted rows are not going to be reused by subsequent inserts. This is the scenario when an index rebuild is most likely to be of use (if some but not many entires remain in a whole bunch of existing leaf blocks).

>
> > Next. " Oracle index nodes are not physically deleted when table rows
are
> > deleted". I would have more confidence in the advice you offer if you
could
> > get the distinction between a node (ie, a block) and a row right.
>
> Yes, I agree, one of us does not know what they are talking about.
>
> > As for this: "Note that Oracle indexes will "spawn" to a fourth level
only
> > in areas of the index where a massive insert has occurred, such that 99%
of
> > the index has three levels, but the index is reported as having four
levels.
> > " ... well, all I can say is: this is complete baloney.
>
> You really should take the time to check your facts before you
> embarrass yourself.
>
> > Oracle's index structures are B*Trees, meaning that they are 'balanced'
trees.
>
> No genius, look at the DESCTs. If you take the trouble to decompile
> the code and look at a few block dumps, you can see exactly how it
> works.

Hummmm. I would love to see evidence to the contrary because the block dumps I taken over the years support my understanding on how indexes work.

Create a table, create an index, populate it slowing and dump to see how the index "grows" and keeps balanced. Then delete rows slowing and reinsert again and you'll see exactly how Oracle uses it's indexes and reuses the deleted space. You see "pointers" or slots that get reused and map to the newly insert index entries.

Report back on your findings ;)

Cheers

Richard

PS. I'm no Einstein but a David Bowie fan who got ripped off today on one exceedingly bad haircut !! Received on Sat Feb 01 2003 - 08:59:41 CST