Tuesday, January 17, 2012

Bitmap Index Locking

Bitmap indexes are useful when the cardinality of a column is low and it is required to join multiples of such columns. Primarily designed for used in data warehouse environments where DML activities are infrequent. Bitmap index can introduce performance overheads if used in a OLTP systems where DML activities are frequent. Reason is the way rows are locked to make changes to the bitmap index when a row is changed or inserted into the table.

This blog is to show these locks in action. Bitmap indexes are only available with Oracle Enterprise Edition.

Setup the initial environment
create table y (a number, b varchar2(20));

begin
    for i in  1 .. 10
    loop
      insert into y values(mod(i,5),dbms_random.string('X',10));
    end loop;
end;
    /

select DBMS_ROWID.ROWID_OBJECT(rowid) "OBJECT",
       DBMS_ROWID.ROWID_RELATIVE_FNO(rowid) "FILE",
       DBMS_ROWID.ROWID_BLOCK_NUMBER(rowid) "BLOCK",
       DBMS_ROWID.ROWID_ROW_NUMBER(rowid) "ROW", rowid,y.* from y order by 5,6;
    
    OBJECT       FILE      BLOCK        ROW ROWID                       A B
---------- ---------- ---------- ---------- ------------------ ---------- ----------
     93735          4        583          0 AAAW4nAAEAAAAJHAAA          1 1ML8L3NZBE
     93735          4        583          1 AAAW4nAAEAAAAJHAAB          2 E79SCS1B26
     93735          4        583          2 AAAW4nAAEAAAAJHAAC          3 OAMU9H2Y7B
     93735          4        583          3 AAAW4nAAEAAAAJHAAD          4 OAIF1LZZLE
     93735          4        583          4 AAAW4nAAEAAAAJHAAE          0 FU68J1S48B
     93735          4        583          5 AAAW4nAAEAAAAJHAAF          1 7WD1OB3O6T
     93735          4        583          6 AAAW4nAAEAAAAJHAAG          2 FC9UTGS8RY
     93735          4        583          7 AAAW4nAAEAAAAJHAAH          3 7H58F7BEZH
     93735          4        583          8 AAAW4nAAEAAAAJHAAI          4 S9UKCCLM38
     93735          4        583          9 AAAW4nAAEAAAAJHAAJ          0 EEBV89AYHA

10 rows selected.

create bitmap index aidx on y(a) compute statistics;
Values shown for column B will be different replace them accordingly.

The bitmap index entry would contain the column A as the index key and low rowid and high row id range encompassing all the rows in that bitmap key entry and the bitmap for the specific rowid range. See the bitmap index storage section

The above bitmap index could be conceptually visualised as
A       low rowid           high rowid          bitmap
1,  AAAW4nAAEAAAAJHAAA,  AAAW4nAAEAAAAJHAAJ,  1000010000
2,  AAAW4nAAEAAAAJHAAA,  AAAW4nAAEAAAAJHAAJ,  0100001000
3,  AAAW4nAAEAAAAJHAAA,  AAAW4nAAEAAAAJHAAJ,  0010000100
4,  AAAW4nAAEAAAAJHAAA,  AAAW4nAAEAAAAJHAAJ,  0001000010
0,  AAAW4nAAEAAAAJHAAA,  AAAW4nAAEAAAAJHAAJ,  0000100001
Now to see how locking takes place open two sql plus sessions and set auto commit off on one of them run a DML to change column A value from 1 to 2 for a single row.
SQL> update y set a = 2 where b  = '1ML8L3NZBE';

1 row updated.
As a result of this update two bitmap index entries will lock. Those are the index entry for 1 (to remove bitmap value 1 and set it to 0 for the row) and index entry for 2 (to set bitmap value from 0 to 1 for the row).

Because of this trying to update column A value from 1 to any other for another row (1 ---> 0,2,3,4) or any other value trying to change to 1 (0,2,3,4 --> 1) from two different sessions will result in session executing in second being blocked and will wait for first session to commit.

Similarly any other row that try to change its column A value to 2 will also block and wait. That is 0,1,3,4 ---> 2 and 2 ---> 0,1,3,4 will block and wait.

To test run the following updates from second session.
-- the other row with 1 on column A will be blocked and wait
--Wait will appear as a enq: TX row lock contention
update y set a = 4 where b = '7WD1OB3O6T'; 

-- row with 0 on column A trying to update to 1 blocked
update y set a = 1 where b = 'EEBV89AYHA';  

