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