Doc ID: / 70067.1 / Type: / BULLETIN
Modified Date : / 04-JUN-2008 / Status: / PUBLISHED
All about Bitmap Indexes
======
PURPOSE
======
The intention of this document is to give a global overview of bitmap indexes.
SCOPE & APPLICATION
======
The informaton contained in this document is targetted at all analysts and dba's.
RELATED DOCUMENTS
======
Oracle8 Release 7.3.4, 8.0.5, 8.1.5 Reference Guide
Oracle8 Release 7.3.4, 8.0.5, 8.1.5,9.0.1, 9.2, 10.1, 10.2 Concepts Guide
Oracle8 Release 7.3.4, 8.0.5, 8.1.5,9.0.1, 9.2, 10.1, 10.2 Tuning Guide
Note 1043819.6 What Effect Does 'ALTER TABLE' Have on Bitmap Indexes ?
Note 143187.1 ORA-28668 or ORA-28670 Attempting to Drop Mapping Table from IOT
Note 143185.1 ORA-28669 Attempting to Create Bitmap Index on an IOT
Note 149521.1 Bitmap Join Index to Avoid Join Operation Between n Tables
BITMAP INDEXES
======
1) Creation
2) Bitmapped Index Structure
3) When to use bitmapped Indexes
4) Restrictions
5) Advantages over B*tree indexes
6) Usage Tips
7) Bitmap Index Example
8) Bitmap Indexes and Nulls
9) Tables & Views
10) Source labels in execution plans
11) Hints usuable with bitmap indexes
12) Initialisation Parameters
1) Creation
------
CREATE BITMAP INDEX index_name ON normal_index_creation_clause;
Oracle creates a series of bitmaps, each one for a particular value of the
columns involved. For example, if the bitmapped index is created for a
column that has the values 'East' and 'Central', then a bitmap would
be built for 'EAST' and another for 'CENTRAL'.
If the index involved more than one column, then there would be a bitmap
for every possible combination.
2) Bitmapped Index Structure
------
A regular B*tree index pairs the ROWID for a row with its key value, then
sorts those pairs into a B*tree structure. The ROWID serves as a pointer to
a row that has that value. A bitmapped index has a very different structure:
the ROWIDS are not stored directly: each different key value has its own
bitmap. (This is why they should only be used when there are few distinct
values in the bitmap indexed column(s)).
Each position in the bitmap maps to a possible ROWID. The contents of that
position in the bitmap for a particular value indicates whether that row
has that value in the bitmapped columns. Thus, each position in a bitmap
stores information about a particular row and thus ROWID. The value stored in
a particular rowid's position is a "1" if the ROWID's values match the
condition and "0" otherwise. Oracle is also able to compress bitmap storage.
3) When to use bitmapped Indexes
------
- The column has a low cardinality: few distinct value
- Bitmapped indexes are especially helpful for complex ad hoc queries with
lengthy WHERE clauses or aggregate queries (containing SUM, COUNT, or other
aggregate functions)
- The table has many rows (1.000.000 rows with 10.000 distinct values is
possibly acceptable)
- There are frequent, possibly ad hoc, queries on the table
- The environment is data warehouse-oriented (DSS system). Bitmap indexes are
not ideal for online transaction processing (OLTP) environments because of
their locking behavior. It is not possible to lock a single bitmap position.
The smallest amount of a bitmap that can be locked is a bitmap segment, which
can be up to half a data block in size. Changing the value of a row results in
a bitmap segment becoming locked, in effect blocking changes on a number of rows.
This is a serious disadvantage when there are many UPDATE, INSERT or DELETE
statements being issued by users. It is not a problem when data is loaded or
updated in bulk actions, as in data warehouse systems.
- Bitmap Join Indexes are a new method in 9.0 by which joins can be avoided by
precreating a bitmap index on the join criteria.
The BJI is a space efficient way of reducing the volume of data selected.
The data that would result from the join operation and restrictions are
permanently stored in a BJI. The join condition is an equi-inner join between
the primary key column/columns of the dimension tables and the foreign key
column/columns in the fact table.
4) Restrictions
------
- Bitmap indexes are not supported for Trusted Oracle.
- Not used by the rule-based optimizer.
- Cannot be used on a partitioned table as a global index.
- No online build/rebuild support for bitmap indexes
- For bitmap indexes with direct load, the "SORTED_INDEX" flag does not apply
- Bitmap indexes cannot be used for referential integrity checking
- A bitmap index cannot be declared as UNIQUE.
- Until 9i, you cannot specify BITMAP when creating an index-organized table.
Oracle9i supports bitmap indexes on index-organized tables: a mapping table is
required for creating bitmap indexes on an IOT.
- You cannot specify BITMAP for a domain index.
5) Advantages over B*tree indexes
------
- Reduced response time for many ad hoc queries
- Substantial reduction of space usage, compared to regular B*tree indexes
a) on a single column with few distinct values:
If a bitmap index is created on a unique key column, it requires more
space than a regular B*-tree index. However, for columns where each
value is repeated hundreds or thousands of times, a bitmap index
typically is less than 25% of the size of a regular B*-tree index.
The bitmaps themselves are stored in compressed format.
(graphics of samples available in Oracle8 Tuning Guide)
b) if multiple columns have to be indexed:
Bitmap indexes can provide considerable storage savings over the use
of multicolumn (or concatenated) B*-tree indexes. In databases
containing only B*-tree indexes, you must anticipate the columns that
would commonly be accessed together in a single query, and create a
composite B*-tree index on these columns.
Not only would this B*-tree index require a large amount of space, but
it would also be ordered. That is, a B*-tree index on (MARITAL_STATUS,
REGION, GENDER) is useless for queries that only access REGION
and GENDER. To completely index the database, you must create
indexes on the other permutations of these columns. For the simple
case of three low-cardinality columns, there are six possible composite
B*-tree indexes. You must consider the trade-offs between disk space
and performance needs when determining which composite B*-tree
indexes to create. Bitmap indexes solve this dilemma. Bitmap indexes
can be efficiently combined during query execution, so three small
single-column bitmap indexes can do the job of six three-column B*-
tree indexes.
- Very efficient parallel DML and loads:
Bitmap indexes benefit data warehousing applications but they are not
appropriate for OLTP applications with a heavy load of concurrent
INSERTs, UPDATEs, and DELETEs. In a data warehousing
environment, data is usually maintained by way of bulk inserts and
updates. Index maintenance is deferred until the end of each DML
operation. For example, if you insert 1000 rows, the inserted rows are
placed into a sort buffer and then the updates of all 1000 index
entries are batched. (This is why SORT_AREA_SIZE must be set properly
for good performance with inserts and updates on bitmap indexes.) Thus,
each bitmap segment is updated only once per DML operation, even if
more than one row in that segment changes.
- Include rows with null value (see Bitmap Indexes and Nulls)
6) Usage Tips
------
- Declaring NOT NULL constraints on all possible columns will reduce storage
requirements because there will not have to be a bitmap for the NULL
values
- Using fixed length datatypes will reduce storage requirements
- Increasing the CREATE_BITMAP_AREA_SIZE initialization parameter can
speed query processing.
This parameter determines the amount of memory allocated for bitmap
creation. The default value is 8 MB. A larger value can result in
larger, continuous bitmaps and thus faster query processing
- Increasing the "BITMAP_MERGE_AREA_SIZE" initialization parameter will
speed range scans of the index. This parameter determines the amount
of memory used to merge bitmaps retrieved from a range scan of the
index. The default value is 1 MB.
7) Bitmap Index Example
------
A company's customer data.
MARITAL_ STATUS REGIONGENDERINCOME_LEVEL
------
101singleeastmalebracket_1
102marriedcentralfemalebracket_4
103marriedwestfemalebracket_2
104divorcedwestmalebracket_4
105singlecentralfemalebracket_2
106marriedcentralfemalebracket_3
Since MARITAL_STATUS, REGION, GENDER, and INCOME_LEVEL are all low-cardinality
columns (there are only three possible values for marital status and region, two
possible values for gender, and four for income level) it is appropriate to
create bitmap indexes on these columns. A bitmap index should not be created on
CUSTOMER# because this is a high-cardinality column.
Instead, a unique B*-tree index on this column in order would provide the most
efficient representation and retrieval.
The bitmap index for the REGION column in this example.
It consists of three separate bitmaps, one for each region.
REGION='east' REGION='central' REGION='west' ##CUSTOMER #
100 <==101
010 <==102
001 <==103
001 <==104
010 <==105
010 <== 106
Each entry (or "bit") in the bitmap corresponds to a single row of the CUSTOMER
table. The value of each bit depends upon the values of the corresponding row
in the table. For instance, the bitmap REGION='east' contains a one as its
first bit. This is because the region is "east" in the first row of the
CUSTOMER table. The bitmap REGION='east' has a zero for its other bits because
none of the other rows of the table contain "east" as their value for REGION.
An analyst investigating demographic trends of the company's customers might
ask, "How many of our married customers live in the central or west regions?"
This corresponds to the following SQL query:
SELECT COUNT(*) FROM CUSTOMER
WHERE MARITAL_STATUS = 'married' AND REGION IN ('central','west');
Bitmap indexes can process this query with great efficiency by merely counting
the number of ones in the resulting bitmap, as illustrated . To identify the
specific customers who satisfy the criteria, the resulting bitmap would be
used to access the table.
status = 'married'region = 'central'region = 'west'
000
110
101
0AND (0OR 1)
010
110
000
111 ==> 2nd row
=111 ==> 3rd row
0AND 1=0
010
111 ==> last row
8) Bitmap Indexes and Nulls
------
Bitmap indexes include rows that have NULL values, quite unlike most other
types of indexes. Indexing of nulls can be useful for some types of SQL
statements, such as queries with the aggregate function COUNT.
Example 1:
------
SELECT COUNT(*) FROM EMP;
Any bitmap index can be used for this query because all table rows are indexed,
including those that have NULL data. If nulls were not indexed, the optimizer
would only be able to use indexes on columns with NOT NULL constraints.
Example 2:
------
SELECT COUNT(*) FROM EMP WHERE COMM IS NULL;
This query can be optimized with a bitmap index on COMM.
Example 3:
------
SELECT COUNT(*) FROM CUSTOMER WHERE GENDER = 'M' AND STATE != 'CA';
This query can be answered by finding the bitmap for GENDER = 'M' and
subtracting the bitmap for STATE = 'CA'. If STATE may contain null values
(that is, if it does not have a NOT NULL constraint), then the bitmaps for
STATE = 'NULL' must also be subtracted from the result.
9) Tables & Views
------
Views USER_INDEXES, ALL_INDEXES, and DBA_INDEXES indicate bitmap indexes by the
value BITMAP appearing in the TYPE column.
10) Source labels in execution plans
------
Oracle8 Tuning Release 8.0
Oracle8i Tuning Release 8.1.5
Oracle9i Database Performance Tuning Guide and Reference Release 1 (9.0.1)
Oracle9i Database Performance Tuning Guide and Reference Release 2 (9.2)
Oracle Database Performance Tuning Guide and Reference 10gRelease 1 (10.1)
Oracle Database Performance Tuning Guide and Reference 10gRelease 2 (10.2)
Chapter Using EXPLAIN PLAN
11) Hints usuable with bitmap indexes (7.3 - 8.0 - 8.1 - 9.0 - 9.2 - 10.1 - 10.2)
------
INDEX
INDEX_COMBINE
12) Initialisation Parameters
------
<Parameter:CREATE_BITMAP_AREA_SIZE>
<Parameter:BITMAP_MERGE_AREA_SIZE>
<Parameter:B_TREE_BITMAP_PLANS>
<Parameter:V733_PLANS_ENABLED>