As of Oracle version 12.1, if a number of buckets N in a histogram is less than the number of distinct values in the data set, Oracle will not generate the instable and imprecise legacy Height Balanced histogram. Instead, two new types of histogram are possible: TOP-Frequency and Hybrid. In order to select between the later and the former type of histogram, Oracle first proceeds to a determination step. It examines how representative the TOP-N distinct values are relative to all values in the data set. If the TOP-N values accounts for more than a certain threshold, a TOP-Frequency is used. When the TOP-N values fail to satisfy the threshold condition, a Hybrid histogram is calculated. This first article investigates the TOP-Frequency histogram. It shows how Oracle determines the TOP-Frequency threshold, examines how the low and high values of the data set influence this threshold value and outlines the arithmetic used by Oracle to work out the cardinality estimates of both popular and non-popular TOP-Frequency histogram.

TOP-Frequency: pre-requisites

Here’s below the simple model we are going to use in order to illustrate the TOP-Frequency histogram:

create table T_TopFreq as
select
    rownum n1
    , case when mod(rownum, 100000)   = 0 then   90
           when mod(rownum, 10000)    = 0 then   180
          when mod(rownum, 1000)= 0 then   84
              when mod(rownum, 100)      = 0 then   125
              when mod(rownum,50)        = 2 then   7
              when mod(rownum-1,80)      = 2 then   22
              when mod(rownum, 10)       = 0 then   19
              when mod(rownum-1,10)      = 5  then   15
              when mod(rownum-1,5)       = 1  then   11
              when trunc((rownum -1/3)) < 5  then   25
              when trunc((rownum -1/5)) < 20  then   33
      else 42
        end n2   
from dual
connect by level <= 2e2;

The above data set contains 200 rows, of which the n2 column has 9 distinct values as shown below:

SQL> compute sum label 'Total rows' of cnt on report
SQL> break   on report
SQL> select *
    from
    (select n2, count(1) cnt
     from t_topfreq
     group by n2
     order by n2);

        N2        CNT
---------- ----------
         7          4
        11         36
        15         20
        19         18
        22          3
        25          3
        33          8
        42        106
       125          2
           ----------
Total rows        200

9 rows selected.

In order to qualify for a TOP-Frequency histogram, the following three conditions must be satisfied:

  • The number of buckets used to gather the histogram must be less than the number of distinct values in the data set
  • The sampling percentage is the default one : AUTO_SAMPLE_SIZE
  • The top most frequent distinct values must exceed a certain threshold (explained later in this article)

The two first conditions are quite obvious, so let’s dig into some details for the third prerequisite.

Top Frequency: Inflexion point

In the following example, we are going to ask Oracle to gather statistics for the dataset above using fewer buckets (8) than the available number of distinct values (9). The AUTO_SAMPLE_SIZE default sampling will be used to ensure we don’t generate a Height Balance histogram. In order to check what Oracle is doing behind the scenes, we are going to trace the call to the dbms_stats package (under 12.1.0.2) as shown in the following:

SQL> exec dbms_stats.set_global_prefs ('TRACE', to_char (1+16)); 
SQL> BEGIN
     dbms_stats.gather_table_stats (user
                                  ,'T_TOPFREQ'
                                  , method_opt=> 'for columns n2 size 8');
   END;
/
SQL> exec dbms_stats.set_global_prefs('TRACE', null);

The ‘TRACE’ parameter in the first call above will trace any call to dbms_stats package by sending the corresponding trace file directly to the dbms_outpout current session. Here’s a snippet of this trace file:

