bitmap conversion to rowid

When Oracle join a b-tree and a bitmap index
and bitmap conversion is occured.
there is from_rowid to join bitmaps,
and to_rowid to get the data from the table.
how does this from and to rowid going on?
how much does it cost? (building bitmap from rowid sounds costly)
do you have a link to a white paper on that subject?

Who is Participating?
renurajConnect With a Mentor Commented:
Bitmap benefits

Indexes provide fast access to table rows in an Oracle database when a small subset of the table data is returned. SQL queries contain conditions for the data to be returned. These conditions constrain column values. If the columns in the where clause are highly selective (have high cardinality), a typical b-tree index will greatly improve the response of the query. Oracle devised bitmap indexes for low-cardinality columns that are frequently constrained by users in their queries. A low-cardinality column has a small set of distinct values. Typically, these columns wouldn't be indexed with a b-tree index because of their low cardinality. A b-tree index will often lengthen the execution time of a query.

To illustrate column cardinality, let's look at a typical table of employee information named EMP. This table contains customer demographic information.
SQL> desc emp
Name            Null?            Type
EMPNO            NOT NULL      NUMBER(4)
ENAME                        VARCHAR2(10)
DEPTNO                        NUMBER(2)
ACTIVE_FLAG                  VARCHAR2(1)
GENDER                        VARCHAR2(1)

Column EMPNO uniquely identifies employees by their social security number. Column ENAME holds each employee's name. These two columns have high cardinality because most or all of the column values are different. A b-tree index is ideal for these columns.

Other columns in this table have low cardinality--the values in the column aren't unique. Some examples include gender, race, status, etc. Gender will be only male or female. Race will be only values from a select list of choices. Status will be only one of four values.
Bitmap details

Let's look briefly at how a bitmap index works. Column GENDER may have only two unique values for a million-record table. Oracle stores each unique value for a bitmap-indexed column only once. For each row in the table, a 1 or 0 is recorded in the index to indicate whether the column value for that row matches its bitmap entry. Consider this six-row table:
Gender Bitmap
M:      0 0 0 1 1 0
F:      1 1 1 0 0 1

Race Bitmap
W:      1 0 1 0 1 0
B:      0 0 0 0 0 1
H:      0 1 0 1 0 0
We want to return all rows where the customer is a black female:
F:      1 1 1 0 0 1
B:      0 0 0 0 0 1
A BITMAP AND operation would indicate that row 6 evaluates to true. Oracle would then calculate the rowid and use it to access that table. Keep these things in mind when considering bitmap indexes:
?h Use bitmap indexes on low-cardinality columns.
?h The ratio of distinct values to total number of rows is best at approximately 1 to 1000.
?h Bitmap indexes work very well when users are constraining on multiple low-cardinality columns.
?h Bitmap indexes shouldn't be used in tables with frequent data-manipulation operations because of the performance cost of these operations in maintaining these indexes.
A bit about setup
To enable bitmap indexes, you must set the following items in the instance initialization file:
compatible =      # or higher
event = "10111 trace name context forever"
event = "10112 trace name context forever"
event = "10114 trace name context forever"
Consider also the parameters shown in Table A.

Table A: Parameters
Parameter                                        Usage
CREATE_BITMAP_AREA_SIZE            Determines the amount of memory allocated for bitmap creation

BITMAP_MERGE_AREA_SIZE      Determines the amount of memory used to merge bitmaps retrieved from a range scan of the index.

V733_PLANS_ENABLED       Determines whether bitmap access paths will be considered for regular indexes on the tables that have at least one bitmap index

One other note: the parallel query option must be installed to be able to create bitmap indexes. If you try to create bitmap indexes and haven't installed the parallel query option, you'll receive a syntax error in your SQL statement--the keyword bitmap won't be recognized. (You can quickly tell that the parallel option is installed by starting SQL*Plus. After a successful login, you'll see the word parallel in the banner text displayed). Creating bitmap indexes is similar to creating b-tree indexes. To specify a bitmap index, add the word bitmap between create and index. All other syntax is identical. For our EMP table, we can maintain indexes with these commands:
Bitmap indexes:
drop index emp_active_bit;
drop index emp_gender_bit;
create bitmap index emp_active_bit on emp (active_flag);
create bitmap index emp_gender_bit on emp (gender);
B-tree indexes:
drop index emp_active;
drop index emp_gender;
create index emp_active on emp (active_flag);
create index emp_gender on emp (gender);

