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
- Index Internals by Julian Dyke
- B-Trees
- Bitmap Index Internals by Julian Dyke
- Bitmap Index Design and Evaluation by Chee-Yong Chan and Yannis E. Ioannidis.
- Bitmap Index vs. B-tree Index: Which and When? by Vivek Sharma
