In part 1 of this series we discussed the reasons why we might want to create some histograms to help the optimizer deal with skewed data distribution. We used an example of a simple ** status** column in an

**table to demonstrate principles, talked about frequency histograms in particular, and highlighted a couple of problems associated with histograms.**

*orders*In part 2 we are going to spend some time on the only other type of histogram that is available in versions of Oracle up to 11g, the height-balanced histogram. There are a few patterns of data where a height-based histogram can be useful, and we’ll be looking at those in part 3; but we’re going to start with an example where our data won’t allow Oracle to create a frequency histogram and a height-balanced histogram can become more of a liability than a benefit; and we’ll describe a strategy (that you will no longer need in 12c) for working around this limitation. Along the way we will look at a very simple example demonstrating the algorithm that Oracle uses to generate the contents of a height-based histogram.

## A simple example

Here’s a report of some important client data – camouflaged, of course – showing an uneven distribution of values for a particularly important column.

select specifier, count(*) from messages group by specifier order by count(*) desc ; -- ca. 10M rows in table SPECIFIER COUNT(*) BVGFJB 1,851,177 LYYVLH 719,582 MTVMIE 672,823 YETSDP 659,661 DAJYGS 504,641 ... KDCFVJ 75,328 JITCRI 74,104 DNRYKC 70,029 BEWPEQ 68,681 ... JXXXRE 1 OHMNVU 1 YGOBWQ 1 UBBWQH 1 352 rows selected.

Clearly I have a very uneven distribution of values here, so a histogram might be quite helpful. Unfortunately there are 352 distinct values, which is beyond the limit allowed by Oracle until 12c, so if I generate a histogram it will have to be a ** height-balanced** histogram.

To generate a height-balanced histogram Oracle starts by sorting the data into order then selects the first row and every Nth row (where N = “number of non-null values in column” divided by “number of buckets requested”). With our sample data we would be selecting roughly every 40,000th row from the sorted data. (10M / 254).

Each selected number is referred to as an endpoint value, and the numbers are labelled with numbers (called the endpoint numbers) from 0 to “number of buckets”. Using this algorithm a value that appears sufficiently frequently in the data set will be selected many times, which allows Oracle to recognize it as a “popular” value. When storing the histogram selection, Oracle doesn’t store repetitions of end point values – if a value appears many times in the list it will be stored just once with its highest endpoint number.

To demonstrate the mechanism involved, and the subsequent cardinality arithmetic, I’m going to take the following (ready-sorted) 20 values and build a histogram of 5 buckets:

5, 6, 6, 6, 9, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 16, 17, 17

Take the first and every 4th number (20 / 5 = 4)

5, 6, 6, 6, 9, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 16, 17, 17

Store them, labeling them from zero since we’ve included the lowest original value in our list:

0 5 1 6 2 12 3 12 4 13 5 17

Now eliminate the earlier copies of any duplicated values:

0 5 1 6 3 12 4 13 5 17

This is what Oracle would store as the height-balanced histogram on the original data set. From this it would infer that 12 was a popular value (it appeared more than once); but, even though we can see that there are just as many 12s as there are 13s, Oracle would not infer that 13 was a popular value. You might like to consider the effect of changing one of the 11s to 16 – if you did this then 12 would cease to appear as a popular value and 13 would become a popular value; conversely if you changed a 16 to 11 then neither 12 nor 13 would appear as popular.

As far as cardinality calculations go, Oracle “counts buckets” for the popular values – in our tiny example we picked every 4th row, our “bucket” size is 4. We know that 12 appears twice in the full histogram, so Oracle calculates the cardinality of the predicate *“n1 = 12”* as 8 (i.e. 2 buckets * 4 rows per bucket). The method the optimizer uses to calculate the cardinality for the values which have not been recognized as popular has varied over time – in 11.2.0.3 one of the calculations is simply: (number of non-popular rows)/(number of non-popular values) which works as follows in our example

Popular values | 1 | (12) |

Non-popular values | 7 | (5,6,9,11,13,16,17) |

Popular rows | 8 | (2 buckets at 4 rows per bucket) |

Non-popular rows | 12 | (20 – 8) |

Non-popular cardinality = 12/7 = 1.714, which rounds up to 2.

There are various complications and variations to the calculations, of course; in particular if Oracle has used a sample to build the histogram the optimizer will need to scale up its calculations by a factor that reflects the difference between the number of relevant rows in the table and the number of rows captured in the histogram.

With this small example in mind, let’s consider the 10M rows and 352 values from my client.

## Precision matters

We have 10M rows – and the first thing we need to do to create the height-balanced histogram is to sort the data, so the very first step is fairly resource intensive. If we take a sample this would reduce the volume of data sorted – but it’s just possible that the sample would miss so many values that Oracle thought it could create a frequency histogram – and that might result in the optimizer making very low estimates of cardinality for values which actually have tens of thousands of rows.

