Oracle Bitmap Index Concepts

Bitmap indexes are widely used in data warehousing environments. The environments typically have large amounts of data and ad hoc queries, but a low level of concurrent DML transactions. For such applications, bitmap indexing provides:

Fully indexing a large table with a traditional B-tree index can be prohibitively expensive in terms of space because the indexes can be several times larger than the data in the table. Bitmap indexes are typically only a fraction of the size of the indexed data in the table.

An index provides pointers to the rows in a table that contain a given key value. A regular index stores a list of rowids for each key corresponding to the rows with that key value. In a bitmap index, a bitmap for each key value replaces a list of rowids.

Oracle bitmap indexes are very different from standard b-tree indexes. In bitmap structures, a two-dimensional array is created with one column for every row in the table being indexed. Each column represents a distinct value within the bitmapped index. This two-dimensional array represents each value within the index multiplied by the number of rows in the table.

Each bit in the bitmap corresponds to a possible rowid, and if the bit is set, it means that the row with the corresponding rowid contains the key value. A mapping function converts the bit position to an actual rowid, so that the bitmap index provides the same functionality as a regular index. If the number of different key values is small, bitmap indexes save space.

At row retrieval time, Oracle decompresses the bitmap into the RAM data buffers so it can be rapidly scanned for matching values. These matching values are delivered to Oracle in the form of a Row-ID list, and these Row-ID values may directly access the required information.

The real benefit of bitmapped indexing occurs when one table includes multiple bitmapped indexes. Each individual column may have low cardinality. The creation of multiple bitmapped indexes provides a very powerful method for rapidly answering difficult SQL queries.

A bitmap merge operation build ROWID lists

Using this bitmap merge methodology, Oracle can provide sub-second response time when working against multiple low-cardinality columns.

For example, assume there is a motor vehicle database with numerous low-cardinality columns such as car_color, car_make, car_model, and car_year. Each column contains less than 100 distinct values by themselves, and a b-tree index would be fairly useless in a database of 20 million vehicles.

However, combining these indexes together in a query can provide blistering response times a lot faster than the traditional method of reading each one of the 20 million rows in the base table. For example, assume we wanted to find old blue Toyota Corollas manufactured in 1981:

select

   license_plat_nbr

from

   vehicle

where

   color = ?blue?

and

   make = ?toyota?

and

   year = 1981;

Oracle uses a specialized optimizer method called a bitmapped index merge to service this query. In a bitmapped index merge, each Row-ID, or RID, list is built independently by using the bitmaps, and a special merge routine is used in order to compare the RID lists and find the intersecting values.

As the number if distinct values increases, the size of the bitmap increases exponentially, such that an index with 100 values may perform thousands of times faster than a bitmap index on 1,000 distinct column values. 

Also, remember that bitmap indexes are only suitable for static tables and materialized views which are updated at nigh and rebuilt after batch row loading.  If your tables are not read-only during query time, DO NOT consider using bitmap indexes!

1 - 7 distinct key values - Queries against bitmap indexes with a low cardinality are very fast.

8-100 distinct key values - As the number if distinct values increases, performance decreases proportionally.

100 - 10,000 distinct key values - Over 100 distinct values, the bitmap indexes become huge and SQL performance drops off rapidly.

Over 10,000 distinct key values - At this point, performance is ten times slower than an index with only 100 distinct values.

Cardinality

The advantages of using bitmap indexes are greatest for columns in which the ratio of the number of distinct values to the number of rows in the table is under 1%. We refer to this ratio as the degree of cardinality. A gender column, which has only two distinct values (male and female), is ideal for a bitmap index. However, data warehouse administrators also build bitmap indexes on columns with higher cardinalities.

For example, on a table with one million rows, a column with 10,000 distinct values is a candidate for a bitmap index. A bitmap index on this column can outperform a B-tree index, particularly when this column is often queried in conjunction with other indexed columns. In fact, in a typical data warehouse environments, a bitmap index can be considered for any non-unique column.

B-tree indexes are most effective for high-cardinality data: that is, for data with many possible values, such as customer_name or phone_number. In a data warehouse, B-tree indexes should be used only for unique columns or other columns with very high cardinalities (that is, columns that are almost unique). The majority of indexes in a data warehouse should be bitmap indexes.

In ad hoc queries and similar situations, bitmap indexes can dramatically improve query performance. AND and OR conditions in the WHERE clause of a query can be resolved quickly by performing the corresponding Boolean operations directly on the bitmaps before converting the resulting bitmap to rowids. If the resulting number of rows is small, the query can be answered quickly without resorting to a full table scan.

Example 6-1 Bitmap Index

The following shows a portion of a company's customers table.

SELECT cust_id, cust_gender, cust_marital_status, cust_income_level
FROM customers;

CUST_ID    C CUST_MARITAL_STATUS  CUST_INCOME_LEVEL
---------- - -------------------- ---------------------
... 
        70 F                      D: 70,000 - 89,999
        80 F married              H: 150,000 - 169,999
        90 M single               H: 150,000 - 169,999
       100 F                      I: 170,000 - 189,999
       110 F married              C: 50,000 - 69,999
       120 M single               F: 110,000 - 129,999
       130 M                      J: 190,000 - 249,999
       140 M married              G: 130,000 - 149,999
...

Because cust_gender, cust_marital_status, and cust_income_level are all low-cardinality columns (there are only three possible values for marital status and region, two possible values for gender, and 12 for income level), bitmap indexes are ideal for these columns. Do not create a bitmap index on cust_id because this is a unique column. Instead, a unique B-tree index on this column provides the most efficient representation and retrieval.

