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.
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.
Using this methodology, Oracle can provide sub-second response time when working against multiple low-cardinality columns:
--------------------------------------------------------------------------------
Oracle Bitmap indexes are a very powerful Oracle feature, but they can be tricky!
You will want a bitmap index when:
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 .
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;
-------------------------------------------------------------------------------
A bitmap index is a special kind of database index.
It works very well with for a column with data which has a small number of distinct values but many occurrences of those values.
Example :
gender : male, female
personal situation : single, divorced, married, widow
Advantages :
#1 : Significant space and performance advantages
#2 : Queries performs logical operations on bitmaps which are very fast
Bitmaps work very well with other bitmaps
Example :
A common example is the "gender" example. It has a small number of distinct values but many occurrences.
The bitmap index is shown as 2 columns with each gender values : female and male.
For each identifier (row id), one line is crossed with the 2 columns and each cell is 1 (TRUE) or 0 (FALSE).
# Mixing bitmap indexes :
You have a table with customers data : customer identifier, name, adress, gender, personal situation, ..., ...
You create 2 bitmap indexes :
Gender : 2 values (male, female)
Personal situation : 4 values (Single, Married, Divorced, Widow)
The bitmap indexes are created as below :
You want to extract all your clients "FEMALE" and "DIVORCED" :
SELECT T.NAME, T.ADRESS
FROM TABLE_CUSTOMER T
WHERE T.GENDER = 'F'
AND T.PERSONAL = 'DIVORCED'
The bitmap indexes will work together :
The "AND" operator is applied on the bitmap indexes, not on the data, so it's very fast.
Let's take a look at the explain plan of that query :
Conclusion :
If you try to optimize your report process, ask yourself 2 questions :
What are the columns that are often filtered ?
Do they fit with bitmap indexes (small distinct values but many occurrences) ?
===================================================================================
Using the Oracle 10g Bitmap Join Index
Oracle 10g has introduced a new method to create speed join queries against very large data warehouse tables. This new method is called the bitmap join index, and this new table access method required the creation of an index that performs the join at index creation time and creates a bitmap index of the keys that are used in the join.
While Oracle markets this new feature with great fanfare, the bitmap join index is only useful for table joins that involve low-cardinality columns (e.g. columns with less than 300 distinct values). Bitmap join indexes are also not useful for OLTP databases because of the high overhead associated with updating bitmap indexes.
For our example, we will use a many-to-many relationship where we have parts and suppliers. Each pert has many suppliers and each supplier provides many parts (Figure 1)
Figure 1 – A many-to-many Oracle table relationship
In this example, the Oracle database has 200 types of parts and the suppliers provide parts in all 50 states. The idea behind a bitmap join index is to pre-join the low cardinality columns together, thereby making the overall join faster:
While b-tree indexes are used in the standard junction records, we can improve the performance of Oracle 10g queries where the predicates involve the low cardinality columns. For example, look at the query below where we want a list of all suppliers of pistons in North Carolina:
select
supplier_name
from
parts
natural join
inventory
natural join
suppliers
where
part_type = ‘piston’
and
state = ‘nc’
;
(Note the use of the new Oracle 10g natural join syntax, removing the need to specify table join criteria)
For queries that have additional criteria in the WHERE clause that does not appear in the bitmap join index, Oracle 10g will be unable to use this index to service the query. The following query will not use the bitmap join index:
select
supplier_name
from
parts
natural join
inventory
natural join
suppliers
where
part_type = ‘piston’
and
state = ‘nc’
and
part_color = ‘yellow’
;
Prior to Oracle 10g, this query would require a nested loop join or hash join of all three tables. In Oracle 10g, we can pre-join these tables based on the low cardinality columns:
To create a bitmap join index we issue the following SQL. Note the inclusion of the FROM and WHERE clauses inside the CREATE INDEX syntax.
create bitmap index
part_suppliers_state
on
inventory( parts.part_type, supplier.state)
from
inventory i,
parts p,
supplier s
where
i.part_id = p.part_id
and
i.supplier_id = p.part_id;
Note that this bitmap join index specified the join criteria for the three tables, and creates a bitmap index on the junction table (inventory) with the type and state keys (Figure 2).
Figure 2 – A bitmap join index
Oracle claims that this indexing method results in more than 8x improvement in table joins in cases where all of the query data resides inside the index. However, this claim is dependent upon many factors, and the bitmap join is not a panacea. In many cases the traditional hash join or nested loop join may out-perform a bitmap join. Some limitations of the bitmap join index join include:
1. The indexed columns must be of low cardinality – usually with less than 300 distinct values
2. The query must not have any references in the WHERE clause to data columns that are not contained in the index.
3. The overhead when updating bitmap join indexes is substantial. For practical use, bitmap join indexes are dropped and re-built each evening about the daily batch load jobs. Hence bitmap join indexes are only useful for Oracle data warehouses that remain read-only during the processing day.
In sum, bitmap join indexes will tremendously speed-up specific data warehouse queries, but at the expense of pre-joining the tables at bitmap index creation time.
===================================================================================
Posts
No comments:
Post a Comment