Interesting....
Scot, June 16, 2005 - 5:16 pm UTC
Yes...that is an excellent answer. You are right, you wouldn't be able to time the usage of both since only one or the other would be chosen.
But, you could measure WHICH ONE would be chosen by the CBO in given situations based on your data, your queries, and your system specs and parameters.
Thanks for showing me that it is possible to put a constant like that after a column in an index, I didn't know you could do that, but it makes total sense. That accomplish what I was requesting. I also find it interesting that you can create a constant index on a table without referring to a column in that table as in:
create table t(a number);
create index idx on t(5); -- or whatever constant
Although I have no idea yet how that would be useful.
Below for a very artificial (but hopefully still valid) example of what I meant for my first usage scenario in my original question, to demonstrate which index the CBO will pick if you hold the query constant but change the data. I'd think I could use the same basic approach to test what would happen if you hold the data constant and change the queries.
MYDBA@ORCL >
MYDBA@ORCL > prompt TEN THOUSAND
TEN THOUSAND
MYDBA@ORCL >
MYDBA@ORCL > create table test(a number);
Table created.
MYDBA@ORCL > insert into test select rownum from all_objects where rownum <= 10000;
10000 rows created.
MYDBA@ORCL > commit;
Commit complete.
MYDBA@ORCL > create index btree_idx on test(a,1);
Index created.
MYDBA@ORCL > create bitmap index bitmap_idx on test(a,2);
Index created.
MYDBA@ORCL > exec dbms_stats.gather_table_stats(user,'test',cascade=>true);
PL/SQL procedure successfully completed.
MYDBA@ORCL >
MYDBA@ORCL > set autotrace traceonly explain;
MYDBA@ORCL > select a from test;
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=6 Card=10000 Bytes=40000)
1 0 TABLE ACCESS (FULL) OF 'TEST' (TABLE) (Cost=6 Card=10000 Bytes=40000)
MYDBA@ORCL > drop index btree_idx;
Index dropped.
MYDBA@ORCL > select a from test;
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=6 Card=10000 Bytes=40000)
1 0 TABLE ACCESS (FULL) OF 'TEST' (TABLE) (Cost=6 Card=10000 Bytes=40000)
MYDBA@ORCL > set autotrace off;
MYDBA@ORCL > drop table test;
Table dropped.
MYDBA@ORCL >
MYDBA@ORCL > prompt ONE THOUSAND
ONE THOUSAND
MYDBA@ORCL >
MYDBA@ORCL > create table test(a number);
Table created.
MYDBA@ORCL > insert into test select rownum from all_objects where rownum <= 1000;
1000 rows created.
MYDBA@ORCL > commit;
Commit complete.
MYDBA@ORCL > create index btree_idx on test(a,1);
Index created.
MYDBA@ORCL > create bitmap index bitmap_idx on test(a,2);
Index created.
MYDBA@ORCL > exec dbms_stats.gather_table_stats(user,'test',cascade=>true);
PL/SQL procedure successfully completed.
MYDBA@ORCL >
MYDBA@ORCL > set autotrace traceonly explain;
MYDBA@ORCL > select a from test;
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=2 Card=1000 Bytes=4000)
1 0 INDEX (FAST FULL SCAN) OF 'BTREE_IDX' (INDEX) (Cost=2 Card=1000 Bytes=4000
)
MYDBA@ORCL > drop index btree_idx;
Index dropped.
MYDBA@ORCL > select a from test;
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=3 Card=1000 Bytes=4000)
1 0 TABLE ACCESS (FULL) OF 'TEST' (TABLE) (Cost=3 Card=1000 Bytes=4000)
MYDBA@ORCL > set autotrace off;
MYDBA@ORCL > drop table test;
Table dropped.
MYDBA@ORCL >
MYDBA@ORCL > prompt ONE HUNDRED
ONE HUNDRED
MYDBA@ORCL >
MYDBA@ORCL > create table test(a number);
Table created.
MYDBA@ORCL > insert into test select rownum from all_objects where rownum <= 100;
100 rows created.
MYDBA@ORCL > commit;
Commit complete.
MYDBA@ORCL > create index btree_idx on test(a,1);
Index created.
MYDBA@ORCL > create bitmap index bitmap_idx on test(a,2);
Index created.
MYDBA@ORCL > exec dbms_stats.gather_table_stats(user,'test',cascade=>true);
PL/SQL procedure successfully completed.
MYDBA@ORCL >
MYDBA@ORCL > set autotrace traceonly explain;
MYDBA@ORCL > select a from test;
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=1 Card=100 Bytes=300)
1 0 BITMAP CONVERSION (TO ROWIDS) (Cost=1 Card=100 Bytes=300)
2 1 BITMAP INDEX (FAST FULL SCAN) OF 'BITMAP_IDX' (INDEX (BITMAP))
MYDBA@ORCL > drop index bitmap_idx;
Index dropped.
MYDBA@ORCL > select a from test;
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=1 Card=100 Bytes=300)
1 0 INDEX (FULL SCAN) OF 'BTREE_IDX' (INDEX) (Cost=1 Card=100 Bytes=300)
MYDBA@ORCL > set autotrace off;
MYDBA@ORCL > drop table test;
Table dropped.
MYDBA@ORCL >
June 16, 2005 - 10:05 pm UTC
...But, you could measure WHICH ONE would be chosen by the CBO....
not really, you would be in an unreal environment. The CBO might choose the b*tree if the bitmap were not there and vice versa. Or it might just be a "tie" and it picks one.
the constant trick is just a "function based index", the constant is an "expression", you could use 1+1 as well....
and in your example, it is very artifical as the indexes are probably bigger than the table itself!
I still don't see it as being too useful
why tis is not working ?
A reader, June 17, 2005 - 9:46 am UTC
ORCL > create table test(a number);
Table created.
ORCL > create index idx1 on test(a);
Index created.
ORCL > create bitmap index idx2 on test(a);
create bitmap index idx2 on test(a)
*
ERROR at line 1:
ORA-01408: such column list already indexed
June 17, 2005 - 3:43 pm UTC
because such a column list is already indexed??
sort of what we were discussing above. You cannot have an index that covers exactly the same "key"
bitmaps "always" better...
Connor, June 19, 2005 - 7:57 am UTC
Oracle published a paper a while back with a series of benchmarks showing that a bitmap index out-performed a b-tree for all cardinalities up to "n/2" where 'n' was the number of rows in the table.
If the paper is indeed valid, it would be reasonable to assume that for (static) tables in a DSS, a bitmap is probably gonna be the way to go more often than not.
June 19, 2005 - 11:42 am UTC
well, I've created more than one compressed b*tree index to serve as a "skinnier version of the base table" with concatenated keys and extra columns -- eg:
create index i on t(key1,key2,key3,attribute1,attribute2) compress n;
just to be able to fast full scan it.
But I would concurr with the premise that a bunch of single column bitmaps in a read mostly/only system works.
Index on single constant
Gary, June 19, 2005 - 10:05 pm UTC
"create index idx on t(5); -- or whatever constant
Although I have no idea yet how that would be useful."
Hmmm. Not many queries where it would be used.
1) SELECT COUNT(*) from t (and indexing a single repeating byte will probably be the skinniest thing you can scan);
2) SELECT COUNT(*) from t where rowid in (....) [possibly, depending on stats]
Create the index in a tablespace, set the tablespace readonly and you can prevent inserts and deletes in the table but allow updates (as long as they don't involve row migration). [Now to think of a circumstance where THAT would be useful.....]
June 20, 2005 - 9:50 am UTC
just as a clarification:
<quote>
(as long as they
don't involve row migration)
</quote>
well, the row can MIGRATE. Migrated rows do not change the rowid.
the row cannot MOVE (enable row movement). Rows can move when:
a) you have a partitioned table, you enable row movement and you update the partition key and cause it to move from partition A to partition B.
b) you are using 10g and 'compact' the table after enabling row movement
c) you are using 10g and flashback the table after enabling row movement.
Bitmap Index and Btree Index on the same column
RJ, January 17, 2007 - 2:06 am UTC
As usual Your concept is great.Thanks .
bitmap and btree index
A reader, October 02, 2010 - 2:06 am UTC
Hi Tom,
I would like to ask some very basic questions:
1) Why we would need an index against a table to search a particular row? I mean index and table both can store Row id. Then why can't it be possible to use a table instead of a index?
2) Is the leaf block of a Bitmap index represent Rowid,Bits? Can we convert bitmap into btree and vice-versa?
3) Why an IOT has such amazing set of Row id (like Block#-Row#-File# combination)? Is there any structural difference between IOT and Index? Can a table be converted into IOT?
4) Can we synchronize Block# from rowid and Block_id from dba_extents?
October 04, 2010 - 1:49 am UTC
I'm going to suggest a book - Expert Oracle Database Architecture (see homepage on asktom.oracle.com). I go over these structures in depth.
Or, you can read the Server Concepts Guide (suggest the 11gR2 copy of that no matter what version of Oracle you are currently using). That is free.
1) a row in a table has a rowid, it is an address - it includes the file the row is in, the block it is on in that file and the slot on the block it resides in.
If you have a rowid - you can get to a row very fast. An index is a structure that contains KEYS and rowids - you can lookup a key very fast in a index (usually in 2-3 IO's). Once you find the key - you get the rowid. The rowid lets you get to the row.
The index is like the index at the end of a book - you can lookup a topic fast, find a page number (rowid) and go to the page (row) straight off.
2) A bitmap index has a key, a low rowid and a high rowid (to cover a range of the table). It also has a bitmap (series of zeroes and ones) that indict whether or not a row in that range has the key value or not. We can take the lo/high rowids and the bitmap to figure out what the rowid of the N'th row in that range would be.
A btree is not a bitmap, a bitmap is not a btree - they are not convert-able one into the other, no.
3) IOTs do not have "amazing rowids", not sure what you mean. Rows in an IOT hav a logical rowid that consists of a base64 representation of the primary key of the row (and a rowid guess).
You have to rebuild a segment to convert it from a heap table to an IOT and vice versa. It is not a simple 'conversion', it would be a complete reorganization.
4) not sure what you mean??
basic queries on index
A reader, October 04, 2010 - 2:50 pm UTC
Hi Tom,
1) I can understand that if we search a row in the table through key column (like empid in emp table) then it will be helpful through index. But what if we want to search through a non-key column (like ename in emp table)? will it include an index search?
2) Can you please explain #3 above with an example: You have to rebuild a segment to convert it from a heap table to an IOT and vice versa. It is not a simple 'conversion', it would be a complete reorganization. ??
3) Can I say that block no. got from Rowid of a table is the same as block_id from dba_extents?
October 05, 2010 - 5:55 am UTC
1) if there is no index on ename - it is highly unlikely it would use an index, but it *might*
if you used first rows optimization and had a query like:
select ename, empno from emp where ename like 'X%' order by empno;
it MIGHT use the index to read the data ordered by empno and then apply the filter "ename like 'X%'" - it might.
but here you are not using the index to search, you are using it to read the data sorted. I don't know what you are trying to ask here really - if you don't have an index on the thing you are searching - how could you use an index to search???
2) you have to rebuild it - reorganize it - recreate it - get rid of what you have and reload a new thing.
I don't know how else to say it. To convert from a regular heap table to an IOT - you have to completely rebuild it from scratch.
3) block_id in dba_extents is a starting block id - it describes the start of a range of blocks. the block number in a rowid is a specific block. they are related to eachother (you can query dba_extents
where <your_block_number> between block_id and block_id+blocks-1
to find the extent your block number from the rowid is in)
Unique Index
A reader, December 26, 2010 - 3:45 am UTC
Hi Tom,
In your book 'Expert Oracle Database', you have specified,"In a unique index,as defined by you, oracle does not add the rowid to the index key."
Does it mean, in an unique index, rowid is not stored along with every index key value in the leaf blocks? If yes then how in an unique index, it can locate the exact location of the row of the table without rowid?
December 26, 2010 - 7:04 pm UTC
no, it means that in an index, there is a key and data associated with a key.
In a non-unique index, we add the rowid to the key, in a unique index - we don't add it to the key - we don't need to - you've told us YOUR key is already to be unique.
Unique Index
A reader, December 26, 2010 - 9:36 pm UTC
Hi Tom,
I didn't get your point: "we don't add it to the key".
1) What do you meant we don't add to the key? Do you mean to say we don't store Rowid in Unique index blocks?
2) I could understand the property of non-unique index though as it store the rowid along with the key column value in leaf blocks. But is it the same case with unique index?
December 27, 2010 - 11:07 am UTC
in an index, there is "key data" and "data data, data that goes with the key"
The key is unique.
the "data data" can be whatever.
An index is a lot like an index organized table - an index organized table has a "key" and "data"- just like an index was. It is not a long jump from an index to an index organized table - there is just more "data" part in an index organized table.
The rowid is absolutely in a unique index (it has to be).
The rowid just isn't part of the KEY (which has to be unique) in a unique index.
The rowid is part of the "data" of the index entry in a unique index.
Unique index
A reader, December 27, 2010 - 1:45 pm UTC
Hi Tom,
Can you please show the structure of an unique index leaf block (what you have mentioned above) with example? I feeling confused still.
December 27, 2010 - 3:53 pm UTC
there are two parts to an index entry:
part1: the key, must be UNIQUE and non-empty
part2: the data, may or may not exist - can be anything you want, doesn't have to be unique
that is all, don't over-think this, it is as simple as it sounds - an index entry has two pieces:
part1: the key, must be unique and non-empty
part2: the data, doesn't have to exist, but if it does - it can be anything.
if you have a table:
create table t ( x int, y int, z int );
and you have a indexes:
create unique index t_idx1 on t(x);
create indext t_idx2 on t(y,z);
then T_IDX1 will have:
key=x
data=rowid
and T_IDX2 will have:
key=y,z,ROWID
data=<nothing>
as the leaf entries.
Unique index
A reader, December 28, 2010 - 9:03 pm UTC
Hi Tom,
I have now understood a bit. But tell me one thing: Suppose I have an unique index over a single column of a table and a non-unique index over a single column of another table. So which do you think will occupy more space in the leaf block? Is it the unique index or non-unique index?
December 30, 2010 - 12:59 pm UTC
they both have
a) a key
b) optionally data
In case 1 - you have a key of that column and data of the rowid
In case 2 - you have a key of that column + rowid and data of nothing
In short - they are effectively the same, however..........
the unique index will be marginally larger because when the rowid is stored with a leading length indicator when stored as data, but without the leading length indicator when stored as part of the key...
ops$tkyte%ORA11GR2> create table t ( x int, y int );
Table created.
ops$tkyte%ORA11GR2>
ops$tkyte%ORA11GR2> insert into t
2 select rownum, rownum
3 from all_objects, (select level l from dual connect by level <= 10 );
719920 rows created.
ops$tkyte%ORA11GR2>
ops$tkyte%ORA11GR2> create unique index t_idx1 on t(x);
Index created.
ops$tkyte%ORA11GR2> create index t_idx2 on t(y);
Index created.
ops$tkyte%ORA11GR2>
ops$tkyte%ORA11GR2> analyze index t_idx1 validate structure;
Index analyzed.
ops$tkyte%ORA11GR2> create table t2
2 as
3 select 'unique' when, index_stats.* from index_stats;
Table created.
ops$tkyte%ORA11GR2>
ops$tkyte%ORA11GR2> analyze index t_idx2 validate structure;
Index analyzed.
ops$tkyte%ORA11GR2> insert into t2
2 select 'nonunq' when, index_stats.* from index_stats;
1 row created.
ops$tkyte%ORA11GR2>
ops$tkyte%ORA11GR2> with data
2 as
3 ( select when, thing, val
4 from t2
5 unpivot ( val for thing in
6 ( LF_ROWS, LF_BLKS, LF_ROWS_LEN, LF_BLK_LEN,
7 BR_ROWS, BR_BLKS, BR_ROWS_LEN, BR_BLK_LEN,
8 DEL_LF_ROWS, DEL_LF_ROWS_LEN, DISTINCT_KEYS,
9 MOST_REPEATED_KEY, BTREE_SPACE, USED_SPACE,
10 PCT_USED, ROWS_PER_KEY, BLKS_GETS_PER_ACCESS,
11 PRE_ROWS, PRE_ROWS_LEN, OPT_CMPR_COUNT, OPT_CMPR_PCTSAVE )
12 )
13 )
14 select THING, "unique", nonunq, "unique"-nonunq diff,
15 case when nonunq > 0 then round("unique"/nonunq*100,2) end "%"
16 from data
17 pivot( max(val) for when in ( 'unique' as "unique", 'nonunq' as nonunq )
18 )
19 order by thing
20 /
THING unique NONUNQ DIFF %
-------------------- ---------- ---------- ---------- ----------
BLKS_GETS_PER_ACCESS 4 4 0 100
BR_BLKS 4 4 0 100
BR_BLK_LEN 8028 8028 0 100
BR_ROWS 1502 1601 -99 93.82
BR_ROWS_LEN 16501 19175 -2674 86.05
BTREE_SPACE 12050100 12841704 -791604 93.84
DEL_LF_ROWS 0 0 0
DEL_LF_ROWS_LEN 0 0 0
DISTINCT_KEYS 719920 719920 0 100
LF_BLKS 1503 1602 -99 93.82
LF_BLK_LEN 7996 7996 0 100
LF_ROWS 719920 719920 0 100
LF_ROWS_LEN 10781432 11501352 -719920 93.74
MOST_REPEATED_KEY 1 1 0 100
OPT_CMPR_COUNT 0 0 0
OPT_CMPR_PCTSAVE 0 0 0
PCT_USED 90 90 0 100
PRE_ROWS 0 0 0
PRE_ROWS_LEN 0 0 0
ROWS_PER_KEY 1 1 0 100
USED_SPACE 10797933 11520527 -722594 93.73
21 rows selected.
Non-unique index
A reader, December 29, 2010 - 10:37 am UTC
Hi Tom,
Why don't we take rowid also in data part of a non-unique index as it is in unique index? Why in the key column part?
December 30, 2010 - 1:22 pm UTC
because there is no such thing as a non-unique index under the covers. The B*Tree index is always unique.
In order to make a non-unique index unique - we simply add rowid to the key instead of the data and viola - it is unique.
Bitmap and Btree index
Arindam, December 31, 2010 - 6:38 am UTC
Hi Tom,
First I would like to wish you "HAPPY NEW YEAR 2011" in advance.
I have couple of questions:
1) Will Bitmap search locks the entire table at any case and Btree index search locks only the row of the table?
2) What is the leaf block structure of the bitmap index? Specially the rowid?
3) Why we would be using Reverse Key index if the entire leaf block is not locked to find a row?
January 03, 2011 - 8:45 am UTC
1) queries do not lock.
2) a bitmap index is stored in a b*tree index. In the b*tree index that is the bitmap index - say on "create bitmap index i on emp(job)" - the index key/data might look like this:
Value lo-rowid hi-rowid compressed-bitmap
CLERK AAAS3XAAEAAAA/7AAA AAAS3XAAEAAAA/7AAN 010001000101001
CLERK AAAS3XAAEAAAA/7AAM AAAS3XAAEAAAA/7AAX 001000100010100
MANAGER AAAS3XAAEAAAA/7AAA AAAS3XAAEAAAA/7AAN 100010001010010
MANAGER AAAS3XAAEAAAA/7AAM AAAS3XAAEAAAA/7AAX 000100010001010
....
So, in the value field you would see the actual key value, coupled with a rowid range (a slice of the table - the slice of the table that that particular bitmap key entry covers) and finally a bitmap string (stored compressed) that tells us whether a given row in that range has that value or not. So, we can see that hte "second row in the first slice of the table is a clerk".
Given that rowid range - we can synthesize any of the rowids in it - so if we look at the bitmap string and the 42nd bit was set "on", we can figure out given the rowid range what the rowid of the 42nd row is.
Note that I purposely put clerk in there twice - a single bitmap key doesn't necessarily cover the ENTIRE table - but rather just a slice of it.
3) that is like asking "why would we cross the street to wake up in the morning". The two things - reverse key index and how a bit index locks - have nothing to do with each other.
You use a bitmap index in a read only / read mostly environment, the goal is to have a small index that can be combined with other bitmaps to rapidly find a small amount of data in a big set of data.
You use a reverse key index to reduce contention (buffer busy waits, not ENQUEUE waits) in a write intensive environment.
Such gems lead to more questions...
Michael Tefft, January 03, 2011 - 11:51 am UTC
1. Is this kind of information available elsewhere? I checked the Concepts guide, performance guide, and data warehousing guide but none of their explanations explain it with this detail.
2. Is the 'slicing' consistent across all key values? It would seem 'sensible' for it to be so (more efficient for and-ing/or-ing the bitmaps) but I don't pretend to know all of the considerations.
3. Is the 'slicing' dictated by the maximum size of the bitmap that can be stored in the leaf?
January 03, 2011 - 12:16 pm UTC
1)
Well, I wrote it up in Expert Oracle Database Architecture ;) It is touched on in the concepts guide (at least the 11g one - I worked on that one). The rowid stuff isn't spelled out (technically - doesn't need to be). But the key+bitmap is - and references to the ability to map the bitmap to a rowid is.
http://www.jlcomp.demon.co.uk/03_bitmap_1.doc http://www.jlcomp.demon.co.uk/06_bitmap_2.doc http://www.jlcomp.demon.co.uk/07_bitmap_3.doc are very good writeups as well.
2) they do not have to be as far as I know. I've never really researched it.
3) not entirely - the bitmaps are stored raw and can get large (covering many thousands of rows with compression). But they can be the limiting factor for the "slice size"
Also relevant would be the 'clustering' of the data values and whether you use single row modifications or big BULK operations. I'll refer you to the first of Jonathan's three papers above - he goes into some detail on that.
Bitmap and Btree indexes
Arindam, January 03, 2011 - 12:46 pm UTC
Hi Tom,
It seems to be getting interesting. Questions are:
1) You have told that an index has 2 parts: key and data. So, can you please explain with an example what is stored in the "data" part for a non-unique index?
2) I am not sure why in OLTP system B-tree index is preferred than a Bitmap. Can you please explain?
3) You have shown hi-rowid and lo-rowid above. How can it be interpreted? Is there any such set of rowids for B-tree index?
Also can you please elaborate compressed-bitmap?
4) In Reverse key index is preferred than regular/normal index so that while accessing the index(normal) block by a session other session might be waiting to get that. Isn't it?
January 03, 2011 - 1:26 pm UTC
1) simply put: the data that isn't part of the unique key is the data.
In a UNIQUE INDEX on T(x) - the key is X, the rowid is the data.
In a non-unique index on T(x) - the key is X+rowid, there is no data
It is just empty.
UNLESS you are an index organized table (IOT) - which is really an index in disguise, then the key is the primary key attributes - and the data is everything else (there is no rowid in an IOT)
2) simply because a single entry in a bitmap index points to potentially thousands of records. If you had a bitmap index on EMP(JOB) and you had thousands of CLERKS and thousands of ADMINS - a simple:
update emp set job = 'ADMIN' where job = 'CLERK' and ename = 'SCOTT'
1 row updated..
would in effect lock thousands of CLERK records (to change a 1 to a 0 in the bitmap) and thousands of ADMIN records (to change a 0 to a 1). You end up in effect locking hundreds or thousands of records - not just one (you lock that index key - not the records really - but the effect is in general the same)
3) I don't know what to say there. What do you mean by "how can it be interpreted"??? It is a rowid range - a slice of the table - a piece of the table - a range of the table. It is a starting address and an ending address and it covers all of the rows in between those two addresses.
A b*tree index just has the single rowid - in a b*tree index - an index key points to A SINGLE ROW. In a bitmap index a single index key points to MANY ROWS (a rowid range covers those rows, points to those rows, includes those rows)
The bitmap of zeroes and ones is stored in a compressed format - nothing more needs be said - instead of storing a bit per row in the range - we might store a lot LESS than a bit per row. That is all. It is compressed.
4) no, not at all. A reverse key index is a special tuning device to be used in certain rare conditions.
If you have access to expert oracle database architecture - I cover all of this in great detail. If not, the concepts guide does a pretty good job too (use the 11gr2 concepts guide)
Bitmap Index structure
A reader, January 07, 2011 - 1:23 pm UTC
Hi Tom,
I have 2 questions:
1) From the above example,suppose I have only 2 rows
Value lo-rowid hi-rowid compressed-bitmap
CLERK AAAS3XAAEAAAA/7AAA AAAS3XAAEAAAA/7AAN 010001000101001
MANAGER AAAS3XAAEAAAA/7AAA AAAS3XAAEAAAA/7AAN 100010001010010
(i)This row signifies the number of employees from ***7AAA to ***7AAN rowids having JOB as either CLERK or MANAGER or nothing. Is this the leaf structure of Bitmap? or it was just an example shown for understanding?
(ii)If I update the JOB as MANAGER of someone who was CLERK then how could the entire BITMAP formation got locked? Is that in a single block?
2) How can Reverse key index upgrades performance?
January 07, 2011 - 2:01 pm UTC
1) bitmap indexes are stored in b*tree indexes.
In a b*tree index we store two bits of information:
the key: this is unique
the data: this is optional (may be empty) and contains data that is not part of the unique key.
So, for example if I create an index t_idx on t(x) then the key would be X+rowid and the data would be empty. If I create a UNIQUE index on t(x) then the key would be x and the data would be rowid.
Now in a bitmap index, the key could be
VALUE+rowid-range
and the data would be
compressed bitmap
Think of it this way, it would look a lot like:
create table bitmap( value, rowid-range, data blob, primary key(value,rowid-range) ) ORGANIZATION INDEX;
The locking within the bitmap index happens at the KEY level - if you update a CLERK to be a MANAGER - you will lock the bitmap key of CLERK+rowid-range to change a one to a zero. THEN you will have to lock the manager entry to change a zero to a one.
it all happens at the key (row) level in the index - the problem is that single key points to hundreds or thousands of rows. In effect, those rows are "locked". Another session cannot delete on of those rows for example because in order to do so it would need to lock a key in the index that is already locked.
2) it might degrade performance, it might improve it, it might do nothing. A reverse key index is used on data that is monotonically changing (increasing or decreasing). If you have an index on that data (like a primary key populated by a sequence) then EVERYONE is trying to update the same index block as all of the values go next to each other. A reverse key index makes it so that the number one is not next to the number two in the index anymore (the bytes are reversed - one is not next to two anymore). That has the effect of spreading the inserts out all over the place in the index - not just on the right hand side. That in turn reduces contention. That is how it might help performance
Bitmap Index structure
A reader, January 07, 2011 - 2:44 pm UTC
Thanks a lot Tom....You got me understood atlast