{"id":1068,"date":"2016-11-22T19:52:11","date_gmt":"2016-11-22T19:52:11","guid":{"rendered":"http:\/\/nenadnoveljic.com\/blog\/?p=1068"},"modified":"2016-11-22T21:19:11","modified_gmt":"2016-11-22T21:19:11","slug":"density-calculation-hybrid-histograms","status":"publish","type":"post","link":"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/","title":{"rendered":"Density Calculation with Hybrid Histograms"},"content":{"rendered":"<p>This blog post describes how the calculation of new density has\u00a0modified with the introduction of hybrid histograms in Oracle 12c. I assume that\u00a0a reader is familiar with the concept of new density which Alberto Dell&#8217;Era\u00a0elaborated\u00a0on in his white paper\u00a0<a href=\"http:\/\/www.adellera.it\/investigations\/11g_newdensity\/11gNewDensity.pdf\" target=\"_blank\">New Density calculation in 11g<\/a> . The article is based on Oracle version 12.1.<\/p>\n<h1>Height-Balanced Histograms<\/h1>\n<p>The new\u00a0density in height-balanced histograms is\u00a0calculated during the optimization process and is used for estimating the cardinality of unpopular values. The following formula is used for the calculation of\u00a0the new density with height-balanced histograms:<\/p>\n<pre>NewDensity = [(BktCnt - PopBktCnt) \/ BktCnt] \/ (NDV - PopValCnt)<\/pre>\n<ul>\n<li>NDV: number of distinct values<\/li>\n<li>PopValCnt: number of popular values<\/li>\n<li>BktCnt: total number of buckets in a height-balanced histogram<\/li>\n<li>PopBktCnt: number of buckets containing popular values<\/li>\n<\/ul>\n<p>Side note: for the sake of simplicity the formula assumes that there aren&#8217;t any null values in the column. Handling the case with null values is trivial &#8211; just subtract the num_nulls from the denominator.<\/p>\n<p>The cardinality of an unpopular value is calculated by multiplying NewDensity with the total number of rows in the table:<\/p>\n<pre>card = num_rows * NewDensity.<\/pre>\n<p>Let&#8217;s take a closer look at:<\/p>\n<pre>[(BktCnt - PopBktCnt) \/ BktCnt]<\/pre>\n<p>This\u00a0expression calculates\u00a0the ratio between the\u00a0number of rows containing unpopular values\u00a0and the total number of rows.\u00a0Alberto Dell&#8217;Era\u00a0coined the term\u00a0Not-Populars SubTable (NPST)\u00a0for the\u00a0subset\u00a0of the table with unpopular values.<\/p>\n<p>Next,\u00a0let&#8217;s\u00a0examine the premise underpinning the formula for NPST-factor. Since in\u00a0<a href=\"https:\/\/docs.oracle.com\/database\/121\/TGSQL\/tgsql_histo.htm#TGSQL379\" target=\"_blank\">height-balanced histograms<\/a>\u00a0all the buckets\u00a0are of \u00a0the same size (or at least almost the same size), the ratio<\/p>\n<pre>[(BktCnt - PopBktCnt) \/ BktCnt]<\/pre>\n<p>will perfectly match the fraction of the rows\u00a0having unpopular values.<\/p>\n<h1>Hybrid Histograms<\/h1>\n<p>In contrast, in\u00a0hybrid histograms Oracle will group all samples having the same value in the same bucket. As a consequence, the\u00a0buckets will vary in size.<\/p>\n<p>Let&#8217;s see what happens with the formula in the case of\u00a0the data distribution with a strong peak when using hybrid histograms. For this purpose, I&#8217;ll create a table\u00a0containing 600 integer values, where all the values except one will have only one row.\u00a0The remaining\u00a0value will be inserted 300 times and will therefore occupy\u00a0the half of the table.<\/p>\n<pre><code>\r\ndrop table t ;\r\n\r\ncreate table t (a number) ;\r\n\r\ninsert into t \r\nSELECT rownum\r\nFROM dual\r\nCONNECT BY level &lt;= 300;\r\n\r\nINSERT INTO T\r\nSELECT 301\r\nFROM dual\r\nCONNECT BY level &lt;= 300 ; \r\n\r\ncommit ; \r\n\r\nexec dbms_stats.gather_table_stats( null,'T',method_opt=&gt;'for columns size 254 A' );\r\n<\/code><\/pre>\n<p>There are 254 buckets in total, but only one containing\u00a0the popular value:<\/p>\n<pre><code>column val format a3\r\ncolumn pop format 9999\r\ncolumn cnt format 9999\r\ncolumn samples format 9999\r\n\r\nselect \r\n  uth.endpoint_actual_value val\r\n  ,case when \r\n  (uth.endpoint_repeat_count - ucs.sample_size\/ucs.num_buckets)&gt;0 \r\n  then 1 else 0 end pop\r\n  ,uth.endpoint_repeat_count cnt\r\n  ,(endpoint_number - nvl ( lag(endpoint_number)over (order by endpoint_number asc) , 0 )) samples\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    = 'T'\r\n    and uth.column_name   = 'A'\r\norder by endpoint_repeat_count ;\r\n\r\nVAL   POP   CNT SAMPLES\r\n--- ----- ----- -------\r\n1       0     1       1\r\n2       0     1       1\r\n3       0     1       1\r\n...\r\n299     0     1       1\r\n301     <span style=\"color: #ff0000;\">1   300     301\r\n<\/span><\/code><\/pre>\n<p>Notice the skew in samples per bucket &#8211; the bucket with the popular value contains 301 samples. In contrast, the buckets with the unpopular values\u00a0have only one or two samples.<\/p>\n<p>The query for identifying popular values is\u00a0based\u00a0on Mohamed Houri&#8217;s query\u00a0from his blog post <a href=\"http:\/\/allthingsoracle.com\/12c-hybrid-histogram\/\" target=\"_blank\">12c hybrid histogram<\/a> .<\/p>\n<p>The factoring expression<\/p>\n<pre>(BktCnt - PopBktCnt)\/BktCnt<\/pre>\n<p>gives us<\/p>\n<pre>(254 -1 ) \/ 254 = 0.9960<\/pre>\n<p>which would mean that 99.60% of the table was populated by unpopular values. Obviously,\u00a0the\u00a0value is\u00a0out of\u00a0the ballpark as we know that only the half of the table is populated by unpopular values. This\u00a0error is a consequence of\u00a0uneven sizes\u00a0of hybrid histograms. Therefore, the ratio of the count of the buckets can&#8217;t be used any more for calculating the percentage of the samples\u00a0with unpopular values. The samples has to be counted instead.<\/p>\n<h1>New Formula<\/h1>\n<p>Therefore, after replacing<\/p>\n<pre>(BktCnt - PopBktCnt)\/BktCnt<\/pre>\n<p>with<\/p>\n<pre>num_rows_unpopular\/num_rows<\/pre>\n<p>we get the following:<\/p>\n<pre>NewDensityHybrid\r\n= num_rows_unpopular \/ num_rows\u00a0\/ NDV_unpopular\r\n= (num_rows - num_rows_popular) \/ num_rows \/ (NDV - PopValCnt)\r\n<\/pre>\n<p>Letting<\/p>\n<pre>num_rows_popular = sum(endpoint_repeat_count_populars) * (num_rows\/sample_size)\r\n\r\nNewDensityHybrid\r\n= (num_rows-sum(endpoint_repeat_count_populars)*(num_rows\/sample_size))\/(NDV-PopValCnt)\/num_rows\r\n= (1-sum(endpoint_repeat_count_populars)\/sample_size)\/(NDV-PopValCnt)\r\n<\/pre>\n<p>Finally, I&#8217;m providing the\u00a0query for calculating the NewDensity value with hybrid histograms which you can download from my <a href=\"https:\/\/github.com\/nenadnoveljic\/oradb\/blob\/master\/hybrid_hist_newdensity.sql\" target=\"_blank\">github repository <\/a> :<\/p>\n<h1>References<\/h1>\n<ul>\n<li>Alberto Dell&#8217;Era: <a href=\"http:\/\/www.adellera.it\/investigations\/11g_newdensity\/11gNewDensity.pdf\" target=\"_blank\">New Density calculation in 11g<\/a><\/li>\n<li>Mohamed Houri: <a href=\"http:\/\/allthingsoracle.com\/12c-hybrid-histogram\/\" target=\"_blank\">12c hybrid histogram<\/a><\/li>\n<li>Oracle Documentation: <a href=\"https:\/\/docs.oracle.com\/database\/121\/TGSQL\/\" target=\"_blank\">Database SQL Tuning Guide<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>This blog post describes how the calculation of new density has modified with the introduction of hybrid histograms in Oracle 12c. <a href=\"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/\" class=\"more-link\">Continue Reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[8,11,5],"tags":[],"class_list":["post-1068","post","type-post","status-publish","format-standard","hentry","category-12c","category-cost-based-optimizer","category-oracle"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.4 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Density Calculation with Hybrid Histograms - All-round Database Topics<\/title>\n<meta name=\"description\" content=\"This blog post describes how the calculation of new density has modified with the introduction of hybrid histograms in Oracle 12c\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Density Calculation with Hybrid Histograms - All-round Database Topics\" \/>\n<meta property=\"og:description\" content=\"This blog post describes how the calculation of new density has modified with the introduction of hybrid histograms in Oracle 12c\" \/>\n<meta property=\"og:url\" content=\"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/\" \/>\n<meta property=\"og:site_name\" content=\"All-round Database Topics\" \/>\n<meta property=\"article:published_time\" content=\"2016-11-22T19:52:11+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2016-11-22T21:19:11+00:00\" \/>\n<meta name=\"author\" content=\"Nenad Noveljic\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@NenadNoveljic\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Nenad Noveljic\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/density-calculation-hybrid-histograms\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/density-calculation-hybrid-histograms\\\/\"},\"author\":{\"name\":\"Nenad Noveljic\",\"@id\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/#\\\/schema\\\/person\\\/51458d9dd86dbbdd19f5add451d44efa\"},\"headline\":\"Density Calculation with Hybrid Histograms\",\"datePublished\":\"2016-11-22T19:52:11+00:00\",\"dateModified\":\"2016-11-22T21:19:11+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/density-calculation-hybrid-histograms\\\/\"},\"wordCount\":558,\"commentCount\":0,\"articleSection\":[\"12c\",\"cost based optimizer\",\"Oracle\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/density-calculation-hybrid-histograms\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/density-calculation-hybrid-histograms\\\/\",\"url\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/density-calculation-hybrid-histograms\\\/\",\"name\":\"Density Calculation with Hybrid Histograms - All-round Database Topics\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/#website\"},\"datePublished\":\"2016-11-22T19:52:11+00:00\",\"dateModified\":\"2016-11-22T21:19:11+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/#\\\/schema\\\/person\\\/51458d9dd86dbbdd19f5add451d44efa\"},\"description\":\"This blog post describes how the calculation of new density has modified with the introduction of hybrid histograms in Oracle 12c\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/density-calculation-hybrid-histograms\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/density-calculation-hybrid-histograms\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/density-calculation-hybrid-histograms\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Density Calculation with Hybrid Histograms\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/\",\"name\":\"All-round Database Topics\",\"description\":\"Nenad Noveljic\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/#\\\/schema\\\/person\\\/51458d9dd86dbbdd19f5add451d44efa\",\"name\":\"Nenad Noveljic\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/a97b796613ea48ec8a7b79c8ffe1c685dcffc920c68121f6238d5caab5070670?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/a97b796613ea48ec8a7b79c8ffe1c685dcffc920c68121f6238d5caab5070670?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/a97b796613ea48ec8a7b79c8ffe1c685dcffc920c68121f6238d5caab5070670?s=96&d=mm&r=g\",\"caption\":\"Nenad Noveljic\"},\"sameAs\":[\"nenad-noveljic-9b746a6\",\"https:\\\/\\\/x.com\\\/NenadNoveljic\"],\"url\":\"https:\\\/\\\/nenadnoveljic.com\\\/blog\\\/author\\\/nenad\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Density Calculation with Hybrid Histograms - All-round Database Topics","description":"This blog post describes how the calculation of new density has modified with the introduction of hybrid histograms in Oracle 12c","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/","og_locale":"en_US","og_type":"article","og_title":"Density Calculation with Hybrid Histograms - All-round Database Topics","og_description":"This blog post describes how the calculation of new density has modified with the introduction of hybrid histograms in Oracle 12c","og_url":"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/","og_site_name":"All-round Database Topics","article_published_time":"2016-11-22T19:52:11+00:00","article_modified_time":"2016-11-22T21:19:11+00:00","author":"Nenad Noveljic","twitter_card":"summary_large_image","twitter_creator":"@NenadNoveljic","twitter_misc":{"Written by":"Nenad Noveljic","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/#article","isPartOf":{"@id":"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/"},"author":{"name":"Nenad Noveljic","@id":"https:\/\/nenadnoveljic.com\/blog\/#\/schema\/person\/51458d9dd86dbbdd19f5add451d44efa"},"headline":"Density Calculation with Hybrid Histograms","datePublished":"2016-11-22T19:52:11+00:00","dateModified":"2016-11-22T21:19:11+00:00","mainEntityOfPage":{"@id":"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/"},"wordCount":558,"commentCount":0,"articleSection":["12c","cost based optimizer","Oracle"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/","url":"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/","name":"Density Calculation with Hybrid Histograms - All-round Database Topics","isPartOf":{"@id":"https:\/\/nenadnoveljic.com\/blog\/#website"},"datePublished":"2016-11-22T19:52:11+00:00","dateModified":"2016-11-22T21:19:11+00:00","author":{"@id":"https:\/\/nenadnoveljic.com\/blog\/#\/schema\/person\/51458d9dd86dbbdd19f5add451d44efa"},"description":"This blog post describes how the calculation of new density has modified with the introduction of hybrid histograms in Oracle 12c","breadcrumb":{"@id":"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/nenadnoveljic.com\/blog\/density-calculation-hybrid-histograms\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/nenadnoveljic.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Density Calculation with Hybrid Histograms"}]},{"@type":"WebSite","@id":"https:\/\/nenadnoveljic.com\/blog\/#website","url":"https:\/\/nenadnoveljic.com\/blog\/","name":"All-round Database Topics","description":"Nenad Noveljic","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/nenadnoveljic.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/nenadnoveljic.com\/blog\/#\/schema\/person\/51458d9dd86dbbdd19f5add451d44efa","name":"Nenad Noveljic","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/a97b796613ea48ec8a7b79c8ffe1c685dcffc920c68121f6238d5caab5070670?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/a97b796613ea48ec8a7b79c8ffe1c685dcffc920c68121f6238d5caab5070670?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/a97b796613ea48ec8a7b79c8ffe1c685dcffc920c68121f6238d5caab5070670?s=96&d=mm&r=g","caption":"Nenad Noveljic"},"sameAs":["nenad-noveljic-9b746a6","https:\/\/x.com\/NenadNoveljic"],"url":"https:\/\/nenadnoveljic.com\/blog\/author\/nenad\/"}]}},"_links":{"self":[{"href":"https:\/\/nenadnoveljic.com\/blog\/wp-json\/wp\/v2\/posts\/1068","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nenadnoveljic.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nenadnoveljic.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nenadnoveljic.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nenadnoveljic.com\/blog\/wp-json\/wp\/v2\/comments?post=1068"}],"version-history":[{"count":1,"href":"https:\/\/nenadnoveljic.com\/blog\/wp-json\/wp\/v2\/posts\/1068\/revisions"}],"predecessor-version":[{"id":1130,"href":"https:\/\/nenadnoveljic.com\/blog\/wp-json\/wp\/v2\/posts\/1068\/revisions\/1130"}],"wp:attachment":[{"href":"https:\/\/nenadnoveljic.com\/blog\/wp-json\/wp\/v2\/media?parent=1068"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nenadnoveljic.com\/blog\/wp-json\/wp\/v2\/categories?post=1068"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nenadnoveljic.com\/blog\/wp-json\/wp\/v2\/tags?post=1068"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}