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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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:
|
1 2 3 4 5 6 7 8 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
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,U<span style="color: red;">8U</span> DBMS_STATS: <span style="color: red;">start processing top n values for column "N2"</span> 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: <span style="color: red; background-color: yellow;">remove last bucket</span>: Typ=2 Len=2: c1,2b add: Typ=2 Len=3: c2,2,1a DBMS_STATS: <span style="color: red; background-color: yellow;">removal_count: 1</span> 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: <span style="color: red;">Mark column "N2" as top N computed</span> DBMS_STATS: Need Actual Values (DSC_EAVS) DBMS_STATS: Histogram Type: <code>TOP-FREQUENCY</code> 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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 <span style="color: red;">TOP-FREQUENCY</span> |
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:
|
1 2 |
InfPoint = <span style="color: red;">round</span> ((N-1)/N * table (num_rows)) InfPoint = <span style="color: red;">round</span> ((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.
|
1 |
TOP-8 N2</code> rows >= 175 rows |
And, as shown in Anju Garg‘s article, the TOP-8 N2 can be computed using the following SQL:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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:
|
1 2 3 4 5 |
SQL> select min(n2), max(n2) from t_topfreq; MIN(N2) MAX(N2) ---------- ---------- 7 125 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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:
|
1 2 |
DBMS_STATS: <span style="color: red;">remove last bucket</span>: 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):
|
1 2 3 4 5 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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:
|
1 |
E-Rows = value_count * num_rows/sample_size |
Applied to N2 = 42, the above estimation formula gives this:
|
1 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
SQL> select count(1) from t_topfreq where n2 = <span style="color: red;">42</span>; 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 | <span style="color: red;">106</span> | ------------------------------------------------ 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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:
|
1 2 |
E-Rows = min (value_count of popular values)/<span style="color: red;">2</span> E-Rows = 1/2 = 0.5 rounded to <span style="color: red;">1</span> |
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:
|
1 2 3 4 5 6 7 8 9 10 |
SINGLE TABLE ACCESS PATH Single Table Cardinality Estimation for T_TOPFREQ[T_TOPFREQ] SPD: Return code in qosdDSDirSetup: NOCTX, estType = TABLE Column (#2): <span style="color: red;">NewDensity: 0.020000</span>, OldDensity: 0.002500 <span style="color: red;">BktCnt: 196</span> 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: <span style="color: red;">Top-Freq</span> #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:
|
1 |
E-Rows = num_rows * NewDensity |
The NewDensity, when there is no extreme value forcing, is calculated using the following formula:
|
1 |
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:
|
1 2 |
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:
|
1 2 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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.
Load comments