Or when rewriting the query rescues the CBO

 
When an unseen query is submitted to Oracle it is hard parsed and a new execution plan is generated. During this compilation phase, the query might undergo a certain number of transformations before its final cost is calculated. The main objective of this transformation phase is to open a new path for the Cost Based Optimizer. And there exist several transformations the CBO can attempt such as view merging, subquery unnesting, transitivity closure, or expansion, predicate pushing, etc....
This article aims to introduce and define what a subquery unnesting transformation is and how to detect when the CBO has attempted and succeeded to unnest a subquery and when it didn't. The second part of the article defines what a disjunctive subquery is and shows the dramatic performance consequences it might induce because its stops the CBO from taking advantage of unnesting it with its parent query. Hopefully, this article in its last part, presents how to manually rewrite a disjunctive subquery into an equivalent normal subquery and allow Oracle to unnest it.

Unnesting Non-Scalar subquery

First the model which consists of a pair of simple heap tables t1 and t2 on which I added a two single column b-tree indexes and have collected statistics without histograms:
create table t1
as
select
   rownum              id,
   trunc((rownum-1)/5) n1,
   lpad(rownum,10,'0') small_vc,
   rpad('x',100)       padding
from
   dual
connect by level <= 1e4;
       
create index t1_id_i1 on t1(id);
       
create table t2
as
select
   rownum               id,
   trunc((rownum-1)/5)  x1,
   lpad(rownum,10,'0')  small_vc,
   rpad('x',100)        padding
from
   dual
connect by level <= 1e4;
       
create index t2_x1_i1 on t2(x1);
   
BEGIN   
 dbms_stats.gather_table_stats(user, 't1', method_opt => 'for all columns size 1');
 dbms_stats.gather_table_stats(user, 't2', method_opt => 'for all columns size 1');
END;
/
Second, the query with a subquery into its predicate part:
select /*+ qb_name(parent) */
     id,
     n1
from
     t1
where
     n1 = 100
and  exists
      (select /*+ qb_name(child) */  
            null
       from t2
       where
            t2.id = t1.id
       and  t2.x1 = 100
       );  
The first part of the above SQL statement is very often referred to as the main query block:
select /*+ qb_name(parent) */
     id,
     n1
from
     t1
where
     n1 = 100
 
The part of the predicate, that contains a query and which is commonly known as a subquery, is:
and  exists
      (select /*+ qb_name(child) */  
            null
       from t2
       where
            t2.id = t1.id
       and  t2.x1 = 100
       );  
 
Using the qb_name hint I've intentionally managed to name the parent query (parent) and the subquery (child) so that it will be easy to decipher the query block names when reading the 10053 CBO trace file.
Now that the Oracle terminology about parent query and its subquery is not a secret for you any more, let’s execute (under 12.1.0.1.0) the original SQL statement and see what execution plan the CBO will come up with:
------------------------------------------------------------------------------------------------
| Id  | Operation                              | Name     | Starts | E-Rows | A-Rows | Buffers |
------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                       |          |      1 |        |      5 |      13 |
|   1 |  NESTED LOOPS                          |          |      1 |        |      5 |      13 |
|   2 |   NESTED LOOPS                         |          |      1 |      5 |      5 |      11 |
|   3 |    SORT UNIQUE                         |          |      1 |      5 |      5 |       3 |
|   4 |     TABLE ACCESS BY INDEX ROWID BATCHED| T2       |      1 |      5 |      5 |       3 |
|*  5 |      INDEX RANGE SCAN                  | T2_X1_I1 |      1 |      5 |      5 |       2 |
|*  6 |    INDEX RANGE SCAN                    | T1_ID_I1 |      5 |      1 |      5 |       8 |
|*  7 |   TABLE ACCESS BY INDEX ROWID          | T1       |      5 |      1 |      5 |       2 |
------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   5 - access("T2"."X1"=100)
   6 - access("T2"."ID"="T1"."ID")
   7 - filter("N1"=100)

Note
-----
   - this is an adaptive plan
You need of course to up your statistics_level parameter from the TYPICAL default value to ALL in order to have the statistics of the row source operations (Starts, E-Rows, A-Rows) collected. One of the immediate points that pops up from the above execution plan is the absence of the exists clause in the predicate part and the presence of a NESTED LOOP join operation despite the absence of any join between t1 and t2 in the submitted query. This is a clear indication that the original SQL statement undergone a CBO transformation the next couple of line aims to explain. The Note at the bottom of the execution plan about adaptive plan indicates that the CBO has switched from a HASH JOIN plan compiled at hard parse time to a NESTED LOOP join during execution time.
 