--another row with 2 on column A trying to update blocked and wait
update y set a = 3 where b = 'FC9UTGS8RY'; -- (could have used E79SCS1B26 as well) 

-- row with 0 on column A trying to update to 2 blocked and wait
update y set a = 2 where b = 'EEBV89AYHA'; 
Trying to delete any of the other rows with values 1 (B = 7WD1OB3O6T) or 2 (B = E79SCS1B26 or B = FC9UTGS8RY) will also block and wait. But it is it is possible to insert rows with values 1 or 2 for column A.

This is why it is considered bad practice to use bitmap indexes on tables with frequent DML activities.

Rollback the update statement on the first session and execute a insert statement
insert into y values (1,'ABCDEF');
now trying to update or delete any row with value 1 on column A will block and wait.

The above locking will take place as long as low rowid and high rowid of the rows in questions are the same index entry. If updating row's rowids are in two different index entries then the updates and deletes will go through without blocking. Taking the above example if new index entries are created in the bitmap index (represented by rowid range starting with BBBW) as below
A       low rowid           high rowid          bitmap
1,  AAAW4nAAEAAAAJHAAA,  AAAW4nAAEAAAAJHAAJ,  1000010000
2,  AAAW4nAAEAAAAJHAAA,  AAAW4nAAEAAAAJHAAJ,  0100001000
3,  AAAW4nAAEAAAAJHAAA,  AAAW4nAAEAAAAJHAAJ,  0010000100
4,  AAAW4nAAEAAAAJHAAA,  AAAW4nAAEAAAAJHAAJ,  0001000010
0,  AAAW4nAAEAAAAJHAAA,  AAAW4nAAEAAAAJHAAJ,  0000100001
1,  BBBW4nAAEAAAAJHAAA,  BBBW4nAAEAAAAJHAAJ,  1000010000
2,  BBBW4nAAEAAAAJHAAA,  BBBW4nAAEAAAAJHAAJ,  0100001000
3,  BBBW4nAAEAAAAJHAAA,  BBBW4nAAEAAAAJHAAJ,  0010000100
4,  BBBW4nAAEAAAAJHAAA,  BBBW4nAAEAAAAJHAAJ,  0001000010
0,  BBBW4nAAEAAAAJHAAA,  BBBW4nAAEAAAAJHAAJ,  0000100001
then when a row is updated in 1,AAAW4nAAEAAAAJHAAA-AAAW4nAAEAAAAJHAAJ rowid range it is possible to update another row in 1,BBBW4nAAEAAAAJHAAA-BBBW4nAAEAAAAJHAAJ
row id range without being blocked. This could be tested by inserting many more rows to the table which will result in additional index entries being created. Run the following from a different session to the two that is opened
begin
    for i in  1 .. 90000
    loop
    insert into y values(mod(i,5),dbms_random.string('X',10));
   end loop;
    end;
    /
commit;

select DBMS_ROWID.ROWID_OBJECT(rowid) "OBJECT",
           DBMS_ROWID.ROWID_RELATIVE_FNO(rowid) "FILE",
           DBMS_ROWID.ROWID_BLOCK_NUMBER(rowid) "BLOCK",
           DBMS_ROWID.ROWID_ROW_NUMBER(rowid) "ROW", rowid,y.* from y where a = 1 order by 5,6;
     
...
...
   OBJECT       FILE      BLOCK        ROW ROWID                       A B
---------- ---------- ---------- ---------- ------------------ ---------- ----------
     93735          4       5375        356 AAAW4nAAEAAABT/AFk          1 PQCAAA3OI7
     93735          4       5375        361 AAAW4nAAEAAABT/AFp          1 6G20GPXCSL
     93735          4       5375        366 AAAW4nAAEAAABT/AFu          1 XH9BDPW8XL
     93735          4       5375        371 AAAW4nAAEAAABT/AFz          1 WFAI39JSNU
     93735          4       5375        376 AAAW4nAAEAAABT/AF4          1 GXE3899NJE
     93735          4       5375        381 AAAW4nAAEAAABT/AF9          1 X8X0I0PMRB

18002 rows selected.
Running
update y set a = 2 where b  ='GXE3899NJE';
on session 1 and
update y set a = 2 where b  ='X8X0I0PMRB';
on session two will result in session 2 being blocked. It is safe to presume (may not always be the case) those two rowids are in the same range. But
update y set a = 2 where b  ='GXE3899NJE';
and
update y set a = 2 where b  = '1ML8L3NZBE';
will not block each other presuming these rowids are in different index entries.