Or expansion: Linear

PREAMBLE

In the previous article, we discussed the two-pass technique used by Oracle to evaluate the cost of the different OR-Expansion states. We have shown that this technique evaluates the cost of only two states, the initial NT state, and the FORE state. We have demonstrated as well that this strategy is used by Oracle whenever the number of conjuncts (aka OR operands) equals 2 or is greater or equal to 5. In this article, we will examine the so-called Linear technique. We will show that this technique is used when the number of OR operands equals to 3 or 4. We will also demonstrate that, under this strategy, Oracle might EXPAND the NT or FUSE the FORE. The former is when the cost of the NT is less than that of the FORE while the latter takes place in the opposite situation. We will also show that, although the or-expansion strategy obeys the Stirling number of the second kind, Oracle has, nevertheless, implemented safeguards to prevent this number from exploding. For example, we will show that when the FORE is FUSED, Oracle will evaluate S(n,k) iterations where k ranges from 1 to n-1. However, the order of the conjunctions (the order in which the FORE has been costed) cannot be permuted. This will implicitly cap the value of S(n,k). Finally, we will also see that when Oracle decides to EXPAND the NT, although the permutation of states is possible, the maximum number of states cannot exceed n+2.

LINEAR TECHNIQUE

Since we’ve demonstrated in the previous article that the two-pass technique is reserved for a DNF having m number of conjuncts where m =2 or m >=5, let’s then analyze a DNF of 3 and 4 conjuncts respectively:

alter session set tracefile_identifier='3Ored';
@53on
select 
   *
from
   t1
where
   (n1 =1          -- conjunct n°1
      or n2  = 42  -- conjunct n°2
      or vc1 ='20' -- conjunct n°3
    );
@53off

egrep "ORE: Using search type|conjunction chain|Switching" ORCLCDB_ora_16232_3Ored.trc 

ORE: Using search type: linear
ORE: # conjunction chain – 3

Notice that Oracle did start by considering the linear technique in order to explore the different or-expansion states, and did not switch, this time, to the two-pass technique contrary to what we observed in the previous article.

egrep "ORE: Switching to|state space|Updated best state|Not update best state|conjunction chain" ORCLCDB_ora_16232_3Ored.trc

ORE: # conjunction chain - 3
ORE: Starting iteration 1, state space = [{ 1 2 3 }]
ORE: Updated best state, Cost = 4.046110
ORE: Starting iteration 2, state space = [{ 1 }]
ORE: Updated best state, Cost = 1.000055
ORE: Starting iteration 2, state space = [{ 2 }]
ORE: Updated best state, Cost = 2.000095
ORE: Starting iteration 2, state space = [{ 3 }]
ORE: Updated best state, Cost = 3.000134
ORE: Starting iteration 3, state space = [{ 1 }]
ORE: Updated best state, Cost = 1.000055
ORE: Starting iteration 3, state space = [{ 2 3 }]
ORE: Not update best state, Cost = 3.023117
ORE: Starting iteration 4, state space = [{ 1 2 }]
ORE: Not update best state, Cost = 3.034589
ORE:   Transferring best state space to preserved query.
ORE:   Transferring best state space to original query.

From the above trace file, we can see that Oracle has explored 4 iterations for a DNF of 3 conjunctions.

•	The NT state[{ 1 2 3 }]
•	The FORE  state [{ 1 }] or [{ 2 }]or [{ 3 }]
•	[{ 1 }] or [{ 2 3 }]
•	[{ 1 2 }] or [{ 3 }]

However, should Oracle used the Stirling number to explore all possible combinations it would have then have considered S(3,k) iterations where k ranges from 1 to 3. That is 5 iterations instead of 4 as shown below:

Number of Iterations = S(3,1) + S(3,2) + S(3,3)
                     = S(3,1) + S(3,2) + S(3,3)= 1+3+1= 5

So why did Oracle only consider 4 iterations in this case?

There are 3 ways to write a DNF of 3 conjuncts into boxes of 2 elements; namely S(3,2)=3. Why then iteration 3 has not considered the 3rd possibility?

[{ 1 3 }] or [{ 2 }]