One of the transformation a subquery, as defined above, is subject to, is unnesting. A subquery is said unnested when it is merged with its parent query. In other words, when a subquery, instead of being evaluated as a filter predicate for each row returned by its parent query, it is rewritten and joined with its parent query, we will say that the subquery has been unnested.
If this subquery unnesting concept is still not clear for you then let’s look at the corresponding 10053 CBO trace file:
*****************************
Cost-Based Subquery Unnesting
*****************************
SU: Unnesting query blocks in query block PARENT (#1) that are valid to unnest.
Subquery Unnesting on query block PARENT (#1)SU: Performing unnesting that does not require costing.
SU: Considering subquery unnest on query block PARENT (#1).
SU:   Checking validity of unnesting subquery CHILD (#2)
SU:   Passed validity checks.
 
The CBO has identified that the subquery I have intentionally named CHILD is valid to unnest with the query block I have also intentionally named PARENT. The trace file is more explicit when it says that the CBO is going to transform the EXISTS subquery into a join:
SU: Transforming EXISTS subquery to a join.
Registered qb: SEL$66652A51 0x24003d48 (SUBQUERY UNNEST PARENT; CHILD)
The outline part of the execution plan we can get using the following select:
SQL> select * from table(dbms_xplan.display_cursor(null, null, format =>'+outline'));

Outline Data
-------------
  /*+
      BEGIN_OUTLINE_DATA
      IGNORE_OPTIM_EMBEDDED_HINTS
      OPTIMIZER_FEATURES_ENABLE('12.1.0.1')
      DB_VERSION('12.1.0.1')
      ALL_ROWS
      OUTLINE_LEAF(@"SEL$66652A51")
      UNNEST(@"CHILD")
      OUTLINE(@"PARENT")
      OUTLINE(@"CHILD")
      INDEX_RS_ASC(@"SEL$66652A51" "T2"@"CHILD" ("T2"."X1"))
      BATCH_TABLE_ACCESS_BY_ROWID(@"SEL$66652A51" "T2"@"CHILD")
      INDEX(@"SEL$66652A51" "T1"@"PARENT" ("T1"."ID"))
      LEADING(@"SEL$66652A51" "T2"@"CHILD" "T1"@"PARENT")
      USE_NL(@"SEL$66652A51" "T1"@"PARENT")
      NLJ_BATCHING(@"SEL$66652A51" "T1"@"PARENT")
      SEMI_TO_INNER(@"SEL$66652A51" "T2"@"CHILD")
      END_OUTLINE_DATA
  */

shows that the CBO has effectively unnested the exists subquery (UNNEST(@"CHILD"). A couple of line further down the same trace file, we can found the following explicit lines:
JPPD: Applying transformation directives
query block PARENT transformed to SEL$66652A51 (#1)
FPD: Considering simple filter push in query block SEL$66652A51 (#1)
"T1"."N1"=100 AND "T2"."ID"="T1"."ID" AND "T2"."X1"=100
try to generate transitive predicate from check constraints for query block SEL$66652A51 (#1)
finally: "T1"."N1"=100 AND "T2"."ID"="T1"."ID" AND "T2"."X1"=100

This is what unnesting a subquery is: merge the exist where clause with its parent select block allowing a filter operation to become a join method.

Unnesting Disjunctive subquery

If, however, I wanted to pre-empt the CBO from unnesting the “exist subquery”, I would have instructed it to don't unnest it by means of the negative no_unnest hint as shown below:
select /*+ qb_name(parent) */
     id,
     n1
from
     t1
where
     n1 = 100
and  exists
      (select /*+ no_unnest qb_name(child) */  
            null
       from t2
       where
            t2.id = t1.id
       and  t2.x1 = 100
       );  
----------------------------------------------------------------------------------------------
| Id  | Operation                            | Name     | Starts | E-Rows | A-Rows | Buffers |
----------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |          |      1 |        |      5 |     196 |
|*  1 |  FILTER                              |          |      1 |        |      5 |     196 |
|*  2 |   TABLE ACCESS FULL                  | T1       |      1 |      5 |      5 |     181 |
|*  3 |   TABLE ACCESS BY INDEX ROWID BATCHED| T2       |      5 |      1 |      5 |      15 |
|*  4 |    INDEX RANGE SCAN                  | T2_X1_I1 |      5 |      5 |     15 |      10 |
----------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter( IS NOT NULL)
   2 - filter("N1"=100)
   3 - filter("T2"."ID"=:B1)
   4 - access("T2"."X1"=100)   
One of the immediate consequences of this non unnesting operation is the absence of a join operation. And in a 12c database context, this immediately stops you taking advantage from the adaptive join feature which helps choosing the best join operation depending on the actual rows the CBO will buffer during the execution of the query. 
The other consequence of non-unnesting the subquery is those funny child operations under the filter predicate (operation n°1). The 5 rows produced by the outer operation n° 2 (full table scan of t1) drive the number of times the inner operations n°3 and 4 (table access by index rowid of t2) are executed. Oracle starts by scanning the t1 table and filter the returned rows in order to throw away rows not satisfying the n1 = 100 clause. For all rows (5 rows) that survive the filter operation n°2 a double index and table t2 access is done in order to check if the two predicates of the exists subquery are satisfied. This is why operations 4 and 3 are executed 5 times. Put it simply, a non unnested subquery might be executed as many times as the number of rows produced by its parent query block.
The CBO trace file in this non-unnested case shows the following lines:
*****************************
Cost-Based Subquery Unnesting
*****************************
SU: Unnesting query blocks in query block PARENT (#1) that are valid to unnest.
Subquery Unnesting on query block PARENT (#1)SU: Performing unnesting that does not require costing.
SU: Considering subquery unnest on query block PARENT (#1).
SU:   Checking validity of unnesting subquery CHILD (#2)
SU: SU bypassed: Negative hint found.
 
Very often if not always, the more the “exist subquery” is started (Starts is big) the less its parent query is performant. This is why when I am tuning and troubleshooting slow query response time, I always scrutinize operations started more than necessary.
Unfortunately real life situations can reveal odd cases where the CBO is unable to merge a subquery with its parent query. In fact in Oracle terminology we use the merge word when a view (being it a real view or an inner view) is combined with the parent query and we use the unnest word when a subquery is combined with its parent SQL statement. But the transformation in both cases aims to merge two distinct pieces of SQL code as if they were submitted as a single SQL statement.
 
One of those unpredictable situations where the CBO is pre-empted from doing a suitable unnest operation is when we use a disjunctive subquery. Let’s first define what a disjunctive subquery is. Simply put, if you go back to the above original sql statement and change the AND exists with an OR exists then your initial non scalar correlated subquery becomes a disjunctive subquery for which a CBO unnest transformation is impossible.
 
select /*+ qb_name(parent) */
     id,
     n1
from
     t1
where
     n1 = 100
OR  exists
      (select /*+ qb_name(child) */  
            null
       from t2
       where
            t2.id = t1.id
       and  t2.x1 = 100
       );  
----------------------------------------------------------------------------------------------
| Id  | Operation                            | Name     | Starts | E-Rows | A-Rows | Buffers |
----------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |          |      1 |        |      5 |   20176 |
|*  1 |  FILTER                              |          |      1 |        |      5 |   20176 |
|   2 |   TABLE ACCESS FULL                  | T1       |      1 |  10000 |  10000 |     181 |
|*  3 |   TABLE ACCESS BY INDEX ROWID BATCHED| T2       |   9995 |      1 |      0 |   19995 |
|*  4 |    INDEX RANGE SCAN                  | T2_X1_I1 |   9995 |      5 |  49975 |   10000 |
----------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter(("N1"=100 OR  IS NOT NULL))
   3 - filter("T2"."ID"=:B1)
   4 - access("T2"."X1"=100)   
Spot that, despite we are still returning the same number of rows, the logical I/O used in this case has exploded (20176). This is mainly due to the high number of executions (9995) done with operation 4 and 3 to full fill the exist subquery predicate that has not been unnested by the CBO. The presence of the filter operation is another indication that the exists subquery has not been “merged” with its parent query block. The corresponding 10053 trace file is not very verbose in this case as it doesn’t show why the unnesting has not been done:
SU: Considering subquery unnesting in query block PARENT (#0)
********************
Subquery Unnest (SU)
********************

try to generate transitive predicate from check constraints for query block CHILD (#0)
finally: "T2"."ID"=:B1 AND "T2"."X1"=100
try to generate transitive predicate from check constraints for query block PARENT (#0)
finally: "T1"."N1"=100 OR  EXISTS (SELECT /*+ QB_NAME ("CHILD") */ 0 FROM "T2" "T2")
Since the CBO has decided to not unnest the subquery let’s instruct it to do so
select /*+ qb_name(parent) */
     id,
     n1
from
     t1
where
     n1 = 100
or  exists
      (select /*+ unnest qb_name(child) */  
            null
       from t2
       where
            t2.id = t1.id
       and  t2.x1 = 100
       );  
--------------------------------------------------------------------------------------
| Id  | Operation                    | Name     | Starts | E-Rows | A-Rows | Buffers |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |          |      1 |        |      5 |   20175 |
|*  1 |  FILTER                      |          |      1 |        |      5 |   20175 |
|   2 |   TABLE ACCESS FULL          | T1       |      1 |  10000 |  10000 |     180 |
|*  3 |   TABLE ACCESS BY INDEX ROWID| T2       |   9995 |      1 |      0 |   19995 |
|*  4 |    INDEX RANGE SCAN          | T2_X1_I1 |   9995 |      5 |  49975 |   10000 |
--------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter(("N1"=100 OR  IS NOT NULL))
   3 - filter("T2"."ID"=:B1)
   4 - access("T2"."X1"=100)   
No changes in the plan. The hint has been ignored which is clearly seen into the corresponding 10053 trace file (used = 0)
Dumping Hints
=============
atom_hint=(@=000000002400F0D8 err=0 resol=1 used=0token=919 org=1 lvl=2 txt=UNNEST)
What else can we do in this case? We are not going to let that huge amount of Buffers (20175) threatining our application.
 
There is a way we can use when dealing with disjunctive subquery performance issues which consists of rewriting the query so that we get rid of the OR clause and nevertheless keep the same results. A simple way to correctly rewrite the OR query is to phrase it first in plain english (or in french or in arabic). And this is what my query phrasing excercise ended up with
 
“ we want id and n1 column from t1 table satifying one of the two conditions
  •          Either the n1 value from t1 table equals 100
  •         Or there exist an id column in t1 table which has its equivalent id in t2 table with a corresponding x1 value of 100”
Since the query should satisfy one of the two conditions we can start by writing two separate queries for each condition as shown below:
 
The first part of the query where we get all rows from t1 satisfying the n1=100 clause
 
select
     id,
     n1
from
     t1
where
     n1 = 100;

And the second part of the query should represent the rows from t1 that satisfy only the second exists subquery clause. This is why we have to exclude rows satisfying the predicate of the first part of the query as shown below:
select
     id,
     n1
from
     t1
where
     n1 != 100
and
    exists
      (select null
       from t2
       where
            t2.id = t1.id
       and  t2.x1 = 100;

Finally coupling the above queries gives a SQL statement honoring the phrasing I used above:
 
select
     id,
     n1
from
     t1
where
     n1 = 100
union all
select
     id,
     n1
from
     t1
where
     n1 != 100
and
    exists
      (select null
       from t2
       where
            t2.id = t1.id
       and  t2.x1 = 100;
There is no disjunctive subquery (OR clause) anymore. This will opens a door for unnesting and therefore a possible better execution path. But we still are not completely done. We are still threatened by the null threat. The t1.n1 column has been designed to accept null values. This makes the new refactored query not compeltely correct .We should slightly change the second part of the above query to work arround the null threat by using the elegant sql function named LNNVL as shown below:
select
     id,
     n1
from
     t1
where
     n1 = 100
union all
select
     id,
     n1
from
     t1
where
     lnnvl(n1 = 100)
and
     exists
      (select null
       from t2
       where
            t2.id = t1.id
       and  t2.x1 = 100);
-------------------------------------------------------------------------------------------------
| Id  | Operation                               | Name     | Starts | E-Rows | A-Rows | Buffers |
--------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                        |          |      1 |        |      5 |     192 |
|   1 |  UNION-ALL                              |          |      1 |        |      5 |     192 |
|*  2 |   TABLE ACCESS FULL                     | T1       |      1 |      5 |      5 |     181 |
|   3 |   NESTED LOOPS                          |          |      1 |        |      0 |      11 |
|   4 |    NESTED LOOPS                         |          |      1 |      5 |      5 |      10 |
|   5 |     SORT UNIQUE                         |          |      1 |      5 |      5 |       3 |
|   6 |      TABLE ACCESS BY INDEX ROWID BATCHED| T2       |      1 |      5 |      5 |       3 |
|*  7 |       INDEX RANGE SCAN                  | T2_X1_I1 |      1 |      5 |      5 |       2 |
|*  8 |     INDEX RANGE SCAN                    | T1_ID_I1 |      5 |      1 |      5 |       7 |
|*  9 |    TABLE ACCESS BY INDEX ROWID          | T1       |      5 |      1 |      0 |       1 |
-------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("N1"=100)
   7 - access("T2"."X1"=100)
   8 - access("T2"."ID"="T1"."ID")
   9 - filter(LNNVL("N1"=100))

Note
-----
   - this is an adaptive plan

Notice how the exist subquery of the second part of the union all has been unnested, merged with its parent query block letting the place for a nice and attractive nested loop join operation(subject to adaptive join method) reducing drastically the number of logical I/O from its initial 20175 Buffers to a ridiculous 192 Buffers.

Conclusion

Subquery unnesting is a wonderful transformation which allows a correlated non-scalar subquery to be transformed and merged with its parent query block so that efficient access path such as join methods and join orders are considered. Unfortunately the Oracle CBO is unable to unnest a disjunctive correlated subquery with its parent query block making the subquery evaluated (started) multiple times. Hopefully, you can always manually rewrite a disjunctive subquery into a two union all part in which you can transform the disjunctive correlated subquery into a normal subquery subject to unnesting and therefore to a possible optimal execution plan.