CBQT-ORE and its FIRST_ROWS optimization inability

Terminology:

CBQT: cost based query transformation
ORE: or expansion

Some days ago, I took a look on a customer’s performance issue which was introduced after their upgrade from 12.1 to 19c. Quite fast we could narrow it down to a new optimizer feature „cost based or expansion“.

To get a basic understanding of the feature, I’ll recommend reading Optimizer Transformations: OR Expansion by Oracle’s CBO PM Nigel Bayliss.

As a quick fix we simply disabled the feature by setting „_optimizer_cbqt_or_expansion“ = off and the performance went back to good again.

Afterwards I wanted to understand the root cause and built a model to reproduce the problem.

rem ######################################
rem # set environment                    #
rem ######################################
alter session set statistics_level=ALL;

rem ######################################
rem # prophylactic cleanup               #
rem ######################################
drop table asc_t2;
drop table asc_t1;
drop table asc_t3;

rem ######################################
rem # create testdata                    #
rem ######################################

--will hold 1M rows with a unique ID
create table asc_t1
as
with gen as
(
   select rownum dummy from dual connect by level <= 1e4
)
select rownum id
  from gen, gen
 where rownum <= 1e6;

--will hold 1M rows with 500 distinct values of T1_ID (20000 records per value)
create table asc_t2
as
select id, mod(id, 500) t1_id, lpad('*', 250, '*') pad
  from asc_t1;

--will hold 1M rows with 500 distinct values of T1_ID (20000 records per value)
create table asc_t3
as
select id, t1_id, pad
  from asc_t2;

--indexes
create unique index asc_t1_uk on asc_t1 (id);
create unique index asc_t2_uk on asc_t2(id);
create index asc_t2_i1 on asc_t2(t1_id);
create unique index asc_t3_uk on asc_t3(id);
create index asc_t3_i1 on asc_t3(t1_id);

And this is the query to be examined:

select t1.*
  from asc_t1 t1
 where id between 1 and 10
   and exists (select 1
                 from asc_t2 t2, asc_t3 t3
                where t2.id = t3.id
                  and (t2.t1_id = t1.id or t3.t1_id = t1.id)
              );

With no hints or further parameters set, this is the plan including some rowsource execution statistics pulled from memory after its execution:
So at first we can see that ORE was used and the query was split into two disjunct union all branches. What’s really interesting for me at a first sight is the presence of a blocking operation in the VW_ORE block (HASH JOIN at ID 4), despite the fact it is called in an exists clause and therefore has the ability to leave after the first row is found.

So for each row we got from ASC_T1 an in-memory hash table was build after scanning the appropriate index on T2 and visiting the table block (IDs 6 and 5).  In total 20.000 rows on 20.078 buffers were read on these operations. After that index ASC_T3_UK was probed against that hash table and here we see the effects of “exists” very cleary:  despite the index contains 1 million entries just 55 rows over all 10 calls needed to be read to find a first match and therefore be able to quit, because the exists clause was fulfilled. The second union-all branch wasn’t called at all.

Let’s look at two more examples.

First: forbid CBQT-ORE from kicking in.

select t1.*
  from asc_t1 t1where id between 1 and 10 
 and exists (select /*+ no_or_expand */1 
                          from asc_t2 t2, asc_t3 t3 
                        where t2.id = t3.id 
                              and (t2.t1_id = t1.id or t3.t1_id = t1.id) 
                            );

And its rowsource execution statistics:
It has got a much lesser cost than the ORE plan and much less buffers were visited to execute the query. It gives also the impression that the CBO is now aware that it has to deal with an “exists” clause here, because that part of the plan was optimized to find a first matching row very quickly. E.g low cost for the FTS on ASC_T2 or the absence of blocking operations are indicators for this strategy.

Second: Switch back to LORE (Legacy OR Expansion)

