Btree vs Bitmap index (oracle)
In this article,we will look at the difference,advantages and disadvantages of using btree(default) and bitmap index
Btree index has a balanced tree like structure with root,branch and leaf nodes.It is the most commonly used index for performance improvement.The index itself store the rowid and column values in a table.If we want to unleash the full potential of btree index,then all the table rowid and column values which needs to be fetched should be stored in index blocks.There are row pointers which points to the table directly from the leaf blocks in index.Basic btree structure looks something like below figure
BTREE STRUCTURE
Like btree index,bitmap index also has similar structure but stores the column values in the form of binary values with combination of 0 and 1.We can say dummy variables created for the low distinct values making an intersection point. The index key points to multiple rows in a table. The structure of bitmap looks similar to below figure.
The figure shows that we try to select a shirt detail from shirt table where the shirt size is medium and i want shirt colour which should be both red and orange. Here columns red and orange are unique columns in the bitmap index
BITMAP STRUCTURE
CARDINALITY :
Btree – high cardinality (high distinct values)
SQL> select count(distinct order_id) as HIGH_CARDINALITY_COLUMN from sales;
HIGH_CARDINALITY_COLUMN
-----------------------
1048576
SQL> select count(*) from sales;
COUNT(*)
----------
1048576
Bitmap – low cardinality (less number of distinct values)
SQL> select count(distinct order_priority) as LOW_CARDINALITY_COLUMN from sales;
LOW_CARDINALITY_COLUMN
----------------------
4
SQL> select count(*) from sales;
COUNT(*)
----------
1048576
SIZE:
Btree – Consume more space
SQL> select segment_name,bytes/1024/1024 as SIZE_MB from dba_segments where segment_name in ('BTREE_SALES_IT','BTREE_SALES_PRIORI');
SEGMENT_NAME SIZE_MB
---------------------------------------- ----------
BTREE_SALES_IT 25 >---- 25MB
BTREE_SALES_PRIORI 16 >---- 16MB
Bitmap – Consume less space compared to Btree provided there should be less distinct values and if high distinct values are present,then consume more space
SQL> column segment_name format a40
SQL> select segment_name,bytes/1024/1024 as SIZE_MB from dba_segments where segment_name in ('BTM_SALES_IT','BTM_SALES_PRIORI');
SEGMENT_NAME SIZE_MB
---------------------------------------- ----------
BTM_SALES_PRIORI .8125 <----- 0.8MB
BTM_SALES_IT 2 <----- 2MB
INDEX USAGE ON NULL VALUES :
Btree – Null values with indexed columns are not stored in Btree
Oracle ignores the index and goes for full table scan when there is a btree indexed null column
SQL> alter table sales add NULL_COLUMN varchar2(10);
Table altered.
SQL> select count(*),count(NULL_COLUMN) from sales;
COUNT(*) COUNT(NULL_COLUMN)
---------- ------------------
1048576 0
SQL> select /*+index(sales btree)*/ count(*) from sales where null_column='';
Elapsed: 00:00:00.00
Execution Plan
----------------------------------------------------------
Plan hash value: 8150843
-----------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 7 | 0 (0)| |
| 1 | SORT AGGREGATE | | 1 | 7 | | |
|* 2 | FILTER | | | | | |
| 3 | TABLE ACCESS FULL| SALES | 1048K| 7168K| 6482 (6)| 00:00:01 |
-----------------------------------------------------------------------------
Bitmap – Null values with indexed columns are stored in Bitmap
Oracle use bitmap index on null columns as well it doesnot matter
SQL> select /*+index(sales bitmap)*/ count(*) from sales where null_column='';
Elapsed: 00:00:00.01
Execution Plan
----------------------------------------------------------
Plan hash value: 633761674
-----------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 7 | 0 (0)| |
| 1 | SORT AGGREGATE | | 1 | 7 | | |
|* 2 | FILTER | | | | | |
| 3 | BITMAP CONVERSION COUNT | | 1048K| 7168K| 23 (0)| 00:00:01 |
| 4 | BITMAP INDEX FAST FULL SCAN| BITMAP | | | | |
-----------------------------------------------------------------------------------------
SYNTAX :
Btree:
create index index_name on table_name(column_name);
SQL> create index btree_SALES_PRIORI on sales(ORDER_PRIORITY);
Index created.
Elapsed: 00:00:03.23 <------- Observe time taken to create btree index on less distinct column
SQL> create index btree_SALES_IT on sales(ITEM_TYPE);
Index created.
Elapsed: 00:00:05.75 <------- Highly time consuming when btree index created on less distinct columns!! :(
Bitmap:
create bitmap index index_name on table_name(column_name) nologging;
SQL> create bitmap index btm_sales_priori on sales(order_priority) nologging;
Index created.
Elapsed: 00:00:00.71 <---- less time taken to create bitmap in less distinct column :)
SQL> create bitmap index btm_sales_it on sales(item_type) nologging;
Index created.
Elapsed: 00:00:00.49 <--- less time taken to create bitmap in less distinct column :)
PURPOSE :
Btree – used for OLTP specifically for heavy DML transactions like INSERT,UPDATE and DELETE
Bitmap – used for OLAP specifically for STAR SCHEMAS with fact and dimension tables with frequent data retrieval like select queries with AND and OR operator in the where clause
DRAWBACKS:
Btree – Foreign key columns should be indexed which is referenced to a primary key column if not it cause locking issues
You will encounter below wait event with Row Exclusive Table Lock on parent table when there is an unindexed foreign key on a child table ,if the user forget to commit the data in case of btree index
Event waited on Times Max. Wait Total Waited
---------------------------------------- Waited ---------- ------------
enq: TM - contention 1 6.75 6.75
Bitmap – DML operations in bitmap indexed columns cause locking issues
So it is better to make bitmap index invisible or unusable when there is a DML load
creating bitmap index on high cardinality columns will
- impact performance negatively
- increase index size
- index rebuild operation is time consuming
SUPPORTED EDITION:
Btree – default index supported in all editions
Bitmap – Supported in enterprise edition
EXECUTION PLAN:
Btree index on high distinct column: <—- See the time taken to create index ,number of physical IO,cost and size when btree created on high distinct column
SQL> create index btree_sales_id on sales(order_id);
Index created.
Elapsed: 00:00:02.98 <----
SQL> select segment_name,bytes/1024/1024 from dba_segments where segment_name='BTREE_SALES_ID';
SEGMENT_NAME BYTES/1024/1024
---------------------------------------- ---------------
BTREE_SALES_ID 19 <---
SQL> set timing on
SQL> set autot traceonly
SQL> select /*+index(btree_sales_id)*/ country,units_sold,unit_price,unit_cost,total_profit from sales where order_id between 123 and 1234;
1112 rows selected.
Elapsed: 00:00:00.02
Execution Plan
----------------------------------------------------------
Plan hash value: 1484275115
--------------------------------------------------------------------------------
----------------------
| Id | Operation | Name | Rows | Bytes | C
ost (%CPU)| Time |
--------------------------------------------------------------------------------
----------------------
| 0 | SELECT STATEMENT | | 1113 | 48972 |
36 (3)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID BATCHED| SALES | 1113 | 48972 |
36 (3)| 00:00:01 |
|* 2 | INDEX RANGE SCAN | BTREE_SALES_ID | 1113 | |
5 (0)| 00:00:01 |
--------------------------------------------------------------------------------
Statistics
----------------------------------------------------------
1 recursive calls
0 db block gets
179 consistent gets
24 physical reads <----
0 redo size
46477 bytes sent via SQL*Net to client
1309 bytes received via SQL*Net from client
77 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1112 rows processed
Bitmap on high distinct column:<—- See the time taken to create,number of physical IO,cost and size when bitmap created on high distinct column
SQL> create bitmap index btm_sales_id on sales(order_id) nologging;
Index created.
Elapsed: 00:00:09.89 <------
SQL> select segment_name,bytes/1024/1024 from dba_segments where segment_name='BTM_SALES_ID';
SEGMENT_NAME BYTES/1024/1024
---------------------------------------- ---------------
BTM_SALES_ID 30 <-----
SQL> select /*+btm_sales_id*/ country,units_sold,unit_price,unit_cost,total_profit from sales where order_id between 123 and 1234;
1112 rows selected.
Elapsed: 00:00:00.07
Execution Plan
----------------------------------------------------------
Plan hash value: 1651313649
--------------------------------------------------------------------------------
--------------------
| Id | Operation | Name | Rows | Bytes | Cos
t (%CPU)| Time |
--------------------------------------------------------------------------------
--------------------
| 0 | SELECT STATEMENT | | 1113 | 48972 | 2
54 (1)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID BATCHED| SALES | 1113 | 48972 | 2
54 (1)| 00:00:01 |
| 2 | BITMAP CONVERSION TO ROWIDS | | | |
| |
|* 3 | BITMAP INDEX RANGE SCAN | BTM_SALES_ID | | |
| |
--------------------------------------------------------------------------------
Statistics
----------------------------------------------------------
239 recursive calls
0 db block gets
559 consistent gets
87 physical reads <----
0 redo size
46278 bytes sent via SQL*Net to client
1300 bytes received via SQL*Net from client
76 SQL*Net roundtrips to/from client
52 sorts (memory)
0 sorts (disk)
1112 rows processed
Btree:
Use btree index most of the time 99% unless there are specific requirement to use other indexes
Below is an example of highly distinct column
SQL> select count(order_id) from sales group by order_id having count(order_id) = 1 fetch next 10 rows only;
COUNT(ORDER_ID)
---------------
1
1
1
1
1
1
1
1
1
1
10 rows selected.
Bitmap:
Use bitmap index when a column has 1% distinct values from overall column
SQL> select count(order_priority) as ORDER_PRIORITY from sales group by order_priority having count(*) > 1;
ORDER_PRIORITY
--------------
261964
262329
262160
262123
Btree index on a low distinct column:<—- See number of physical IO and cost when btree created on low distinct column
SQL> select /*+index(sales btree_SALES_PRIORI) index(sales btree_SALES_IT)*/ country,ITEM_TYPE,SALES_CHANNEL,ORDER_PRIORITY from sales where item_type='Vegetables' and order_priority='L';
21769 rows selected.
Elapsed: 00:00:00.56
Execution Plan
----------------------------------------------------------
Plan hash value: 329813273
----------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
----------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 21795 | 659K| 12458 (2)| 00:00:01 |
|* 1 | TABLE ACCESS BY INDEX ROWID BATCHED| SALES | 21795 | 659K| 12458 (2)| 00:00:01 |
|* 2 | INDEX RANGE SCAN | BTREE_SALES_PRIORI | 262K| | 519 (8)| 00:00:01 |
------------------------------------------------------------------------------------------------------
Statistics
----------------------------------------------------------
4 recursive calls
0 db block gets
15143 consistent gets
12305 physical reads <-----
0 redo size
705620 bytes sent via SQL*Net to client
16504 bytes received via SQL*Net from client
1453 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
21769 rows processed
Bitmap index on a low distinct column:<—- See effect of number of physical IO and cost when bitmap created on low distinct column
Creating bitmap indexes in multiple columns would enhance the data retrieval with lightning performance!
SQL> select country,ITEM_TYPE,SALES_CHANNEL,ORDER_PRIORITY from sales where item_type='Vegetables' and order_priority='L';
21769 rows selected.
Elapsed: 00:00:00.34
Execution Plan
----------------------------------------------------------
Plan hash value: 948039403
--------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 21845 | 661K| 2743 (1)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID BATCHED| SALES | 21845 | 661K| 2743 (1)| 00:00:01 |
| 2 | BITMAP CONVERSION TO ROWIDS | | | | | |
| 3 | BITMAP AND | | | | | |
|* 4 | BITMAP INDEX SINGLE VALUE | BTM_SALES_IT | | | | |
|* 5 | BITMAP INDEX SINGLE VALUE | BTM_SALES_PRIORI | | | | |
------------------------------------------------------------------------------------------------------
Statistics
----------------------------------------------------------
35 recursive calls
5 db block gets
12123 consistent gets
10022 physical reads <-----
956 redo size
705400 bytes sent via SQL*Net to client
16439 bytes received via SQL*Net from client
1453 SQL*Net roundtrips to/from client
2 sorts (memory)
0 sorts (disk)
21769 rows processed
From this post, it has been practically observed that both btree and bitmap index are very efficient in their own way and solve the purpose! we also learnt the basic differences between both indexes and where to effectively use them