Wednesday, November 7, 2018

Bitmap index locking in the cloud or not

Bitmap indexes are really great for flexibility of data selection in data warehouse application environments.  This is achieved by the optimizer being able to use sets of bitmaps at a time to find data in the table and the set of indexes used can change based on the need of the moment.  Bitmap indexes can be merged together (typically with a bitmap AND or OR operation) unlike normal B-tree indexes.  But in a transactional system they can really cause problems.  And locking is the issue.  The problem is that when you lock an index entry in a bitmap index you lock a set of rowids, not just one as you do in a normal b-tree index. 

A simplified look at bitmap entry on a column COLOR would be something like this:

 Control Bytes    Key        Start ROWID       End ROWID         Bitmap
FLG-LCK-LEN      BLUE      AAAcc7AA…       AAAcc7AA…       1010111100000…

The range of rowids for any one entry could cover one extent of a table, but there could be more than one entry for a value on large extents.  What this means is that if I were to do any INSERTS, UPDATES or DELETES of rows for BLUE in this range, I’ve effectively locked that entire set of rows in the table.  I don’t of course; the lock is on the index entry not at the table level.  But from a functionally point of view that hardly matters, I can’t do DML on other rows in that same range with the same value.   (Here I mean DML as in the commands INSERT, UPDATE and DELETE.  The SELECT command is a DML statement but isn’t part of this discussion.)

Here is an example to illustrate the point. 

Session ONE                       Session TWO
Time 1 - insert into bitmaplock values (9000,'RED');
                                                Time 2 - insert into bitmaplock values (9001,'BLUE');
Time 3 - insert into bitmaplock values (9002,'BLUE');
Session one is now waiting on session two.
                                                Time 4 - insert into bitmaplock values (9003,'RED');
                                                Session two is now waiting on session one, a deadlock.
Session one is now gets this message:
insert into bitmaplock values (9002,'BLUE')
ERROR at line 1:
ORA-00060: deadlock detected while waiting for resource

At this point session one must either commit or rollback to get out of the deadlock situation.  Reissuing the insert will just continue the deadlock and no one gets anywhere.

Notice that this example is using INSERT commands. It should be impossible to have a deadlock for an insert, since either session is aware of the other session’s row, how could they be deadlocked?  It’s because they are deadlocked on the bitmap index not the table data.   Of course if the two sessions happen to do the inserts into different extents of the table they would be fine.  Even so, I’m sure you can see this is just a tripwire that will be hit at some point.

The bottom line on this, don’t use bitmap indexes on table that have DML activity.  You may be able to get away with relatively small amounts of DML from a single session.  Many folks have found that even small amounts of DML can be problematic.  Hence they will drop all bitmaps on a table, do the DML operation, and then recreate the bitmap indexes.  Good news is that bitmap indexes tend to be much smaller and build faster than normal b-trees. 

Here is the code to do this example yourself:

drop table bitmaplock;

create table bitmaplock (id number, color varchar2(10));

  for i in 1..1000 loop
    insert into bitmaplock values(1, 'RED');
    insert into bitmaplock values(2, 'WHITE');
    insert into bitmaplock values(3, 'BLUE');
    insert into bitmaplock values(4, 'YELLOW');
    insert into bitmaplock values(5, 'GREEN');
    insert into bitmaplock values(6, 'BROWN');
    insert into bitmaplock values(7, 'BLACK');
    insert into bitmaplock values(8, 'TAN');
    insert into bitmaplock values(9, 'GRAY');
    insert into bitmaplock values(10, 'GOLD');
  end loop;

create bitmap index bitmaplock_idx on bitmaplock(color);

exec dbms_stats.gather_table_stats(ownname=>null, tabname=>'BITMAPLOCK', estimate_percent=>100, cascade=>true, method_opt=>'FOR ALL COLUMNS SIZE 1');

-- the following steps must be done in order
-- need two sessions using same schema
-- in first session
insert into bitmaplock values (9000,'RED');

-- in other session
insert into bitmaplock values (9001,'BLUE');

-- in first session
insert into bitmaplock values (9002,'BLUE');

-- in other session
insert into bitmaplock values (9003,'RED');

-- at this point you will get a deadlock error