In this blog post I’ll be writing about a little imperfection in the Oracle optimizer which revealed itself when MINUS set operator have been used in a subquery. What I mean by that is that the cardinalities might be hugely overestimated in such case. The example I’ll be using here is just a simplification of a production query which suffered from this problem.
Oracle
Firstly, I’ll create some tables and fill them with data:
create table t1 ( n1 number ) ;
insert into t1
select 1
from dual connect by level <=50000 ;
create table t2 ( n1 number ) ;
insert into t2
select 2
from dual connect by level <=100000 ;
create table t3 ( n1 number ) ;
insert into t3
select level
from dual connect by level <=150000 ;
commit ;
exec dbms_stats.gather_table_stats( null, 'T1' ) ;
exec dbms_stats.gather_table_stats( null, 'T2' ) ;
exec dbms_stats.gather_table_stats( null, 'T3' ) ;It’s worth noting that the n1 column of the table t3 is very selective while the same column in the tables t1 and t2 contains just a bunch of repeating values. Now, let’s take a look at the following query and its execution plan:
select /*+ gather_plan_statistics */ *
from t3 where n1 in (
select n1 from t1
minus
select n1 from t2
) ;
N1
----------
1
-----------------------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | OMem | 1Mem | Used-Mem |
-----------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 1 |00:00:00.01 | 524 | | | |
|* 1 | HASH JOIN | | 1 | 50000 | 1 |00:00:00.01 | 524 | 2545K| 2545K| 810K (0)|
| 2 | VIEW | VW_NSO_1 | 1 | 50000 | 1 |00:00:00.01 | 275 | | | |
| 3 | MINUS | | 1 | | 1 |00:00:00.01 | 275 | | | |
| 4 | SORT UNIQUE | | 1 | 50000 | 1 |00:00:00.01 | 84 | 2048 | 2048 | 2048 (0)|
| 5 | TABLE ACCESS FULL| T1 | 1 | 50000 | 50000 |00:00:00.01 | 84 | | | |
| 6 | SORT UNIQUE | | 1 | 100K| 1 |00:00:00.01 | 191 | 2048 | 2048 | 2048 (0)|
| 7 | TABLE ACCESS FULL| T2 | 1 | 100K| 100K|00:00:00.01 | 191 | | | |
| 8 | TABLE ACCESS FULL | T3 | 1 | 150K| 150K|00:00:00.01 | 249 | | | |
-----------------------------------------------------------------------------------------------------------------------As you can see, the optimizer estimated that the subquery block with MINUS would return 50’000 rows instead of just 1. Apparently, the NDV of t1.n1 was not used at all for estimating the number of rows that are going to be returned by the SORT UNIQUE step.
Therefore, I recommended introducing DISTINCT when selecting t1.n1 as a workaround in this case. After doing so, the optimizer immediately came up with much better cardinality estimates.
For instance, we can see below a significant improvement of the estimated cardinality after adding DISTINCT into the subquery:
select /*+ gather_plan_statistics */ *
from t3 where n1 in (
select distinct n1 from t1
minus
select n1 from t2
) ;
-----------------------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | OMem | 1Mem | Used-Mem |
-----------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 1 |00:00:00.01 | 524 | | | |
|* 1 | HASH JOIN | | 1 | 1 | 1 |00:00:00.01 | 524 | 2545K| 2545K| 808K (0)|
| 2 | VIEW | VW_NSO_1 | 1 | 1 | 1 |00:00:00.01 | 275 | | | |
| 3 | MINUS | | 1 | | 1 |00:00:00.01 | 275 | | | |
| 4 | SORT UNIQUE | | 1 | 1 | 1 |00:00:00.01 | 84 | 2048 | 2048 | 2048 (0)|
| 5 | TABLE ACCESS FULL| T1 | 1 | 50000 | 50000 |00:00:00.01 | 84 | | | |
| 6 | SORT UNIQUE | | 1 | 100K| 1 |00:00:00.01 | 191 | 2048 | 2048 | 2048 (0)|
| 7 | TABLE ACCESS FULL| T2 | 1 | 100K| 100K|00:00:00.01 | 191 | | | |
| 8 | TABLE ACCESS FULL | T3 | 1 | 150K| 150K|00:00:00.01 | 249 | | | |
-----------------------------------------------------------------------------------------------------------------------All releases I’ve tested with, i.e. 11.2, 12.1 and 12.2, have behaved in the same way.
SQL Server
Furthermore, I cross-checked the quality of the cardinality estimation in SQL Server.
Firstly, here are the commands to create exactly the same data set:
create table t1 ( n1 integer ) ;
insert into t1 select top(50000)
1
FROM sys.all_objects AS s1 CROSS JOIN sys.all_objects AS s2
OPTION (MAXDOP 1);
create table t2 ( n1 integer ) ;
insert into t2 select top(100000)
2
FROM sys.all_objects AS s1 CROSS JOIN sys.all_objects AS s2
OPTION (MAXDOP 1);
create table t3 ( n1 integer ) ;
insert into t3 select top(150000)
ROW_NUMBER() OVER (ORDER BY s1.[object_id])
FROM sys.all_objects AS s1 CROSS JOIN sys.all_objects AS s2
OPTION (MAXDOP 1);Secondly, the select has to be slightly changed. I mean the key word “minus” must be replaced with “except” in SQL Server:
select *
from t3 where n1 in (
select n1 from t1
except
select n1 from t2
) ;
set showplan_all on
EstimateRows StmtText
1 select * from t3 where n1 in ( select n1 from t1 except select n1 from t2 ) ;
1 |--Hash Match(Inner Join, HASH:([master].[dbo].[t1].[n1])=([master].[dbo].[t3].[n1]), RESIDUAL:([master].[dbo].[t3].[n1]=[master].[dbo].[t1].[n1]))
1 |--Nested Loops(Left Anti Semi Join, OUTER REFERENCES:([master].[dbo].[t1].[n1]))
1 | |--Hash Match(Aggregate, HASH:([master].[dbo].[t1].[n1]), RESIDUAL:([master].[dbo].[t1].[n1] = [master].[dbo].[t1].[n1]))
50000 | | |--Table Scan(OBJECT:([master].[dbo].[t1]))
1 | |--Top(TOP EXPRESSION:((1)))
1 | |--Table Scan(OBJECT:([master].[dbo].[t2]), WHERE:([master].[dbo].[t1].[n1] = [master].[dbo].[t2].[n1]))
150000 |--Table Scan(OBJECT:([master].[dbo].[t3]))
Obviously, the estimation was perfect even without DISTINCT.
Likewise, I conducted the test on multiple releases, in particular on SQL Server 2014 and 2016.
Conclusion
In summary, Oracle optimizer doesn’t seem to use columns statistics when calculating the cardinality of a result set returned by the MINUS operator. Consequently, cardinality mentioned might be massively overestimated which in turn can give rise to suboptimal execution plans. This is especially true when the first select of the MINUS operator returns a non-selective column. In such cases, SELECT DISTINCT in the subquery might be an appropriate workaround for obtaining more accurate estimation.
In contrast, SQL Server optimizer produces excellent cardinality estimations event without DISTINCT.
Updates
2nd March 2018 – set-join conversion (SJC)
Stefan Koehler suggested using SJC transformation instead of adding a redundant DISTINCT into the subquery. SJC is transformation which converts a set operation to JOIN. The obvious advantage of this approach is that you wouldn’t need to change each and every query to get better execution plans. On the other hand, it doesn’t seem to be a widely used feature, so some caution and extensive testing are needed before rolling it out into production.
If you decide to go with it, you’ll have to explicitly enable it by setting the hidden parameter, for instance:
alter session set "_convert_set_to_join" = true ;We’ve got indeed the accurate estimate in our example after enabling SJC:
-----------------------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | OMem | 1Mem | Used-Mem |
-----------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 1 |00:00:00.05 | 527 | | | |
|* 1 | HASH JOIN | | 1 | 1 | 1 |00:00:00.05 | 527 | 2545K| 2545K| 812K (0)|
| 2 | VIEW | VW_NSO_1 | 1 | 1 | 1 |00:00:00.05 | 275 | | | |
| 3 | HASH UNIQUE | | 1 | 1 | 1 |00:00:00.05 | 275 | 2442K| 2442K| 780K (0)|
|* 4 | HASH JOIN ANTI | | 1 | 500 | 50000 |00:00:00.05 | 275 | 3987K| 2659K| 4476K (0)|
| 5 | TABLE ACCESS FULL| T1 | 1 | 50000 | 50000 |00:00:00.01 | 84 | | | |
| 6 | TABLE ACCESS FULL| T2 | 1 | 100K| 100K|00:00:00.01 | 191 | | | |
| 7 | TABLE ACCESS FULL | T3 | 1 | 150K| 150K|00:00:00.01 | 249 | | | |
-----------------------------------------------------------------------------------------------------------------------April 13, 2018 – Bug
A bug with the following reference was filed for this problem: 27853032 – IMPROVE CARDINALITY ESTIMATES FOR MINUS OPERATOR
September 2, 2021 – Oracle 21c
The problem hasn’t been fixed.
One Comment