In a bitmap index, the database stores a bitmap for each index key. In a conventional B-tree index, one index entry points to a single row. In a bitmap index, each index key stores pointers to multiple rows.
Bitmap indexes are primarily designed for data warehousing or environments in which queries reference many columns in an ad hoc fashion. Situations that may call for a bitmap index include:
For a data warehouse example, the sh.customers table has a cust_gender column with only two possible values: M and F. Suppose that queries for the number of customers of a particular gender are common. In this case, the customers.cust_gender column would be a candidate for a bitmap index.
Each bit in the bitmap corresponds to a possible rowid. If the bit is set, then the row with the corresponding rowid contains the key value. A mapping function converts the bit position to an actual rowid, so the bitmap index provides the same functionality as a B-tree index although it uses a different internal representation.
If the indexed column in a single row is updated, then the database locks the index key entry (for example, M or F) and not the individual bit mapped to the updated row. Because a key points to many rows, DML on indexed data typically locks all of these rows. For this reason, bitmap indexes are not appropriate for many OLTP applications.
Example 3-4 shows a query of the sh.customers table. Some columns in this table are candidates for a bitmap index.
SQL> SELECT cust_id, cust_last_name, cust_marital_status, cust_gender
2 FROM sh.customers
3 WHERE ROWNUM < 8 ORDER BY cust_id;
CUST_ID CUST_LAST_ CUST_MAR C
---------- ---------- -------- -
1 Kessel M
2 Koch F
3 Emmerson M
4 Hardy M
5 Gowen M
6 Charles single F
7 Ingram single F
7 rows selected.
The cust_marital_status and cust_gender columns have low cardinality, whereas cust_id and cust_last_name do not. Thus, bitmap indexes may be appropriate on cust_marital_status and cust_gender. A bitmap index is probably not useful for the other columns. Instead, a unique B-tree index on these columns would likely provide the most efficient representation and retrieval.
Table 3-2 illustrates the bitmap index for the cust_gender column output shown in Example 3-4. It consists of two separate bitmaps, one for each gender.
| Value | Row 1 | Row 2 | Row 3 | Row 4 | Row 5 | Row 6 | Row 7 |
|---|---|---|---|---|---|---|---|
|
M |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
|
F |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
A mapping function converts each bit in the bitmap to a rowid of the customers table. Each bit value depends on the values of the corresponding row in the table. For example, the bitmap for the M value contains a 1 as its first bit because the gender is M in the first row of the customers table. The bitmap cust_gender='M' has a 0 for the bits in rows 2, 6, and 7 because these rows do not contain M as their value.
Bitmap indexes can include keys that consist entirely of null values, unlike B-tree indexes. Indexing nulls can be useful for some SQL statements, such as queries with the aggregate function COUNT.
An analyst investigating demographic trends of the customers may ask, "How many of our female customers are single or divorced?" This question corresponds to the following SQL query:
SELECT COUNT(*)
FROM customers
WHERE cust_gender = 'F'
AND cust_marital_status IN ('single', 'divorced');
Bitmap indexes can process this query efficiently by counting the number of 1 values in the resulting bitmap, as illustrated in Table 3-3. To identify the customers who satisfy the criteria, Oracle Database can use the resulting bitmap to access the table.
| Value | Row 1 | Row 2 | Row 3 | Row 4 | Row 5 | Row 6 | Row 7 |
|---|---|---|---|---|---|---|---|
|
M |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
|
F |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
|
single |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
divorced |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
single or divorced, and F |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
Bitmap indexing efficiently merges indexes that correspond to several conditions in a WHERE clause. Rows that satisfy some, but not all, conditions are filtered out before the table itself is accessed. This technique improves response time, often dramatically.
A bitmap join index is a bitmap index for the join of two or more tables. For each value in a table column, the index stores the rowid of the corresponding row in the indexed table. In contrast, a standard bitmap index is created on a single table.
A bitmap join index is an efficient means of reducing the volume of data that must be joined by performing restrictions in advance. For an example of when a bitmap join index would be useful, assume that users often query the number of employees with a particular job type. A typical query might look as follows:
SELECT COUNT(*) FROM employees, jobs WHERE employees.job_id = jobs.job_id AND jobs.job_title = 'Accountant';
The preceding query would typically use an index on jobs.job_title to retrieve the rows for Accountant and then the job ID, and an index on employees.job_id to find the matching rows. To retrieve the data from the index itself rather than from a scan of the tables, you could create a bitmap join index as follows:
CREATE BITMAP INDEX employees_bm_idx ON employees (jobs.job_title) FROM employees, jobs WHERE employees.job_id = jobs.job_id;
As illustrated in Figure 3-2, the index key is jobs.job_title and the indexed table is employees.
Conceptually, employees_bm_idx is an index of the jobs.title column in the SQL query shown in Example 3-5 (sample output included). The job_title key in the index points to rows in the employees table. A query of the number of accountants can use the index to avoid accessing the employees and jobs tables because the index itself contains the requested information.
SELECT jobs.job_title AS "jobs.job_title", employees.rowid AS "employees.rowid" FROM employees, jobs WHERE employees.job_id = jobs.job_id ORDER BY job_title; jobs.job_title employees.rowid ----------------------------------- ------------------ Accountant AAAQNKAAFAAAABSAAL Accountant AAAQNKAAFAAAABSAAN Accountant AAAQNKAAFAAAABSAAM Accountant AAAQNKAAFAAAABSAAJ Accountant AAAQNKAAFAAAABSAAK Accounting Manager AAAQNKAAFAAAABTAAH Administration Assistant AAAQNKAAFAAAABTAAC Administration Vice President AAAQNKAAFAAAABSAAC Administration Vice President AAAQNKAAFAAAABSAAB . . .
In a data warehouse, the join condition is an equijoin (it uses the equality operator) between the primary key columns of the dimension tables and the foreign key columns in the fact table. Bitmap join indexes are sometimes much more efficient in storage than materialized join views, an alternative for materializing joins in advance.
Oracle Database uses a B-tree index structure to store bitmaps for each indexed key. For example, if jobs.job_title is the key column of a bitmap index, then the index data is stored in one B-tree. The individual bitmaps are stored in the leaf blocks.
Assume that the jobs.job_title column has unique values Shipping Clerk, Stock Clerk, and several others. A bitmap index entry for this index has the following components:
Conceptually, an index leaf block in this index could contain entries as follows:
Shipping Clerk,AAAPzRAAFAAAABSABQ,AAAPzRAAFAAAABSABZ,0010000100 Shipping Clerk,AAAPzRAAFAAAABSABa,AAAPzRAAFAAAABSABh,010010 Stock Clerk,AAAPzRAAFAAAABSAAa,AAAPzRAAFAAAABSAAc,1001001100 Stock Clerk,AAAPzRAAFAAAABSAAd,AAAPzRAAFAAAABSAAt,0101001001 Stock Clerk,AAAPzRAAFAAAABSAAu,AAAPzRAAFAAAABSABz,100001 . . .
The same job title appears in multiple entries because the rowid range differs.
Assume that a session updates the job ID of one employee from Shipping Clerk to Stock Clerk. In this case, the session requires exclusive access to the index key entry for the old value (Shipping Clerk) and the new value (Stock Clerk). Oracle Database locks the rows pointed to by these two entries—but not the rows pointed to by Accountant or any other key—until the UPDATE commits.
The data for a bitmap index is stored in one segment. Oracle Database stores each bitmap in one or more pieces. Each piece occupies part of a single data block.
Overview of Function-Based Indexes >>
