Dion Cho – Oracle Performance Storyteller

We are natural born scientists

Function-based Index and Or-Expansion

with 3 comments

Let me show you a sad story I recently hit at OTN forum.

http://forums.oracle.com/forums/message.jspa?messageID=3661603

  1. They are on standard edition.
  2. Standard edition does not support 1) bitmap index and 2) it’s sister index combination.
  3. They rely on the function-based index.
  4. And query is composed of “OR” predicate.
  5. Most of all, they have no direct control on the SQL text. It’s fixed in the software.

Here let me show you why this is a sad story.

1. Create objects.

drop table t1 purge;

create table t1(c1 int, c2 int, c3 int);

insert into t1 
select level, level, level
from dual
connect by level <= 100000;

create index t1_n1 on t1(c1+1);  -- function-based index
create index t1_n2 on t1(c2+1);  -- function-based index
create index t1_n3 on t1(c1);  -- normal index
create index t1_n4 on t1(c2);  -- normal index

exec dbms_stats.gather_table_stats(user, 't1');

2.With index combination enabled, Oracle builds the most efficient execution plan imagineable.

alter session set "_b_tree_bitmap_plans" = true;

explain plan for
select *
from t1
where c1+1 = 1 or c2+1 = 1
;

-------------------------------------------------------------------------------
| Id  | Operation                        | Name  | Rows  | Bytes | Cost (%CPU)|
-------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                 |       |     2 |    48 |     2   (0)|
|   1 |  TABLE ACCESS BY INDEX ROWID     | T1    |     2 |    48 |     2   (0)|
|   2 |   BITMAP CONVERSION TO ROWIDS    |       |       |       |            |
|   3 |    BITMAP OR                     |       |       |       |            |
|   4 |     BITMAP CONVERSION FROM ROWIDS|       |       |       |            |
|*  5 |      INDEX RANGE SCAN            | T1_N1 |       |       |     1   (0)|
|   6 |     BITMAP CONVERSION FROM ROWIDS|       |       |       |            |
|*  7 |      INDEX RANGE SCAN            | T1_N2 |       |       |     1   (0)|
-------------------------------------------------------------------------------
                                                                               
Predicate Information (identified by operation id):                            
---------------------------------------------------                            
                                                                               
   5 - access("C1"+1=1)                                                        
   7 - access("C2"+1=1)                                                        

3. What if the index combination got disabled?

alter session set "_b_tree_bitmap_plans" = false; -- In standard edition, this would be fixed behavior.

explain plan for
select *
from t1
where c1+1 = 1 or c2+1 = 1
;

---------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)|
---------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |     2 |    48 |    99   (6)|
|*  1 |  TABLE ACCESS FULL| T1   |     2 |    48 |    99   (6)|
---------------------------------------------------------------
                                                               
Predicate Information (identified by operation id):            
---------------------------------------------------            
                                                               
   1 - filter("C1"+1=1 OR "C2"+1=1)                            

Table full scan!

4. But with normal indexes, Oracle’s choice is Or-Expansion, which is quite natural and efficient.

explain plan for
select *
from t1
where c1 = 1 or c2 = 1
;

---------------------------------------------------------------------------
| Id  | Operation                    | Name  | Rows  | Bytes | Cost (%CPU)|
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |       |     2 |    30 |     4   (0)|
|   1 |  CONCATENATION               |       |       |       |            |
|   2 |   TABLE ACCESS BY INDEX ROWID| T1    |     1 |    15 |     2   (0)|
|*  3 |    INDEX RANGE SCAN          | T1_N4 |     1 |       |     1   (0)|
|*  4 |   TABLE ACCESS BY INDEX ROWID| T1    |     1 |    15 |     2   (0)|
|*  5 |    INDEX RANGE SCAN          | T1_N3 |     1 |       |     1   (0)|
---------------------------------------------------------------------------
                                                                           
Predicate Information (identified by operation id):                        
---------------------------------------------------                        
                                                                           
   3 - access("C2"=1)                                                      
   4 - filter(LNNVL("C2"=1))                                               
   5 - access("C1"=1)                                                      

5. Okay, maybe Oracle has some logic holes with function-based indexes. Would appropriate hints force the Or-Expansion with function-based indexes?

explain plan for
select 
		/*+
				INDEX_RS_ASC(@"SEL$1_2" "T1"@"SEL$1_2" "T1_N1")
				INDEX_RS_ASC(@"SEL$1_1" "T1"@"SEL$1" "T1_N2")
				USE_CONCAT(@"SEL$1" 8) */
		*
