Chinar Aliyev`s blog

October 2, 2018

Join Skew Handling Subject to Filter Conditions

Filed under: Cardinality Estimation,CBO,Join,Skew,Tuning — Chinar Aliyev @ 1:52 pm

I have written about the problem in my previous post but re-raising the mentioned problem by Jonathan Lewis enforced me to think about other possible solution of it. A suggested solution in Jonathan`s blog is applying fact table`s column distribution to the dimension table`s column. In my opinion, if a column distribution will not express its data by faked statistics, then it is not a good idea to apply the method to production systems. As he said the method does not work as expected from 12 R2 afterward. For some predicate values it works, but for other does not.
In this blog post I am going to describe another possible and supported way to correct the cardinality estimation of the join.
Let`s create the test case again

// tested in Oracle Database version: 18.3.0.0.0, 12.2.0.1.0, 12.1.0.2.0

create table dim_table (type_code number, object_type varchar2(10));
insert into dim_table values (1,'TABLE');
insert into dim_table values (2,'INDEX');
insert into dim_table values (3,'VIEW');
insert into dim_table values (4,'SYNONYM');
insert into dim_table values (5,'OTHER');
commit;
-- I do not create primary index for dim_table, because we consider the case for general purpose

exec dbms_stats.gather_table_stats(user,'dim_table');

create table t1 
nologging
as 
select 
        object_id, object_name, 
        decode(object_type, 'TABLE',1,'INDEX',2,'VIEW',3,'SYNONYM',4,5) type_code 
from 
        all_objects
where
where
        rownum <= 50000;
  
insert into t1 select * from t1;
insert into t1 select * from t1;
insert into t1 select * from t1;
  
exec dbms_stats.gather_table_stats(null, 't1', cascade=>true,method_opt=>'for all columns size 254');

The value of type_code is 1 for object_type=’TABLE’ then

explain plan for
select  *
from
        t1
where
        t1.type_code = 1; 

(SQL 1)

select * from table(dbms_xplan.display(null,null,null));

Plan hash value: 3617692013                                               
                                                                          
--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      | 14336 |   602K|   726   (1)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   | 14336 |   602K|   726   (1)| 00:00:01 |
--------------------------------------------------------------------------
                                                                          
Predicate Information (identified by operation id):                       
---------------------------------------------------                       
                                                                          
   1 - filter("T1"."TYPE_CODE"=1)   
  EP1

It means in my case, the cardinality of the following join should be calculated as 14336, but:

explain plan for
select 
        t1.object_id
from
        t1, dim_table dt
where
        t1.type_code   = dt.type_code 
and     dt.object_type = 'TABLE';

(SQL 2)

select * from table(dbms_xplan.display(null,null,null));
Plan hash value: 1679886631                                                     
                                                                                
--------------------------------------------------------------------------------
| Id  | Operation          | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           | 80000 |  1328K|   728   (1)| 00:00:01 |
|*  1 |  HASH JOIN         |           | 80000 |  1328K|   728   (1)| 00:00:01 |
|*  2 |   TABLE ACCESS FULL| DIM_TABLE |     1 |     9 |     2   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| T1        |   400K|  3125K|   725   (1)| 00:00:01 |
--------------------------------------------------------------------------------
                                                                                
Predicate Information (identified by operation id):                             
---------------------------------------------------                             
                                                                                
   1 - access("T1"."TYPE_CODE"="DT"."TYPE_CODE")                                
   2 - filter("DT"."OBJECT_TYPE"='TABLE')                                       
EP2

As in the previous blog posts was mentioned that in this case optimizer doesn’t estimate cardinality properly due to several of factors. First of all, we cannot say that in the case optimizer doesn`t consider the column distribution for estimating the join size. In contrast, it calculates join selectivity (JS) based on join columns distribution, so histograms data of the join columns are used to calculate JS, in other words these are used for the join cardinality. Let’s prove it then we will return our base query.

create table dim_table2 (type_code number, object_type varchar2(10));
 
insert into dim_table2 values (1,'TABLE');
insert into dim_table2 values (1,'TABLE');
insert into dim_table2 values (2,'INDEX');
insert into dim_table2 values (3,'VIEW');
insert into dim_table2 values (4,'SYNONYM');
insert into dim_table2 values (5,'OTHER');

commit;
 

exec dbms_stats.gather_table_stats(user,'dim_table2',method_opt=&gt;'for all columns size skewonly');
explain plan for
select 
        t1.object_id
from
        t1, dim_table2 dt
