12 Replies Latest reply on Dec 22, 2015 6:52 PM by BPeaslandDBA

    Join Cardinality Estimation

    933257

      Hi I am using version- 11.2.0.4.0 - Oracle.

      I have below stats details for two tables with no histograms on columns

       

      Table T1 - NUM_ROWS -  8,900,759
      ------------------------------
      column_name      num_nulls      num_distinct    density
      c1                  0              100800       9.92063492063492E-6
      c2                  0              7184         0.000139198218262806


      Table T2 - NUM_ROWS - 28835
      ---------------------------------
      column_name      num_nulls      num_distinct    density
      c1                  0              101       0.0099009900990099
      c2                  0              39         0.0256410256410256

       

      Query:
      ------

      select * from T1, T2
      WHERE t1.c1= t2.c1;


      Execution Plan
      ----------------------------------------------------------
      Plan hash value: 4149194932

      --------------------------------------------------------------------------------------------------------------------------------
      | Id  | Operation                   | Name                     | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |
      --------------------------------------------------------------------------------------------------------------------------------
      |   0 | SELECT STATEMENT            |                          |  2546K|   675M|       | 65316   (1)| 00:13:04 |       |       |
      |*  1 |  HASH JOIN                  |                          |  2546K|   675M|  5944K| 65316   (1)| 00:13:04 |       |       |
      |   2 |   TABLE ACCESS STORAGE FULL | T2 | 28835 |  5603K|       |   239   (1)| 00:00:03 |       |       |
      |   3 |   PARTITION RANGE ALL       |                          |  8900K|   670M|       | 26453   (1)| 00:05:18 |     1 |     2 |
      |   4 |    TABLE ACCESS STORAGE FULL| T1             |  8900K|   670M|       | 26453   (1)| 00:05:18 |     1 |     2 |
      --------------------------------------------------------------------------------------------------------------------------------


      as below rule says its

       

      Join Selectivity =
      ((num_rows(t1) - num_nulls(t1.c1)) / num_rows(t1)) *
      ((num_rows(t2) - num_nulls(t2.c2)) / num_rows(t2)) /
      greater(num_distinct(t1.c1), num_distinct(t2.c2))

       

      Join selectivity=   ((((28835 - 0)/(28835)) * ((8900759-0)/8900759))/ 100800)

       

      join cardinality = join selectivity*num_rows(t1)*num_rows(t2)
                       = ((((28835 - 0)/(28835)) * ((8900759-0)/8900759))/ 100800) * (8900759*28835)
            = 2546164.54 which matches to the above plan output.

       

       

      but when i add another join condition as below , i am not able to understand, how the join cardinality becomes 28835? And how different will it behave in case of presence of histogram?

       

      select * from T1, T2
      WHERE t1.c1= t2.c1
      and t1.c2=t2.c2;


      Execution Plan
      ----------------------------------------------------------
      Plan hash value: 1645075573

      ---------------------------------------------------------------------------------------------------------------------------------
      | Id  | Operation                    | Name                     | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |
      ---------------------------------------------------------------------------------------------------------------------------------
      |   0 | SELECT STATEMENT             |                          | 28835 |  7828K|       | 65316   (1)| 00:13:04 |       |       |
      |*  1 |  HASH JOIN                   |                          | 28835 |  7828K|  5944K| 65316   (1)| 00:13:04 |       |       |
      |   2 |   PART JOIN FILTER CREATE    | :BF0000                  | 28835 |  5603K|       |   239   (1)| 00:00:03 |       |       |
      |   3 |    TABLE ACCESS STORAGE FULL | T2 | 28835 |  5603K|       |   239   (1)| 00:00:03 |       |       |
      |   4 |   PARTITION RANGE JOIN-FILTER|                          |  8900K|   670M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|
      |   5 |    TABLE ACCESS STORAGE FULL | T1             |  8900K|   670M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|
      ---------------------------------------------------------------------------------------------------------------------------------

       

       

      Total selectivity = selectivity of c1 * selectivity of c2

                               = ((((28835 - 0)/(28835)) * ((8900759-0)/8900759))/ 100800)*((((28835 - 101)/(28835)) * ((8900759-0)/8900759))/ 7184)


      total cardinality = total selectivity*num_rows(t1)*num_rows(t2)

                       =

      ((((28835 - 0)/(28835)) * ((8900759-0)/8900759))/ 100800)*((((28835 - 101)/(28835)) * ((8900759-0)/8900759))/ 7184)*(8900759)*(28835) = 353.18 but its not matching the above outut

        • 1. Re: Join Cardinality Estimation
          Jonathan Lewis

          Best read on the topic is from Alberto Dell'Era: Alberto Dell'Era: investigations

           

          There are variations, but in the simplest case the selectivity of a pair of predicate is the product of the separate selectivities with a limit of 1/num_rows

          For the join selectivity with two equality predicates we take both selectivities (based on num_rows) from the same side of the join

           

          T1 - 100,800 * 7184 = 724147200:  take the upper bound of 8,900,759

          T2 - 101 * 39 = 3939

           

          Join Selectivity = 1/8,900,859

          Join Cardinality = 8,900859 * 28,835 * 1/8,900,859  = 28,835

           

          Regards

          Jonathan Lewis

          1 person found this helpful
          • 2. Re: Join Cardinality Estimation
            933257

            Thank you so much. I will check the url in detail which you mentioned.  But one quick thing want to share with you, that the actual no of rows out of the second join condition comes out to br 4.9million but optimizer estimates it as 28835 and due to this all the future join conditions got worse and I am getting very poor plan which runs for hours. To cater these type of scenario, is possible HINT is the only rescue or we have any other work around?

             

            Although I tried but not seeing any benefit of creating top n frequency histogram on column t2.c1 as that was seems to be skewed obe.

            • 3. Re: Join Cardinality Estimation
              Jonathan Lewis

              Unless there's a very big skew to the data the most likely problem is that there is a strong correlation between the c1 and c2 columns on the larger table (or possibly on both). You may find that creating a column group on (c1, c2) on t1 is sufficient to address the critical problem.

               

              Regards

              Jonathan Lewis

              • 4. Re: Join Cardinality Estimation
                933257

                I tried gathering extended stats as below but seeing no change in cardinality estimation


                SELECT DBMS_STATS.CREATE_EXTENDED_STATS('USER', 'T1', '(c1,c2)') FROM DUAL;

                 

                then verified the plan


                Execution Plan
                ----------------------------------------------------------
                Plan hash value: 1645075573

                ---------------------------------------------------------------------------------------------------------------------------------
                | Id  | Operation                    | Name                     | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |
                ---------------------------------------------------------------------------------------------------------------------------------
                |   0 | SELECT STATEMENT             |                          | 28835 |  7828K|       | 65316   (1)| 00:13:04 |       |       |
                |*  1 |  HASH JOIN                   |                          | 28835 |  7828K|  5944K| 65316   (1)| 00:13:04 |       |       |
                |   2 |   PART JOIN FILTER CREATE    | :BF0000                  | 28835 |  5603K|       |   239   (1)| 00:00:03 |       |       |
                |   3 |    TABLE ACCESS STORAGE FULL | T2 | 28835 |  5603K|       |   239   (1)| 00:00:03 |       |       |
                |   4 |   PARTITION RANGE JOIN-FILTER|                          |  8900K|   670M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|
                |   5 |    TABLE ACCESS STORAGE FULL | T1             |  8900K|   670M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|
                ---------------------------------------------------------------------------------------------------------------------------------

                 

                then gathered histogram on the column group and verified the plan

                 

                exec DBMS_STATS.GATHER_TABLE_STATS ( OWNNAME => 'user' ,TABNAME => 'T1' ,ESTIMATE_PERCENT => DBMS_STATS.AUTO_SAMPLE_SIZE ,METHOD_OPT => 'FOR COLUMNs SYS_STULDV#AIWU61Z5BDV15BELFQ4' );

                 

                SELECT column_name,
                       t.num_distinct,
                       t.histogram, t.density
                FROM   dba_stat_extensions e
                       JOIN dba_tab_col_statistics t ON e.extension_name=t.column_name
                AND    t.table_name = 'T1';

                 

                column_name                            num_distinct     Histogram       density
                SYS_STULDV#AIWU61Z5BDV15BELFQ4          593024        HEIGHT BALANCED  9.08821531026416E-13

                 

                i still see same cardinality estimation with no change as below.


                Execution Plan
                ----------------------------------------------------------
                Plan hash value: 1645075573

                ---------------------------------------------------------------------------------------------------------------------------------
                | Id  | Operation                    | Name                     | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |
                ---------------------------------------------------------------------------------------------------------------------------------
                |   0 | SELECT STATEMENT             |                          | 28835 |  8166K|       | 70364   (1)| 00:14:05 |       |       |
                |*  1 |  HASH JOIN                   |                          | 28835 |  8166K|  5944K| 70364   (1)| 00:14:05 |       |       |
                |   2 |   PART JOIN FILTER CREATE    | :BF0000                  | 28835 |  5603K|       |   239   (1)| 00:00:03 |       |       |
                |   3 |    TABLE ACCESS STORAGE FULL | T2 | 28835 |  5603K|       |   239   (1)| 00:00:03 |       |       |
                |   4 |   PARTITION RANGE JOIN-FILTER|                          |  8900K|   772M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|
                |   5 |    TABLE ACCESS STORAGE FULL | T1             |  8900K|   772M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|
                ---------------------------------------------------------------------------------------------------------------------------------

                • 5. Re: Join Cardinality Estimation
                  SUPRIYO DEY

                  please try with Dynamic Sampling.

                  • 6. Re: Join Cardinality Estimation
                    Jonathan Lewis

                    Did you gather stats (without histogram) on the extended stats after creating them ? It looks as if they weren't created (using size auto_sample_size).

                    You shouldn't need to have matching extended stats at the opposite end of the join, but if the set at one end doesn't work by itself I would create them at the other as well.

                     

                    Funny things can happen when you mix histograms and extended stats, so don't try histograms until you need to.

                     

                    Regards

                    Jonathan Lewis

                    • 7. Re: Join Cardinality Estimation
                      Jonathan Lewis

                      Additionally, if the num_distinct shown when you have the histogram is appropriate then the estimated join rows will be about 429,000 rather than your 4.9M.. This means either a significant skew on the join columns, or a multiplying effect from the other end of the join.

                       

                      Regards

                      Jonathan Lewis

                      • 8. Re: Join Cardinality Estimation
                        933257

                        In previous case which i posted, i have gathered stats on the table with no histogram(for all column size 1) on the individual column level. But after creating the column group i had collected histogram on the column group only, and as i had shown i saw no change in join cardinality.

                         

                        Now i tried collecting stats on the table again with no histogram on the column/column group, i am still seeing no change in join cardinality.

                         

                        exec DBMS_STATS.GATHER_TABLE_STATS ( OWNNAME => 'USER' ,TABNAME => 'T2' ,ESTIMATE_PERCENT => DBMS_STATS.AUTO_SAMPLE_SIZE ,METHOD_OPT => 'FOR All columns size 1' );

                         

                        SELECT column_name,
                               t.num_distinct,
                               t.histogram, t.density
                        FROM   dba_stat_extensions e
                               JOIN dba_tab_col_statistics t ON e.extension_name=t.column_name
                        AND    t.table_name = 'T2';

                         

                        column_name                     Num_distinct    Histogram       Density 
                        SYS_STULDV#AIWU61Z5BDV15BELFQ4 593024         NONE         1.68627239369739E-6

                         

                         

                         

                         

                        ----------------------------------------------------------
                        Plan hash value: 1645075573

                        ---------------------------------------------------------------------------------------------------------------------------------
                        | Id  | Operation                    | Name                     | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |
                        ---------------------------------------------------------------------------------------------------------------------------------
                        |   0 | SELECT STATEMENT             |                          | 28835 |  8166K|       | 70364   (1)| 00:14:05 |       |       |
                        |*  1 |  HASH JOIN                   |                          | 28835 |  8166K|  5944K| 70364   (1)| 00:14:05 |       |       |
                        |   2 |   PART JOIN FILTER CREATE    | :BF0000                  | 28835 |  5603K|       |   239   (1)| 00:00:03 |       |       |
                        |   3 |    TABLE ACCESS STORAGE FULL | T1 | 28835 |  5603K|       |   239   (1)| 00:00:03 |       |       |
                        |   4 |   PARTITION RANGE JOIN-FILTER|                          |  8900K|   772M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|
                        |   5 |    TABLE ACCESS STORAGE FULL | T2             |  8900K|   772M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|


                        The table T1 is a global temporary table and i wont be able to have the extended stats collection on columns for them.

                         

                        And also in any of the above tested scenario, I didn't get the join cardinality '429,000' which I think , would have been much closer to 4.9 million and would have influence the optimizer to have better execution plan rather 28835.

                        • 9. Re: Join Cardinality Estimation
                          Jonathan Lewis

                          I'm probably missing something obvious here.

                           

                          A couple of easy questions:

                          Are both the columns in the join in the partition key, or just one of them ?

                          how do the low and high values of the two sets of columns compare

                          how many partitions in the range-partitioned table

                          how many partitions do you expect to be visiting in the range-partitioned table

                          how many (if any) of the partitions are completely empty

                          have you tried creating the column group and collecting stats on it at the other end of the join  (also no histograms)

                          are you using EXPLAIN PLAN, or actually running the query ? If the latter are you flushing the shared pool after collecting stats ?

                          Can you publish the predicate section so that we can see what Oracle is doing with your join predicates.

                           

                          Slightly harder

                          1) Are there any combinations of values as either end of the join that are hugely more popular than anything else in the table.

                          select c1, c2, count(*) from t1 group by c1, c2 having count(*) > 10 /* adjust as necessary */ order by count(*) desc;

                           

                          2) Is there any way the join (and the small table) could be targetted at a subset of the partitions that happen to be the larger partitions

                           

                           

                          Update: looking back it seems as if you have two partitions and c2 is your partitioning column.

                           

                          Regards

                          Jonathan Lewis

                          1 person found this helpful
                          • 10. Re: Join Cardinality Estimation
                            933257

                            -->C2 for table T2 is range partitioned column. T1 is non partitioned.
                            -->There are two range partitions for T2. And one of them is empty, data resides in only one partition.
                            -->As one partition is empty, so it would visit only one partition for getting the final results.
                            -->I am using 'set autotrace traceonly explain' for getting the plan for the query.


                            -->below is the max and min value for c1 and c2 for T2

                            max(c1)  min(c1)    max(c2)                 Min(c2)
                            383759  86         2/28/2011 11:59:38 PM 2/28/2011 12:00:02 AM

                            below is the max and min value for c1 and c2 for T1

                            max(c1)  min(c1)    max(c2)                 Min(c2)
                            354087  4860    2/28/2011 11:55:47 PM 2/28/2011 12:07:49 AM

                             

                            -->Given below is the plan with predicate section

                            Execution Plan
                            ----------------------------------------------------------
                            Plan hash value: 1645075573

                            ---------------------------------------------------------------------------------------------------------------------------------
                            | Id  | Operation                    | Name                     | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |
                            ---------------------------------------------------------------------------------------------------------------------------------
                            |   0 | SELECT STATEMENT             |                          | 28835 |  8166K|       | 70364   (1)| 00:14:05 |       |       |
                            |*  1 |  HASH JOIN                   |                          | 28835 |  8166K|  5944K| 70364   (1)| 00:14:05 |       |       |
                            |   2 |   PART JOIN FILTER CREATE    | :BF0000                  | 28835 |  5603K|       |   239   (1)| 00:00:03 |       |       |
                            |   3 |    TABLE ACCESS STORAGE FULL | T1 | 28835 |  5603K|       |   239   (1)| 00:00:03 |       |       |
                            |   4 |   PARTITION RANGE JOIN-FILTER|                          |  8900K|   772M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|
                            |   5 |    TABLE ACCESS STORAGE FULL | T2             |  8900K|   772M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|
                            ---------------------------------------------------------------------------------------------------------------------------------

                            Predicate Information (identified by operation id):
                            ---------------------------------------------------

                               1 - access("T2"."C2"="T1"."C2" AND "T2"."C1"="T1"."C1")
                              

                            -->i see below three values in current data set for T2 which is having count > 10,000
                            C1         C2                   Count(*)
                            171966 2/28/2011 7:21:14 AM 14990
                            41895 2/28/2011 8:41:36 AM 12193
                            7408 2/28/2011 6:16:20 AM 12158
                            53120 2/28/2011 6:16:13 AM 7931
                            51724 2/28/2011 6:03:22 PM 6783
                            51724 2/28/2011 6:02:58 PM 6757
                            51724 2/28/2011 4:02:22 PM 6451
                            51724 2/28/2011 4:02:01 PM 6388
                            51724 2/28/2011 2:01:29 PM 5979
                            234233 2/28/2011 7:21:14 AM 5975
                            51724 2/28/2011 2:01:09 PM 5917
                            7408 2/28/2011 6:16:13 AM 5355
                            51724 2/28/2011 8:04:18 PM 5074
                            51724 2/28/2011 8:03:54 PM 5058



                            i see below three values in current data set for T1 which is having count > 75
                            C1         C2                   Count(*)
                            4860 2/28/2011 7:33:45 PM 82
                            31217 2/28/2011 11:27:54 PM 82
                            31217 2/28/2011 11:48:14 PM 79
                            4860 2/28/2011 5:36:07 PM 78
                            4860 2/28/2011 8:00:11 PM 78
                            4860 2/28/2011 6:20:13 PM 78
                            4860 2/28/2011 2:35:39 PM 78
                            4860 2/28/2011 7:48:06 PM 77
                            4860 2/28/2011 12:30:29 PM 77
                            4860 2/28/2011 3:32:31 PM 77
                            4860 2/28/2011 5:48:05 PM 76
                            4860 2/28/2011 5:02:26 PM 76
                            4860 2/28/2011 10:27:02 PM 76

                             

                            -->Yes the join is targeted on the larger partition, as because another is just empty.
                              
                            -->Below is the stats and plan after getting extended stats collected on column group c1, c2 of T1(by converting it to physical one) with no histogram. now its giving a better estimate which is closure to actual cardinality.But issue is that in reality, table T1 is global temp table, so i wont be able to gather extended stat on this. Is there any other work around, to get this estimation?
                             

                            column_name                                                          Num_distinct   Histogram   Density

                            SYS_STUMW3X8MDKZEJOG$$AHPEND1W           2699             NONE        0.000370507595405706
                              
                               Execution Plan
                            ----------------------------------------------------------
                            Plan hash value: 1645075573

                            ---------------------------------------------------------------------------------------------------------------------------------
                            | Id  | Operation                    | Name                     | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |
                            ---------------------------------------------------------------------------------------------------------------------------------
                            |   0 | SELECT STATEMENT             |                          |   432K|   124M|       | 70380   (1)| 00:14:05 |       |       |
                            |*  1 |  HASH JOIN                   |                          |   432K|   124M|  6280K| 70380   (1)| 00:14:05 |       |       |
                            |   2 |   PART JOIN FILTER CREATE    | :BF0000                  | 28835 |  5941K|       |   239   (1)| 00:00:03 |       |       |
                            |   3 |    TABLE ACCESS STORAGE FULL | T1 | 28835 |  5941K|       |   239   (1)| 00:00:03 |       |       |
                            |   4 |   PARTITION RANGE JOIN-FILTER|                          |  8900K|   772M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|
                            |   5 |    TABLE ACCESS STORAGE FULL | T2             |  8900K|   772M|       | 26453   (1)| 00:05:18 |:BF0000|:BF0000|
                            ---------------------------------------------------------------------------------------------------------------------------------

                            Predicate Information (identified by operation id):
                            ---------------------------------------------------

                               1 - access("T2"."C2"="T1"."C2" AND "T2"."C1"="T1"."C1")

                            • 11. Re: Join Cardinality Estimation
                              Jonathan Lewis

                              It would have been quite useful to have been told from the start that t1 was a global temporary table.

                              Is it declared as "on commit preserve rows" or "on commit delete rows" (the default).

                               

                              To get the correct calculation you need the column group to be defined at both ends; however you can get the same effect if you have the column group at the permanent end and an index on the two columns at the temporary end - provided the index has suitable stats on it, and that's quite easy if you have a GTT defined with "on commit preserve" since you can create the index while the table is empty, get some representative data into it, then gather stats.  (NOTE - the index doesn't have to be useful, it merely needs to exist so that the "column group" num_distinct can be seen in the index's distinct_keys.

                               

                              If the GTT is the default "on commit delete" then find out how you got the column stats on it that you quoted in your first post and use the same strategy to get index stats onto the index.

                               

                              Regards

                              Jonathan Lewis

                              • 12. Re: Join Cardinality Estimation
                                BPeaslandDBA

                                Keep in mind that with a GTT, Oracle cannot see the table contents. The data in the GTT is private to that session. So when Oracle runs its nightly job to calculate stats, that table likely has, from Oracle's viewpoint, zero rows in it. The stats think the table is empty. One of the tricks I've used is to populate the table with some sample data and then determine what the stats are and use DBMS_STATS.SET_TABLE_STATS to force the stats to "good" values. Then use LOCK_TABLE_STATS so they don't get overwritten. Now the CBO will have better stats to (hopefully) make a better-informed decisions. This doesn't always work because sometimes stats that lead to good plans for one session can lead to bad plans for other sessions that may have a different data volume in the GTT.

                                 

                                If you upgrade to 12c, you can have session private stats on the GTT. See this for more info: https://oracle-base.com/articles/12c/session-private-statistics-for-global-temporary-tables-12cr1

                                I like the session private stats better because then the stats are for that session with that session's data. This helps solve the issues where the "good" stats I picked are only good for a few sessions, not all sessions.

                                 

                                I did find with private session stats in 12c, that after I populated the GTT with data in my session, a call to DBMS_STATS.GATHER_TABLE_STATS can introduce locking issues for highly-concurrent access to the GTT. This caused major issues with one of my applications that uses a GTT seemingly everywhere. So what I did was in the package code where the GTT was populated with data, I determined how many rows were inserted and then used DBMS_STATS.SET_TABLE_STATS to set the table stats for that session and this seemed to keep concurrency issues at bay and it improved the CBO's decisions when other parts of the app used that GTT.

                                 

                                HTH,

                                Brian

                                1 person found this helpful