{"id":73136,"date":"2016-01-26T15:16:24","date_gmt":"2016-01-26T15:16:24","guid":{"rendered":"https:\/\/www.red-gate.com\/simple-talk\/uncategorized\/12c-hybrid-histogram\/"},"modified":"2021-07-14T13:07:18","modified_gmt":"2021-07-14T13:07:18","slug":"12c-hybrid-histogram","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/oracle-databases\/12c-hybrid-histogram\/","title":{"rendered":"12c Hybrid histogram"},"content":{"rendered":"

In the previous article about the Oracle 12c TOP-Frequency<\/a> histogram, we saw that Oracle carries out a preliminary determination step to see how dominant the TOP-N values are with regards to the total number of rows in\u00a0the data set. I demonstrated that a TOP-Frequency is possible provided a threshold condition is satisfied. This second article explores the Hybrid histogram type which occurs when the data set fails to qualify for a TOP-Frequency. Firstly, it shows that the method used by Oracle to compute a Hybrid histogram is strongly related to the TOP-Frequency preliminary determination step. It then shows that a column value can be popular<\/strong>, non-popular with an endpoint value<\/strong> or non-popular without an endpoint value<\/strong>. It then examines the formulas used by the optimizer to compute its cardinality estimation for each of the above three cases.<\/p>\n

Natural or Adjusted?<\/h2>\n

In order to investigate the method used by Oracle to calculate a Hybrid histogram, I am going to use a data set example taken from Jonathan Lewis<\/a>‘ blog as shown below:<\/p>\n

SQL> create table t1 (id number, n1 number);\r\n\r\nSQL> start InsT1.sqlScript (see downloadable script at the end<\/a>)<\/pre>\n
In the following, I am going to gather Hybrid histogram in 12c (12.1.0.2.0<\/span>) by specifying fewer buckets (20) than distinct value (37) for the current data set and using default sampling:<\/p>\n
SQL> exec dbms_stats.set_global_prefs ('TRACE', to_char (1+16)); \r\nSQL> BEGIN\r\n        dbms_stats.gather_table_stats\r\n          (user, 't1', method_opt => 'for columns n1 size 20<\/span>');\r\n     END;\r\n    \/\r\nSQL> exec dbms_stats.set_global_prefs('TRACE', null);<\/pre>\n
As in the previous article, the above call to dbms_stats package has been traced so that we can explore its content in the following snippet:<\/p>\n
DBMS_STATS:  NNV  NDV  AVG  MMX  HST  EP   RP   NNNP IND  CNDV HSTN HSTR  COLNAME\r\nDBMS_STATS:   Y    Y    Y    Y    Y    Y    Y    Y                   Y    N1\r\nDBMS_STATS: Approximate NDV Options\r\nDBMS_STATS: ACL,TOPN,NIL,NIL,RWID,U,U20U\r\nDBMS_STATS: start processing top n values for column \"N1\"\r\nDBMS_STATS:   >> frequency histograms is not feasible<\/span>\r\n                       (topn_values is null), skip!<\/span>\r\nDBMS_STATS: Iteration: 1 numhist: 1\r\nDBMS_STATS:  NNV  NDV  AVG  MMX  HST  EP   RP   NNNP IND  CNDV HSTN HSTR  COLNAME\r\nDBMS_STATS:                       Y    Y    Y    Y                   Y    N1\r\nDBMS_STATS: Building Histogram for N1<\/span>\r\nDBMS_STATS:  bktnum=20, nnv=100, snnv=100, sndv=37, est_ndv=37, mnb=20\r\nDBMS_STATS:  Trying hybrid histogram<\/pre>\n
As expected, Oracle started by carrying out the usual TOP-Frequency preliminary determination step. It is worth emphasizing that this data set fails to immediately qualify for a TOP-Frequency histogram because the TOP-20 values account for 80 rows while the threshold is 95 rows, as shown below:<\/p>\n
SQL> select\r\n         sum (cnt) TopNRows\r\n    from (select\r\n            n1\r\n           ,count(*) cnt\r\n         from t1\r\n         group by n1\r\n          order by count(*) desc\r\n          )\r\n   where rownum <= 20;\r\n\r\n  TOPNROWS\r\n----------\r\n        80\r\n\r\nSQL> select round ((20-1)\/20 * 100) threshold from dual;\r\n\r\n THRESHOLD\r\n----------\r\n        95<\/pre>\n
This is what I tend to qualify as a “Natural Hybrid”<\/em><\/strong> histogram representing a data set which doesn’t qualify for a TOP-Frequency because the threshold is greater than the naturally non-adjusted TopNRows<\/code>, as explained in the previous article. However, what happens for a data set that initially satisfies the TOP-Frequency threshold but\u00a0fails to qualify for a TOP-Frequency histogram because Oracle finds at the middle of the process that the Adjusted TopNRows<\/code> is greater than the threshold. A dbms_stats trace file of such a kind of data set shows a different content:<\/p>\n
DBMS_STATS: start processing top n values for column \"N1\"\r\nDBMS_STATS:   >> frequency histograms is not feasible<\/span>\r\n                       (topn_values is null), skip!<\/span>\r\nDBMS_STATS: start processing top n values for column \"N2\"<\/span>\r\nDBMS_STATS: topn sql (len: 589):\r\nDBMS_STATS: +++ select \/*+  no_parallel(t) no_parallel_index(t) \r\n                           dbms_stats cursor_sharing_exact use_weak_name_resl\r\n                           dynamic_sampling(0) no_monitoring \r\n\t\t\t\t xmlindex_sel_idx_tbl no_substrb_pad  \r\n                        *\/ \r\n\t           substrb(dump(\"N2\",16,0,64),1,240) val\r\n                 ,rowidtochar(rowid) rwid \r\n\t          from \"XXXX\".\"T1\" t \r\n\t\t    where rowid in  \r\n              (chartorowid('AAAJmWAAEAACN1zAAA'),chartorowid('AAAJmWAAEAACN1zAAB')\r\n\t        ,chartorowid('AAAJmWAAEAACN1zAAC'),chartorowid('AAAJmWAAEAACN1zAAF' \r\n\t        ,chartorowid('AAAJmWAAEAACN1zAAG'),chartorowid('AAAJmWAAEAACN1zAAH')\r\n\t        ,chartorowid('AAAJmWAAEAACN1zAAJ'),chartorowid('AAAJmWAAEAACN1zAAU')) \r\n\t        order by \"N2\"\t   \r\nDBMS_STATS: remove last bucket: Typ=2 Len=2: c1,2b add: Typ=2 Len=3: c2,2,1a<\/span>\r\nDBMS_STATS: removal_count: 1 total_nonnull_rows: 200 mnb:  8\r\nDBMS_STATS: Abort top-n histogram, as the addition of min\/max does not preserve the minimum coverage: .85225054 vs. .91<\/span>\r\nDBMS_STATS:  Building Histogram for N2\r\nDBMS_STATS:  Trying hybrid histogram<\/pre>\n
While in the first case Oracle immediately abandoned the Top-Frequency path, in the second case it went a little bit deeper before aborting the top-frequency process in favor of a Hybrid histogram. This is what I tend to qualify as the “Adjusted Hybrid”<\/em><\/strong> histogram representing a data set that fails to qualify for a TOP-Frequency because Oracle finds that the threshold is greater than the Adjusted TopNRows in the middle of the process.<\/p>\n
The method used by Oracle to compute Hybrid histogram depends on whether the data set is of a “Natural Hybrid”<\/em> type or of an “Adjusted Hybrid<\/em>” one. For the later type Oracle will take profit of the pre-process it has accomplished and transform the aborted top-frequency into a hybrid histogram. In the former case Oracle will use a bucket-frequency strategy.<\/p>\n
The data set used in this article qualifies for a “Natural Hybrid”<\/em> histogram. This is why the next section explains the method used by Oracle to collect this kind of hybrid histogram. The explanation of the “Adjusted Hybrid<\/em>” method will be left to a separate article.<\/p>\n
The method<\/h2>\n
Oracle has computed a Hybrid histogram for the current data set using a bucket size of 5 (sample_size\/num_buckets = 100\/20), as shown below:<\/p>\n
SQL> select\r\n       column_name\r\n      ,num_distinct\r\n      ,num_buckets\r\n      ,sample_size\r\n      ,histogram\r\n    from\r\n       user_tab_col_statistics\r\n    where table_name = 'T1'\r\n    and column_name  ='N1';\r\n\r\nCOLUMN_NAME  NUM_DISTINCT NUM_BUCKETS SAMPLE_SIZE HISTOGRAM\r\n------------ ------------ ----------- ----------- -----------\r\nN1                  37          20         100     HYBRID<\/pre>\n
At this stage of the article, let’s label this bucket size as the “original”<\/em><\/strong> bucket size. The method used by Oracle to compute this kind of histogram seems to obey the following strategy:<\/p>\n
    \n
  1. a distinct value should not be found in more than one bucket<\/li>\n
  2. a bucket size is allowed to be extended in order to contain all instances of the same distinct value<\/li>\n<\/ol>\n
    As long as the bucket size can be extended so that no distinct value will span multiple buckets, deciphering the new<\/em><\/strong> size of the extended buckets represents a crucial step in figuring out the method used by Oracle to compute Hybrid histogram. Below is the histogram information stored in the data dictionary:<\/p>\n
    SQL> SELECT\r\n        (row_number() over(order by ept_nbr)-1) NumBucket\r\n        ,ept_nbr\r\n        ,ept_act_val\r\n        ,rpt_cnt\r\n        ,ept_nbr - (lag(ept_nbr,1,0) over(order by ept_nbr)) \"new bucket size\"\r\n        ,bucket_size \"original bucket_size\"\r\n    FROM\r\n        (SELECT\r\n             ah.endpoint_number            ept_nbr\r\n            ,ah.endpoint_actual_value      ept_act_val\r\n            ,lag(ah.endpoint_number,1,0) over(order by ah.endpoint_number) ept_lag\r\n            ,ah.endpoint_repeat_count rpt_cnt\r\n            ,at.sample_size\/at.num_buckets bucket_size\r\n         FROM\r\n            user_tab_histograms      ah\r\n           ,user_tab_col_statistics  at\r\n         WHERE ah.table_name  = at.table_name\r\n         AND ah.column_name = at.column_name\r\n         AND ah.table_name  = 'T1'\r\n         AND ah.column_name = 'N1'\r\n       ) ORDER BY ept_nbr;\r\n\r\n NUMBUCKET    EPT_NBR EPT_ACT_VA    RPT_CNT new<\/span> bucket size original<\/span> bucket_size\r\n---------- ---------- ---------- ---------- --------------- --------------------\r\n         0          1 8                   1               1                    5\r\n         1          6 13                  3               5                    5\r\n         2         12 18                  2               6                    5\r\n         3         20 20                  5               8                    5\r\n         4         26 23                  2               6                    5\r\n         5         32 26                  3               6                    5\r\n         6         38 27                  6               6                    5\r\n         7         44 28                  6               6                    5\r\n         8         50 29                  6               6                    5\r\n         9         58 31                  5               8                    5\r\n        10         69 33                  8              11                    5\r\n        11         79 35                  7              10                    5\r\n***     12         86 38                  5               7                    5\r\n        13         90 41                  1               4                    5\r\n        14         92 42                  2               2                    5\r\n        15         95 43                  3               3                    5\r\n        16         96 44                  1               1                    5\r\n        17         97 45                  1               1                    5\r\n        18         98 46                  1               1                    5\r\n        19        100 59                  1               2                    5 \r\n20 rows selected.<\/pre>\n
    Excluding the boundaries, and up to the 13th<\/sup> endpoint number 86, all new<\/em><\/strong> bucket sizes are greater or equal<\/strong> to the original<\/em><\/strong> bucket size. In order to have a clue about what’s happening behind the scenes, let’s draw an ordered picture of the data set divided into 20 buckets each of size 5 as shown below:<\/p>\n
    8 12 12 13 13 |13<\/span> 15 16 16 17 |18 18 19 19 19|20 20 20 20 20|21 22 22 22 23|23<\/span> 24 24 25 26|\r\n\r\n26<\/span> 26 27 27 27|27<\/span> 27 27 28 28 |28<\/span> 28 28 28 29|29 29 29 29 29|30 30 30 31 31|31 31 31 32 32|\r\n\r\n32<\/span> 33 33 33 33|33<\/span> 33 33 33 34 |34<\/span> 34 35 35 35|35<\/span> 35 35 35 36|37 38 38 38 38|38<\/span> 39 39 40 41|\r\n\r\n42 42 43 43 43|44 45 46 50 59|<\/pre>\n
    Oracle starts walking the above ordered data set until it finds that value 13<\/span> <\/strong>traverses two buckets. Based on the first rule above, Oracle extends bucket n\u00b01 by moving all instances of 13<\/span><\/strong> from bucket_id n\u00b02 into it, giving us these intermediary results:<\/p>\n
    8 12 12 13 13 13<\/span>| 15 16 16 17 |18 18 19 19 19|<\/pre>\n
    Note that 13 is not only an endpoint number of bucket n\u00b01 but since it is uniquely located into a single bucket, Oracle is able to count its frequency of 3 (endpoint_repeat_count) as shown in the histogram information reproduced below:<\/p>\n
    NUMBUCKET    EPT_NBR EPT_ACT_VA    RPT_CNT new<\/span> bucket size original<\/span> bucket_size\r\n---------- ---------- ---------- ---------- --------------- --------------------\r\n         1          6 13<\/span>                  3<\/strong><\/span>               5                    5\r\n         2         12 18                  2               6                    5<\/pre>\n
    However, the above histogram information is showing that bucket n\u00b02 is of size 6 and has 18 as its endpoint number, with a frequency of 2. This is not in accordance with this picture:<\/p>\n
    8 12 12 13 13 13<\/span>| 15 16 16 17 |18 18 19 19 19|<\/pre>\n
    Looking at this new situation we can spot that when jumping from bucket n\u00b02 to bucket n\u00b03 there are no distinct values crossing multiple buckets. So we could keep this bucket with its new size of 4. This, however, is not the case. In fact, it appears that there is a third rule used by Oracle when generating “Natural Hybrid<\/em>” histogram which is:<\/p>\n
      \n
    1. do not create buckets with a size less than the original size (5) \u2013not applicable at the end of the data set\u2013<\/li>\n<\/ol>\n
      As long as the above rule is applied, with bucket n\u00b02 being of size 4, it has to be extended to reach a size of 5. This is why the first instance from bucket n\u00b03 (18) has to be moved into bucket n\u00b02 as in the following:<\/p>\n
      8 12 12 13 13 13| 15 16 16 17 18| 18 19 19 19|<\/pre>\n
      However, since there are two instances of 18 in bucket n\u00b03 they have to move together to obey the first rule in the strategy: no distinct values spanning multiple buckets. This gives us the following situation:<\/p>\n
      8 12 12 13\u00a013 13<\/span>| 15 16 16\u00a017 18 18<\/span>| 19 19 19<\/pre>\n
      As a result of this, we see that we do indeed have a bucket n\u00b02 of size 6, with 18 as its endpoint number and a frequency of 2. We will see later in this article that it is this rule 3) of the may introduce instability in the Hybrid histogram.<\/p>\n
      Oracle will continue traversing the rest of the data set applying the three point strategy above until it finds that value 23<\/strong><\/span> spans multiple buckets:<\/p>\n
      8 12 12 13\u00a013 13<\/span>| 15 16 16\u00a017 18 18<\/span>| 19 19 19 20 20 20 20 20<\/span>|-|21 22 22 22 23|23<\/span> 24 24 25 26|<\/pre>\n
      Applying the same rule again, all instances of values 23<\/strong><\/span> will be moved from bucket _id n\u00b06 to bucket_id n\u00b05, resulting in the following situation:<\/p>\n
      8 12 12 13\u00a013 13<\/span>| 15 16 16\u00a017 18 18<\/span>| 19 19 19 20 20 20 20 20<\/span>|-|21 22 22 22 23 23<\/span>| 24 24 25 26|<\/pre>\n
      And so on until it reaches the end of the data set producing such a final histogram result:<\/p>\n
      8 12 12 13 13 13<\/span>|15 16 16 17 18 18<\/span>|19 19 19 20 20 20 20 20<\/span>|-|21 22 22 22 23 23<\/span>|24 24 25 26 26<\/span> 26|27 27 27 27<\/span> 27 27|28 28 28<\/span> 28 28 28 |29 29 29 29 29 29|-|30 30 30 31 31 31 31 31<\/span>|32 32 32 33 33 33 33 33 33 33 33<\/span>|-|34 34<\/span> 34 35 35 35 35<\/span> 35 35 35|-|36 37 38 38 38 38 38<\/span>|-|39 39 40 41|42 42 |43 43 43|44|45|46|50 59|<\/pre>\n
      You will notice that, starting from the thirteenth buckets at value 39, the bucket extension rule and minimum size requirement seem to be ignored. At this stage of the data set Oracle is left with 14 distinct values to spread over 8 buckets. This last phrase paved the way to what seems to be the fourth rule applied by Oracle when gathering Natural Hybrid<\/em> histogram:<\/p>\n
        \n
      1. the original number of buckets (20) should not be reduced<\/li>\n<\/ol>\n
        Instead of reducing the original number of buckets (20), Oracle seems to divide the number of remaining distinct values (14) by the number of remaining buckets (8) and spread them accordingly. Unfortunately, I didn’t succeed in working out the exact strategy used by Oracle in this last step to spread the data across the remaining buckets, rather than the one which consists of keeping the initial number of buckets unchanged.<\/p>\n
        Popular or non-popular?<\/h2>\n
        Oracle developers and tuning specialists are interested in having optimal execution plans. When the Optimizer is supplied with accurate statistics it will mostly come up with an optimal execution plan. However, when the optimizer uses a histogram to get its cardinality estimate, the arithmetic it employs for a popular value differs from that used for a non-popular value. This is why identifying the popularity of a column value represents a crucial step in the tuning process. This section of the article shows when a column with a hybrid histogram is considered popular or not and shows the arithmetic used by Oracle to compute the cardinality estimate for each case.<\/p>\n
        When it comes to a hybrid histogram Oracle considers a value to be popular when its recorded endpoint_repeat_count value exceeds the original<\/em> bucket size. The endpoint_repeat_count is a new 12c histogram column property in which Oracle stores the number of times a distinct value has been repeated in a bucket. Let’s put this in a SQL format:<\/p>\n
        SQL> select\r\n         uth.endpoint_number\r\n        ,uth.endpoint_actual_value\r\n        ,uth.endpoint_repeat_count\r\n        ,ucs.sample_size\/ucs.num_buckets bucket_size      \r\n        ,(uth.endpoint_repeat_count - ucs.sample_size\/ucs.num_buckets) Popularity\r\n    from\r\n        user_tab_histograms uth\r\n       ,user_tab_col_statistics ucs\r\n   where\r\n        uth.table_name   = ucs.table_name\r\n    and uth.column_name   = ucs.column_name\r\n    and uth.table_name    = 'T1'\r\n    and uth.column_name   = 'N1'\r\n   order by uth.endpoint_number;\r\n\r\nENDPOINT_NUMBER ENDPOINT_A ENDPOINT_REPEAT_COUNT BUCKET_SIZE POPULARITY\r\n--------------- ---------- --------------------- ----------- ----------\r\n              1 8                              1           5         -4\r\n              6 13                             3           5         -2\r\n             12 18                             2           5         -3\r\n             20 20                             5           5          0\r\n             26 23                             2           5         -3\r\n             32 26                             3           5         -2\r\n             38 27                             6           5          1\r\n             44 28                             6           5          1\r\n             50 29                             6           5          1\r\n             58 31                             5           5          0\r\n             69 33                             8           5          3\r\n             79 35                             7           5          2\r\n             86 38                             5           5          0\r\n             90 41                             1           5         -4\r\n             92 42                             2           5         -3\r\n             95 43                             3           5         -2\r\n             96 44                             1           5         -4\r\n             97 45                             1           5         -4\r\n             98 46                             1           5         -4\r\n            100 59                             1           5         -4\r\n20 rows selected.<\/pre>\n
        The Popularity<\/strong> column above represents the difference between the frequency of appearance of each column and the bucket size (sample_size\/num_buckets). It can easily be inferred from this column that a value is considered popular when its Popularity<\/strong> column value is greater than zero. Refactoring the above query a little gives this:<\/p>\n
        SQL> select\r\n         endpoint_number\r\n        ,endpoint_actual_value\r\n        ,endpoint_repeat_count\r\n        ,bucket_size\r\n        ,case when Popularity > 0 then 'Pop'\r\n                   else 'Non-Pop'\r\n          end Popularity\r\n    from\r\n   (\r\n     select\r\n         uth.endpoint_number\r\n        ,uth.endpoint_actual_value\r\n        ,uth.endpoint_repeat_count\r\n        ,ucs.sample_size\/ucs.num_buckets bucket_size      \r\n        ,(uth.endpoint_repeat_count - ucs.sample_size\/ucs.num_buckets) Popularity\r\n    from\r\n        user_tab_histograms uth\r\n       ,user_tab_col_statistics ucs\r\n   where\r\n        uth.table_name   = ucs.table_name\r\n    and uth.column_name   = ucs.column_name\r\n    and uth.table_name    = 'T1'\r\n    and uth.column_name   = 'N1'\r\n    )\r\n   order by endpoint_number;\r\n\r\nENDPOINT_NUMBER ENDPOINT_A ENDPOINT_REPEAT_COUNT BUCKET_SIZE POPULAR\r\n--------------- ---------- --------------------- ----------- -------\r\n              1 8                              1           5 Non-Pop\r\n              6 13                             3           5 Non-Pop\r\n             12 18                             2           5 Non-Pop\r\n             20 20                             5           5 Non-Pop\r\n             26 23                             2           5 Non-Pop\r\n             32 26                             3           5 Non-Pop\r\n             38 27                             6           5 Pop\r\n             44 28                             6           5 Pop\r\n             50 29                             6           5 Pop\r\n             58 31                             5           5 Non-Pop\r\n             69 33                             8           5 Pop\r\n             79 35                             7           5 Pop\r\n             86 38                             5           5 Non-Pop\r\n             90 41                             1           5 Non-Pop\r\n             92 42                             2           5 Non-Pop\r\n             95 43                             3           5 Non-Pop\r\n             96 44                             1           5 Non-Pop\r\n             97 45                             1           5 Non-Pop\r\n             98 46                             1           5 Non-Pop\r\n            100 59                             1           5 Non-Pop\r\n20 rows selected.<\/pre>\n
        Simply put, a captured Hybrid histogram value is considered to be:<\/p>\n