where
        t1.type_code   = dt.type_code 
and     dt.object_type = 'TABLE';

(SQL 3)

select * from table(dbms_xplan.display(null,null,null));

Plan hash value: 1964253718                                                      
                                                                                 
---------------------------------------------------------------------------------
| Id  | Operation          | Name       | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |            |   138K|  2292K|   728   (1)| 00:00:01 |
|*  1 |  HASH JOIN         |            |   138K|  2292K|   728   (1)| 00:00:01 |
|*  2 |   TABLE ACCESS FULL| DIM_TABLE2 |     2 |    18 |     2   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| T1         |   400K|  3125K|   725   (1)| 00:00:01 |
---------------------------------------------------------------------------------
                                                                                 
Predicate Information (identified by operation id):                              
---------------------------------------------------                              
                                                                                 
   1 - access("T1"."TYPE_CODE"="DT"."TYPE_CODE")                                 
   2 - filter("DT"."OBJECT_TYPE"='TABLE')
EP3

As you see, although number of distinct values of the columns (NDV) has not been changed but Join cardinality has been changed. NDV is 5 for both columns, it means Join Cardinality should be

JCARD=Filtered_CARD(DIM_TABLE2)* Filtered_CARD(T1)/5=2*400k/5=160000. 

But it is not 160K, it was calculated 138K! The reason is that JS is calculated based on frequency information but not just based on NDVs in this case due to histograms.
Now if optimizer considers column distribution then what was wrong with (SQL 1) statement? The answer is the filter predicates. These directly influence the join cardinality and JS doesn`t depend on filter predicates. I pointed out it two years ago at Hotsos symposium 2016 – in this the paper. It means, if we find a way to remove filter predicates from the SQL1 in order to completely eliminate the influencing the join cardinality estimation then we will attain the desired result.
But how we could achieve it? The first thing come to my mind was using extended statistics and rewriting SQL statement to get the result. I thought it should work. So, what I have done? I have added following virtual column to the table and gathered histogram for that.

BEGIN
  DBMS_STATS.GATHER_TABLE_STATS( null,'dim_table',
  METHOD_OPT =&gt; 'FOR ALL COLUMNS SIZE 254 ' ||
                'FOR COLUMNS SIZE 254 (CASE "OBJECT_TYPE" WHEN ''TABLE'' THEN "TYPE_CODE"  END )' );
END;
/

select column_name,
       num_distinct,
       num_buckets,
       histogram from user_tab_col_statistics
where table_name='DIM_TABLE'

COLUMN_NAME                          NUM_DISTINCT NUM_BUCKETS  HISTOGRAM
------------------------------------ ------------ -----------  -----------
TYPE_CODE                            5            5            FREQUENCY
OBJECT_TYPE                          5            5            FREQUENCY
SYS_STU#S#WF25Z#QAHIHE#MOFFMM_       1            1            FREQUENCY

As you see we have frequency histogram for each column including our virtual column. It is very important having histogram of the columns to take advantage of them in order to calculate JC correctly.
Now we can rewrite the original SQL1 with one following SQL statements and can see the estimation.

SELECT   t1.object_id
  FROM   t1, dim_table dt
 WHERE   t1.type_code =
             CASE dt.object_type 
             WHEN 'TABLE' THEN dt.type_code 
             END;
 (SQL4)

OR 

SELECT   t1.object_id
  FROM   t1, dim_table dt
 WHERE   t1.type_code = dt."SYS_STU#S#WF25Z#QAHIHE#MOFFMM1_"; 
 (SQL5)

These SQL2, SQL4, SQL5 are semantically equivalent queries. Explain plans of both SQL4 and SQL5 are same:

Plan hash value: 1679886631                                                     
                                                                                
--------------------------------------------------------------------------------
| Id  | Operation          | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           | 80000 |   781K|   728   (1)| 00:00:01 |
|*  1 |  HASH JOIN         |           | 80000 |   781K|   728   (1)| 00:00:01 |
|*  2 |   TABLE ACCESS FULL| DIM_TABLE |     1 |     2 |     2   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| T1        |   400K|  3125K|   725   (1)| 00:00:01 |
--------------------------------------------------------------------------------
                                                                                
Predicate Information (identified by operation id):                             
---------------------------------------------------                             
                                                                                
   1 - access("T1"."TYPE_CODE"=CASE "OBJECT_TYPE" WHEN 'TABLE' THEN             
              "TYPE_CODE" END )                                                 
   2 - filter(CASE "OBJECT_TYPE" WHEN 'TABLE' THEN "TYPE_CODE" END  IS          
              NOT NULL)   
EP4

Unfortunately, we have not got the expected cardinality. What is the reason? Is something wrong with this method?
Let`s look at the optimizer trace file to catch the problem.

***************************************
BASE STATISTICAL INFORMATION
***********************
Table Stats::
  Table: DIM_TABLE  Alias: DT
  #Rows: 5  SSZ: 0  LGR: 0  #Blks:  1  AvgRowLen:  10.00  NEB: 0  ChainCnt:  0.00  ScanRate:  0.00  SPC: 0  RFL: 0  RNF: 0  CBK: 0  CHR: 0  KQDFLG: 1
  #IMCUs: 0  IMCRowCnt: 0  IMCJournalRowCnt: 0  #IMCBlocks: 0  IMCQuotient: 0.000000
  Column (#3): SYS_STU#S#WF25Z#QAHIHE#MOFFMM_(NUMBER)
    AvgLen: 2 NDV: 1 Nulls: 4 Density: 0.500000 Min: 1.000000 Max: 1.000000
***********************
Table Stats::
  Table: T1  Alias: T1
  #Rows: 400000  SSZ: 0  LGR: 0  #Blks:  2664  AvgRowLen:  43.00  NEB: 0  ChainCnt:  0.00  ScanRate:  0.00  SPC: 0  RFL: 0  RNF: 0  CBK: 0  CHR: 0  KQDFLG: 1
  #IMCUs: 0  IMCRowCnt: 0  IMCJournalRowCnt: 0  #IMCBlocks: 0  IMCQuotient: 0.000000
  Column (#3): TYPE_CODE(NUMBER)
    AvgLen: 3 NDV: 5 Nulls: 0 Density: 0.017180 Min: 1.000000 Max: 5.000000
    Histogram: Freq  #Bkts: 5  UncompBkts: 400000  EndPtVals: 5  ActualVal: yes
try to generate single-table filter predicates from ORs for query block SEL$1 (#0)
finally: "T1"."TYPE_CODE"=CASE "DT"."OBJECT_TYPE" WHEN 'TABLE' THEN "DT"."TYPE_CODE" END  AND CASE "DT"."OBJECT_TYPE" WHEN 'TABLE' THEN "DT"."TYPE_CODE" END  IS NOT NULL

It is seen that optimizer detected virtual column for join processing but there is something missing. The trace file displays all basic column statistics for the virtual column but doesn`t talk about its frequency histogram! And why? The answer is that there is one bucket and there is only one number of distinct value for the virtual column. Therefore optimizer thought it is not necessary to look at the histogram data.
So, what is the next? What can we do for the next step?
We have one distinct value and four nulls for the column, let`s replace the null values with the other values (which not included in the table) in order to create more buckets for histogram. In this case, such histogram will trigger optimizer to consider frequency information from the histogram:

BEGIN
    DBMS_STATS.drop_extended_stats (
        NULL,
        'dim_table',
        '(CASE "OBJECT_TYPE" WHEN ''TABLE'' THEN "TYPE_CODE" END )');
END;
/
BEGIN
  DBMS_STATS.GATHER_TABLE_STATS( null,'dim_table',
  METHOD_OPT =&gt; 'FOR ALL COLUMNS SIZE 254 ' ||
                'FOR COLUMNS SIZE 254 (CASE "OBJECT_TYPE" WHEN ''TABLE'' THEN "TYPE_CODE" ELSE (-1) END )' );
END;
/

select column_name,
       num_distinct,
       num_buckets,
       histogram from user_tab_col_statistics
where table_name='DIM_TABLE'

COLUMN_NAME                          NUM_DISTINCT NUM_BUCKETS  HISTOGRAM
------------------------------------ ------------ -----------  -----------
TYPE_CODE                            5            5            FREQUENCY
OBJECT_TYPE                          5            5            FREQUENCY
SYS_STUE_0VSFXQ_4T7QQLFLMZRDPV       2            2            FREQUENCY

Now, let`s see the execution plan of :

explain plan for
SELECT   t1.object_id
  FROM   t1, dim_table dt
 WHERE   t1.type_code =
             CASE dt.object_type 
             WHEN 'TABLE' THEN dt.type_code else -1 
             END;
select * from table(dbms_xplan.display);
Plan hash value: 1679886631                                                     
                                                                                
--------------------------------------------------------------------------------
| Id  | Operation          | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           | 14336 |   168K|   728   (1)| 00:00:01 |
|*  1 |  HASH JOIN         |           | 14336 |   168K|   728   (1)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| DIM_TABLE |     5 |    20 |     2   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| T1        |   400K|  3125K|   725   (1)| 00:00:01 |
--------------------------------------------------------------------------------
                                                                                
Predicate Information (identified by operation id):                             
---------------------------------------------------                             
                                                                                
   1 - access("T1"."TYPE_CODE"=CASE "OBJECT_TYPE" WHEN 'TABLE' THEN             
              "TYPE_CODE" ELSE (-1) END )                                       
  EP5
explain plan for
SELECT   t1.object_id
  FROM   t1, dim_table dt
 WHERE   t1.type_code = dt." SYS_STUE_0VSFXQ_4T7QQLFLMZRDPV"; 
 select * from table(dbms_xplan.display);
Plan hash value: 1679886631                                                     
                                                                                
--------------------------------------------------------------------------------
| Id  | Operation          | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           | 14336 |   168K|   728   (1)| 00:00:01 |
|*  1 |  HASH JOIN         |           | 14336 |   168K|   728   (1)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| DIM_TABLE |     5 |    20 |     2   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| T1        |   400K|  3125K|   725   (1)| 00:00:01 |
--------------------------------------------------------------------------------
                                                                                
Predicate Information (identified by operation id):                             
---------------------------------------------------                             
                                                                                
   1 - access("T1"."TYPE_CODE"=CASE "OBJECT_TYPE" WHEN 'TABLE' THEN             
              "TYPE_CODE" ELSE (-1) END )   

As you see the last explain plans do not contain filter predicate anymore and we have got the correct cardinality. And the trace file shows that optimizer was going to use histogram of the virtual column for join processing:

***************************************
BASE STATISTICAL INFORMATION
***********************
Table Stats::
  Table: DIM_TABLE  Alias: DT
  #Rows: 5  SSZ: 0  LGR: 0  #Blks:  1  AvgRowLen:  13.00  NEB: 0  ChainCnt:  0.00  ScanRate:  0.00  SPC: 0  RFL: 0  RNF: 0  CBK: 0  CHR: 0  KQDFLG: 1
  #IMCUs: 0  IMCRowCnt: 0  IMCJournalRowCnt: 0  #IMCBlocks: 0  IMCQuotient: 0.000000
  Column (#3): SYS_STUE_0VSFXQ_4T7QQLFLMZRDPV (NUMBER)
    AvgLen: 4 NDV: 2 Nulls: 0 Density: 0.100000 Min: -1.000000 Max: 1.000000
    Histogram: Freq  #Bkts: 2  UncompBkts: 5  EndPtVals: 2  ActualVal: yes
***********************
Table Stats::
  Table: T1  Alias: T1
  #Rows: 400000  SSZ: 0  LGR: 0  #Blks:  2664  AvgRowLen:  43.00  NEB: 0  ChainCnt:  0.00  ScanRate:  0.00  SPC: 0  RFL: 0  RNF: 0  CBK: 0  CHR: 0  KQDFLG: 1
  #IMCUs: 0  IMCRowCnt: 0  IMCJournalRowCnt: 0  #IMCBlocks: 0  IMCQuotient: 0.000000
  Column (#3): TYPE_CODE(NUMBER)
    AvgLen: 3 NDV: 5 Nulls: 0 Density: 0.017180 Min: 1.000000 Max: 5.000000
    Histogram: Freq  #Bkts: 5  UncompBkts: 400000  EndPtVals: 5  ActualVal: yes
try to generate single-table filter predicates from ORs for query block SEL$1 (#0)
finally: "T1"."TYPE_CODE"=CASE "DT"."OBJECT_TYPE" WHEN 'TABLE' THEN "DT"."TYPE_CODE" ELSE (-1) END 

Note: there is another way to solve the problem and will be published in a future blog post, stay tuned 🙂

Advertisements

2 Comments »

  1. […] of days ago, Chinar Aliyev has written an article about a method for persuading the optimizer to calculate the correct cardinality estimate without using for any undocumented, or otherwise dubious, mechanisms. His method essentially relies […]

    Pingback by Join Cardinality | Oracle Scratchpad — October 3, 2018 @ 11:01 am | Reply

  2. […] previous blog post I described a way how to estimate join size correctly. I used two virtual columns in order to avoid […]

    Pingback by Join Skew Handling Subject to Filter Conditions-2 | Chinar Aliyev`s blog — October 19, 2018 @ 11:33 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: