Oracle introduced cost based OR-expansion (ORE) in 12.2, and then significantly enhanced it in 19c to include subqueries [1]. But this improvement doesn’t work for my old test case . As it turned out, undocumented heuristics and a bug prevent the transformation.
Here’s what I learned.
Data
drop table t_large ;
drop table t_small ;
create table t_large ( id number , a number not null ) ;
create table t_small ( b number , c number ) ;
insert into t_large
SELECT level,level
FROM dual
CONNECT BY level <= 1000000;
insert into t_small values (1,1) ;
insert into t_small values (2,2) ;
commit ;
exec dbms_stats.gather_table_stats(null, 'T_LARGE');
exec dbms_stats.gather_table_stats(null, 'T_SMALL');Unnesting without ORE
I’ll start this demo with subquery unnesting (SU), which is a prerequisite for ORE:
Query A
select /*+ qb_name(main) */ a from t_large l
where id in ( select /*+ qb_name(sbq) */ b from t_small s );---------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 576 (100)| |
|* 1 | HASH JOIN RIGHT SEMI| | 2 | 46 | 576 (3)| 00:00:01 |
| 2 | VIEW | VW_NSO_1 | 2 | 26 | 2 (0)| 00:00:01 |
| 3 | TABLE ACCESS FULL | T_SMALL | 2 | 6 | 2 (0)| 00:00:01 |
| 4 | TABLE ACCESS FULL | T_LARGE | 1000K| 9765K| 569 (2)| 00:00:01 |
---------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("ID"="B")SU is, expectedly, a cost based decision:
SU: Passed validity checks, but requires costing.SU opens up new possibilities for the optimizer when searching for an optimal plan.
FILTER without ORE
Without SU, the optimizer generates an inferior plan with FILTER:
Query B (no_unnest hint added to the Query A)
select /*+ qb_name(main) */ a from t_large l
where id in ( select /*+ no_unnest qb_name(sbq) */ b from t_small s );------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 1979K(100)| |
|* 1 | FILTER | | | | | |
| 2 | TABLE ACCESS FULL| T_LARGE | 1000K| 9765K| 570 (2)| 00:00:01 |
|* 3 | TABLE ACCESS FULL| T_SMALL | 1 | 3 | 2 (0)| 00:00:01 |
------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter( IS NOT NULL)
3 - filter("B"=:B1)The subquery runs for every row returned by the main query [2]. The total cost, therefore, can be calculated as follows :
Cost of acquiring data in the main query + Cardinality of result from the main query * Cost of single subquery execution = 570 + 10^6 * 2 = 2 * 10^6 [3]
The subquery execution is performance killer.
FILTER with ORE
After adding an OR operand to the query A, optimizer, surprisingly, doesn’t unnest anymore, and generates a plan with FILTER.
Query C (OR added to the query A)
select /*+ qb_name(main) */ a from t_large l where id in
( select /*+ qb_name(sbq) */ b from t_small s )
or a = 1 ;
------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 572 (100)| |
|* 1 | FILTER | | | | | |
| 2 | TABLE ACCESS FULL| T_LARGE | 1000K| 9765K| 572 (3)| 00:00:01 |
|* 3 | TABLE ACCESS FULL| T_SMALL | 1 | 3 | 2 (0)| 00:00:01 |
------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter(("A"=1 OR IS NOT NULL))
3 - filter("B"=:B1)The cost wrongly slumped from 1979K to 572, because the subquery execution isn’t factored in in the total cost anymore. Consequently, that cost is severely underestimated.
Indexing driving table
ORE was bypassed due to missing indexes on the driving table:
ORE: Bypassed for disjunct chain: No Index or Partition driver found(“Disjunct chain” is a synonym for OR operands.)
As we can see, the ORE decision isn’t entirely cost based – the optimizer rejects the transformation if the OR operands aren’t indexed.
The “ORE: Bypassed…” message disappeared after creating the following index on t_large.a:
create index i_t_large_1 on t_large(a);Yet the plan didn’t change. The index above is necessary but not sufficient.
Reducing ORE cost
Now I’m enforcing ORE with the hint.
Query D (or_expand hint added to the Query C)
select /*+ qb_name(main) or_expand(@main) */ a from t_large l
where id in ( select /*+ qb_name(sbq) */ b from t_small s )
or a = 1 ;------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 581 (100)| |
| 1 | VIEW | VW_ORE_48C33071 | 3 | 39 | 581 (3)| 00:00:01 |
| 2 | UNION-ALL | | | | | |
|* 3 | INDEX RANGE SCAN | I_T_LARGE_1 | 1 | 5 | 3 (0)| 00:00:01 |
|* 4 | HASH JOIN RIGHT SEMI| | 2 | 46 | 578 (3)| 00:00:01 |
| 5 | VIEW | VW_NSO_1 | 2 | 26 | 2 (0)| 00:00:01 |
| 6 | TABLE ACCESS FULL | T_SMALL | 2 | 6 | 2 (0)| 00:00:01 |
|* 7 | TABLE ACCESS FULL | T_LARGE | 999K| 9765K| 571 (2)| 00:00:01 |
------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("A"=1)
4 - access("ID"="B")
7 - filter(LNNVL("A"=1))The ORE cost is slightly higher than the miscalculated FILTER cost, so we have to reduce it. The following index eliminates the expensive full table scan on t_large:
create index i_t_large_2 on t_large(id)The plan for the query D (with or_expand hint) indeed became much more efficient:
--------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 12 (100)| |
| 1 | VIEW | VW_ORE_48C33071 | 3 | 39 | 12 (9)| 00:00:01 |
| 2 | UNION-ALL | | | | | |
|* 3 | INDEX RANGE SCAN | I_T_LARGE_1 | 1 | 5 | 3 (0)| 00:00:01 |
| 4 | NESTED LOOPS | | 2 | 46 | 9 (12)| 00:00:01 |
| 5 | NESTED LOOPS | | 2 | 46 | 9 (12)| 00:00:01 |
| 6 | VIEW | VW_NSO_1 | 2 | 26 | 2 (0)| 00:00:01 |
| 7 | HASH UNIQUE | | 2 | 6 | | |
| 8 | TABLE ACCESS FULL | T_SMALL | 2 | 6 | 2 (0)| 00:00:01 |
|* 9 | INDEX RANGE SCAN | I_T_LARGE_2 | 1 | | 2 (0)| 00:00:01 |
|* 10 | TABLE ACCESS BY INDEX ROWID| T_LARGE | 1 | 10 | 3 (0)| 00:00:01 |
--------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("A"=1)
9 - access("ID"="B")
10 - filter(LNNVL("A"=1))That’s clearly a better plan, but optimizer rejects it. But, why?
Unique constraint on the table in the subquery
The reason is recorded in the trace file:
ORE: Checking validity of OR Expansion for query block SBQ (#2)
ORE: Predicate chain before QB validity check - SBQ
:B1="S"."B"
ORE: Predicate chain after QB validity check - SBQ
:B1="S"."B"
ORE: bypassed - No valid predicate for OR expansion.“No valid predicate for OR expansion”, wrote optimizer. “Which predicate isn’t valid; and why?”, I wondered.
Just couple of lines above…
ORE: applying simple unnesting on interleaved qb.
SU: Transform an ANY subquery to semi-join or distinct.
Registered qb: SEL$397D8923 0x8485cfb0 (SUBQ INTO VIEW FOR COMPLEX UNNEST SEL$7DA70B07)The subquery was converted to semi-join (as opposed to join), because the correlated column in the subquery isn’t unique.
Will ORE work with a unique constraint?
create unique index i_t_small_1 on t_small(b);It will!
--------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 9 (100)| |
| 1 | VIEW | VW_ORE_48C33071 | 3 | 39 | 9 (0)| 00:00:01 |
| 2 | UNION-ALL | | | | | |
|* 3 | INDEX RANGE SCAN | I_T_LARGE_1 | 1 | 5 | 3 (0)| 00:00:01 |
| 4 | NESTED LOOPS | | 2 | 26 | 6 (0)| 00:00:01 |
| 5 | NESTED LOOPS | | 2 | 26 | 6 (0)| 00:00:01 |
| 6 | INDEX FULL SCAN | I_T_SMALL_1 | 2 | 6 | 1 (0)| 00:00:01 |
|* 7 | INDEX RANGE SCAN | I_T_LARGE_2 | 1 | | 2 (0)| 00:00:01 |
|* 8 | TABLE ACCESS BY INDEX ROWID| T_LARGE | 1 | 10 | 3 (0)| 00:00:01 |
--------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("A"=1)
7 - access("ID"="B")
8 - filter(LNNVL("A"=1))Summary
Cost based ORE of disjunctive subqueries is a huge improvement in 19c. But the decision isn’t entirely cost based. The optimizer has heuristics which can unnecessarily rule out a good plan.
I discovered the following requirements:
- The uncorrelated OR operands must be indexed.
- The correlated column in the subquery must be unique.
“ORE: bypass” and “ORE: Bypass” trace entries indicate that optimizer didn’t consider the transformation.
Miscalculated FILTER cost is another reason for rejecting ORE. In addition, underestimated FILTER cost pervades all the parent operations, which can cause havoc in larger execution plans.
What can you do?
Reduce ORE cost as a workaround for the FILTER costing bug. If that doesn’t help, enforce ORE with the or_expand hint.
References
[1] Jonathan Lewis, Subquery with OR. August 20, 2020.
[2] Maria Colgan, Optimizer Transformations: Subquery Unnesting part 1. September 15, 2010.
[3] Jonathan Lewis, Cost-Based Oracle Fundamentals. 2006.
