| Lesson 2 | Bitmapped Indexes |
| Objective | Describe B-tree and Bitmapped Indexes. |
Describe B-tree and Bitmapped Indexes
For high cardinality data or data with many possible values, B-tree indexes are most effective.
B-tree indexes are most effective for high cardinality data, or data with many possible values. A common problem with traditional B-tree indexes occurs when an indexed column has low cardinality, which means it has too few distinct values to speed query access.
For example, an index of a REGION column that has only 4 values (North, South, East, West) does not have enough distinct values to speed access for queries. It is an index column with relatively few distinct values, compared to the number of rows in the table, and is referred to as a low cardinality column.
Oracle's answer to the problem of low cardinality is the bitmapped index.
B-tree indexes are most effective for high cardinality data, or data with many possible values. A common problem with traditional B-tree indexes occurs when an indexed column has low cardinality, which means it has too few distinct values to speed query access.
For example, an index of a REGION column that has only 4 values (North, South, East, West) does not have enough distinct values to speed access for queries. It is an index column with relatively few distinct values, compared to the number of rows in the table, and is referred to as a low cardinality column.
Oracle's answer to the problem of low cardinality is the bitmapped index.
Bitmapped indexes
We know that the purpose of an index is to provide pointers to the rows in a table that contain a given key value. In a bitmap index, a bitmap for each key value is used instead of a list of ROWIDs.
Each bit in the bitmap corresponds to a possible ROWID. If the bit is set, the row with the matching ROWID includes the key value. A mapping function converts the bit position to an actual ROWID, so the bitmap index functions as a regular index although it has a different internal structure. If the number of different key values is small, bitmap indexes are very space-efficient.
Each bit in the bitmap corresponds to a possible ROWID. If the bit is set, the row with the matching ROWID includes the key value. A mapping function converts the bit position to an actual ROWID, so the bitmap index functions as a regular index although it has a different internal structure. If the number of different key values is small, bitmap indexes are very space-efficient.
Oracle Bitmap
Speeding queries using bitmapped indexes
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.
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.
4)Oracle then sorts these two lists of ROWID's and returns rows where the ROW ID appears in both ROWID lists.
Bitmapped Indexes To Speed Queries
Advantages of using bitmapped indexes
| Minimal Storage Requirements | In contrast to B-tree index, a bitmapped index has minimal storage requirements |
| Improved response time | In 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.
Oracle bitmap Response
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:
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.
- Index columns have few distinct values (less than 20)
- The SQL has several predicates involving bitmap indexes in the WHERE clause
- 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
Bitmapped Indexes - Exercise