from t1
where c1+1 = 1 or c2+1 = 1
;

----------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)|
----------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     2 |    48 |   195   (4)|
|   1 |  CONCATENATION     |      |       |       |            |
|*  2 |   TABLE ACCESS FULL| T1   |     1 |    24 |    98   (5)|
|*  3 |   TABLE ACCESS FULL| T1   |     1 |    24 |    98   (5)|
----------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter("C2"+1=1)
   3 - filter("C1"+1=1 AND LNNVL("C2"+1=1))

No.

The question is why this is happening. This is well documented here.
http://download.oracle.com/docs/cd/B14117_01/appdev.101/b10795/adfns_in.htm#1006464

Yes, unfortunately, Oracle is not able to use function-based indexes with or expansion. Hence in this case, full table scan is the only option remaining.

6. There are another trick we can try when the SQL text itself is not modifiable. Stored outline. But in this case, even stored outline cannot change the execution plan to use function-based indexes. Mission impossible.

7. The last trick. Oracle 10g supports the feature called advanced query rewriting, which enables us to change the SQL text on the fly. But it has many restrictions.

  • Enterpnrise edition feature.
  • Select stateme only.
  • Bind variable not supported.

Fortunately, my simple and stupid test case can be resolved with this feature.

begin
  sys.dbms_advanced_rewrite.declare_rewrite_equivalence (
     name           => 'rewrite1',
     source_stmt =>
'select *
from t1
where c1+1 = 1 or c2+1 = 1',
    destination_stmt =>
'select *
from t1
where c1 = 0 or c2 = 0',
     validate       => false,
     rewrite_mode   => 'text_match');
end;
/

alter session set query_rewrite_integrity = trusted;

explain plan for
select *
from t1
where c1+1 = 1 or c2+1 = 1
;
        
---------------------------------------------------------------------------
| Id  | Operation                    | Name  | Rows  | Bytes | Cost (%CPU)|
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |       |     2 |    30 |     4   (0)|
|   1 |  CONCATENATION               |       |       |       |            |
|   2 |   TABLE ACCESS BY INDEX ROWID| T1    |     1 |    15 |     2   (0)|
|*  3 |    INDEX RANGE SCAN          | T1_N4 |     1 |       |     1   (0)|
|*  4 |   TABLE ACCESS BY INDEX ROWID| T1    |     1 |    15 |     2   (0)|
|*  5 |    INDEX RANGE SCAN          | T1_N3 |     1 |       |     1   (0)|
---------------------------------------------------------------------------
                                                                           
Predicate Information (identified by operation id):                        
---------------------------------------------------                        
                                                                           
   3 - access("C2"=0)                                                      
   4 - filter(LNNVL("C2"=0))                                               
   5 - access("C1"=0)                                                      

But, this feature would not be easily adopted in the real life. Too many restrictions.

It was a sad story, which made me think about how to control the execution plan of the non-modifiable SQL.

About these ads

Written by Dion Cho

July 31, 2009 at 8:59 am

3 Responses

Subscribe to comments with RSS.

  1. Hi Dion
    Thank you for great explanation.
    So, what is the difference between case 4 and this transformation done in the last step (step 7).
    If I have b tree indexes on c1 and c2 columns, they would be used wheter I am in SE or EE. The index is not being used in 7 because we have a function based index. It still is not using Function based index. It is working because a normal b tree index is usable in this case
    But the point here I think is that, if you have a regular b tree index and you cannot use function based index because of several restrictions, you can force the sql to use regular b tree indexes instead of a full table scan.
    I think even if you are on EE , because of the restrictions on Function based index, the index would probably not be usable even in the case reported by the actual user.

    Is this right ?

    Thank you
    -Kumar

    Kumar

    August 3, 2009 at 4:48 pm

    • Kumar.

      > if you have a regular b tree index and you cannot use function based index because of several restrictions, you can force the sql to use regular b tree indexes instead of a full table scan.
      Yes, absolutely. But in the above case, they had no direct control on the source code.

      > I think even if you are on EE , because of the restrictions on Function based index, the index would probably not be usable even in the case reported by the actual user.
      Right. Even EE can’t use function-based index with OR expansion, but Oracle has an alternative called index combination. Index combination would convert (btree) function-based index into in-memory bitmap and would combine the bitmaps. So there is no need to use OR expansion.

      Dion Cho

      August 4, 2009 at 4:57 am

  2. [...] Dion Cho- Function-based Index and Or-Expansion [...]


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

Follow

Get every new post delivered to your Inbox.

Join 61 other followers

%d bloggers like this: