Re: Index management

"Brian Peasland" <dba_at_remove_spam.peasland.com> wrote in message news:409FF911.C3AD82AC_at_remove_spam.peasland.com...
> "Howard J. Rogers" wrote:
> >
> > Brian Peasland wrote:
> >
> > > On this last point, you and I agree, sort of.
> >
> > And it's a point Mike just made up. No-one has ever accused him of
> > advocating rebuilding all indexes.
> >
> > > I don't say rebuild
> > > indexes just because of some magic number. And I don't say to never
> > > rebuild indexes. There are times to rebuild indexes and times not to.
> > > But for me, those times are more dictated by the expected flow of
data,
> > > not by some magic number. If an index has a tendancy to get one-sided
> > > (normally due to the use of a monotic sequence as the value to the
> > > indexed column followed by deletions of "older" values) then
rebuilding
> > > periodically can help.
> >
> > See, this is where that paper you wrote is wrong, too, IIRC. If the
> > index has got "lop-sided" because you deleted a lot of older values,
> > then you now have a lot of empty leaf nodes on the left-hand edge of
> > your index, and those empty blocks can now receive the next inserts from
> > your monotonically incrementing sequence number. Which means that a
> > rebuild is *not* warranted.
>
> I would disagree with you here. The empty leaf nodes on the left-hand
> edge of the index cannot receive new inserts because those inserts will
> always be on the right hand side! I'll draw a crude diagram to
> illustrate my point. I have a table called EMP with an index on EMPID.
> The EMPID column is populated from my EMPID_SEQ sequence, so the next
> employee id will always be larger than previous employee id. Let's say I
> have an index that crudely looks like:
>
>
>
>
> |
> ---------------------------------------
> | |
> -------------------- ---------------
> | | | |
> ---------------- ---------------- ---------------- ------
> | | | | | | | | | | | | | |
> 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014
>
>
> (Please excuse the very rough diagram of this simple B-tree structure.
> And I do hope that the formatting does go through for people.)
>
> Anyway, The next employee id to this index will be 1015 which will be
> added to the right side of the B-tree. Since this key is increasing, it
> must be larger than all other previous index entries.
>
>
> |
> ---------------------------------------
> | |
> -------------------- ---------------
> | | | |
> ---------------- ---------------- ----------------
> -----------
> | | | | | | | | | | | | | |
> |
> 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014
> 1015
>
>
> Now as life goes one, people leave the company for various reasons. So
> let's assume that some people have left the company. The leaf nodes in
> the tree might look something like the following:
>
>
> |
> ---------------------------------------
> | |
> -------------------- ---------------
> | | | |
> ---------------- ---------------- ----------------
> -----------
> | | | | | | | | | | | | | |
> |
> 1003 1005 1009 1010 1011 1012 1013 1014
> 1015
>
> Will the next employee id use one of those empty slots? It can't. The
> next employee will be numbered 1016. How can it reuse one of those empty
> slots?
>
> Given enough time, you can have a tree structure that starts to look
> similar to the following:
>
>
> |
> ---------------------------------------
> | |
> -------------------- ---------------
> | | | |
> ---------------- ---------------- ----------------
> -----------
> | | | | | | | | | | | | | |
> |
> 1009 1010 1011 1012 1013 1014
> 1015
>
>
> The entire left side of the tree is unnecessarily contributing to the
> height of the index.
>
> This same concept gets even worse for something like invoices. The
> invoice numbers are generated by a sequence. All new invoices will get
> added to the right side of the tree. What makes this worse is that
> companies tend to remove the oldest invoices all at once. For instance,
> the company may decide to remove all of last year's invoices (or older)
> from the table. In that case, there won't be a sparse look to the tree
> like I indicated in my 3rd diagram.
>
>
> Looking at these examples, how is it that those empty blocks can now
> receive the next inserts from your monotonically incrementing sequence
> number"?
>
>

Hi Brian,

Because empty index leaf nodes are placed on the freelist and are reused by subsequent index leaf splits. The fact that leaf blocks are not reused is yet another indexing myth.

See my presentation/white paper for the details.

Cheers

Richard Received on Mon May 10 2004 - 17:09:23 CDT