Dion Cho – Oracle Performance Storyteller

We are natural born scientists

Posts Tagged ‘function based index

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.

Written by Dion Cho

July 31, 2009 at 8:59 am

Function based index and suspicious filter predicates

with 3 comments

One of my customers sent a very interesting question.

1. See following result, especially with attention to the filter predicate for the index range scan.

drop table t1 purge;

create table t1 (
	c1 varchar2(10),
	c2 varchar2(10),
	c3 varchar2(10),
	c4 varchar2(10),
	c5 varchar2(10)
);

insert into t1
select mod(level, 2), mod(level, 2), mod(level, 2), mod(level, 2), level
from dual 
connect by level <= 1000
;

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

create index t1_n1 on t1(c1, c2, nvl(c3,'x'), c4);
  
explain plan for
select /*+ index(t1 t1_n1) */
    *   
from t1 
where c1 = :b1 and c2 = :b2 and nvl(c3,'x') >= :b3 and c4 = :b4 and c5 = :b5
;

--------------------------------------------------------------------------
| Id  | Operation                   | Name  | Rows  | Bytes | Cost (%CPU)|
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |       |     1 |    11 |     3   (0)|
|*  1 |  TABLE ACCESS BY INDEX ROWID| T1    |     1 |    11 |     3   (0)|
|*  2 |   INDEX RANGE SCAN          | T1_N1 |     4 |       |     2   (0)|
--------------------------------------------------------------------------
                                                                           
Predicate Information (identified by operation id):                        
---------------------------------------------------                        
                                                                           
   1 - filter("C5"=:B5)                                                    
   2 - access("C1"=:B1 AND "C2"=:B2 AND NVL("C3",'x')>=:B3 AND "C4"=:B4 AND
              NVL("C3",'x') IS NOT NULL)                                   
       filter("C4"=:B4)                                                    

So far so good. Because the preceding condition is range predicate(NVL(“C3″,’x’)>=:B3), “C4″=:B4 condition is used as the filter predicate.

2. Now I create the 2nd function index. Do you notice the very suspicious filter predicate appended? – SUBSTR(“T1″.”C4″,1,3)=SUBSTR(:B4,1,3). And by virtue of this predicate, the estimated cardinality got down from 4 to 1.

create index t1_n2 on t1(c1, c2, substr(c4,1,3));  -- Note on substr(c4,1,3)!

explain plan for
select /*+ index(t1 t1_n1) */
    *   
from t1 
where c1 = :b1 and c2 = :b2 and nvl(c3,'x') >= :b3 and c4 = :b4 and c5 = :b5
;

--------------------------------------------------------------------------
| Id  | Operation                   | Name  | Rows  | Bytes | Cost (%CPU)|
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |       |     1 |    11 |     3   (0)|
|*  1 |  TABLE ACCESS BY INDEX ROWID| T1    |     1 |    11 |     3   (0)|
|*  2 |   INDEX RANGE SCAN          | T1_N1 |     1 |       |     2   (0)|
--------------------------------------------------------------------------
                                                                           
Predicate Information (identified by operation id):                        
---------------------------------------------------                        
                                                                           
   1 - filter("C5"=:B5)                                                    
   2 - access("C1"=:B1 AND "C2"=:B2 AND NVL("C3",'x')>=:B3 AND "C4"=:B4 AND
              NVL("C3",'x') IS NOT NULL)                                   
       filter("C4"=:B4 AND SUBSTR("T1"."C4",1,3)=SUBSTR(:B4,1,3))          

SUBSTR(“T1″.”C4″,1,3)=SUBSTR(:B4,1,3) predicate? Where does this predicate come from? Why does Oracle use the expression in the 2nd index while using the 1st index?

You might already know the answer – function based index generates hidden column!

3. Diff on the 10053 traces shows the best readibility on this problem.

