Oracle Scratchpad

February 8, 2007

Index Combine

Filed under: CBO,Execution plans,Indexing,Tuning — Jonathan Lewis @ 7:52 pm GMT Feb 8,2007

Someone recently asked the following question:

I have two tables, t1 and t2, and a query of the following form:

Since there are two indexes on table t2, is it possible to make Oracle use its bitmap conversion method to do a nested loop from t1 to t2 ?

select
	t1.colX, t2.colY
from
	t1, t2
where
	t1.n1 = {constant}
and	t2.b1 = t1.n2
and	t2.b2 = {constant}
;

There are B-tree indexes defined on t1(n1), t2(b1), and t2(b2).

At first sight you may think that the answer is no because (a) the only descriptions of the bitmap conversion that get published seem to involve accessing a single table, and (b) the mental image that usually goes with the nested loop join involves using a range (or unique) scan on a single B-tree index.

However, if you think about how the optimiser does its calculations, you will realise that the answer ought to be yes; and you should also be able to create a test case that checks whether or not the answer really is yes.

When working out the cost of joining tables, the optimizer sets up each possible “join order” for the tables in turn (though it rarely goes through the complete set of possibilities) and works out the cost of joining the tables in that order.

To work out a single join order of “N” tables, the optimizer works out the cost of joining the first “N-1″ tables and then works out the cost of joining the Nth table to the intermediate result. Of course, if Oracle has already joined the “N-1″ tables, any join predicates to the Nth table can become access predicates (of unknown value – hence equivalent to bind variables) at that point in the calculation because at run-time the actual values from the previous tables will be known before you access the next table. So, in theory, any single table access method can be a join access method.

You may recall I wrote a note about a problem that someone was having with the index skip scan hint, and followed it up with a note on my website about the resulting 10053 trace file concluding with a comment that I believed I had identified a bug because the index skip scan was a “single table access path” that was not considered as an option during a nested loop join.

So, all I have to do to answer the original question is set up a nested loop join, forcing a bitmap conversion into the second table. Here’s the first attempt I made at writing some SQL to do this:

drop table t2;
drop table t1;   

create table t1
as
select
	mod(rownum,1000)	n1,
	mod(rownum,1000)	n2,
	rpad('x',100)
		padding
from
	all_objects
where
	rownum <= 3000
;   

create table t2
as
select
	mod(rownum,50)		b1,
	mod(rownum,50)		b2,
	rpad('a',10)		small_vc,
	rpad('x',100)		padding
from
	all_objects
where
	rownum <= 3000
;   

create index t1_n1 on t1(n1);   

rem
rem	Create two indexes on the second table
rem	One for the join predicate, a "spare"
rem	to see if we can get the bitmap conversion
rem   

create index t2_b1 on t2(b1);
create index t2_b2 on t2(b2);   

rem     Gather Statistics at this point.   

select
	/*+
		ordered
		use_nl(t2)
		index_combine(t2 t2_b1 t2_b2)
	*/
	t1.n2, t2.small_vc
from
	t1, t2
where
	t1.n1 = 500
and	t2.b1 = t1.n2
and	t2.b2 = 20
;   

set autotrace off   

The index_combine() hint tells Oracle to consider any combination of the listed indexes as candidates for doing a B-tree/Bitmap conversion. This results in the following execution plan (10gR2 style, although the script produces the same plan on 9i and 8i):

Execution Plan
----------------------------------------------------------
Plan hash value: 3267785842  

-------------------------------------------------------------------------------------------
| Id  | Operation                         | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                  |       |     5 |   125 |    19   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID      | T2    |     2 |    34 |    19   (0)| 00:00:01 |
|   2 |   NESTED LOOPS                    |       |     5 |   125 |    19   (0)| 00:00:01 |
|   3 |    TABLE ACCESS BY INDEX ROWID    | T1    |     3 |    24 |     4   (0)| 00:00:01 |
|*  4 |     INDEX RANGE SCAN              | T1_N1 |     3 |       |     1   (0)| 00:00:01 |
|   5 |    BITMAP CONVERSION TO ROWIDS    |       |       |       |            |          |
|   6 |     BITMAP AND                    |       |       |       |            |          |
|   7 |      BITMAP CONVERSION FROM ROWIDS|       |       |       |            |          |
|*  8 |       INDEX RANGE SCAN            | T2_B2 |    60 |       |     1   (0)| 00:00:01 |
|   9 |      BITMAP CONVERSION FROM ROWIDS|       |       |       |            |          |
|* 10 |       INDEX RANGE SCAN            | T2_B1 |    60 |       |     1   (0)| 00:00:01 |
-------------------------------------------------------------------------------------------  

Predicate Information (identified by operation id):
---------------------------------------------------
   4 - access("T1"."N1"=500)
   8 - access("T2"."B2"=20)
  10 - access("T2"."B1"="T1"."N2")

9 Comments »

  1. ….getting up to speed on how to use the hints and they work magic; I’m becoming fond of the “materialize” one…. seems to be pretty good for our purpose…

    perhaps someone ought to write a book (when he’s not writing other books!) on how to use the hints more properly, how to use them in combination, for maximum efficiency! the manuals do a good job of listing them, but a poor one on exactly how and why to use them in tandem ;-)

    cheers,
    Cos

    Comment by Cos — February 9, 2007 @ 4:25 am GMT Feb 9,2007 | Reply

  2. Thanks Jonathan, not a HINT I’d considered evaluating before (as a result of ignorance more than anything else). Well worth the knowing.

    Comment by SeanMacGC — February 9, 2007 @ 11:20 am GMT Feb 9,2007 | Reply

  3. I had the good fortune to work with you while you were consulting at The Hartford in Hartford, CT a few years ago. We had a brief conversation about Btree Bitmap conversion plans that were showing up as we moved from 8.1.7 to 9i. We eventually set _b_tree_bitmap_plans=false since the performance of every query with a Bitmap plan was pretty bad. In your experience, what kind of SQL benefits from Bitmap conversions?

    Comment by Chuck — February 10, 2007 @ 6:39 pm GMT Feb 10,2007 | Reply

  4. Chuck, good question. In the early versions of 9i it looked as if the arithmetic had an accidental bias that produced bitmap conversions too frequently. I haven’t checked back to 9.0, but in 9.2 there is a “fudge factor” of 1.1 that increases the cost of bitmap plans. It’s possible that this was to address the early problems.

    These plans can be very effective on systems which have lots of single-column B-tree indexes that don’t happen to be very effective access paths but which can be combined to identify just a few rows in the table.

    In some ways, it’s a “damage limitation” path, rather than a path you would usually design into the system. If you can change index definitions easily, you would probably choose to introduce some enhanced B-tree indexes rather than pushing queries into the bitmap conversion.

    Comment by Jonathan Lewis — February 10, 2007 @ 7:41 pm GMT Feb 10,2007 | Reply

  5. Jonathan, if I understand correctly – row source operations from 5 to 10 will be restarted for every value that comes “out” of 3, is that correct ?
    Thanks in advance of course.

    Comment by Alberto Dell'Era — February 10, 2007 @ 7:59 pm GMT Feb 10,2007 | Reply

  6. Alberto, that is correct. That is the implication of the nested loop, rather than having anything to do with this particular use of indexes though.

    Comment by Jonathan Lewis — February 11, 2007 @ 7:20 pm GMT Feb 11,2007 | Reply

  7. Jonathan,
    In reply to Chuck, you said,
    “If you can change index definitions easily, you would probably choose to introduce some enhanced B-tree indexes rather than pushing queries into the bitmap conversion.”

    I searched on internet but could not find any info on enhanced B-tree indexes. Can you please explain about it.

    Thanks

    Comment by Sreenivas — September 23, 2007 @ 4:24 pm GMT Sep 23,2007 | Reply

  8. Sreenivas,
    I can see how easy it was to mis-interpret my comment, but there’s no such technology labelled “enhanced B-tree indexes”.

    All I meant was that Chuck should take his current set of indexes and work out how best to improve the set by doing things like adding columns, changing column orders, and compression.

    Comment by Jonathan Lewis — September 23, 2007 @ 4:39 pm GMT Sep 23,2007 | Reply

  9. [...] Lewis还有另外一篇关于index Combine的文章 [...]

    Pingback by 关于index_equal index_join index_combine » a db thinker's home — January 28, 2010 @ 5:12 pm GMT Jan 28,2010 | 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

Theme: Rubric. Get a free blog at WordPress.com

Follow

Get every new post delivered to your Inbox.

Join 4,308 other followers