The answer is again in the 10053 trace file. The linear technique starts by evaluating the cost of both the NT and the FORE. If the cost of the NT is smaller than that of the FORE, Oracle will iteratively EXPAND the NT to cost the different or-expansion states. If it is the opposite then Oracle will iteratively FUSE the FORE.

Let’s go back to the trace file to make it clearer.  The cost of the NT is 4.046110

ORE: Starting iteration 1, state space = [{ 1 2 3 }]
ORE: Updated best state, Cost = 4.046110

While the cost of the FORE is 3.000134

ORE: Starting iteration 2, state space = [{ 1 }]
ORE: Updated best state, Cost = 1.000055
ORE: Starting iteration 2, state space = [{ 2 }]
ORE: Updated best state, Cost = 2.000095
ORE: Starting iteration 2, state space = [{ 3 }]
ORE: Updated best state, Cost = 3.000134

Sine Cost (FORE) < Cost (NT) Oracle will then FUSE the FORE as the 10053 trace file clearly indicates:

kkoqbc: finish optimizing query block SEL$1_9 (#1)
ORE: Updated best state, Cost = 3.000134
ORE: Applying FUSE on FORE state
ORE: Starting iteration 3, state space = [{ 1 }]

However, there is a subtlety here. When the FORE is FUSED, this fusion can only be done in the order in which the FORE has been costed. In other words, the order of the conjunctions (the order of the states) cannot be permuted. Or more precisely each state of the DNF is fused with its element to the right. This is precisely why the iteration [{ 1 3 }] or [{ 2 }] has not been considered because it permutes states 2 and 3.

Hopefully this answer Nenad Noveljic question you can find in this article and reproduced here below:

Interestingly, what wasn’t considered at all was the UNION ALL consisting of the state space = [{ 2 }] and state space = [{ 1 3 }], which, generally, could yield a good execution plan.

Finally, when Oracle FUSE the FORE it uses S(n,k) combinations where n represents the number of conjunctions (3 here) and where k ranges from 1 to n-1. Applied to the current case Oracle would then have fused the FORE into S(3,1)+S(3,2) = 1+3 = 4. This is exactly what the corresponding 10053 trace file shows.

Let’s now repeat the experiment for a DNF of 4 conjunctions

alter session set tracefile_identifier='4Ored';
@53on
select 
   *
from
   t1
where
   (n1 =1           -- conjunct n°1 
      or n2  = 42   -- conjunct n°2
      or vc1 = '20' -- conjunct n°3
      or n3  = 9    -- conjunct n°4
     );

@53off

egrep "ORE: Using search type|conjunction chain" ORCLCDB_ora_16232_4Ored.trc

ORE: Using search type: linear
ORE: # conjunction chain – 4

egrep "ORE: Switching to|state space|Applying FUSE|Updated best state|Not update best state|conjunction chain" ORCLCDB_ora_16232_4Ored.trc

ORE: # conjunction chain - 4
ORE: Starting iteration 1, state space = [{ 1 2 3 4 }]
ORE: Updated best state, Cost = 5.069131
ORE: Starting iteration 2, state space = [{ 1 }]
ORE: Updated best state, Cost = 1.000055
ORE: Starting iteration 2, state space = [{ 2 }]
ORE: Updated best state, Cost = 2.000095
ORE: Starting iteration 2, state space = [{ 3 }]
ORE: Updated best state, Cost = 3.000134
ORE: Starting iteration 2, state space = [{ 4 }]
ORE: Updated best state, Cost = 4.000174
ORE: Applying FUSE on FORE state              -----> cost(FORE) = 4.000174 < cost (NT)=5.069131
ORE: Starting iteration 3, state space = [{ 1 }]
ORE: Updated best state, Cost = 1.000055
ORE: Starting iteration 3, state space = [{ 2 }]
ORE: Updated best state, Cost = 2.000095
ORE: Starting iteration 3, state space = [{ 3 4 }]
ORE: Not update best state, Cost = 4.034666
ORE: Applying FUSE on FORE state
ORE: Starting iteration 4, state space = [{ 1 }]
ORE: Updated best state, Cost = 1.000055
ORE: Starting iteration 4, state space = [{ 2 3 }]
ORE: Updated best state, Cost = 3.023117
ORE: Starting iteration 4, state space = [{ 4 }]
ORE: Not update best state, Cost = 4.023156
ORE: Applying FUSE on FORE state
ORE: Starting iteration 5, state space = [{ 1 2 }]
ORE: Updated best state, Cost = 3.034589
ORE: Starting iteration 5, state space = [{ 3 }]
ORE: Not update best state, Cost = 4.034628
ORE:   Transferring best state space to preserved query.

As you can see, since the cost of the NT is greater than that of the FORE, Oracle decided to FUSE the FORE leading to an exploration of 5 states. Since we are dealing with a set of 4 conjuncts, the size of the exhaustive state space would have been S(4,k) where k ranges from 1 to 3:

S(4,k) = S(4,1)+S(4,2)+S(4,3)= 1+7+6=14 

In other words, there should have been at least more than 5 iterations considering the non-permutation of OR-expansion states when the FORE is fused. Why then there are only 5 states.

Here’s a case where Oracle decides to EXPAND the NT of 4 conjuncts

kkoqbc: finish optimizing query block SEL$1_9 (#1)
ORE: Not update best state, Cost = 7.001340
ORE: Applying EXPAND on no transformation state
ORE: Starting iteration 3, state space = [{ 1 }]

And, where the size of the expansion states is still equal to 5 despite the permutation states is possible under EXPAND of the NT:

egrep "ORE: Switching to|state space|Updated best state|Not update best state" ORCLCDB_ora_25335_Expand4Ored.trc
ORE: Starting iteration 1, state space = [{ 1 2 3 4 }]
ORE: Updated best state, Cost = 6.689797   ----> cost of NT
ORE: Starting iteration 2, state space = [{ 1 }]
ORE: Updated best state, Cost = 3.000551
ORE: Starting iteration 2, state space = [{ 2 }]
ORE: Updated best state, Cost = 5.000945
ORE: Starting iteration 2, state space = [{ 3 }]
ORE: Not update best state, Cost = 7.001340     ----> cost of FORE
ORE: Starting iteration 3, state space = [{ 1 }]
ORE: Updated best state, Cost = 3.000551
ORE: Starting iteration 3, state space = [{ 2 3 4 }]
ORE: Updated best state, Cost = 6.460474
ORE: Starting iteration 4, state space = [{ 1 }]
ORE: Updated best state, Cost = 3.000551
ORE: Starting iteration 4, state space = [{ 2 }]
ORE: Updated best state, Cost = 5.000945
ORE: Starting iteration 4, state space = [{ 3 4 }]
ORE: Not update best state, Cost = 7.345876
ORE: Starting iteration 5, state space = [{ 1 }]
ORE: Updated best state, Cost = 3.000551
ORE: Starting iteration 5, state space = [{ 3 }]
ORE: Updated best state, Cost = 5.000945
ORE: Starting iteration 5, state space = [{ 2 4 }]
ORE: Not update best state, Cost = 7.345876
ORE:   Transferring best state space to preserved query.
ORE:   Transferring best state space to original query.

CONCLUSION

In fact, as per the US Patent (Selecting From OR-Expansion States Of A Query) whatever the number of conjuncts is, under a linear technique, when Oracle decides to FUSE the FORE or to EXPAND the NT, although it will use the Stirling number of the second kind, the maximum number of states it can explore is n+2 where n is the number of conjuncts.

Or expansion: Two-pass, Linear or Greedy

Abstract

The OR Expansion represents the ability of the CBO to transform an initial query that includes predicates linked together by an OR operator into a UNION ALL operator applied on two or more query blocks known as the UNION ALL branches. This transformation allows the CBO to consider new index access paths and join methods that would have been impossible should the initial query has not been transformed. But, the higher the number of ORs in the original query, the higher the number of semantically equivalent OR-expansion transformations. Letting the CBO evaluate the cost-benefit of this high percentage of OR-expansion states would have been very expensive. This is why Oracle has implemented three different best-cost evaluation techniques when the OR Expansion transformation is considered: Two-pass, Linear, and Greedy.  This article aims to explain when and how these techniques are used.

Warning

This is not an article that will help you in your daily performance and trouble-shooting work since it doesn’t really matter which strategy Oracle has used to evaluate the best-costed OR-expansion transformation, Two-pass, Linear, or Greedy. What matters, from a performance point of view, is whether Oracle has used the OR expansion or not. It even seems that an alter session to switch from one strategy to another is ignored. So don’t be surprised if the content of this article does not add any value to your diagnostic and performance tuning skills:

Terminology

   a) Disjunctive Normal Form

Before the CBO considers the method or the procedure of evaluating the best cost of one or many OR-Expansion states, it must first transform the initial query into a form called Disjunctive Normal Form. Let’s consider the following query

select 
    *
from
   t1
where
   (n1 =1)                  -- conjunct n°1
 and ( n2 = 42 or vc1 ='20')-- conjunct n°2
;

The predicate part of the above query is not a DNF form because one of its conjuncts (n°2) is a disjunction (contains or).  Before applying one of the three OR expansion techniques Oracle will transform the initial query into its DNF form by distributing the conjunction (and) over the disjunction (or) as shown below:

select 
    *
from
   t1
where
     (n1 =1 and n2=42)     -- conjunct n°1
 or  (n1 =1 and vc1 ='20') -- conjunct n°2;

The corresponding 10053 trace file contains a part related to this normalization which is labeled DNF Matrix as shown below:

ORE: # conjunction chain - 2
ORE: Checking validity of disjunct chain

DNF Matrix (Before sorting OR branches)
            P1  P2  P3
CNJ (#1) :   1   1   0
CNJ (#2) :   1   0   1

ORE:  Predicate list
P1 : "T1"."N1"=1
P2 : "T1"."N2"=42
P3 : "T1"."VC1"='20'

DNF Matrix (After OR branch sorting)
            P1  P2  P3
CNJ (#1) :   1   1   0
CNJ (#2) :   1   0   1

It is thus very clear that Oracle has built a chain of conjunctions with two elements on which it will apply a disjunction. For more details please read this Nenad Noveljic blog post.

   b) NT and FORE

NT represents the Non Transformed initial query when the OR expansion transformation is not applied to the query. FORE refers to the Full OR Expansion where all the disjunctive predicates are transformed into UNION ALL branches. Concretely the following query is in an NT state:

select 
    *
from
   t1
where
     (n1 =1 and n2=42)     -- conjunct n°1
 or  (n1 =1 and vc1 ='20') -- conjunct n°2;

But the following query is in a FORE state:

select 
    *
from
   t1
where
  (n1 =1 and n2=42)    
union all
select 
    *
from
   t1
where
  (n1 =1 and vc1 ='20')
and LNVNL( ((n1 =1 and n2=42));

   c) Stirling Number of the second kind

There exist two types of Stirling Number (SN): SN of the first kind and SN of the second kind. The SN of the second kind is denoted by S(n,k) and it represents the number of ways to partition n objects into k non-empty similar boxes. In the context of the OR-expansion, the total number of expansion states costed by Oracle follows the Stirling Number S(n,k) where n represents the number of disjunctive predicates (aka the number of conjunction chains) and where k (could very well represent the number of Or predicate)  ranges from 1 to n. To calculate the number of possible Or-expansion states that obey the Stirling number of the second kind we will use the recursive way as shown below:

S(n,k) = S(n-1,k-1)+ k*S(n-1,k)

With the following fixed values known in advance:

S(0,0) = 1
S(n,0) = 0 for n>=1 
S(n,n) = 1

Following the above recursive formula, S(4,3) will be found to equal 6 as shown below:

S(4,3) = S(3,2) + 3*S(3,3)
S(4,3) = S(3,2) + 3*1 
S(4,3) = S(3,2) + 3 
 
-- where
S(3,2) = S(2,1) + 2*S(2,2) = 1 + 2 = 3
-- Hence
S(4,3) = 3+3 = 6

Two-pass technique

There are five possible values for the  _optimizer_cbqt_or_expansion parameter:

SQL> @pvalid _optimizer_cbqt_or_expansion
Display valid values for multioption parameters matching "_optimizer_cbqt_or_expansion"...

  PAR# PARAMETER                     ORD VALUE    
------ ----------------------------- --- ---------
  4675 _optimizer_cbqt_or_expansion    1 OFF
       _optimizer_cbqt_or_expansion    2 ON
       _optimizer_cbqt_or_expansion    3 LINEAR
       _optimizer_cbqt_or_expansion    4 GREEDY
       _optimizer_cbqt_or_expansion    5 TWO_PASS

In the two-pass search strategy, Oracle will evaluate the cost of only two states, the initial NT state, and the FORE state. My investigations have shown that the two-pass technique is systematically used when one of the following conditions is met:

• either the number of conjunct chains= 2
• or the number of conjunct chains>=5

Here’s below the demonstration starting with 2 conjuncts, 5 conjuncts and then 6 conjuncts:

alter session set tracefile_identifier='1Ored';
@53on
-- query n°1
select 
   *
from
   t1
where
   (n1    = 1  -- conjunct 1
    or n2 = 42 -- conjunct 2       
    );
@53off

egrep "ORE: Using search type|conjunction chain" ORCLCDB_ora_9365_1Ored.trcORE: 
ORE: Using search type: linear
ORE: # conjunction chain – 2

As you can see, Oracle has started by considering to evaluate the cost of the different OR expansion states using the Linear technique. It has also recognized that it has to deal with a DNF of two conjunctions.

However, a few lines further down in the same trace file we can see that Oracle has changed its mind and decided to switch to the two-pass technique:

egrep "ORE: Switching to|state space|Updated best state|Not update best state|conjunction chain" ORCLCDB_ora_9365_1Ored.trc
ORE: # conjunction chain - 2
ORE: Switching to two pass because of # conjunction: 2 -----> switch occurs here
ORE: Starting iteration 1, state space = [{ 1 2 }]
ORE: Updated best state, Cost = 581.063707
ORE: Starting iteration 2, state space = [{ 1 }]
ORE: Updated best state, Cost = 1.000055
ORE: Starting iteration 2, state space = [{ 2 }]
ORE: Updated best state, Cost = 2.000095
ORE:   Transferring best state space to preserved query.
ORE:   Transferring best state space to original query.

As you can read, Oracle decided to switch to two-pass because the DNF form to be processed contains 2 conjunctions.

By the way, it is useless to re-explain here what Nenad Noveljic has already done with certain brilliance in the popularization of what a state space, [{ 1 2 }] for example, represents. I invite you to read his article to get a clear picture. Let me just say the following:

state space = [{ 1 2 }] = original non transformed NT query 
state space = [{ 1 }]   = select * from t1 where (n1 =1)
state space = [{ 2 }]   = select * from t1 where (n12 =42) and lnnvl (n1=1)    

Let’s now repeat the same experiment for a DNF of 5 and 6 conjuncts respectively:

alter session set tracefile_identifier='5Ored';
@53on
select 
   *
from
   t1
where
   (n1 =1
      or n2  = 42
      or vc1 = '20'
	  or n3  = 9 
	  or vc2 = '10'
    );
@53off

egrep "ORE: Using search type|conjunction chain" ORCLCDB_ora_9365_5Ored.trc
ORE: Using search type: linear
ORE: # conjunction chain - 5

egrep "ORE: Switching to|state space|Updated best state|Not update best state|conjunction chain" ORCLCDB_ora_9365_5Ored.trc
ORE: # conjunction chain - 5
ORE: Switching to two pass because of # conjunction: 5   -----> switch occurs here
ORE: Starting iteration 1, state space = [{ 1 2 3 4 5 }]
ORE: Updated best state, Cost = 581.744310
ORE: Starting iteration 2, state space = [{ 1 }]
ORE: Updated best state, Cost = 1.000055
ORE: Starting iteration 2, state space = [{ 2 }]
ORE: Updated best state, Cost = 2.000095
ORE: Starting iteration 2, state space = [{ 3 }]
ORE: Updated best state, Cost = 3.000134
ORE: Starting iteration 2, state space = [{ 4 }]
ORE: Updated best state, Cost = 4.000174
ORE: Starting iteration 2, state space = [{ 5 }]
ORE: Updated best state, Cost = 5.000247
ORE:   Transferring best state space to preserved query.
ORE:   Transferring best state space to original query.
ORE: # conjunction chain – 5

alter session set tracefile_identifier='6Ored';
@53on
select 
   *
from
   t1
where
   (n1 =1
      or n2  = 42
      or vc1 = '20'
	  or n3  = 9 
	  or vc2 = '10'
	  or n5  = 36
    );
@53off

egrep "ORE: Using search type|conjunction chain" ORCLCDB_ora_9365_6Ored.trc
ORE: Using search type: linear
ORE: # conjunction chain - 6

egrep "ORE: Switching to|state space|Updated best state|Not update best state|conjunction chain" ORCLCDB_ora_9365_6Ored.trc
ORE: # conjunction chain - 6
ORE: Switching to two pass because of # conjunction: 6  -----> switch occurs here
ORE: Starting iteration 1, state space = [{ 1 2 3 4 5 6 }]
ORE: Updated best state, Cost = 581.870344
ORE: Starting iteration 2, state space = [{ 1 }]
ORE: Updated best state, Cost = 1.000055
ORE: Starting iteration 2, state space = [{ 2 }]
ORE: Updated best state, Cost = 2.000095
ORE: Starting iteration 2, state space = [{ 3 }]
ORE: Updated best state, Cost = 3.000134
ORE: Starting iteration 2, state space = [{ 4 }]
ORE: Updated best state, Cost = 4.000174
ORE: Starting iteration 2, state space = [{ 5 }]
ORE: Updated best state, Cost = 5.000247
ORE: Starting iteration 2, state space = [{ 6 }]
ORE: Updated best state, Cost = 6.000287
ORE:   Transferring best state space to preserved query.
ORE:   Transferring best state space to original query.

It is more and more clear now that whatever the DNF is, if it has a number of conjunctions equal to 2 or greater than or equal to 5, then Oracle will use the two-pass technique when considering the Cost based Or Expansion. This technique consists in evaluating the cost of the original query (NT) and that of the FULL transformed UNION ALL query (FORE). There is no use of the Stirling number in this case.

Moreover, as already mentioned in the abstract section, it seems that forcing the linear technique has no effect. It is fairly likely that the condition of the number of conjunction 2 (or >=5) that governs the two-pass technique is hard coded in the CBO code as the following tends to prove:

alter session set tracefile_identifier='Linear';

***************************************
PARAMETERS USED BY THE OPTIMIZER
********************************
  *************************************
  PARAMETERS WITH ALTERED VALUES
  ******************************
Compilation Environment Dump
optimizer_index_cost_adj            = 10
_optimizer_cbqt_or_expansion        = linear
_swat_ver_mv_knob                   = 0

egrep "ORE: Using search type|conjunction chain" ORCLCDB_ora_16232_Linear.trc
ORE: Using search type: linear
ORE: # conjunction chain – 5

egrep "ORE: Switching to|state space|Updated best state|Not update best state|conjunction chain" ORCLCDB_ora_16232_Linear.trc
ORE: # conjunction chain - 5
ORE: Switching to two pass because of # conjunction: 5
ORE: Starting iteration 1, state space = [{ 1 2 3 4 5 }]

In order not to make this blog post too heavy I will try to devote a separate article to the Linear technique as soon as possible.

Model

Here is the model I used to conduct my experiments:

CREATE TABLE t1 (
    n1   NUMBER,
    n2   NUMBER,
    n3   NUMBER,
    n4   NUMBER,
    n5   NUMBER,
    n6   NUMBER,
    vc1  VARCHAR2(10),
    vc2  VARCHAR2(100),
    d1   DATE
);

INSERT INTO t1
    SELECT
        rownum,
        mod(rownum, 10),
        trunc((rownum - 1 / 3)),
        trunc((rownum - 1 / 5)),
        trunc((rownum - 1 / 7)),
        mod(rownum,10),
        lpad('x', 10),
        lpad('y',100),
        date '2022-01-01' + (level-1) * interval '15' minute
    FROM
        dual
    CONNECT BY
        level <= 1e5;
		
create index t1_idx1 on t1(n1,n2);
create index t1_idx2 on t1(n2);
create index t1_idx3 on t1(n3);
create index t1_idx4 on t1(n4);
create index t1_idx5 on t1(n5);
create index t1_idx6 on t1(n6);
create index t1_idx7 on t1(vc1);
create index t1_idx8 on t1(vc2);
create index t1_idx9 on t1(d1);

exec dbms_stats.gather_table_stats(user, 't1');
alter session set optimizer_index_cost_adj =10;