Bitmap Join Indexes

In addition to a bitmap index on a single table, you can create a bitmap join index, which is a bitmap index for the join of two or more tables. A bitmap join index is a space efficient way of reducing the volume of data that must be joined by performing restrictions in advance. For each value in a column of a table, a bitmap join index stores the rowids of corresponding rows in one or more other tables. In a data warehousing environment, the join condition is an equi-inner join between the primary key column or columns of the dimension tables and the foreign key column or columns in the fact table.

Bitmap join indexes are much more efficient in storage than materialized join views, an alternative for materializing joins in advance. This is because the materialized join views do not compress the rowids of the fact tables.

Example 6-3 Bitmap Join Index: Example 1

Creating a bitmap join index with the following sales table:

SELECT time_id, cust_id, amount FROM sales;

TIME_ID   CUST_ID    AMOUNT
--------- ---------- ----------
01-JAN-98      29700       2291
01-JAN-98       3380        114
01-JAN-98      67830        553
01-JAN-98     179330          0
01-JAN-98     127520        195
01-JAN-98      33030        280
...

CREATE BITMAP INDEX sales_cust_gender_bjix
ON sales(customers.cust_gender)
FROM sales, customers
WHERE sales.cust_id = customers.cust_id
LOCAL;

The following query shows how to use this bitmap join index and illustrates its bitmap pattern:
SELECT sales.time_id, customers.cust_gender, sales.amount
FROM sales, customers
WHERE sales.cust_id = customers.cust_id;

TIME_ID   C AMOUNT
--------- - ----------
01-JAN-98 M       2291
01-JAN-98 F        114
01-JAN-98 M        553
01-JAN-98 M          0
01-JAN-98 M        195
01-JAN-98 M        280
01-JAN-98 M         32

Example 6-4 Bitmap Join Index: Example 2
You can create a bitmap join index on more than one column, as in the following example, which uses customers(gender, marital_status):
CREATE BITMAP INDEX sales_cust_gender_ms_bjix
ON sales(customers.cust_gender, customers.cust_marital_status)
FROM sales, customers
WHERE sales.cust_id = customers.cust_id
LOCAL NOLOGGING;
Example 6-5 Bitmap Join Index: Example 3

You can create a bitmap join index on more than one table, as in the following, which uses customers(gender) and products(category):
CREATE BITMAP INDEX sales_c_gender_p_cat_bjix
ON sales(customers.cust_gender, products.prod_category)
FROM sales, customers, products
WHERE sales.cust_id = customers.cust_id
AND sales.prod_id = products.prod_id
LOCAL NOLOGGING;

Example 6-6 Bitmap Join Index: Example 4

You can create a bitmap join index on more than one table, in which the indexed column is joined to the indexed table by using another table. For example, we can build an index on countries.country_name, even though the countries table is not joined directly to the sales table. Instead, the countries table is joined to the customers table, which is joined to the sales table. This type of schema is commonly called a snowflake schema.
CREATE BITMAP INDEX sales_c_gender_p_cat_bjix
ON sales(customers.cust_gender, products.prod_category)
FROM sales, customers, products
WHERE sales.cust_id = customers.cust_id
AND sales.prod_id = products.prod_id
LOCAL NOLOGGING;


Bitmap Join Index Restrictions

Join results must be stored, therefore, bitmap join indexes have the following restrictions:




Parallel DML is currently only supported on the fact table. Parallel DML on one of the participating dimension tables will mark the index as unusable.
Only one table can be updated concurrently by different transactions when using the bitmap join index.
No table can appear twice in the join.
You cannot create a bitmap join index on an index-organized table or a temporary table.
The columns in the index must all be columns of the dimension tables.
The dimension table join columns must be either primary key columns or have unique constraints.
If a dimension table has composite primary key, each column in the primary key must be part of the join.



You will want a bitmap index when:
 Bitmap indexes are primarily intended for data warehousing applications where users query the data rather than update it. They are not suitable for OLTP applications with large numbers of concurrent transactions modifying the data.

1 - Table column is low cardinality - As a ROUGH guide, consider a bitmap for any index with less than 100 distinct values

    select region, count(*) from sales group by region;

2 - The table has LOW DML - You must have low insert./update/delete activity.  Updating bitmapped indexes take a lot of resources, and bitmapped indexes are best for largely read-only tables and tables that are batch updated nightly.

3 - Multiple columns - Your SQL queries reference multiple, low cardinality values in there where clause.  Oracle cost-based SQL optimizer (CBO) will scream when you have bitmap indexes on . 

Restrictions on Bitmap Indexes 

Bitmap indexes are subject to the following restrictions:

• You cannot specify BITMAP when creating a global partitioned index.
• You cannot create a bitmap secondary index on an index-organized table unless the index-organized table has a mapping table associated with it.
• You cannot specify both UNIQUE and BITMAP.
• You cannot specify BITMAP for a domain index.

Troubleshooting Oracle bitmap indexes:

Some of the most common problems when implementing bitmap indexes include:

1. Small table - The CBO may force a full-table scan if your table is small!

2. Bad stats - Make sure you always analyze the bitmap with dbms_stats right after creation:

CREATE BITMAP INDEX
emp_bitmap_idx
ON index_demo (gender);

exec dbms_stats.gather_index_stats(OWNNAME=>'SCOTT', INDNAME=>'EMP_BITMAP_IDX');

  3. Test with a hint - To force the use of your new bitmap index, just use a Oracle INDEX hint:

select /*+ index(emp emp_bitmap_idx) */
   count(*)
from
   emp, dept
where
   emp.deptno = dept.deptno;