You'll find information in the data dictionary for bitmap indexes in dba_indexes, all_indexes, and user_indexes with the word BITMAP in the Uniqueness column.
More than a bit smaller
Bitmap indexes on appropriate columns are much smaller than b-tree indexes since only distinct values are stored and bitmaps are stored instead of rowids. To demonstrate the size savings, consider the EMP table with only 8000 records. We create both the bitmap and b-tree indexes. Then we select the index size from the DBA_SEGMENTS data dictionary view, as shown in Listing A.
Listing A: Once you create a bitmap index you can check its size.
SQL> create bitmap index emp_active_bit on emp

Index created.

SQL> create bitmap index gender on emp (gender);

Index created.


EMP             TABLE         286720
EMP_ACTIVE_BIT  INDEX         30720
EMP_PK          INDEX         153600
EMP_GENDER_BIT  INDEX         30720

SQL> create index emp_active on emp (active_flag);

Index created.

SQL> create index emp_gender on emp (gender);

Index created.


EMP            TABLE         86720
EMP_ACTIVE     INDEX         143360
EMP_GENDER     INDEX         153600
EMP_PK         INDEX         153600
EMP_PK         INDEX         153600
Note the bitmap indexes EMP_GENDER_BIT and EMP_STATUS_BIT are 30KB compared to b-tree indexes; EMP_GENDER and EMP_STATUS are both 150KB. These sizes represent indexes on a table with only 8,000 rows.
At a client site, we found dramatic decreases in disk space required when using bitmap indexes. For example, a b-tree index occupying approximately 100MB in disk space required only 1MB when re-created as a bitmap index. (However, if the low-cardinality rule is violated, the size of the bitmap index can grow very fast and use more disk space.)
More than a bit easier
For well-chosen columns, it takes less time to create and drop bitmap indexes than to create and drop b-tree indexes. We recorded the following results by dropping and creating b-tree and bitmap indexes to compare the execution times:
SQL> create index emp_active on emp (active_flag);

Index created.

 real: 2420
SQL> create index emp_gender on emp (gender);

Index created.

 real: 1750
SQL> drop index emp_active;

Index dropped.

 real: 550
SQL> drop index emp_gender;

Index dropped.

 real: 280
SQL> create bitmap index emp_active_bit on
emp (active_flag);

Index created.

 real: 550
SQL> create bitmap index emp_gender_bit on emp

Index created.

 real: 500
SQL> drop index emp_active_bit;

Index dropped.

 real: 270
SQL> drop index emp_gender_bit;

Index dropped.

 real: 270
As you can see, these smaller indexes are easier to manage--especially for very large tables. This advantage is most evident when performing large data loads. At a recent client site, we dropped the bitmap indexes before performing the initial large data loads from staging tables to production tables. After the load, we re-created the indexes to prevent the overhead of updating the indexes during the load. Bitmap indexes, as shown above, are much faster to drop and re-create than b-tree indexes.
More than a bit faster
Smaller. Easier. And faster! We ran the following query on our 8,000-row table to quantify the difference between indexing types.
select count(*)
from emp
where active_flag = 'Y'
and gender = 'F';
With bitmap indexes, we achieved these results:

real: 820
With b-tree indexes, we achieved these results:

real: 1540
Using our bitmap indexes, we found that the response time was about twice as fast. By looking at the execution plan, you can see whether bitmap indexes are being used. For the following query, the following execution plan was generated:
select count(*)
 from emp
 where active_flag = 'Y';


You may experience dramatic increases in performance when selecting distinct counts of columns using bitmap indexes on very large tables. We found that a query on a 2 million-row fact table returned in less than a second. Now that's quite a bit faster!
A little bit about execution plan
After you've created your bitmap indexes, you can confirm that your SQL makes use of them. Table B shows some typical operations you'll find in an execution plan. By evaluating your SQL execution plan, you can confirm that your SQL is using your bitmap indexes as desired.
Table B: Typical operations you'll see in an execution plan

Operation                  Description
BITMAP AND                  Computes the bitwise AND of two bitmaps

BITMAP OR                  Computes the bitwise OR of two bitmaps

BITMAP MINUS            Subtracts the bits of one bitmap from another

BITMAP MERGE            Merges several bitmaps resulting from a range scan into one bitmap

BITMAP CONVERSION COUNT      Returns the number of rowids if the actual values aren't needed

BITMAP CONVERSION TO ROWIDS      Converts the bitmap representation to actual rowids that can be          used to access the table

BITMAP CONVERSION FROM ROWIDS      Converts the rowids to a bitmap representation

BITMAP INDEX SINGLE VALUE      Looks up the bitmap for a single key value in the index (BITMAP UNIQUE SCAN)

