This blog post is about suboptimal execution plans for uncorrelated subqueries involved in set operations.
First of all, I’d like to give a short overview of three optimization modes: all_rows, first_rows(k) and first_rows. In doing so, I’ll use the following data set on a 12.2.0.1.180116 database:
create table t1 as select rownum n1 from dual
connect by level <= 100000 ;
create table t2 as select rownum n1, mod(rownum,20000)+1 n2, lpad('A',3000,'A') c1
from dual connect by level <= 100000 ;
alter table t2 add constraint t2_pk primary key (n1) ;
create index ix_t2_n2 on t2 (n2) ;
The column n1, which will be used for joining tables t1 and t2, contains consecutive integer values between 1 and 100000. The column t2.n2 contains uniformly distributed integer values between 1 and 20000.
all_rows
Because of the size of the tables, the optimizer prefers the hash join (HJ) to the nested loops (NL):
select /*+ all_rows */ 1
from t1 inner join t2 on t1.n1 = t2.n1 and t2.n2 = 10000 ;
----------------------------------------------------------------------
| Id | Operation | Name | Rows | Cost (%CPU)|
----------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | 53 (100)|
|* 1 | HASH JOIN | | 5 | 53 (2)|
| 2 | TABLE ACCESS BY INDEX ROWID| T2 | 5 | 6 (0)|
|* 3 | INDEX RANGE SCAN | IX_T2_N2 | 5 | 1 (0)|
| 4 | TABLE ACCESS FULL | T1 | 100K| 46 (0)|
----------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("T1"."N1"="T2"."N1")
3 - access("T2"."N2"=10000)
first_rows(k)
The first_rows(k) (a.k.a "First K Rows") optimization goal is to produce the execution plan for retrieving the first k rows as fast as possible.
It's important to understand that the number of the estimated rows of the outer table in NL is the expected number of rows of the outer table that need to be fetched to return the first k rows. Therefore, this estimated cardinality is calculated as the expected value of the fetched number of the outer table rows to find k matching rows in the inner table which fulfill the filter condition. Let k=1, this expected value can be calculated as follows:
E = ( num_rows_inner + 1) / ( cardinality_inner + 1 )
- num_rows_inner is the total number of the inner table rows.
- cardinality_inner is the number of remaining rows of the inner table after applying the filter condition.
In other words, the optimizer estimates how many unmatched outer table rows need to be fetched to find the first row in the inner table.
This means, the less selective the predicate on the inner table, the higher the expected cardinality of the outer table, the higher the NL cost.
Consequently, a less selective filter on the inner table is more likely to produce a HJ plan, such as:
select /*+ first_rows(1) */ 1
from t1 inner join t2 on t1.n1 = t2.n1
and t2.n2 = 10000 ;
----------------------------------------------------------------------
| Id | Operation | Name | Rows | Cost (%CPU)|
----------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | 17 (100)|
|* 1 | HASH JOIN | | 5 | 17 (0)|
| 2 | TABLE ACCESS BY INDEX ROWID| T2 | 5 | 6 (0)|
|* 3 | INDEX RANGE SCAN | IX_T2_N2 | 5 | 1 (0)|
| 4 | TABLE ACCESS FULL | T1 | 20129 | 11 (0)|
----------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("T1"."N1"="T2"."N1")
3 - access("T2"."N2"=1000)
But if we replace the equality condition with a range the expected t1 cardinality will reach some tipping point where the execution plan will switch to NL:
select /*+ first_rows(1) */ 1
from t1 inner join t2 on t1.n1 = t2.n1
and t2.n2 between 1 and 10000 ;
-------------------------------------------------------------------
| Id | Operation | Name | Rows | Cost (%CPU)|
-------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | 42 (100)|
| 1 | NESTED LOOPS | | 40 | 42 (0)|
| 2 | NESTED LOOPS | | 40 | 42 (0)|
| 3 | TABLE ACCESS FULL | T1 | 40 | 2 (0)|
|* 4 | INDEX UNIQUE SCAN | T2_PK | 1 | 0 (0)|
|* 5 | TABLE ACCESS BY INDEX ROWID| T2 | 1 | 1 (0)|
-------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - access("T1"."N1"="T2"."N1")
5 - filter(("T2"."N2"<=1000 AND "T2"."N2">=1))The optimizer estimated that in average 40 rows from t1 have to be fetched in order to find a matching row in t2 that fulfills the filter condition.
The key point is that the optimizer runs a probability calculation to decide on the join method. In other words, the first_rows(k) optimization is fully cost based.
By the way, the CBO trace provides a clue that the first_rows(k) optimization was done:
First K Rows: Setup begin
First K Rows: K = 1.00, N = 5.00
First K Rows: Setup end
First K Rows: old pf = -1.0000000, new pf = 0.2012800
SINGLE TABLE ACCESS PATH (First K Rows)
First K Rows: old pf = -1.0000000, new pf = 1.0000000
SINGLE TABLE ACCESS PATH (First K Rows)
First K Rows: unchanged join prefix len = 1
First K Rows: K = 1.00, N = 5.00
First K Rows: old pf = 1.0000000, new pf = 0.2012900
SINGLE TABLE ACCESS PATH (First K Rows)
First K Rows: old pf = 0.2012800, new pf = 1.0000000
SINGLE TABLE ACCESS PATH (First K Rows)
...
Final cost for query block SEL$58A6D7F6 (#0) - First K Rows Plan:first_rows
The first_rows optimization is partially rule based and therefore inferior to the first_rows(k) optimization. In fact, the Oracle database documentation recommends to avoid it: "FIRST_ROWS is available for backward compatibility and plan stability; use FIRST_ROWS_n instead."
For instance, a suboptimal NL plan gets produced for the equal condition predicate, just because of some hard coded heuristics:
select /*+ first_rows */ 1
from t1 inner join t2 on t1.n1 = t2.n1
and t2.n2 = 10000
-------------------------------------------------------------------
| Id | Operation | Name | Rows | Cost (%CPU)|
-------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | 100K(100)|
| 1 | NESTED LOOPS | | 5 | 100K (1)|
| 2 | NESTED LOOPS | | 100K| 100K (1)|
| 3 | TABLE ACCESS FULL | T1 | 100K| 46 (0)|
|* 4 | INDEX UNIQUE SCAN | T2_PK | 1 | 0 (0)|
|* 5 | TABLE ACCESS BY INDEX ROWID| T2 | 1 | 1 (0)|
-------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - access("T1"."N1"="T2"."N1")
5 - filter("T2"."N2"=10000)
Also in this case, the optimizer leaves a notice in the CBO trace that the first_rows optimization was performed:
Final cost for query block SEL$58A6D7F6 (#0) - First Rows Plan:As we shall see later, the optimizer can also switch optimization modes without being instructed to do so. So better remember the difference in the trace output between "First Rows" and "First K Rows" optimization, because it's good to know which one was effectively used when troubleshooting a bad execution plan.
Uncorrelated Subquery
Let's remove the hint in the previous query and use it to build an uncorrelated subquery:
select 1 from dual where exists (
select 1
from t1 inner join t2 on t1.n1 = t2.n1
and t2.n2 = 10000) ;
-----------------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Starts | E-Rows | Cost (%CPU)| A-Rows | A-Time | Buffers |
-----------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 19 (100)| 1 |00:00:00.01 | 25 |
|* 1 | FILTER | | 1 | | | 1 |00:00:00.01 | 25 |
| 2 | FAST DUAL | | 1 | 1 | 2 (0)| 1 |00:00:00.01 | 0 |
|* 3 | HASH JOIN RIGHT SEMI | | 1 | 5 | 17 (0)| 1 |00:00:00.01 | 25|
| 4 | TABLE ACCESS BY INDEX ROWID| T2 | 1 | 5 | 6 (0)| 5 |00:00:00.01 | 7 |
|* 5 | INDEX RANGE SCAN | IX_T2_N2 | 1 | 5 | 1 (0)| 5 |00:00:00.01 | 2 |
| 6 | TABLE ACCESS FULL | T1 | 1 | 20129 | 11 (0)| 9999 |00:00:00.01 | 18 |
-----------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter( IS NOT NULL)
3 - access("T1"."N1"="T2"."N1")
5 - access("T2"."N2"=10000)
Unsurprisingly, the optimizer produced a HJ plan for a non-selective equal condition filter. Furthermore, by looking into the CBO trace we can see that the optimizer implicitly used the "First 1 Rows" optimization for the uncorrelated subquery:
First K Rows: Setup begin
First K Rows: K = 1.00, N = 5.00
First K Rows: Setup end
First K Rows: K = 1.00, N = 5.00
First K Rows: old pf = -1.0000000, new pf = 0.2012800
SINGLE TABLE ACCESS PATH (First K Rows)
First K Rows: unchanged join prefix len = 1
First K Rows: K = 1.00, N = 5.00
First K Rows: old pf = 1.0000000, new pf = 0.2012900
Final cost for query block SEL$F1D6E378 (#2) - First K Rows Plan:In fact, that's a very smart optimization technique, as we're not interested in retrieving all of the rows - merely one row is sufficient for evaluating the exists subquery to TRUE.
Union
Unfortunately, the execution plan will change for worse if we add just a simple union:
select 1 from dual
union
select 1 from dual where exists (
select 1
from t1 inner join t2 on t1.n1 = t2.n1
and t2.n2 = 10000 ) ;
-------------------------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Starts | E-Rows | Cost (%CPU)| A-Rows | A-Time | Buffers | Reads |
-------------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 100K(100)| 1 |00:00:00.14 | 10160 | 4752 |
| 1 | SORT UNIQUE | | 1 | 2 | 100K (1)| 1 |00:00:00.14 | 10160 | 4752 |
| 2 | UNION-ALL | | 1 | | | 2 |00:00:00.14 | 10160 | 4752 |
| 3 | FAST DUAL | | 1 | 1 | 2 (0)| 1 |00:00:00.01 | 0 | 0 |
|* 4 | FILTER | | 1 | | | 1 |00:00:00.14 | 10160 | 4752 |
| 5 | FAST DUAL | | 1 | 1 | 2 (0)| 1 |00:00:00.01 | 0 | 0 |
| 6 | NESTED LOOPS SEMI | | 1 | 5 | 100K (1)| 1 |00:00:00.14 | 10160 | 4752 |
| 7 | TABLE ACCESS FULL | T1 | 1 | 100K| 46 (0)| 9999 |00:00:00.01 | 19 | 0 |
|* 8 | TABLE ACCESS BY INDEX ROWID| T2 | 9999 | 1 | 1 (0)| 1 |00:00:00.12 | 10141 | 4752 |
|* 9 | INDEX UNIQUE SCAN | T2_PK | 9999 | 1 | 0 (0)| 9999 |00:00:00.01 | 142 | 0 |
-------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - filter( IS NOT NULL)
8 - filter("T2"."N2"=10000)
9 - access("T1"."N1"="T2"."N1")
As a consequence, the number of logical reads rocketed from just 25 to 10160.
This sudden change can be explained by looking into the CBO trace:
Final cost for query block SEL$5BF935F8 (#4) - First Rows Plan:I couldn't believe my eyes when I first saw that - the optimizer itself switched to the rule-based first_rows optimization.
Obviously, there's still code around which implicitly optimizes for first_rows. So, you'll possibly need to hint the query to correct this behavior.
For example, you might well decide that the all_rows plan is an acceptable compromise for your data set and filter predicates. In that case, you could embed the first_rows(1) hint into the query. The optimizer, however, won't take the hint - presumably because of the SORT UNIQUE operation, but it will silently switch to the all_rows mode:
select /*+ first_rows(1) */ 1 from dual
union
select 1 from dual where exists (
select 1
from t1 inner join t2 on t1.n1 = t2.n1
and t2.n2 = 10000) ;
-------------------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Starts | E-Rows | Cost (%CPU)| A-Rows | A-Time | Buffers |
-------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 59 (100)| 1 |00:00:00.01 | 26 |
| 1 | SORT UNIQUE | | 1 | 2 | 59 (6)| 1 |00:00:00.01 | 26 |
| 2 | UNION-ALL | | 1 | | | 2 |00:00:00.01 | 26 |
| 3 | FAST DUAL | | 1 | 1 | 2 (0)| 1 |00:00:00.01 | 0 |
|* 4 | FILTER | | 1 | | | 1 |00:00:00.01 | 26 |
| 5 | FAST DUAL | | 1 | 1 | 2 (0)| 1 |00:00:00.01 | 0 |
|* 6 | HASH JOIN SEMI | | 1 | 5 | 53 (2)| 1 |00:00:00.01 | 26 |
| 7 | TABLE ACCESS BY INDEX ROWID| T2 | 1 | 5 | 6 (0)| 5 |00:00:00.01 | 7 |
|* 8 | INDEX RANGE SCAN | IX_T2_N2 | 1 | 5 | 1 (0)| 5 |00:00:00.01 | 2 |
| 9 | TABLE ACCESS FULL | T1 | 1 | 100K| 46 (0)| 9999 |00:00:00.01 | 19 |
-------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - filter( IS NOT NULL)
6 - access("T1"."N1"="T2"."N1")
8 - access("T2"."N2"=10000)
In contrast, hinting the subquery with all_rows doesn't have any impact on the optimization mode - the first_rows optimization will be used in this case.
Am I the only one who finds it strange that you need to use the first_rows(1) hint to enforce the all_rows optimization?
References:
first_rows_n, Jonathan Lewis
Expectations, David Pollard
Database Reference 12c Release 2 (12.2), Oracle Corp.
I haven’t run your model, but one thing to consider is that the
“select 1 from dual where exists ()” construct is recognised as a special case that is being used to check existence. If you enable rowsource execution stats then I think you’ll find that the “select from dual” doesn’t start in the simple case, but has to start in the UNION ALL case because you really appear to want the actual value returned from dual.
Somewhere there’s a fix-control (or maybe a MoS note) that lets you know that the query block for an existence subquery will optimize with first_rows(1) – it’s interesting that this seems to make tthat rule very flexible.
There’s the execution plan with rowsource execution statistics for the “select 1 from dual where exists” construct in the paragraph “Uncorrelated Subquery”. Starts is 1 for the “select from dual” step.
In my humble opinion, the flexibility of switching to first_rows in this special case is not the consequence of a deliberate design decision. More likely, it’s the old code that hasn’t been changed yet.