Part 2 - The Bitmap Supremacy
The Structure of a Bitmap Index
I’ve been tuning Oracle database applications for a long time now. I started out recognising some simple patterns and applying template fixes (Got a full table scan? Use an index!) but such a collection of “Do this; don’t do that” anecdotes will only take you so far. If you are curious (I was), you can uncover the reasons why one method is faster than another; i.e. what is the computer doing to make slow code so slow. I found that a good understanding of the internals meant that you didn’t always need to know how to tune a specific example because you could work it out for yourself.
In a database application, these investigations frequently lead to data structures; how does the database store its information and how does it retrieve it? Good information on the internals of Bitmap Indexes is hard to piece together, so in Part 2 of this Bitmap Indexing epic we will look more closely at the internals of Bitmap indexes.
- The Structure of a Bitmap Index
- What do Bitmap Indexes do with NULLs?
- Cardinality and Compression
- Inserting new rows and creating new bitmaps
- Breaking down long bitmaps
- Storage of the bitmap keys
- Bitmap Conversion to ROWIDs
- How does this help?
- Appendix B – IO impact of a single update on a Bitmap Index
What do Bitmap Indexes do with NULLs?
Simple answer here: NULLs are indexed. In a regular B-Tree index NULLs are not stored, so predicates such as “COL IS NULL” cannot use a B-Tree index. This is not the case for Bitmap Indexes.
SQL> SELECT *
2 FROM bradys
3 WHERE birthorder IS NULL;
-------------------------------------------------------------
| Id | Operation | Name
-------------------------------------------------------------
| 0 | SELECT STATEMENT | |
| 1 | TABLE ACCESS BY INDEX ROWID | BRADYS |
| 2 | BITMAP CONVERSION TO ROWIDS| |
|* 3 | BITMAP INDEX SINGLE VALUE | BRADYS_BIRTHORDER_IX |
-------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("BIRTHORDER" IS NULL Looking at the Explain Plan for this statement, we see that:
- At Step 3, a single Bitmap is retrieved from the BRADYS_BIRTHORDER_IX index.
- At Step 2, that bitmap is converted into ROWIDs. A ROWID is a physical row address in a table.
- At Step 1, the ROWIDs from Step 2 are used to find matching rows in the table BRADYS
Cardinality and Compression
If Bitmap Indexes store a separate bitmap for every distinct value of a column, then it seems like the storage space would become prohibitive for large tables with a lot of distinct values. For example, if a table contains 1 million rows with 10,000 distinct values, won’t the Bitmap Index contain 1,000,000 x 10,000 = 10,000,000,000 bits? That would be 1.2GB. A million-row table is pretty small for a data warehouse, but 1.2GB is pretty big.
In fact, storage space is not a significant consideration for bitmap indexes with a large number of distinct values. This is because Oracle uses some clever compression where long sequences of 1s or 0s in the bitmap consume hardly any space. This is described in painstaking detail in Oracle’s Bitmap Index Compression Patent US6205442.
With a lot of distinct values, instances of a particular value will be widely spread. This means long strings of zeros in the bitmap which become heavily compressed.
The effect is best illustrated with an example. First, create a table with:
- 1 million rows
- 2 identical columns with 10,000 distinct values
- A B-Tree index on one column
- A Bitmap Index on the other column
SQL> CREATE TABLE card_test 2 AS 3 SELECT mod(LEVEL, 10000) AS col1 4 , mod(LEVEL, 10000) AS col2 5 FROM dual 6 CONNECT BY LEVEL <= 1000000; Table created. SQL> CREATE INDEX card_test_col1_ix ON card_test(col1); Index created. SQL> CREATE BITMAP INDEX card_test_col2_bx ON card_test(col2); Index created.
Now, compare the size of each index.
SQL> SELECT segment_name, sum(bytes)/1024/1024 AS mb 2 FROM user_segments 3 WHERE segment_name LIKE 'CARD%' 4 GROUP BY segment_name; SEGMENT_NAME MB ------------------------------ -------- CARD_TEST 15 CARD_TEST_COL2_BX 4 CARD_TEST_COL1_IX 17
Instead of 1.2GB, we can see that the Bitmap Index has been squished down to just 4MB – one-quarter the size of the B-Tree index! In fact, I ran this same test with 1 million distinct values (ie. One row per value) and still the bitmap index was only 50% larger than the B-Tree index.
The most difficult bitmaps to compress contain strings of zeros that are interrupted by one or two “ones” in each byte. These types of bitmaps won’t compress at all, but if every 8th row has the same value then there can only be 8 such uncompressible bitmaps for the column.
In other words:
- If there are many distinct values then each bitmap will be very compressed because they contain a lot of zeros
- If the bitmaps do not contain a lot of zeros and are not very well compressed then there will not be many of them because there are only a few distinct values
Conclusion: there may be a number of factors that affect our choice of Bitmap vs B-Tree indexes, but disk consumption is not one of them.
Inserting new rows and creating new bitmaps
Whenever a brand new value is used in a Bitmap Index, Oracle must create a bitmap for that value. If the table contains a million rows then that bitmap will be a million bits long. Even if it compresses down to something quite small, wouldn’t it take a long time to create such a long bitmap?
Thankfully no; it is actually quite fast. The secret is in another feature of Oracle’s Bitmap Index compression technique. We already understand that long series of zeros or ones are compressed; but leading and trailing strings of zeros are not even stored. Instead, each bitmap stores a first and last ROWID; i.e. the address of the first row and the last row in the table containing the mapped index value.
For example: consider what would happen in the Brady Bunch table above if we add Tiger- the family sheepdog – and we leave the AGEGRP column NULL.
M
C A C P B A | T
M A R I G E O L | I
I R C J N R T B I | G
K O I A D E E B C | E
E L A N Y G R Y E | R
- - - - - - - - - | -
ADULT 1 1 0 0 0 0 0 0 1 | 0
TEEN 0 0 1 0 0 1 0 0 0 | 0
CHILD 0 0 0 1 1 0 1 1 0 | 0
<null> 0 0 0 0 0 0 0 0 0 | 1
Logically, the bitmap for AGEGRP = NULL is 0000000001, but since the first nine rows are all mapped to 0 in the bitmap, they are not stored. All that needs to be stored is the key value (NULL), the first ROWID (10), the last ROWID (10), and the bitmap for the rows between these two ROWIDs (1). i.e. The bitmap is only 1 bit long!
The Bitmap Index actually stores the following:
KEY FIRST LAST BITMAP ------ ----- ---- --------- ADULT 1 9 110000001 TEEN 3 6 1001 CHILD 4 8 11011 <null> 10 10 1
We also notice that since TIGER was inserted at the end of the table, there is no need to append a trailing 0 to all of the other bitmaps (ADULT, TEEN, and CHILD) because the last ROWID with a non-zero bit has not changed.
Of course, real Oracle ROWIDs are not short integers like this; they are 20 digit base-64 numbers that look a bit like this:
SQL> SELECT ROWID FROM DUAL; ROWID ------------------ AAAAB0AABAAAAOhAAA
Breaking down long bitmaps
Compression and truncation of bitmaps notwithstanding, it is still possible to get logical bitmaps in large tables that would be millions of bits long. If we do need to update one of these bitmaps, won’t it generate huge amount of IO reading and writing the long bitmaps?
Fortunately not! As with Tables and B-Tree indexes, Oracle stores Bitmap Indexes in database blocks. A database block may be between 2KB and 32KB, although 8KB is the default for Oracle 11g. Each logical bitmap is broken down into chunks that do not exceed the size of a single block; these chunks are known as “pieces”. Each piece is logically independent; it contains an index key value, a low and high ROWID and a bitmap. Together they cannot exceed one database block.
When you update a row in a very large table, two bitmaps will be affected (flip one bit “off” for the old index key and one bit “on” for the new key); but no matter how long those bitmaps are, only one Piece of each bitmap will be impacted. Instead of rewriting an entire (say) 100MB bitmap, we may just rewrite one 8KB chunk of that bitmap.
Well, that’s the theory. The reality is somewhere in-between; Oracle seems to read and write more than one piece of the bitmap, but it certainly does not appear to rewrite entire bitmaps. See the results of an experiment in Appendix B. Interestingly, a single update on longer bitmaps does seem to generate more IO than an identical update on smaller bitmaps – this is a warning for the potential cost of DML operations on very large Bitmap Indexed tables.
Storage of the bitmap keys
So let’s just recap what we already know:
- Each distinct value of a bitmap indexed column has its own bitmap – one bit per row
- Bitmaps are compressed and broken into “pieces” that fit within Oracle Database Blocks
- Each Piece comprises a key value, a start ROWID, an end ROWID and a bitmap
How are these Pieces stored in an Index Segment? Surely they can’t just be in an unstructured heap. Remember that the index key (column value) is stored in the database block along with the bitmap. Oracle’s minimum unit of I/O is the database block so it cannot just read the keys on their own; a brute force search for a key would read the entire index.
According to the 11g Concepts manual, the Pieces of a Bitmap Index are arranged in a B-Tree data structure. Although both B-Tree and Bitmap Indexes both use B-Tree data structures under the covers, these structures are not identical and neither are Oracle’s access methods. This is like saying my attic and my kitchen are both “rooms” in my house; but they are also different because the attic is accessed by a ladder and has sloping walls that are also its ceiling.
If you are not familiar with B-Trees in Oracle, it’s worth reviewing them in the Oracle Database Concepts manual. The Cliff Notes version: a B-Tree (or Balance Tree) Index is a tree data structure that includes branch blocks and leaf blocks. Leaf blocks contain index entries – one per row in the table. So if 100 index entries fit in a leaf – and there are 10,000 rows in the table – then there will be at least 100 leaf blocks. These index entries contain two things: a key and a payload. The key is the column value being indexed and the payload is the address (ROWID) of a row in the table. Branch blocks link the leaf blocks into a search tree that is ordered by the index key column(s).
The structure of the Bitmap Index B-Tree is similar, but with the following significant differences:
- The Index Entries still contain a key and a payload, but the payload is a bitmap (or piece of a bitmap) rather than a ROWID
- There is one Index Entry per bitmap piece rather than one per row in the table. We can think of this as one index entry per distinct column value, but this is not quite right because long bitmaps must be broken into multiple entries.
The B-Tree architecture of Bitmap Indexes has an interesting side-effect. The B-Tree means that the keys are ordered, so we can find a single key easily without having to read the entire index. It also means that we can find a range of keys - e.g. ACCOUNTING_YEAR BETWEEN 2010 AND 2012 – without having to scan the entire index. Oracle can pull the bitmap for each distinct value in the range and then OR them together to get a combined bitmap result.
Note the Range Scan in step 4 of the execution plan below.
SQL> SELECT avg(col1)
2 FROM piece_test
3 WHERE col2 BETWEEN 4 AND 6
4 /
AVG(COL1)
----------
500001
------------------------------------------------------------
| Id | Operation | Name |
------------------------------------------------------------
| 0 | SELECT STATEMENT | |
| 1 | SORT AGGREGATE | |
| 2 | TABLE ACCESS BY INDEX ROWID | PIECE_TEST |
| 3 | BITMAP CONVERSION TO ROWIDS| |
|* 4 | BITMAP INDEX RANGE SCAN | PIECE_TEST_COL2_BX |
------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - access("COL2">=4 AND "COL2"<=6)
Bitmap Conversion to ROWIDs
So bitmaps are compressed, chopped up into pieces and arranged into a B-Tree from which they can be accessed by range or single value. Separate bitmaps from the same index can be combined (for IN-lists or range scans) and they can be combined with bitmaps on other columns to satisfy combination predicates. All of this is well and good, but how does Oracle convert a final bitmap into ROWIDs so that it can look up rows the table?
This was a mystery to me for a long time. I knew from experience that table blocks were not uniform density; some contained more rows than others. If the 100,005th bit is set and there are 100 rows per block, then we know that the 100,005th row will be the 5th row in block number 1,001 – we could easily calculate the ROWID of any row using just the ROWID of the 1st row and an offset. But some blocks might contain 98 rows, or 95 rows, or even 0 rows; as DELETEs and INSERTs occur this will change continually. More importantly, if we delete the 100,005th row, do we have to update every bitmap to remove the 100,005th bit? Even from those bitmaps where the bit is unset?
I had considered this at length but couldn’t work out how Oracle could do it efficiently. That might show lack of imagination (considering how simple the solution is), but I feel slightly vindicated that it took me only one clue to work it out (note: I can’t find this documented by Oracle, so it is still technically a theory).
My clue was in an error message that occurred when a Partition Exchange failed.
ORA-14642: Bitmap index mismatch for tables in ALTER TABLE EXCHANGE PARTITION
Cause: The two tables in the EXCHANGE have usable bitmap indexes,
and the INCLUDING INDEXES option has been specified and the tables
have different hakan factors.
Action: Perform the exchange with the EXCLUDING INDEXES option or alter
the bitmap indexes to be unusable.
For a Partition Exchange you swap one partition of a table with a completely separate but identically structured table. The other table must have the same columns with the same data types in the same order and – if the INCLUDING INDEXES clause is specified – its indexes must be identical to the Locally Partitioned Indexes on the partitioned table. This error is telling us that the tables are not identically structured; they have a different Hakan Factor … whatever that is?
A little Googling tells us that a Hakan Factor is an estimate of the maximum number of rows that can fit into a block. In other words, it is a measure of maximum theoretical row density.
In my case I had created the partitioned table with fewer columns and then added columns with ALTER TABLE commands, but I created the exchange table with a single CREATE TABLE command. These two methods arrived at different Hakan Factors.
So why is the Hakan Factor important for Bitmap Indexes? The answer is pretty straightforward: when Oracle is trying to convert the 100,005th bit of a bitmap into a ROWID, it is not trying to find the 100,005th row; it is trying to find the 100,005th possible row assuming maximum theoretical block density. If the Hakan Factor was (say) 100 – meaning that each block cannot hold more than 100 rows – then the 100,005th bit simply refers to Row 5 in Block 1,001. Note that blocks 1 thru 1000 probably don’t contain 100 rows each, but they could. Also note that Row 5 in Block 1,001 is not necessarily the 5th row in that block; it was the 5th row when it was inserted, but any of Rows 1-4 may have since been deleted.
All of this means that the bitmaps in Bitmap Indexes redundantly store zeros for theoretical but non-existent rows. If Block 1 contains just 98 rows and the Hakan Factor is 100, then the 99th and 100th bit of every bitmap of every bitmap index on that table will be zero. This redundancy takes a little more space, but it allows Oracle to discover the ROWID of any set bit (set to 1) in a bitmap using only the starting ROWID, the bit number/offset and the Hakan Factor.
How does this help?
Indexes – both Bitmap and B-Tree – have only one purpose: to make applications faster. Before you go creating a new index it is handy to have a good understanding of whether it will improve your application performance or not. If you are designing a new application, it is even more important to be able to make educated guesses about which indexes you will need and which ones will not add value.
Understanding the internals of index data structures is only part of the process though. Now we know how data gets IN to bitmap indexes, the next thing to learn is how Oracle gets data OUT of them. This is the subject of Part 3: Bitmap Execution Plans.
Return to main article
Read Part 3 - The Bitmap Dominion
Appendix B – IO impact of a single update on a Bitmap Index
Consider the following test case where we insert 1 million rows into a table and then update one bitmap indexed value in one row. The Bitmap Index has 7 distinct values, with each value repeating every 7 rows.
This should make for 7 bitmaps with poor compression.
SQL> CREATE TABLE piece_test 2 AS 3 SELECT LEVEL AS col1, mod(LEVEL, 7) AS col2 4 FROM dual 5 CONNECT BY LEVEL <= 1000000; Table created. SQL> CREATE INDEX piece_test_col1_ix ON piece_test(col1); Index created. SQL> CREATE BITMAP INDEX piece_test_col2_bx ON piece_test(col2); Index created. SQL> UPDATE piece_test 2 SET col2 = 4 3 WHERE col1 = 7; 1 row updated. SQL> COMMIT; Commit complete.
To measure the impact on the bitmap index, I queried the data dictionary view V$SEGSTAT before and after the UPDATE to see how many physical and logical reads and writes were performed on the bitmap index object. I also performed a CHECKPOINT to make sure the changes were written to the data files. Here is a summary of the impacts:
STATISTIC_NAME BEFORE AFTER DIFF ------------------------------ ------ ----- ---- physical reads direct 0 0 0 physical reads 0 5 5 physical write requests 39 49 10 physical writes 144 159 15 physical writes direct 144 144 0 physical read requests 0 2 2 logical reads 544 560 16
Even though only 1 row of the table was changed (affecting 1 block each of 2 bitmaps), we can see 15 blocks were written to the index. The index consumes 144 blocks in total to store 7 bitmaps (20 blocks per bitmap), so with just 15 blocks written it is clear that Oracle has not rewritten one or two entire bitmaps. This overhead could possibly be explained by Oracle attempting to optimize compression of the bitmap pieces; as a result of the update the bitmaps might compress more or less efficiently resulting in index blocks splitting or perhaps bitmap pieces merging.
To see whether the size of the bitmaps has a significant impact on these overheads, I ran the same test again using a 10 million row table (10x larger):
STATISTIC_NAME BEFORE AFTER DIFF -------------------------- ------ ----- ---- physical reads direct 0 0 0 physical reads 0 4 4 physical write requests 369 404 35 physical writes 1428 1463 35 physical writes direct 1428 1428 0 physical read requests 0 4 4 logical reads 2144 2176 32
The larger bitmaps has resulted in increased IO for updating a single row, but even though the bitmaps were 1000% longer, the IO increased by only about 100%.
No conclusions can be drawn from these results except to observe that updates on bitmap indexed values carry overheads that extend beyond updating the impacted rows.
Return to main article
Read Part 3 - The Bitmap Dominion
- rleishman's blog
- Log in to post comments