BITMAP INDEX RANGE SCAN            Retrieves bitmaps for a key value range

BITMAP INDEX FULL SCAN            Performs a full scan of the bitmap index because there's no start or stop key
A bit about warehouses
Bitmap indexes are primarily for use with data warehouse applications because of their high maintenance costs. For example, the bitmap index is rebuilt after each DML statement--no matter how many rows are affected. Also, when a bitmap-indexed column is updated, every row associated with that bitmap entry is locked--potentially affecting hundreds or thousands of records. When a column with a b-tree index is updated, only the rowids of the affected columns are locked. This illustrates why you'd avoid bitmap indexes on OLTP database tables with insert and update traffic. When using bitmap indexes, the optimizer is very sensitive to the statistics generated with the ANALYZE command. You'll find that the COMPUTE STATISTICS clause yields better optimizer choices than the ESTIMATE STATISTICS clause. This is true even when the ESTIMATE percentage is set as high as 60 percent. You should perform the ANALYZE command frequently. We perform the ANALYZE command nightly after loading data in our data warehousing applications. You can run the ANALYZE on each individual indexed column separately to alleviate any temporary tablespace problems.
Bitmap indexes are very suited to data warehousing applications because of their performance, size, and ability to create and drop very quickly. Since most dimension tables in a warehouse need to have nearly every column indexed, the space savings is also very important. For example, we have a Product table that has approximately 70 indexes, 60 or so of which are bitmap indexes. On large loads into tables with many bitmap indexes, you'll want to drop the bitmap indexes, perform the load, then re-create the indexes. This is especially true for loads where a number of DML statements are being executed (e.g., one statement for every record loaded).
A few questions answered
As you begin to use bitmap indexes on your system, you may have some questions or encounter a few snags. Here are some questions we've run across that you may find relevant:
Q. Is there an advantage in using just one bitmap index on a table, or is the true advantage of bitmap indexes realized when you have two or more on one table?
A. While it's true that one of the major benefits of bitmap indexes are the bitmap operations used on multiple constraints in a query, a single bitmap index in a table can still offer advantages. For example, if you're browsing this table for a data warehouse, a bitmap index on this column can quickly display the distinct values that are available to constrain the query. Another example would be to display the distinct count of a particular bitmap column.
Q. Bitmap indexes appear to take up much more space than a non-bitmap index. Why?
A. A bitmap index created on a column with very high cardinality would be larger than a conventional b-tree index.
Q. How does this relate with parallelism? It appears that if a bitmap index is used, the query isn't executed in parallel.
A. I haven't observed this. In fact, I've seen almost the opposite to be true. The optimizer tended to try to use parallelism in cases where the bitmap indexes would have performed better. (However, I'd need to perform more tests on this topic to be certain.)
Q. How does a bitmap index work with the "rebuild" alter command? (Sometimes this command seems to get lost.)
A. You may have problems using the alter...rebuild command on bitmap indexes because the create_bitmap_area_size in the database initialization file needs adjusting.
Q. Why do my bitmap indexes sometimes remain in direct-load state after a successful database SQL*Load?
A. This is an Oracle bug that's fixed in release 7.3.3 of the RDBMS. You can work around this problem by dropping the index before the load. Then create the index after the load.

Wow, that's an answer and half ranuraj.  I was very impressed by its completeness and the way you anticipated possible problems.  
eyalshaniAuthor Commented:
this is all very nice,
but you didn't answer my question.
I asked if there is a white paper which explains the alogorithm of transforming b-tree entries to bitmap entries when a bitmap from rowid occures. Please don't copy and paste the Oracle docs on bitmap indexes.

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

Mark GeerlingsDatabase AdministratorCommented:
There may not be a paper explaining exactly what you are asking for, but renuraj's comment clearly explains most of the advantages of bitmap indexes.  Are you just concerned about the possible performance cost of the bitmap-to-rowid conversions?  Do you have an actual situation where you have tried a bitmapped index and the performance was slower than you expected?

Stay away from bitmap indexes for most OLTP systems, but in a reporting situation, they can be very helpful.
Please update and finalize this old, open question. Please:

1) Award points ... if you need Moderator assistance to split points, comment here with details please or advise us in Community Support with a zero point question and this question link.
2) Ask us to delete it if it has no value to you or others
3) Ask for a refund so that we can move it to our PAQ at zero points if it did not help you but may help others.


Thanks to all,
Moondancer - EE Moderator

P.S.  Click your Member Profile, choose View Question History to go through all your open and locked questions to update them.
Force accepted

** Mindphaser - Community Support Moderator **
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.