Re: bitmap index Q.

This was well discusssed a few weeks back. First of all/ one has to define balance, if by you mean that all leaf nodes are equidistant from the root of the tree, then the tree stays balanced even if the keys are input sequentially. However, if by balance you mean a tree which stays shallow and wide instead deep and narrow, then no, the tree will not be in balance.

Lets sat you have a leaf node containing keys 1-9. In order to accomodate key 10
it is necessary to split the block. This operations leaves keys 1-5 in the first block and keys 6-10 in the second block. The first block will never have another key entered into it. The same thing will happen to the second, third, etc as values are entered. Using only 50% of the space in means more splits, more splits mean move ripples up to the root of the tree, which means a deep narrow index.

Ian MacGregor
Stanford Linear Accelerator Center
ian_at_slac.stanford.edu

"A. Bardeen" wrote:
>
> >I do this stuff for fun. :)
> So do I! I *don't* want to know what this says about us ;)
>
> But back to the topic at hand, I don't think the issue is how the btree is
> balanced, but how Oracle uses space in the index blocks.
>
> I did the following on my 8.0.5 play db on NT (2K blocksize):
>
> SQLWKS> create table indextest1 as select * from big1 nologging;
> Statement processed.
> SQLWKS> create table indextest2 as select * from big1 nologging;
> Statement processed.
> SQLWKS> alter table indextest1 add indxcol number;
> Statement processed.
> SQLWKS> alter table indextest2 add indxcol number;
> Statement processed.
> SQLWKS> create sequence indexseq1;
> Statement processed.
> SQLWKS> create sequence indexseq2;
> Statement processed.
> SQLWKS> update indextest1 set indxcol=indexseq1.nextval;
> 26625 rows processed.
> SQLWKS> commit;
> Statement processed.
> SQLWKS> create unique index indextest1_idx on indextest1 (indxcol);
> Statement processed.
> SQLWKS> create unique index indextest2_idx on indextest2 (indxcol);
> Statement processed.
> SQLWKS> update indextest2 set indxcol=indexseq2.nextval;
> 26625 rows processed.
> SQLWKS> commit;
> Statement processed.
>
> So basically indextest1_idx and indextest2_idx should be identical indexes
> as they are both created on a column whose values were populated with the
> same sequence values. The difference being that indexttest1_idx was created
> after the data was loaded and indextest2_idx was created by the update
> command.
>
> SQLWKS> select segment_name,initial_extent,next_extent,blocks,extents from
> user_segments where segment_name like 'INDEX%_IDX';
> SEGMENT_NAME INITIAL_EX NEXT_EXTEN BLOCKS EXTENTS
> ---------------- ---------- ---------- ---------- ----------
> INDEXTEST1_IDX 51200 67584 270 9
> INDEXTEST2_IDX 51200 65536 235 8
>
> Hmm, I expected the index which was built after the fact to use fewer blocks
> as I could swear I remember a discussion about how the index entries were
> stored in a monotonically increasing index in one of the performance tuning
> classes. As I recall that's the whole purpose behind reverse key indexes.
> Hmm, I also can't recall whether it was an Oracle7 or Oracle8 class, so it's
> possible things have changed.
>
> Damn, now this is gonna bug me. Looks like I'll be dumping index blocks
> tonight!
>
> -- Anita
>
> >From: Jared Still <jkstill_at_bcbso.com>
> >Reply-To: ORACLE-L_at_fatcity.com
> >To: Multiple recipients of list ORACLE-L <ORACLE-L_at_fatcity.com>
> >Subject: RE: bitmap index Q.
> >Date: Mon, 01 May 2000 12:47:00 -0800
> >
> >
> >I do this stuff for fun. :)
> >
> >
> >On Mon, 1 May 2000 Lisa_Koivu_at_gelco.com wrote:
> >
> > > GOOD exercise? I had to do it in school, automatic balancing, etc. in
> >C++
> > > You wanna talk about a nightmare... if it wasn't for the cute TA I
> >would have
> > > never passed data structures!
> > >
> > > That's probably the ONE THING I learned studying CSCI that actually
> >directly
> > > applies to my job.
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > Jared Still <jkstill_at_bcbso.com> on 05/01/2000 01:00:32 PM
> > >
> > > Please respond to ORACLE-L_at_fatcity.com
> > >
> > > To: Multiple recipients of list ORACLE-L <ORACLE-L_at_fatcity.com>
> > > cc: (bcc: Lisa Koivu/GELCO)
> > >
> > >
> > >
> > >
> > >
> > >
> > > Hmm... That sounds like a good exercise.
> > >
> > > Time to break out the 'Data Structures' book, and put it in
> > > the queue with the other 20 or so books I'm supposed to read.
> > >
> > > Jared
> > >
> > > On Mon, 1 May 2000, I.S. Manager wrote:
> > >
> > > > Automatic tree-balancing is a basic feature of the btree algorithm. I
> >wrote
> > > > a btree function once just to get a feel for what it does, and I can
> >tell
> > > > you that it makes absolutely no difference whether the keys go in in
> > > > sequential, reverse-sequential, or random order.
> > > >
> > > >
> > > > At 02:49 PM 4/28/00 -0800, Jain, Akshay wrote:
> > > > >Is it true that if data is loaded in *sequential* order, with
> >indexing on,
> > > > >the index gets lop sided. Thus only rebuilding the index(es) can
> > > > >restore its beneficial, shallow and wide structure.
> > > > >
> > > > >Unless there is automatic tree-balancing for indexes that Oracle
> > > > >does by itself?
> > > > >
> > > > >Akshay Jain
> > > > >_______________________
> > > > >Newcourt-CIT
> > > > >Tel. (416) 507-5385
> > > > >mailto:Akshay.Jain_at_cit.com
> > > > >_______________________
> > > > >
> > > > >
> > > > >-----Original Message-----
> > > > >Sent: Friday, April 28, 2000 3:54 PM
> > > > >To: Multiple recipients of list ORACLE-L
> > > > >
> > > > >
> > > > >Hola!
> > > > >
> > > > >One of our data marts here had awful performance yesterday. The only
> >thing
> > > > >that
> > > > >was different between yesterday and the previous days was that the
> >load ran
> > > > >with
> > > > >all indexes, including bitmaps, on the tables. Only 10,000 rows were
> >added
> > > > >-
> > > > >less than 1% change. The analyze was run for all tables to be hit by
> >the
> > > > >reports. However performance really bit yesterday until the indexes
> >were
> > > > >dropped and rebuilt.
> > > > >
> > > > >In class I remember talking about the tradeoff between a fast
> >load/building
> > > > >indexes and a slow load/leaving indexes up. Has anyone seen this
> >type of
> > > > >behavior before? I can not say for sure that the load is not
> >updating the
> > > > >fields the bitmap indexes were on.
> > > > >
> > > > >Any comments are appreciated.
> > > > >
> > > > >Lisa 'Almost Certified' Koivu
> > > > >
> > > > >
> > > > >
> > > > >--
> > > > >Author:
> > > > > INET: Lisa_Koivu_at_gelco.com
> > > > >
> > > > >Fat City Network Services -- (858) 538-5051 FAX: (858) 538-5051
> > > > >San Diego, California -- Public Internet access / Mailing
> >Lists
> > > > >--------------------------------------------------------------------
> > > > >To REMOVE yourself from this mailing list, send an E-Mail message
> > > > >to: ListGuru_at_fatcity.com (note EXACT spelling of 'ListGuru') and in
> > > > >the message BODY, include a line containing: UNSUB ORACLE-L
> > > > >(or the name of mailing list you want to be removed from). You may
> > > > >also send the HELP command for other information (like subscribing).
> > > > >--
> > > > >Author: Jain, Akshay
> > > > > INET: Akshay.Jain_at_cit.com
> > > > >
> > > > >Fat City Network Services -- (858) 538-5051 FAX: (858) 538-5051
> > > > >San Diego, California -- Public Internet access / Mailing
> >Lists
> > > > >--------------------------------------------------------------------
> > > > >To REMOVE yourself from this mailing list, send an E-Mail message
> > > > >to: ListGuru_at_fatcity.com (note EXACT spelling of 'ListGuru') and in
> > > > >the message BODY, include a line containing: UNSUB ORACLE-L
> > > > >(or the name of mailing list you want to be removed from). You may
> > > > >also send the HELP command for other information (like subscribing).
> > > > >
> > > > >
> > > > ---
> > > > Dennis Taylor
> > > > ---
> > > > The opinions expressed herein are mine. Get your own opinions!
> > > > ---
> > > > --
> > > > Author: I.S. Manager
> > > > INET: ismgr_at_pctc.com
> > > >
> > > > Fat City Network Services -- (858) 538-5051 FAX: (858) 538-5051
> > > > San Diego, California -- Public Internet access / Mailing Lists
> > > > --------------------------------------------------------------------
> > > > To REMOVE yourself from this mailing list, send an E-Mail message
> > > > to: ListGuru_at_fatcity.com (note EXACT spelling of 'ListGuru') and in
> > > > the message BODY, include a line containing: UNSUB ORACLE-L
> > > > (or the name of mailing list you want to be removed from). You may
> > > > also send the HELP command for other information (like subscribing).
> > > >
> > >
> > >
> > > Jared Still
> > > Certified Oracle DBA and Part Time Perl Evangelist ;-)
> > > Regence BlueCross BlueShield of Oregon
> > > jkstill_at_bcbso.com - Work - preferred address
> > > jkstill_at_teleport.com - private
> > >
> > >
> > > --
> > > Author: Jared Still
> > > INET: jkstill_at_bcbso.com
> > >
> > > Fat City Network Services -- (858) 538-5051 FAX: (858) 538-5051
> > > San Diego, California -- Public Internet access / Mailing Lists
> > > --------------------------------------------------------------------
> > > To REMOVE yourself from this mailing list, send an E-Mail message
> > > to: ListGuru_at_fatcity.com (note EXACT spelling of 'ListGuru') and in
> > > the message BODY, include a line containing: UNSUB ORACLE-L
> > > (or the name of mailing list you want to be removed from). You may
> > > also send the HELP command for other information (like subscribing).
> > >
> > >
> > >
> > >
> > >
> > >
> > > --
> > > Author:
> > > INET: Lisa_Koivu_at_gelco.com
> > >
> > > Fat City Network Services -- (858) 538-5051 FAX: (858) 538-5051
> > > San Diego, California -- Public Internet access / Mailing Lists
> > > --------------------------------------------------------------------
> > > To REMOVE yourself from this mailing list, send an E-Mail message
> > > to: ListGuru_at_fatcity.com (note EXACT spelling of 'ListGuru') and in
> > > the message BODY, include a line containing: UNSUB ORACLE-L
> > > (or the name of mailing list you want to be removed from). You may
> > > also send the HELP command for other information (like subscribing).
> > >
> >
> >
> >Jared Still
> >Certified Oracle DBA and Part Time Perl Evangelist ;-)
> >Regence BlueCross BlueShield of Oregon
> >jkstill_at_bcbso.com - Work - preferred address
> >jkstill_at_teleport.com - private
> >
> >
> >--
> >Author: Jared Still
> > INET: jkstill_at_bcbso.com
> >
> >Fat City Network Services -- (858) 538-5051 FAX: (858) 538-5051
> >San Diego, California -- Public Internet access / Mailing Lists
> >--------------------------------------------------------------------
> >To REMOVE yourself from this mailing list, send an E-Mail message
> >to: ListGuru_at_fatcity.com (note EXACT spelling of 'ListGuru') and in
> >the message BODY, include a line containing: UNSUB ORACLE-L
> >(or the name of mailing list you want to be removed from). You may
> >also send the HELP command for other information (like subscribing).
>
> ________________________________________________________________________
> Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
>
> --
> Author: A. Bardeen
> INET: abardeen_at_hotmail.com
>
> Fat City Network Services -- (858) 538-5051 FAX: (858) 538-5051
> San Diego, California -- Public Internet access / Mailing Lists
> --------------------------------------------------------------------
> To REMOVE yourself from this mailing list, send an E-Mail message
Received on Mon May 01 2000 - 16:56:02 CDT