Index Techniques   «Prev  Next»
Lesson 3Speeding Bitmapped Indexes
ObjectiveHow to increase Speedx

How to use bitmapped Indexes to speed up Queries

Bitmap indexes are a powerful feature in Oracle databases that significantly enhance the speed of SQL queries, especially when dealing with low-cardinality columns, those that have few unique values relative to the number of rows that contain them. They are highly efficient in scenarios where the cardinality of a column is less than 1% of the number of rows in the table. Bitmap indexes are used in Data Warehousing environments where ad hoc queries, often complex, are common and the data is primarily read-only. Here is an in-depth explanation of how bitmap indexes boost query performance:
  1. Storage Efficiency: Bitmap indexes store rowids associated with each distinct column value as a set of bits (1s and 0s), not as physical or logical rowids as in the case of B-tree indexes. This makes bitmap indexes much smaller and more space-efficient than their B-tree counterparts. The reduced size helps decrease I/O operations and increase buffer cache hit ratios, leading to faster query responses.
  2. Bitwise Operations: Bitmap indexes take advantage of bitwise operations (AND, OR, XOR) for query processing. For instance, when a SQL query includes conditions on multiple bitmap indexed columns combined with logical operators (like AND or OR), Oracle can rapidly perform these operations on the corresponding bitmaps to get the result set. Bitwise operations are extremely fast, even on large bitmaps, accelerating query performance.
  3. Star Schema Queries: Bitmap indexes are especially efficient for star schema queries, a common structure in data warehousing environments. When joining a large fact table to one or more smaller dimension tables, bitmap indexes can leverage a technique called bitmap star transformation. This process converts the join into a set of bitmap operations, yielding a considerable speedup compared to traditional join operations.
  4. Bitmap Join Indexes: Bitmap join indexes, a specific type of bitmap index, pre-join a large table to a smaller one, storing the result as a bitmap index on the larger table. When a query includes a join between these tables, Oracle can use the bitmap join index instead of performing the join operation, significantly speeding up the query.
  5. Bitmap Conversion to Rowids: In certain scenarios, Oracle uses a feature called Bitmap Conversion to Rowids (BCR). BCR transforms the bitmap index into actual rowids during the execution of the query. It's beneficial for mixed workloads where you have both OLTP and decision support within the same application, adding to the flexibility of query optimization.
  6. Parallel Execution: Bitmap indexes are inherently suitable for parallel query execution. The bitmaps for different values are independent and can be operated on in parallel, thus further increasing the performance on multi-core, multi-CPU systems.

In conclusion, bitmap indexes provide a range of benefits in the context of Oracle SQL tuning, particularly for data warehousing and reporting applications. However, they are not a one-size-fits-all solution. They can significantly slow down transactional workloads with frequent updates due to the need to lock the entire bitmap for a particular value during updates, which can lead to concurrency issues. Therefore, understanding the workload type and data characteristics is essential to leverage bitmap indexes effectively.
Let us examine how Oracle can speed queries using bitmapped indexes.
1) The query specifies two low cardinality columns in the WHERE clause, region and type.
1) The query specifies two low cardinality columns in the WHERE clause, region and type. 
SELECT customer_name
FROM CUSTOMER WHERE 
region = 'East'
AND 
type = 'Partnership'

2) Oracle scans the region bitmap, quickly building a list of ROWID's for all rows in the East region.
2) Oracle scans the region bitmap, quickly building a list of ROWID's for all rows in the East region.

3) Oracle scans the type bitmapped index and quickly builds a list of ROWID'S for all Partnerships.
3) Oracle scans the type bitmapped index and quickly builds a list of ROWID'S for all Partnerships.

4) Oracle then sorts these two lists of ROWID's and returns rows where the ROW ID appears in both ROWID lists.
4) Oracle then sorts these two lists of ROWID's and returns rows where the ROW ID appears in both ROWID lists.


Advantages of using bitmapped indexes

Minimal Storage RequirementsIn contrast to B-tree index, a bitmapped index has minimal storage requirements
Improved response timeIn certain situations, a bitmapped index dramatically improves the response time

This is often the case where there are indexes that correspond to several conditions in a WHERE clause. A bitmap index efficiently merges these indexes, and this often dramatically improves the response time.

Improved response time for a Bitmap Scan

As shown below, access is much faster than a full-table scan or a B-tree index scan.
Because rows which satisfy some ( but not all) conditions are filtered out before the table itself is accessed.
a) Because rows which satisfy some ( but not all) conditions are filtered out before the table itself is accessed.

access is much faster than a full-table scan or a B-tree index scan. For large tables it is often hundreds of times faster than traditional indexing methods.
b) access is much faster than a full-table scan or a B-tree index scan. For large tables it is often hundreds of times faster than traditional indexing methods.

Oracle Index Bitmap Response

Because rows which satisfy some ( but not all) conditions are filtered out before the table itself is accessed.
1) Because rows which satisfy some conditions are filtered out, before the table itself is accessed.

Access is much faster than a full-table scan or a B-tree index scan. For large tables it is often hundreds of times faster than traditional indexing methods.
2) Access is much faster than a full-table scan or a B-tree index scan. For large tables it is often hundreds of times faster than traditional indexing methods.

About Using Bitmap Indexes in Data Warehouses

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:
  1. Reduced response time for large classes of ad hoc queries.
  2. Reduced storage requirements compared to other indexing techniques.
  3. Dramatic performance gains even on hardware with a relatively small number of CPUs or a small amount of memory.
Fully indexing a large table with a traditional B-tree index can be prohibitively expensive in terms of disk 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. 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. Bitmap indexes store the bitmaps in a compressed way. If the number of distinct key values is small, bitmap indexes compress better and the space saving benefit compared to a B-tree index becomes even better.
Bitmap indexes are most effective for queries that contain multiple conditions in the WHERE clause. Rows that satisfy some, but not all, conditions are filtered out before the table itself is accessed. This improves response time, often dramatically. If you are unsure of which indexes to create, the SQL Access Advisor can generate recommendations on what to create. As the bitmaps from bitmap indexes can be combined quickly, it is usually best to use single-column bitmap indexes. When creating bitmap indexes, you should use NOLOGGING and COMPUTE STATISTICS. In addition, you should keep in mind that bitmap indexes are usually easier to destroy and re-create than to maintain.

When to use a Bitmapped Index

In spite of the advantages they offer, bitmapped indexes are not applicable to every query. They are most useful when the following conditions are true:
  1. Index columns have few distinct values (less than 20)
  2. The SQL has several predicates involving bitmap indexes in the WHERE clause
  3. The SQL select statement is INDEX ONLY, meaning that reading the index without reading the table will satisfy the query.

In summary, bitmap indexes provide excellent performance, while using less storage. Because of their different performance characteristics, you should create bitmap indexes on low cardinality data, and keep B*tree indexes on high-cardinality data.
The next lesson discusses STAR index queries.

Bitmapped Indexes - Exercise

Before you continue, click the Exercise link below to complete an exercise on how to create a set of index definitions.
Bitmapped Indexes - Exercise

SEMrush Software