DBMS_STATS:  NNV  NDV  AVG  MMX  HST  EP   RP   NNNP IND  CNDV HSTN HSTR  COLNAME
DBMS_STATS:   Y         Y                                                 N1
DBMS_STATS:   Y    Y    Y    Y    Y    Y    Y                        Y    N2
DBMS_STATS: Approximate NDV Options
DBMS_STATS: ACL,TOPN,NIL,NIL,RWID,U,U8U
DBMS_STATS: start processing top n values for column "N2"
DBMS_STATS: topn sql (len: 589):
DBMS_STATS: +++ select /*+  no_parallel(t) no_parallel_index(t) 
                           dbms_stats cursor_sharing_exact use_weak_name_resl
                           dynamic_sampling(0) no_monitoring 
				 xmlindex_sel_idx_tbl no_substrb_pad  
                        */ 
	          substrb(dump("N2",16,0,64),1,240) val
                ,rowidtochar(rowid) rwid 
	       from "XXXX"."T_TOPFREQ" t 
		where rowid in  
               (chartorowid('AAAJmWAAEAACN1zAAA'),chartorowid('AAAJmWAAEAACN1zAAB')
	         ,chartorowid('AAAJmWAAEAACN1zAAC'),chartorowid('AAAJmWAAEAACN1zAAF'		  ,chartorowid('AAAJmWAAEAACN1zAAG'),chartorowid('AAAJmWAAEAACN1zAAH')
	        ,chartorowid('AAAJmWAAEAACN1zAAJ'),chartorowid('AAAJmWAAEAACN1zAAU')) 
	   order by "N2"
DBMS_STATS: remove last bucket: Typ=2 Len=2: c1,2b add: Typ=2 Len=3: c2,2,1a
DBMS_STATS: removal_count: 1 total_nonnull_rows: 200 mnb:  8
DBMS_STATS:  adjusted coverage: .98
DBMS_STATS: hist_type in exec_get_topn: 2048 ndv:9 mnb:8
DBMS_STATS: Evaluating frequency histogram for col: "N2"
DBMS_STATS:  number of values = 8, max # of buckects = 8, pct = 100, ssize = 200
DBMS_STATS:   csr.hreq: 1 Histogram gathering flags: 2055
DBMS_STATS: done_hist in process_topn: TRUE csr.ccnt: 1
DBMS_STATS: Mark column "N2" as top N computed
DBMS_STATS:          Need Actual Values (DSC_EAVS)
DBMS_STATS:          Histogram Type: TOP-FREQUENCY Data Type: 2
DBMS_STATS:          Histogram Flags: 8196 Histogram Gathering Flags: 2310
DBMS_STATS:          Incremental: FALSE Fix Control 13583722: 1

The above trace file is clearly showing (start processing top n values for column "N2") that, before attempting to collect a Hybrid histogram, Oracle did internal arithmetic in order to process the TOP-8 distinct values for column N2 to see how representative they are when compared to the rest of the remaining values. That is, Oracle has tried to work out the proportion of unpopular values that are statistically insignificant when compared to very few distinct popular ones. If popular values dominate the dataset then Oracle will generate a TOP-Frequency histogram for the TOP-8 values and ignore the remaining insignificant values. The above trace file shows that Oracle has indeed succeeded to pass the threshold prerequisite (Mark column "N2" as top N computed) and produced a TOP-Frequency histogram as shown below:

SQL> select
        column_name
       ,num_distinct
       ,num_buckets
       ,sample_size
       ,histogram
     from
        user_tab_col_statistics
     where table_name = 'T_TOPFREQ'
     and column_name  = 'N2';

COLUMN_NAME  NUM_DISTINCT NUM_BUCKETS SAMPLE_SIZE HISTOGRAM
------------ ------------ ----------- ----------- ---------------
N2                      9           8        200 TOP-FREQUENCY

In fact, I have been playing with the above call to dbms_stats package changing the number of buckets several times until I succeeded in producing a TOP-FREQUENCY histogram with 8 buckets. Nevertheless, as specified in Anju Garg’s article, it is possible to derive the number of buckets upon which Oracle will generate a TOP-FREQUENCY histogram based on the following inflexion point (or threshold in Oracle words) where N represents the number of specified buckets:

               InfPoint = round ((N-1)/N * table (num_rows))
              InfPoint = round ((8-1)/8 * 200) = 175

In other words, to qualify for a TOP-FREQUENCY histogram, the TOP-8 N2 distinct values should occupy more than 175 rows in the data set i.e.

                     TOP-8 N2 rows >= 175 rows

And, as shown in Anju Garg‘s article, the TOP-8 N2 can be computed using the following SQL:

SQL> select
         sum (cnt) TopNRows
      from (select
               n2
              ,count(*) cnt
            from t_topfreq
            group by n2
            order by count(*) desc
            )
     where rownum <= 8;

  TOPNROWS
----------
       198

The TOP-8 N2 values occupy 198 rows which is more than the inflexion row count threshold of 175 rows. This is why the current configuration qualifies for a TOP-FREQUENCY.

Top Frequency: Inflexion point and low-high values

Whatever the type of histogram Oracle has to generate, the low and high values must be in the histogram information. When these two extreme values are naturally present in the TOP-N distinct values then the above threshold formula remains correct. However, when they are insignificant and negligible they will be forced into the histogram information. This value forcing is possible to the detriment of excluding a victim value from the actual TOP-N distinct values. The victim values are those with the less popular distinct value.

Let’s see whether the low and high values are among the TOP-8 N2 distinct values:

SQL> select min(n2), max(n2) from t_topfreq;

   MIN(N2)    MAX(N2)
---------- ----------
        7        125
SQL> SQL> select
            n2, cnt
         from (select
                 n2
                ,count(*) cnt
              from t_topfreq
              group by n2
              order by count(*) desc, n2
               )
        where rownum <= 8;


        N2        CNT
---------- ----------
        42        106
        11         36
        15         20
        19         18
        33          8
         7          4 → low value is present in the TOP-8
        22          3 → 22 is the first least popular value
        25          3

8 rows selected.

In the previous example, the highest value (125) is not among the TOP-8 N2 distinct values. However, as explained above, this extreme value has been forced in the histogram information as shown in the following:

SQL> select
         endpoint_actual_value value,
         endpoint_number,
         endpoint_number - (lag(endpoint_number,1,0)
                           over(order by endpoint_number)) value_count
     from
        user_tab_histograms
     where
        table_name    = 'T_TOPFREQ'
     and column_name  = 'N2'
     order by
     endpoint_number
     ;

VALUE      ENDPOINT_NUMBER VALUE_COUNT
---------- --------------- -----------
7                        4           4
11                      40          36
15                      60          20
19                      78          18
25                      81           3
33                      89           8
42                     195         106
125                    196           1 → forced high value with frequency 1

8 rows selected.

As you can see the insignificant high value 125 has been forced into the histogram table with a hardcoded frequency of 1. This forcing has been possible at the cost of a value exclusion from the TOP-8 naturally dominant values. And, as mentioned above, the victim value in this case is 22 representing the first value with the least popular frequency (3).

Notice that the above dbms_stats trace file also indicates that Oracle has proceeded to a remove-forcing operation via the following line:

DBMS_STATS: remove last bucket: Typ=2 Len=2: c1,2b add: Typ=2 Len=3: c2,2,1a
DBMS_STATS: removal_count: 1 total_nonnull_rows: 200 mnb: 8

Although the trace file is not very clear, it nevertheless indicates that something is removed to let a room for the high value 125 (Typ=2 Len=3: c2,2,1a):

SQL> select dump(125) high_value from dual;

HIGH_VALUE
---------------------
Typ=2 Len=3: 194,2,26

Whenever Oracle operates such an exclusion-forcing value into the histogram table, the TOP-N count of rows should be adjusted before to be compared with the threshold as shown in the following:

SQL> select
         sum (cnt) TopNRows
      from (select
               n2
              ,count(*) cnt
            from t_topfreq
            group by n2
            order by count(*) desc
            )
     where rownum <= 8;

  TOPNROWS
----------
       198

AdjustedTopNRows = TopNRows - count (least popular TOP-8) + 1 (forced frequency)
AdjustedTopNRows = 198 - 3 + 1 = 196

It’s worth noting that, in this particular case, both TopNRows and AdjustedTopNRows are greater than the threshold of 175 rows. However, whenever Oracle generates a Hybrid histogram where you think that your TOP-N setup qualify for the a TOP-FREQUENCY, you must ensure that you are comparing the correct TopNRows with the threshold number of rows.

2. Top Frequency: cardinality estimation

2.1 Popular values

The select statement exposed below shows the resulting metadata produced for captured popular N2 column values when it qualifies for TOP-FREQUENCY histogram due to the appropriate number of buckets (8):

SQL> select
         endpoint_actual_value value,
         endpoint_number - (lag(endpoint_number,1,0)
                           over(order by endpoint_number)) value_count
     from
        user_tab_histograms
     where
        table_name   = 'T_TOPFREQ'
     and column_name = 'N2'
     order by
        endpoint_number;

VALUE      VALUE_COUNT
---------- -----------
7                    4
11                  36
15                  20
19                  18
25                   3
33                   8
42                 106 ***
125                  1

8 rows selected.

For the above captured popular values, the Optimizer uses the following formula to calculate its cardinality estimates:

E-Rows = value_count * num_rows/sample_size

Applied to N2 = 42, the above estimation formula gives this:

E-Rows = 106 * 200/200 = 106

This is of course backed by the following execution plan where we can see that Oracle has come up with exactly the same cardinality estimation of 106:

SQL> select count(1) from t_topfreq where n2 = 42;

  COUNT(1)
----------
         106

SQL> select * from table(dbms_xplan.display_cursor);
------------------------------------------------
| Id  | Operation          | Name      | Rows  |
------------------------------------------------
|   0 | SELECT STATEMENT   |           |       |
|   1 |  SORT AGGREGATE    |           |     1 |
|*  2 |   TABLE ACCESS FULL| T_TOPFREQ |   106 |
------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("N2"=42)

However, the exclusion-forcing value operation done by Oracle in order to insert the high value into the histogram table makes both the forced value (125) and the excluded value (22) not following the same cardinality estimation formula. The next section discusses this particular case.

2.2 Non-Popular values

Since Oracle concentrated on capturing the most representative 8 N2 values over the available 9 distinct ones, then the following least occurring distinct values have not been captured and have been consequently considered to be non-popular:

SQL> with popular_val as
        (select
           endpoint_actual_value value
        from
           user_tab_histograms
        where
            table_name  = 'T_TOPFREQ'
        and column_name = 'N2')
       select distinct n2
      from t_topFreq all_val
      where not exists (select null
                        from
                           popular_val pop_val
                        where
                        all_val.n2 = pop_val.value);

        N2
----------
        22

Let’s now see what cardinality estimate Oracle will come up with for this non-popular non-captured value:

SQL> select count(1) from t_topfreq where n2 = 22;

  COUNT(1)
----------
         3

SQL> select * from table(dbms_xplan.display_cursor);
------------------------------------------------
| Id  | Operation          | Name      | Rows  |
------------------------------------------------
|   0 | SELECT STATEMENT   |           |       |
|   1 |  SORT AGGREGATE    |           |     1 |
|*  2 |   TABLE ACCESS FULL| T_TOPFREQ |     4 |
------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("N2"=22)

I have to restrain the enthusiasm of those using the ‘‘half least popular value” rule to get the selectivity of a non-popular frequency histogram before they extend it to the current non-popular top-frequency using the following formula:

E-Rows = min (value_count of popular values)/2
E-Rows = 1/2 = 0.5 rounded to 1

The best way to reverse engineer the path used by Oracle to get its cardinality estimates is to use the corresponding 10053 trace file, of which a snippet is shown below:

SINGLE TABLE ACCESS PATH 
  Single Table Cardinality Estimation for T_TOPFREQ[T_TOPFREQ] 
  SPD: Return code in qosdDSDirSetup: NOCTX, estType = TABLE
  Column (#2): 
NewDensity: 0.020000, OldDensity: 0.002500 BktCnt: 196 PopBktCnt:195, PopValCnt:7, NDV:9
  Column (#2): N2(NUMBER)
    AvgLen: 4 NDV: 9 Nulls: 0 Density: 0.020000 Min: 7.000000 Max: 125.000000
    Histogram: Top-Freq  #Bkts: 196  UncompBkts: 196  EndPtVals: 8  ActualVal: yes
  Table: TOPFREQ3 Alias: TOPFREQ3
    Card: Original: 200.000  Rounded: 4  Computed: 4.000000  Non Adjusted: 4.000000

This tends to suggest that Oracle is simply using the following formula to compute the selectivity of non-popular (insignificant) TOP-Frequency values:

E-Rows = num_rows * NewDensity

The NewDensity, when there is no extreme value forcing, is calculated using the following formula:

NewDensity = (sample_size-TopNRows)/(num_distinct-num_buckets)/sample_size

And the formula exposed below when Oracle has forced an extreme value into the histogram information:

NewDensity = (sample_size- AdjustedTopNRows)/(num_distinct-num_buckets)/sample_size
NewDensity = (200 – 196) /(9-8)/200 = 0.02

Finally, using this computed NewDensity and applying it in the above mentioned cardinality estimation formula for a non-popular TOP-Frequency gives the following:

E-Rows = num_rows * NewDensity
E-Rows = 200 * .02 = 4

There is however an odd situation happening here. Oracle is considering the forced high value 125 to be non-popular and is applying the NewDensity to get its selectivity as shown below:

SQL> select count(1) from t_topfreq where n2 = 125;

  COUNT(1)
----------
         2
SQL> select * from table(dbms_xplan.display_cursor);
------------------------------------------------
| Id  | Operation          | Name      | Rows  |
------------------------------------------------
|   0 | SELECT STATEMENT   |           |       |
|   1 |  SORT AGGREGATE    |           |     1 |
|*  2 |   TABLE ACCESS FULL| T_TOPFREQ |     4 |
------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("N2"=125)

Oracle is certainly flagging somewhere in its internal code that the high value present in the histogram has been forced, which allows the Optimizer to recognize it and use the ”appropriate” cardinality formula.

Conclusion

Prior to Oracle 12c, when histograms are collected for a data set using fewer buckets than the number of distinct values in the data set, Oracle will systematically generate an instable and imprecise Height Balanced histogram where at most 127 (254/2) values can be captured. With 12c under default value of AUTO_SAMPLE_SIZE, Oracle will not only cease to generate Height Balanced histogram, but will also carry out a preliminary determination step to see how dominant the TOP-N (N is the number of buckets) values are with regards to the total number of rows in the data set. If these TOP-N values are beyond the inflexion point then a TOP-FREQUENCY histogram is calculated for the dominant values while the neglected ones are considered to be hybrid non-popular values. This new type of histogram really helps the optimizer to come up with highly-accurate cardinality estimation, a fundamental prerequisite for optimal execution plans. In the next article we will examine the 12c Hybird histogram.

Tags: , ,