Having sorted the data, how many of our “popular” values are likely to appear to be popular by the time we do the selection of every 40,000th row? Our most popular value has 1.8M rows, which accounts for 46 buckets, the next three values account for a further 63 buckets, leaving only 155 buckets – and since it takes two buckets to identify a popular value at all we’re only going to be able to identify at most another 72 popular values – everything else will be treated as “average”.

In fact this is one of the really irritating features of the grey area between frequency and height-balanced histograms. A frequency histogram can handle 254 popular values, but if Oracle has to switch to a height-balanced histogram it can’t identify more than 127 (i.e. 254/2) popular values – if your data goes a little over the frequency limit your precision can drop dramatically.

Stability is another problem – in the middle of my list I reported a number of values for which there were about 70,000 rows each. Are these going to be captured in the histogram? Given that a bucket represents 40,000 rows a value that has 40,001 rows can just appear twice in our selection, on the other hand a value that has 79,999 rows might just fail to appear twice. All you have to do is add or delete a few rows each day and values will “randomly” appear and disappear from the histogram each time you gather it. When I analysed the data set in detail I came to the following conclusions – for a 100% sample:

- There are 25 values that WILL get captured each day (more than 80,000 rows per value)
- There are 35 values that might get captured one day and disappear the next (40,000 to 80,000 rows)

Height-balanced histograms can be very unstable – if any of those 35 values are the rows that users are really interested in then their execution plans may change dramatically every time the histogram is gathered. And the randomness of the sample makes things worse if we don’t use 100% of the data to gather the histogram.

But here’s another aspect of analysing the data in detail:

- The top 140 values account for 99% of the data.
- The top 210 values account for 99.9% of the data
- The top 250 values account for 99.98% of the data
- The last 102 values account for about 2,000 rows from 10M

(Remember, by the way, that we were only going to be able to capture at most 81 (77 + 3 + 1) popular values anyway because of the number of buckets the very popular values will cover.)

We have 352 distinct values in the table, but 102 of them are virtually invisible. Wouldn’t it be nice if we could create a frequency histogram on the top 250 values (adding in the low and high values for the column, if necessary) and tell Oracle how to assume that any other values have an average of about 20 rows each. That’s what 12c does, by the way, with its new ** top-N** histogram, and it’s what we can do with a few calls to the

**package if we really feel that it’s important.**

*dbms_stats*## Faking the Frequency

Let’s go back to the data set we used in the previous article to demonstrate how to construct a simple frequency histogram when we have a good idea of the values we want to use. Remember that we had a status column with a data distribution that looked like this:

S COUNT(*) C 529,100 P 300 R 300 S 300 X 500,000

Since it’s a very small set of values, and we’re quite happy to say that this set of figures is a “good enough” model of the data whenever we need to get the optimizer to run our critical queries, it’s very easy to write a procedure to recreate a frequency histogram whenever Oracle’s ordinary stats gathering mechanism creates new stats on this table.

The code depends on three key procedures in the package: get_column_stats(), prepare_column_stats() and set_column_stats(), and assumes that table stats (of some description) have already been gathered since it reads the current stats for the column into local variables, adjusts the variables and then writes them back to the data dictionary.

declare m_distcnt number; -- num_distinct m_density number; -- density m_nullcnt number; -- num_nulls m_avgclen number; -- avg_col_len srec dbms_stats.statrec; -- stats record c_array dbms_stats.chararray; -- varchar2 array begin dbms_stats.get_column_stats( ownname => user, tabname => 'orders', colname => 'status', distcnt => m_distcnt, density => m_density, nullcnt => m_nullcnt, srec => srec, avgclen => m_avgclen ); m_distcnt := 5; -- set my num_distinct m_density := 0.00001; -- used for “missing values” srec.epc := 5; -- number of buckets in histogram c_array := dbms_stats.chararray( rpad('C',15), rpad('P',15), rpad('R',15), rpad('S',15), rpad('X',15) ); -- list of values – in order srec.bkvals := dbms_stats.numarray( 529100, 300, 300, 300, 500000 ); -- corresponding list of frequencies dbms_stats.prepare_column_values(srec, c_array); dbms_stats.set_column_stats( ownname => user, tabname => 'orders', colname => 'status', distcnt => m_distcnt, density => m_density, nullcnt => m_nullcnt, srec => srec, avgclen => m_avgclen ); end; /