select /*+ opt_param('_optimizer_cbqt_or_expansion', 'off') */ t1.* 
  from asc_t1 t1 
 where id between 1 and 10 
    and exists (select 1 
                             from asc_t2 t2, asc_t3 t3 
                          where t2.id = t3.id 
                                and (t2.t1_id = t1.id or t3.t1_id = t1.id) 
                            );

Again rowsource execution statistics:
This one now shows the lowest cost and least buffers visited overall. It also seems to be aware of the exists clause and adapts a first_rows strategy in the relevant parts of the execution plan! This is basically what I would have expected from the CBQT-ORE.

So we now have a theory that CBQT-ORE loses track that its query block is called in an “exists” clause and provides an execution plan as if it was a standalone query, where it would need to fetch all the rows.

There’s some more evidence to this theory.

1.) The transformed query from the VW_ORE query block shows the same cost and execution plan when it is costed as a standalone query. The correlated value from the outer rowsource was replaced with a bind variable in the following example:

select 0
  from (
             select 1
                 from asc_t3 t3, asc_t2 t2
              where t2.id = t3.id and t2.t1_id = :b1
            union all
           select 1
               from asc_t3 t3, asc_t2 t2
            where t2.id = t3.id      
                 and t3.t1_id = :b1 
                 and lnnvl (t2.t1_id = :b1)
              );

generates this plan, which matches the “VW_ORE_82971ECB” from our first query.

2.) The 10053 traces for both the disabled CBQT-ORE and the old-style OR-Expansion (LORE) show lots of references that a first_rows optimization approach was chosen for the query blocks in question.

Like:

On the other hand when looking at the 10053 trace of the first query, interestingly before the ORE checks kicked in, the same plan was already found which was used in query 2, where I explicitly disabled the transformation.

Final cost for query block SEL$2 (#2) – First K Rows Plan:
  Best join order: 1
  Cost: 506.142990  Degree: 1  Card: 2.000000  Bytes: 71964.000000
  Resc: 506.142990  Resc_io: 506.000000  Resc_cpu: 4233492
  Resp: 506.142990  Resp_io: 506.000000  Resc_cpu: 4233492

Later in the same tracefile, the ORE transformation and costing was performed and produced a final cost (8591) which was (way) higher than the formerly calculated plan with a final cost of 506. But however at the end it was not picked and the CBO stayed with the cheapest ORE-plan.

Summary:
CBQT-ORE does not seem to be aware when its query block resides in an “exists” clause and therefore doesn’t optimize for first rows access patterns. The query block gets optimized as if all rows would be needed to fetch. Additionally in certain scenarios it seems to “forget” if cheaper plans were found during the whole optimization process. If this effects you in a negative way, as a first action the cost based transformation can be turned off and the legacy version used instead. Additionally an SR was raised to tackle this issue.

Further Reading:
Excellent articles on the topic of CBQT Or-Expansion can also be found on the blogs of Patrick Joliffe, Mohamed Houri and Nenad Noveljic

Update 1:
After playing with the same testcase in my 21c lab I noticed the that the problem went away. After quick look into v$system_fix_control I found bug 28414968 “expansion with some constant branches;fkr1 in (NOT)EXISTS subque” which is first available in 19.11 and has to be activated proactively. That plan now gets produced in in 21c and after setting alter session set „_fix_control“=’28414968:3′; in >=19.11
10 buffers less visited compared to the LORE plan, as ID 8 was superfluous in the LORE plan.

Funnily, if I code the union-all instead of the or-predicate myself, I still get the old plan. But that’s one topic for another post I guess.

select t1.id id
  from demo.asc_t1 t1
 where t1.id >= 1
   and t1.id <= 10
   and exists (select 0
                            from demo.asc_t3 t3, demo.asc_t2 t2
                         where t2.id = t3.id
                               and t2.t1_id = t1.id 
                         union all
                         select 1
                             from demo.asc_t3 t3, demo.asc_t2 t2
                          where t2.id = t3.id
                                and t3.t1_id = t1.id
                                and lnnvl (t2.t1_id = t1.id)
                            );