# 12c Histogram: TOP-Frequency

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

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.