There are a couple of key details that are worth mentioning. First, in the previous article, I said that Oracle uses “half the least popular frequency” for predicates involving values that are missing from the histogram; it seems that when you use set_column_sets() to create stats, Oracle uses the density to calculate the cardinality of missing values – which is why I have set the density in this code, I’ve decided that if you query for a missing value its cardinality should be 10. (If you check view ** user_tab_columns** the only difference between gathering and setting stats is that the column

**is set to YES when you set stats, and NO when you gather them.)**

*user_stats*Secondly, you’ll notice that for my list of values I’ve right-padded each value to 15 characters with spaces. My table definition had ** status** as a char() column, and Oracle treats char() and varchar2() slightly differently when converting strings to numbers – for char() columns you must rpad() to 15 characters like this, for varchar2() you must not pad. If you get this wrong the calculations will be wrong.

Finally, I have used an array of type dbms_stats.chararray; there are several other array types defined for the dbms_stats package (e.g. numarray, datearray) and you need to choose the type that is appropriate for the column you are hacking.

## Choosing your stats

So if you know what values to use and their frequencies you can easily set up a fake frequency histogram. If you don’t know the data very well you might want to derive the histogram information from the data. My view on histograms is that you really ought to have only a very small number, they’re generally frequency histograms, and you usually need to know the data, so I’ve never written a generic (hence complicated) script to deal with every option; I have a framework I use and create a custom procedure for each column that needs it. The core of the procedure is basically a simple SQL statement that identifies the minimum and maximum values and the top N most frequently occurring values along with their frequencies, and some high-level summary information; here’s a sample query with sample output:

select sample_size sample, sum(ct) over() hist_size, count(ct) over() buckets, min_n1, max_n1, n1, ct from ( select sum(ct) over () sample_size, min(n1) over() min_n1, max(n1) over() max_n1, n1, ct from ( select n1, count(*) ct from t1 -- could use a sample clause here group by n1 ) order by ct desc ) where rownum <= 20 or min_n1 = n1 or max_n1 = n1 order by n1 ; SAMPLE HIST_SIZE BUCKETS MIN_N1 MAX_N1 N1 CT ---------- ---------- ---------- ---------- ---------- ---------- ---------- 10000 7062 22 162 239 162 1 10000 7062 22 162 239 190 233 10000 7062 22 162 239 191 259 10000 7062 22 162 239 192 268 10000 7062 22 162 239 193 300 10000 7062 22 162 239 194 317 10000 7062 22 162 239 195 312 10000 7062 22 162 239 196 394 10000 7062 22 162 239 197 415 10000 7062 22 162 239 198 389 10000 7062 22 162 239 199 406 10000 7062 22 162 239 200 777 10000 7062 22 162 239 201 400 10000 7062 22 162 239 202 405 10000 7062 22 162 239 203 393 10000 7062 22 162 239 204 358 10000 7062 22 162 239 205 315 10000 7062 22 162 239 206 306 10000 7062 22 162 239 207 284 10000 7062 22 162 239 208 276 10000 7062 22 162 239 209 253 10000 7062 22 162 239 239 1 22 rows selected.

The innermost part of the query is the aggregate by column value that we need, and which we hope will reduce a large data set to a small result set. We then order this by column frequency, using a couple of analytic functions to bring in the values corresponding to the minimum and maximum column values. Then we select the rows corresponding to the top N frequencies and the minimum and maximum column values. Finally we use a couple of analytic functions to count the actual number of buckets we’ve selected and sum the total volume of data in the histogram, returning the results in order of column value.

The difference between the sample value and the hist_size tells us whether this is likely to be a “good enough” approximation to the whole data set. The buckets value tells us whether we’ve had to add the minimum and maximum values to the list or whether they naturally fell into our Top-N, and the min_n1, max_n1 columns tell us the actual minimum and maximum values for the columns. The N1 and CT columns give us the details that (with a little manipulation, perhaps) we’re going to put into the two dbms_stat arrays.

Once we have a query like this, we need do little more than change our previous version of the procedure to get rid of the array assignments, replacing them with a cursor for loop:

for r in ({query}) loop n_array.extend; srec.bkvals.extend; ct := ct+1; n_array(ct) := r.n1; srec.bkvals(ct) := r.ct; end loop;

There are a number of little details needed around the edges to make this a complete solution – initialising variables, deciding on a suitable density, deciding how to handle the case where the minimum and maximum values didn’t appear in the Top-N, deciding what to do if the volume of data captured is too small compared to the sample size, and so on. Further refinements are left as an exercise to the reader.

## Conclusion

Sometimes you have to do some fairly subtle things to get the best out of Oracle, and when you’re dealing with histograms you’re in an area where you’re most likely to need some custom mechanisms to get things right – but probably only for a few special cases.

