Skip to Main Content

Breadcrumb

May 4th

Question and Answer

Connor McDonald

Thanks for the question, Itsik.

Asked: December 10, 2007 - 7:08 pm UTC

Last updated: June 30, 2021 - 3:02 am UTC

Version: 10.2.0

Viewed 10K+ times! This question is

You Asked

Hi Tom

I would like to ask a Question about Bitmap indexes, somethings in this indexes is still unclear for me.
Many rumors revolves around what exactly gets locked (and how) during a DML operation on column\row with Bitmap index, it starts with a full exclusive lock on the table (untrue) and ends with same behaver as Btree works (row-level exclusive lock of the effected rows), so what really happens in there, what is the logic ?
is this locking overhead related to the *fact* that bitmap indexes are not recommended for heavy DML stress tables ?


Thanks for your help
Itsik

and Tom said...


In a bitmap index, you have

a) a key value
b) a low-rowid value
c) a high-rowid value
d) a bit map that indicates for each rowid in that range whether the row that rowid points to has that value or not.



Suppose you have the EMP table and you create bitmap index bm on emp(deptno);


So, in the bitmap index, you might have key values like:

DEPTNO         LOW-ROWID          HIGH-ROWID        BITMAP
----------     ------------       -------------     ---------------
10             afdafda            badfasd           01010101010101
10             bbdafadafd         bcdafdfda         11010101010101
20             afdafda            badfasd           10101010101010
......




so, for each deptno in the EMP table, you will have 1 or more entries in the bitmap index. Each entry in the bitmap index points to potentially HUNDREDS of rows (the rows between low and high rowid).

Suppose you update:

update emp set deptno = 20 where empno = 1234;

and empno 1234 was in DEPTNO=10. That will update one of the bitmap keys bitmaps to remove the "1" (presume that is the first key in the above example). That will update one of the bitmap keys bitmaps to add a "1" for deptno=20 (presume that is the third key above).

Now, those two bitmap entries are locked by you.


Now, suppose I try to

update emp set deptno = 10 where empno = 5678;

And further, presume that record is currently showing deptno=20. That record is pointed to by the third bitmap key above - and when I try to update it, I block - I block on you - you have that key locked already. We are updating entirely different rows, however we need to update the SAME bitmap key since that bitmap key points to hundreds of rows.



... is this locking overhead related to the *fact* that bitmap indexes are not recommended for heavy DML stress tables ? ...


There is a locking implication by design in bitmap indexes, the keys point to hundreds of rows and if I lock a single key entry in a bitmap index, I've locked the key entry for hundreds of other rows.

that is WHY bitmaps are not recommended - if you update a bitmap indexed column OR you insert/delete from the table (which will modify the bitmap index), you'll find serialization at best and deadlocks all over the place at worst.

Rating

  (8 ratings)

Is this answer out of date? If it is, please let us know via a Comment

Comments

Itsik Harel, December 11, 2007 - 2:54 pm UTC

Thanks for your perfect answer.
Itsik

What about direct-path inserts?

PB, December 11, 2007 - 6:27 pm UTC

You said: "that is WHY bitmaps are not recommended - if you update a bitmap indexed column OR you insert/delete from the table (which will modify the bitmap index), you'll find serialization at best and deadlocks all over the place at worst."

What about doing insert /*+ append */ operations? I'm thinking in terms of data warehouse operations (single large, parallel insert in batch mode). Do those create the same serialization? I was thinking they wouldn't since index maintenance happens after the insert - is that right?

Tom Kyte
December 11, 2007 - 9:44 pm UTC

well, given that insert /*+ append */ itself SERIALIZES (only one thing at a time will be doing that) there is by definition - no problem.

if you do a parallel insert /*+ append */ - no problem either - because each parallel thread will have it's own rowid ranges - their low/highs are different.


index maintain happens during the insert really - when you direct path insert, a mini index is built for the new data and merged in bulk to the main index after the work is done.

queries locks with bitmap indexes

Avishai, November 25, 2008 - 5:38 am UTC

Hi

Are there any locking issues with selects ( without the "for update" clause) during the update/insert operations when bitmap indexes are used? Or the good old "we don't block selects" / read consistency is true with bitmap indexes as well.

Thanks,
Avishai


Tom Kyte
November 25, 2008 - 11:48 am UTC

good old read consistency and multiversioning - the read only selects will not block.


Bitmap index causing deadlocks.

Sahoo Dillip, November 22, 2012 - 4:29 am UTC

Hi Tom,
I am facing a situation where a materialized view used for reporting is being updated parallely by multiple jobs issued by a auto job scheduling tool. This materialized view is having multiple Bitmap Indexes.
The jobs updating Materialized views carryout either of the below statements:
(1) Merge followed by Delete
(or)
(2) Delete followed by Insert
Since 2-3 months post 10gR2 to 11gR2 migration , I am facing some of these jobs are failing due to Deadlocks. But same situation not used to exists with 10gR2.
I could see the tracefile signaling the deadlock was created due to blocks on Indexes and queries causing these deadlocks are mostly due to Delete combined with parallely running Merge.
Could you please guide us on suggestions/fix? Is that Deferring Indexes before DML operation then Activating Indexes using "ALTER INDEX <> IMMEDIATE" will help?
Tom Kyte
November 29, 2012 - 6:33 am UTC

