Thursday, January 2, 2014

Indexes in Oracle Database - Part 3

This is Part 3 in 3 part series. Read Part 1, Part 2 here.


Record locking; b-tree index versus bitmap index

In Oracle database there is no centralized mechanism for record locking, instead the locks are maintained as an attribute of the data. When a transaction wants to lock a particular row, it goes to the data block where the data is, and locks the row by storing the transaction related information along with the row.  Given below is the block dump for a b-tree index leaf node.



row#0[4521] flag: -----, lock: 0

col 0; len 3500; (3500):  34 34 34 34 34 34 34 34 34

col 1; len 6; (6):  03 c0 0a 92 00 00
row#1[1010] flag: -----, lock: 0
col 0; len 3500; (3500):  35 35 35 35 35 35 35 35 35
col 1; len 6; (6):  03 c0 0a 92 00 01
----- end of leaf block dump -----


The dump shows 2 leaf node entries where the index key (col 0 in the block dump) is stored together with the rowid (col 1 in the block dump).  Apart from the index key and rowid, Oracle also stores certain other information for each row and this includes the locking information. In case of b-tree index, since Oracle maintains one entry for each row in the leaf nodes, locking information is also maintained on per row basis. Because of this reason, for b-tree indexes the row locking can be at individual row level. In case of Bitmap indexes since Oracle stores the index keys as a bitmap for a range of rowid, locking information is not really available at individual row level. Shown below is a data block dump for a leaf node of a bitmap index.  There are three entries here in this block dump row#0, row#1 and row#2 each for rowids as represented by col 1 and col 2. col 0 is the index key and col 3, the bitmap in the data block dump.


row#0[8003] flag: -----, lock: 0

col 0; len 1; (1):  30 30 30 30 30 30 30 30

col 1; len 6; (6):  03 c0 0a 8e 00 00
col 2; len 6; (6):  03 c0 0a 93 00 07
col 3; len 10; (10):  00 c0 a1 01 c0 44 c0 44 c0 44
row#1[7976] flag: -----, lock: 2
col 0; len 1; (1):  31 31 31 31 31 31 31 31
col 1; len 6; (6):  03 c0 0a 8e 00 00
col 2; len 6; (6):  03 c0 0a 93 00 07
col 3; len 8; (8):  01 c1 fe 01 c1 44 c1 44
row#2[7956] flag: -----, lock: 2
col 0; len 1; (1):  32 32 32 32 32 32 32 32
col 1; len 6; (6):  03 c0 0a 90 00 00
col 2; len 6; (6):  03 c0 0a 90 00 07
col 3; len 1; (1):  01
----- end of leaf block dump -----


In case of bitmap indexes also, locking information is maintained for each entry in the leaf node. What makes it different form b-tree an index is that in b-tree index each entry (or row) in the index leaf node represents only one row (couple of rows in case of non unique indexes); where as in case of bitmap index each entry in the leaf node represents a large number of rows. So when the user modifies one of the records in the rowid range in the bitmap index, Oracle is forced to lock the entire range of rows as the lock information is maintained for the range of rows.


The block dump shown above is for a table having 10 rows and row#0 in the bitmap index covers all the records in the table, row#1 covers 8 records and row#2 covers one record. In this case if the user updates a record for which the bitmap is stored in row#1, all the rows in the rowid range mentioned in row#1 gets locked and hence in this particular case since the rowid range stored in the bitmap index is overlapping almost the entire table gets locked.

B-tree index versus Bitmap index; which one to use and when?


B-tree indexes are well suited for online transaction processing (OLTP) systems where the same set of queries are run repeatedly and the queries well tuned before deploying into production phase. Also efficient index management functions available for b-tree indexes make it a preferable choice in OLTP environments where the data is modified (insert/update/delete) very frequently.
Bitmap indexes are well suited for data warehousing environments where the data is not modified frequently and queries are mostly ad-hoc in nature. Bitmap indexes can help Oracle to efficiently answer queries that include AND, OR or XOR operations exploiting the hardware supported bit level operations. When used in environments where the data is frequently modified, bitmap indexes can cause serious troubles due to fact that update operations on bitmap indexes are very expensive and such operations on tables with bitmap indexes may lock a large number of rows in the table depending on the cardinality of the column.



A finely tuned Oracle database is key to many of the applications running around the world supporting critical business operations and any performance issues with the database can break the whole purpose of the application adversely affecting the business operations. Oracle supports various types of data structures to speed up the data retrieval from the database and indexes, which are optional structures associated with database tables are one among them.  Oracle supports different types of indexes suited for different types of environments and understanding the way Oracle maintains the indexes can help selecting the right type of index for a given environment which can give optimal database performance.


References



  1. Index Internals by Julian Dyke
  2. B-Trees
  3. Bitmap Index Internals by Julian Dyke
  4. Bitmap Index Design and Evaluation by Chee-Yong Chan and Yannis E. Ioannidis.
  5. Bitmap Index vs. B-tree Index: Which and When? by Vivek Sharma