One special case appears when you have a column that holds more distinct values than Oracle currently allows for a frequency histogram (254) and you find that a height-balanced histogram doesn’t capture as much information as you would like and, quite possibly, gives you changes in execution plans whenever you gather statistics. In a case like this you may decide to construct a “fake” frequency histogram that holds details of the most popular values in the table and also tells the optimizer how to work out a representative cardinality for the rest of the values.

If you know your data well you could set up a procedure that uses a fixed set of numbers for the histogram, otherwise you could query the data to generate a suitable “top N” set of stats. Whichever you choose to do, you need to remember that the optimizer will scale up the size of the histogram you’ve generated to match the value of (** user_tables.num_rows** –

**), so you should use this technique only when the popular values represent a very large percentage (perhaps as much as 98%) of the total volume of data.**

*user_tab_cols.num_nulls*
## 9 Comments

Earl Shaffer

01/10/2013

great article

thanks for sharing with us

Jonathan Lewis

27/01/2014

A reader emailed me about an error in this note, which turned out to be two errors. I've corrected both in the body of the text.

In the calculation for "non-popular" values I had said "divided by number of non-popular buckets" when this should have been "divided by the number of non-popular values".

I had then used 12/8 in the arithmetic rather than 12/7

Roman

18/07/2015

Hi Jonathan,

Could you please share information on how to generate the row source from the article?

And may be overview of approach usually used?

Best Regards,

Roman.

Jonathan Lewis

19/07/2015

Roman,

The data set was from a client. I just wrote a query that took the original "specifier, count(*)", put it into an inline view and joined it to a "select from dual connect by" that generated some random strings.

If I want to model data with this type of pattern I might start with an expression like: trunc(100 * exp(dbms_random.normal)) - generate a million rows of that expression and that would give (I guess) around 250 distinct values with a spread that's similar (lots of rows for 0, a sharp drop off for 1,2,3, and a long tail) sort of pattern. The trick is just to pick a suitable scale factor and number of rows

Roman

20/07/2015

Jonathan,

Thank you for information.

But still I don't quite understand how to generate repeating random strings in normal ditribution? Could you point me in the right direction please?

Here's what I have so far.

{noformat}

WITH data AS (

SELECT /*+ MATERIALIZE */ dbms_random.string('U',6) AS Specifier

FROM dual

CONNECT BY level <= 250

)

SELECT d1.specifier

FROM data d1, data d2;

create table t3 as

SELECT dbms_random.string('U',6) AS Specifier

FROM dual

CONNECT BY level <= 4000000

/

create table t3 as

SELECT a.Specifier

FROM (select dbms_random.string('U',6) AS Specifier from dual) a,

(select dbms_random.string('U',6) AS Specifier from dual) b

CONNECT BY level <= 100000

/

create table t3 as

select *

from ( select trunc(100*exp(dbms_random.normal)) from dual), (select dbms_random.string('U',6) from dual)

connect by level <= 100

/

{noformat}

Roman

05/08/2015

Sorry, didn't read your response thoroughly.

Having read the reply for the 3rd time really shed some light on the matter.

Timmy Okeowo

23/11/2015

Please can anyone clarify how to make a histogram with minimum value of 1 and maximum value 250..the class interval and the bin; the frequency is not ahead zero...rather closer to the vertical axis..please help me!

Jonathan Lewis

03/12/2015

If you want to create a frequency histogram based on a number column there's an example of the method here: https://jonathanlewis.wordpress.com/2009/05/28/frequency-histograms/

Ann Veremeychik

15/04/2016

Hello, Mr Lewis!

I am an Oracle beginner. I was going through this article and got some questions.

We divide 10M rows by 40000. So the number of buckets is 10000000/40000=250 buckets and since we are including the first one value from the data set it would led us to 251 values in histogram before we eliminate all duplicated values.

The most popular value got 1,8M rows which means that there is 18000000/40000=45 buckets accounted for it. Where do we get 46th value?

If we have 251 original values in the list and 46 of them are for the most popular value and 63 are for the next three, we have only 251-46-63=142 values remain. How did you get 155?

And if there are only 155 buckets left and it takes two buckets to identify the popular value, wouldn't it be 155/2=77 possible popular values left? Why 72?

Kind regards,

Anna.

Histograms | Oracle Scratchpad

01/10/2013

[...] Part 2 was a bit late – but it’s now out. [...]

Histograms Part 3 – When? – All Things Oracle

16/10/2013

[...] part 2 we looked at the way that Oracle collects and uses height –balanced histograms, and raised the [...]

Demo data | Oracle Scratchpad

03/08/2015

[…] time ago included a listing of the data distribution for some client data which I had camouflaged. A recent comment on the article asked how I had generated the data – of course the answer was that I […]

Histograms | Oracle Scratchpad

12/11/2015

[…] 2 – Height balanced histograms and how to address their limitations. Chinese […]

No trackbacks yet.