you cannot have a bitmap index on a table with multiple concurrent modifications. It just doesn't work (by design)

bitmap indexes are only suitable on a segment that is modified by one thing at a time. period.

You got lucky in 10gr2, nothing more, nothing less.


You'll have to forgo the bitmap indexes on any segment that undergoes concurrent modifications (this has *always* been true) or set them unusable, do your operation and rebuild them.

Materialized Views updates creating Deadlocks

Dillip Kumar Sahoo, December 10, 2012 - 4:31 am UTC

Thanks a ton for writing a followup on my query.

1) Is that switching index type from BITMAP to BTREE would help.

2) Please note, Business users are running very heavy queries on these MViews, so How badly the query performance would be affected due to change in index type from Bitmap to BTree.

3) Could you please clarify, we generally use BITMAP index on columns with less number of unique values. Is there any limits on number of unique/distinct values to be maintained by a BITMAP index.
As, The few columns on which BITMAP indexes are created have almost 10k to 80k distinct values.
Tom Kyte
December 14, 2012 - 2:31 pm UTC

1) you cannot have bitmap indexes in an environment where you want more than one transaction happening at a time.

2) insufficient data. Unless you are merging more than one bitmap together to get your results, problem none. If you are merging many bitmaps together - probably a lot.

3) that isn't a reason to use bitmaps. that is a myth.
http://jonathanlewis.wordpress.com/2006/11/29/bitmap-indexes/


you use bitmaps predominantly when you want to merge together many of them at run time and there is no sensible way to b*tree index them. eg: an ad-hoc query environment where the users might pick any N columns out of M and query on them - no way to b*tree index them - but you could create a series of single column bitmaps that we'll merge together using AND/OR's to create a new bitmap index on the fly to find your rows.

Thanks for the answer

Mikhail Onishchenko, June 17, 2021 - 8:53 am UTC

Hello.

I have a table to which inserts only happen in batches. Some of the columns have only 1 distinct value per batch(yes, I know it's a poor case of denormalization).

Those columns have very few distinct values and are often used to query data. Which makes them an incredibly good candidate for bitmaps in my opinion. The issue is that there are concurrent updates going on that table. However they are not touching any of those columns, they just update a date and a status field.

So the question is, how do bitmaps work with concurrent updates on a column that is not a part of the bitmap?
Connor McDonald
June 22, 2021 - 1:52 am UTC

As long as you are not *touching* the bitmap column, you should be fine.

eg run the following


create table t as 
select 1 x, rownum y, rownum z from dual connect by level <= 100
union all
select 2 x, rownum+1000 y, rownum z from dual connect by level <= 100;

-- session 1
update t 
set z=z+1,x=2
where y = 75;

-- session 2
update t 
set z=z+1,x=3
where y = 70;


with and without a bitmap index on 'x'. You'll see

- without the bitmap index at all, you're fine
- without the "x=" in the update, you're fine.

but setting X and having the bitmap gets you stuck

Thanks for the answer

Mikhail Onishchenko, June 24, 2021 - 8:57 am UTC

Thanks for the example!

As far as I know, rowid of an updated row isn't going to change as long as it remains in the same block after update, so the bitmap doesn't have to be updated.

What if I have insufficient pctfree and rows have to frequently migrate to different blocks after updates? Rowids would change and that would require an update of the bitmap even if I'm not touching the column it's created on.

Do I need to make sure that my worst case scenario updates fit into pctfree?
Chris Saxon
June 24, 2021 - 11:01 am UTC

The rowid remains the same after row migration. From the docs:

In row migration, Oracle Database moves the entire row to a new data block, assuming the row can fit in a new block. The original row piece of a migrated row contains a pointer or "forwarding address" to the new block containing the migrated row. The rowid of a migrated row does not change.

You can verify this with a quick demo:

- Create a two-column table with pctfree 0
- Load it with data, populating the first column & leaving the second null
- Check the rowid for a row
- Update the second column to a large value
- Recheck the rowid

You'll see that they are still the same:

create table t (
  c1 int, c2 varchar2(4000)
) pctfree 0;

insert into t ( c1 )
with rws as (
  select level x from dual
  connect by level <= 8000
)
  select x from rws;
  
commit;

select rowid from t
where  c1 = 1;

ROWID                
AAAlP/AAcAAAG0lAAA    

update t set c2 = lpad ( 'x', 4000, 'x' )
where  c1 = 1;

select rowid from t
where  c1 = 1;

ROWID                
AAAlP/AAcAAAG0lAAA   

Thanks for the answer

Mikhail Onishchenko, June 25, 2021 - 9:12 am UTC

Wow, I completely missed the fact that ROWID is imutable. Thanks again!

What if a row migrates a hundred times between blocks? Will there be a chain of a hundred pointers and oracle will have to read a 100 blocks to fetch that row by rowid? Or does oracle update the pointer at row's original location for every new migration?
Connor McDonald
June 30, 2021 - 3:02 am UTC

For a migration, we have a row point and the entire row elsewhere.

So the only way to "navigate" to that row is via the pointer. So if we had to migrate it elsewhere, we simply update the pointer. So only one hop.

But don't forget, there is also row chaining. A row with (say) 50 or 100 columns all of varchar2(4000) will span potentially dozens of blocks. So its possible to do multiple hops to read a single row anyway.

In each case, we have a pointer from one block to the next, so keep those pointer(s) in sync as a row is modified