-- With 1 function index				    -- With 2 function indexes
SINGLE TABLE ACCESS PATH                      | SINGLE TABLE ACCESS PATH                            
  Column (#1): C1(VARCHAR2)                   |   Column (#1): C1(VARCHAR2)                         
    AvgLen: 10.00 NDV: 0 Nulls: 0 Density: 0.0|     AvgLen: 10.00 NDV: 0 Nulls: 0 Density: 0.0000e+0
  Column (#2): C2(VARCHAR2)                   |   Column (#2): C2(VARCHAR2)                         
    AvgLen: 10.00 NDV: 0 Nulls: 0 Density: 0.0|     AvgLen: 10.00 NDV: 0 Nulls: 0 Density: 0.0000e+0
  Column (#4): C4(VARCHAR2)                   |   Column (#7): SYS_NC00007$(VARCHAR2)  NO STATISTICS
    AvgLen: 10.00 NDV: 0 Nulls: 0 Density: 0.0|     AvgLen: 6.00 NDV: 0 Nulls: 0 Density: 0.0000e+00
  Column (#5): C5(VARCHAR2)                   |   Column (#4): C4(VARCHAR2)                         
    AvgLen: 10.00 NDV: 0 Nulls: 0 Density: 0.0|     AvgLen: 10.00 NDV: 0 Nulls: 0 Density: 0.0000e+0
  Column (#6): SYS_NC00006$(VARCHAR2)  NO STAT|   Column (#5): C5(VARCHAR2)                         
    AvgLen: 10.00 NDV: 0 Nulls: 0 Density: 0.0|     AvgLen: 10.00 NDV: 0 Nulls: 0 Density: 0.0000e+0
  Table: T1  Alias: T1                        |   Column (#6): SYS_NC00006$(VARCHAR2)  NO STATISTICS
    Card: Original: 0  Rounded: 1  Computed: 0|     AvgLen: 10.00 NDV: 0 Nulls: 0 Density: 0.0000e+0
kkofmx: index filter:                         |   Table: T1  Alias: T1                              
			"T1"."C4"=:B1 AND                 |     Card: Original: 0  Rounded: 1  Computed: 0.00  N
			"T1"."C5"=:B2 AND                 | kkofmx: index filter:                               
			NVL("T1"."C3",'x')>=:B3           | 		SUBSTR("T1"."C4",1,3)=SUBSTR(:B1,1,3) AND       
  Access Path: index (IndexOnly)              | 		"T1"."C4"=:B2 AND "T1"."C5"=:B3 AND             
    Index: T1_N1                              | 		NVL("T1"."C3",'x')>=:B4                         
    resc_io: 0.00  resc_cpu: 200              | kkofmx: index filter:                               
    ix_sel: 9.0000e-007  ix_sel_with_filters: | 		"T1"."C4"=:B1 AND                               
    Cost: 0.00  Resp: 0.00  Degree: 1         | 		"T1"."C5"=:B2 AND                               
  Best:: AccessPath: IndexRange  Index: T1_N1 | 		NVL("T1"."C3",'x')>=:B3                         
         Cost: 0.00  Degree: 1  Resp: 0.00  Ca|   Access Path: index (IndexOnly)                    
                                              |     Index: T1_N1                                    
                                              |     resc_io: 0.00  resc_cpu: 200                    
                                              |     ix_sel: 9.0000e-007  ix_sel_with_filters: 9.0000
                                              |     Cost: 0.00  Resp: 0.00  Degree: 1               
                                              |   Best:: AccessPath: IndexRange  Index: T1_N1       
                                              |          Cost: 0.00  Degree: 1  Resp: 0.00  Card: 0.
                                              | 
                        

With the 2nd function index, hidden column SYS_NC00007$(SUBSTR(“T1″.”C4″,1,3)) was generated. And this hidden column is used in the predicate because the 1st index includes the real column of the hidden column.

This phenemon would have no problem in general, but the lowered cardinality would cause unwanted result under specific situation.

And Oracle has the kindness to show how exactly it generates the index filter – the power of 10053 trace.

Footnote1: Another interesting info from above 10053 trace is that hidden column doesn’t have any statistics. While Oracle 10g automatically gather statistics with index creation(rebuild), it does not gather statistics for the hidden column.

Written by Dion Cho

July 30, 2009 at 6:06 am

Follow

Get every new post delivered to your Inbox.

Join 59 other followers