Oracle Scratchpad

April 18, 2014

Bitmap loading

Filed under: bitmaps,Indexing,Oracle — Jonathan Lewis @ 12:43 pm BST Apr 18,2014

Everyone “knows” that bitmap indexes are a disaster (compared to B-tree indexes) when it comes to DML. But at an event I spoke at recently someone made the point that they had observed that their data loading operations were faster when the table being loaded had bitmap indexes on it than when it had the equivalent B-tree indexes in place.

There’s a good reason why this can be the case.  No prizes for working out what it is – and I’ll supply an answer in a couple of days time.  (Hint – it may also be the reason why Oracle doesn’t use bitmap indexes to avoid the “foreign key locking” problem).

Answer

As Martin (comment 3) points out, there’s a lot of interesting information in the statistics once you start doing the experiment. So here’s some demonstration code, first we create a table with one of two possible indexes:


create table t1
nologging
as
with generator as (
	select	--+ materialize
		rownum id
	from dual
	connect by
		level <= 1e4
)
select
	rownum			id,
	mod(rownum,1000)	btree_col,
	mod(rownum,1000)	bitmap_col,
	rpad('x',100)		padding
from
	generator	v1,
	generator	v2
where
	rownum <= 1e6
;

begin
	dbms_stats.gather_table_stats(
		ownname		 => user,
		tabname		 =>'T1',
		method_opt	 => 'for all columns size 1'
	);
end;
/

create        index t1_btree on t1(btree_col) nologging;
-- create bitmap index t1_bitmap on t1(bitmap_col) nologging;

You’ll note that the two columns I’m going to build indexes on hold the same data in the same order – and it’s an order with maximum scatter because of the mod() function I’ve used to create it. It’s also very repetitive data, having 1000 distinct values over 1,000,0000 rows. With the data and (one of) the indexes in place I’m going to insert another 10,000 rows:

execute snap_my_stats.start_snap

insert /* append */ into t1
with generator as (
	select	--+ materialize
		rownum id
	from dual
	connect by
		level <= 1e4
)
select
	1e6 + rownum		id,
	mod(rownum,1000)	btree_col,
	mod(rownum,1000)	bitmap_col,
	rpad('x',100)		padding
from
	generator
;

execute snap_my_stats.end_snap

You’ll note that I’ve got an incomplete append hint in the code – I’ve tested the mechanism about eight different ways, and left the append in as a convenience, but the results I want to talk about (first) are with the hint disabled so that the insert is a standard insert. The snap_my_stats calls are my standard mechanism to capture deltas of my session statistics (v$mystat) – one day I’ll probably get around to using Tanel’s snapper routine everywhere – and here are some of the key results produced in the two tests:


11.2.0.4 with btree
===================
Name                                                                     Value
----                                                                     -----
session logical reads                                                   31,403
DB time                                                                     64
db block gets                                                           31,195
consistent gets                                                            208
db block changes                                                        21,511
redo entries                                                            10,873
redo size                                                            3,591,820
undo change vector size                                                897,608
sorts (memory)                                                               2
sorts (rows)                                                                 1

11.2.0.4 with bitmap
====================
Name                                                                     Value
----                                                                     -----
session logical reads                                                   13,204
DB time                                                                     42
db block gets                                                            8,001
consistent gets                                                          5,203
db block changes                                                         5,911
redo entries                                                             2,880
redo size                                                            4,955,896
undo change vector size                                              3,269,932
sorts (memory)                                                               3
sorts (rows)                                                            10,001

As Martin has pointed out, there are a number of statistics that show large differences between the B-tree and bitmap approaches, but the one he didn’t mention was the key: sorts (rows). What is this telling us, and why could it matter so much ? If the B-tree index exists when the insert takes place Oracle locates the correct place for the new index entry as each row is inserted which is why you end up with so many redo entries, block gets and block changes; if the bitmap index exists, Oracle postpones index maintenance until the table insert is complete, but accumulates the keys and rowids as it goes then sorts them to optimize the rowid to bitmap conversion and walks the index in order updating each modified key just once.

The performance consequences of the two different strategies depends on the number of indexes affected, the number of rows modified, the typical number of rows per key value, and the ordering of the new data as it arrives; but it’s possible that the most significant impact could come from ordering.  As each row arrives, the relevant B-tree indexes are modified – but if you’re unlucky, or have too many indexes on the table, then each index maintenance operation could result in a random disk I/O to read the necessary block (how many times have you seen complaints like: “we’re only inserting 2M rows but it’s taking 45 minutes and we’re always waiting on db file sequential reads”). If Oracle sorts the index entries before doing the updates it minimises the random I/O because it need only update each index leaf block once and doesn’t run the risk of re-reading many leaf blocks many times for a big insert.

Further Observations

The delayed maintenance for bitmap indexes (probably) explains why they aren’t used to avoid the foreign key locking problem.  On a large insert, the table data will be arriving, the b-tree indexes will be maintained in real time, but a new child row of some parent won’t appear in the bitmap index until the entire insert is complete – so another session could delete the parent of a row that exists, is not yet committed, but is not yet visible. Try working out a generic strategy to deal with that type of problem.

It’s worth noting, of course, that when you add the /*+ append */ hint to the insert then Oracle uses exactly the same optimization strategy for B-trees as it does for bitmaps – i.e. postpone the index maintenance, remember all the keys and rowids, then sort and bulk insert them.  And when you’ve remembered that, you may also remember that the hint is (has to be) ignored if there are any enabled foreign key constraints on the table. The argument for why the hint has to be ignored and why bitmap indexes don’t avoid the locking problem is (probably) the same argument.

You may also recall, by the way, that when you have B-tree indexes on a table you can choose the optimal update or delete strategy by selecting a tablescan or index range scan as the execution path.  If you update or delete through an index range scan the same “delayed maintenance” trick is used to optimize the index updates … except for any indexes being used to support foreign key constraints, and they are maintained row by row.

In passing, while checking the results for this note I re-ran some tests that I had originally done in 2006 and added one more test that I hadn’t considered at the time; as a result I can also point out that index will see delayed maintenance if you drive the update or delete with an index() hint, but not if you drive it with an index_desc() hint.

 

10 Comments »

  1. Hi Jonathan, I’m looking forward to have the answer about foreign key problem. Is there some kind of optimization where the bitmap index maintenance is delayed so a concurrent session cannot check for uncommitted inserts ?

    Comment by @FranckPachot — April 19, 2014 @ 10:53 am BST Apr 19,2014 | Reply

    • Franck,

      Delayed maintenance comes into the performance part of the question, and I think that it could also have something to do with the foreign key locking.

      Comment by Jonathan Lewis — April 20, 2014 @ 11:48 am BST Apr 20,2014 | Reply

  2. The data loading operations were faster in that case because without the bitmap index maybe there was a lot of concurrency overhead or contention from other sessions. With the bitmap index, an exclusive lock on the table blocked the other sessions?

    Comment by George — April 20, 2014 @ 2:46 am BST Apr 20,2014 | Reply

    • George,

      That’s a very good idea – though it’s not the generic thought I had in mind.

      It’s ALWAYS worth considering that a performance COULD be a side effect of concurrency. Even without explicit locking problems sequencing processes (and allowing each individual process to complete quickly) the simple fact that two things are happening at once and competing over the same resources could mean that they spend a lot more “fighting” than they do getting on with the job.

      Comment by Jonathan Lewis — April 20, 2014 @ 11:53 am BST Apr 20,2014 | Reply

  3. Jonathan,

    using Richard Foote’s test setup from http://richardfoote.wordpress.com/2014/04/17/indexing-foreign-key-constraints-with-bitmap-indexes-locked-out/ and checking the session statistics I see that the insert of 1M rows into bowie_kid (I think I mentioned already that it’s an example designed by Mr. Foote) with an existing b*tree index uses much more resources (and time) than the same insert with a bitmap index: especially the redo size (* 9) and the undo change vector size (* 36) are massively increased (and the b*tree insert uses 50MByte of session pga/uga memory while these statistics show no resource usage for the bitmap case). Furthermore the b*tree maintenance uses much more recursive queries (mostly related to segment management – according to a sql_trace; but the bitmap index is much smaller so that’s not really surprising).

    So I guess in the case of the b*tree the read consistency is taken much more seriously than in the case of the bitmap index. But of course that’s rather general – and not a very precise statement.

    Regards

    Martin

    Comment by Martin Preiss — April 21, 2014 @ 7:49 pm BST Apr 21,2014 | Reply

    • Martin,

      You’ve picked a good direction to follow – the statistics usually tell us everything – but you’ve not gone quite far enough in your choice of statistics to explain what’s happening and what it is about the processing that may make bitmap indexes the cheaper option.

      Comment by Jonathan Lewis — April 22, 2014 @ 1:00 pm BST Apr 22,2014 | Reply

      • another difference I could offer would be: enqueue requests with 3522 (b*tree) to 9 (bitmap). In v$lock I don’t see a corresponding number of changes: just the TX lock for the transaction (mode 6) and tm locks for bowie_kid and bowie_dad (each in mode 3). But if I look at v$enqueue_statistics I see something like 500 additional requests for “DML”, 2700 for “Transaction” and 300 for “Segment High Water Mark” while the rows are inserted (in a test system, 11.2.0.1, no other traffic). So it seems a lot of intermediate locking is taking place – and the picture seems to be less static then I thougth v$lock was telling me.

        Comment by Martin Preiss — April 22, 2014 @ 1:44 pm BST Apr 22,2014 | Reply

        • Martin,

          Looks like you’re using freelist management rather than ASSM or you’d probably have mentioned a few hundred FB enqueues as well.

          If you check the session stats for “leaf node splits” the value will probably be similar to the number of TX enqueues (add in “branch node splits” too). The large number is partly a side effect of the extremely repetitive nature of the data, the cyclic order in which it was inserted, and the fact that you started from an empty table and index.

          Comment by Jonathan Lewis — April 22, 2014 @ 3:07 pm BST Apr 22,2014

  4. Hi Jonathan,

    is it possibile, since you talk about load and not insert, that new extents are created for the index like for data during an Append operation? In this case Oracle does not have to think about concurrency and eventual split of the leafs as with the b-tree.

    Comment by Fabio — April 21, 2014 @ 7:56 pm BST Apr 21,2014 | Reply

    • Fabio,

      A key point that you ALWAYS have to remember when considering index maintenance when compared to table maintenance is that an index entry has to go to the correct position. If you hadn’t highlighted the point that I used the word “load” rather than “insert” I would have suggested that your comment was clearly in error – but since you’ve considered the possibility that the table was empty to start with you comments are heading in the right direction. (In fact, even when the table isn’t empty there’s a difference and a reason why the performance may favour the bitmap index.)

      Comment by Jonathan Lewis — April 22, 2014 @ 12:57 pm BST Apr 22,2014 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 3,990 other followers