Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I have a table with 250K rows in my test database. (There are a few hundred millions in production, we can observe the same issue there.) The table has an nvarchar2(50) string identifier, not null, with a unique index on it (it's not the PK).

The identifiers are made up of a first part that has 8 different values in my test database (and about a thousand in production), then an @ sign, and finally a number, 1 to 6 digits long. For example there could be 50 thousand rows that start with 'ABCD_BGX1741F_2006_13_20110808.xml@', and it is followed by 50 thousand different numbers.

When I query for a single row based on its identifier, the cardinality is estimated as 1, the cost is very low, it works fine. When I query for more than one row with several identifiers in an IN expression or an OR expression, the estimations for the index are completely wrong, so a full table scan is used. If I force the index with a hint, it is very fast, the full table scan is actually executed an order of magnitude slower (and a lot more slower in production). So it is an optimizer problem.

As a test, I duplicated the table (in the same schema+tablespace) with the exact same DDL and exact same content. I recreated the unique index on the first table for good measure, and created the exact same index on the clone table. I did a DBMS_STATS.GATHER_SCHEMA_STATS('schemaname',estimate_percent=>100,cascade=>true);. You can even see that the index names are consecutive. So now the only difference between the two tables is that the first one was loaded in random order over a long time period, with blocks scattered on the disk (in a tablespace together with several other big tables), the second was loaded as one batched INSERT-SELECT. Other than that, I can't imagine any difference. (The original table has been shrinked since the last big deletion, and there hasn't been a single delete after that.)

Here are query plans for the sick and the clone table (The strings under the black brush are the same all over the picture, and also under they gray brush.):

query plans

(In this example, there are 1867 rows that start with the identifier that is black brushed. A 2-row query produces a cardinality of 1867*2, a 3-row query produces a cardinality of 1867*3, etc. Can't be a coincidence, Oracle seems to not care about the end of the identifiers.)

What could cause this behavior? Obviously it would be pretty expensive to recreate the table in production.

USER_TABLES: http://i.stack.imgur.com/nDWze.jpg USER_INDEXES: http://i.stack.imgur.com/DG9um.jpg I only changed the schema and tablespace name. You can see that the table and index names are the same as on the query plan screenshot.

share|improve this question

migrated from stackoverflow.com Jan 4 at 15:26

This question came from our site for professional and enthusiast programmers.

2  
What is the execution plan if you use the condition where id = 'xxxxxxxxxxx1' OR id = 'xxxxxxxxxxx2' ? –  ypercube Jan 4 at 15:10
3  
it looks like you are posting edited versions of the plan. Can you post the actual SQL you are running for explain plan, and the actual output (including hints etc)? –  Jack Douglas Jan 4 at 15:23
2  
Can you try and reproduce it on sqlfiddle.com ? BTW, what is your national character set? What's the average row length of the rows in the table? –  Phil Jan 4 at 15:40
2  
Is the column defined as not null? If not, could you set up a test case and rerun the query after adding a not null constraint? –  Dimitre Radoulov Jan 4 at 15:43
2  
Can you edit USER_INDEXES and USER_TABLES output into your question for both indexes and tables (original and clone)? Thanks. –  Phil Jan 4 at 17:06

3 Answers 3

up vote 7 down vote accepted

(This answers the other question about why the histograms are different.)

Histograms are created by default based on column skew and whether the column was used in a relevant predicate. Copying the DDL and the data is not enough, the workload information is also important.

According to the Performance Tuning Guide:

When you drop a table, workload information used by the auto-histogram gathering feature and saved statistics history used by the RESTORE_*_STATS procedures is lost. Without this data, these features do not function properly.

For example, here is a table with skewed data but no histogram:

drop table test1;
create table test1(a date);
insert into test1 select date '2000-01-01'+level from dual connect by level <= 10;
insert into test1 select date '2000-01-01' from dual connect by level <= 1000;
begin
    dbms_stats.gather_table_stats(user, 'TEST1');
end;
/
select histogram from user_tab_columns where table_name = 'TEST1';

HISTOGRAM
---------
NONE

Running the same thing, but with a query before the statistics are gathered, will generate a histogram.

drop table test1;
create table test1(a date);
insert into test1 select date '2000-01-01'+level from dual connect by level <= 10;
insert into test1 select date '2000-01-01' from dual connect by level <= 1000;
select count(*) from test1 where a = sysdate; --Only new line
begin
    dbms_stats.gather_table_stats(user, 'TEST1');
end;
/
select histogram from user_tab_columns where table_name = 'TEST1';

HISTOGRAM
---------
FREQUENCY
share|improve this answer
2  
Brilliantly simple example. Do you have any idea why the CBO was using histograms for cardinality estimates on a unique scan rather than just assuming 1? –  Jack Douglas Jan 5 at 14:46
    
Thanks! I made a complete repro with my kind of data and queries on my blog: joco.name/2014/01/05/… –  fejesjoco Jan 5 at 20:07
    
@Jack I think it's laziness. Oracle engineers must have figured that the statistics of a unique index will have the same number of distinct values as rows, so the 1 cardinality assumption is not hardwired, but simply used from the statistics, as in any other case. Also, as a general case, histograms trump simple statistics. My case seems to be very special because of the long keys only, but I believe this works pretty well otherwise. –  fejesjoco Jan 5 at 20:10
    
@fejesjoco I think JL's explanation is more likely, as the histograms would also have trumped the general stats in the case of a single lookup (without the in), wouldn't it? I think the CBO does make the cardinality 1 assumption, but only in the very simplest case. I assume you could work around the whole thing using a big UNION ALL but there may be other reasons not to do that and JL mentions other possible workarounds in the linked blog post. –  Jack Douglas Jan 6 at 8:57
1  
One other minor mystery to consider - how did this histogram get created in the first place? Oracle only seems to consider a column to be skewed if it has duplicates, which obviously your unique column cannot have. Did someone intentionally build this histogram (unlikely), or did someone gather stats with the non-recommended method_opt=>'for all indexed columns'? –  jonearles Jan 7 at 4:25

I found the solution! It is so beautiful and I actually learned a LOT about Oracle.

In one word: histograms.

I started reading a lot about how Oracle's CBO works and I stumbled upon histograms. I didn't fully understand so I took a look at the USER_HISTOGRAMS table, and voilá. There were several rows for the sick table, and practically nothing for the cloned table. For the sick table, there was one row for each of the 8 different identifier-starting-parts. And this is the key: they were cut off at 32 characters, before the @ sign. As I said, the first part of keys is highly repetitive, they become different after the @ sign.

It seems that histograms can be more powerful than the simple fact that a unique index always has a cardinality of 0 or 1 for a given value. When I was querying for 2+ rows, Oracle looked at the histogram, it thought that there could be tens of thousands of values for that identifier-starting-part, and it threw the CBO off course.

I deleted the histograms for that column in the old table and the problem went away!

More reading: https://blogs.oracle.com/optimizer/entry/how_do_i_drop_an_existing_histogram_on_a_column_and_stop_the_auto_stats_gathering_job_from_creating

share|improve this answer
2  
I mentioned that in our chat room :) chat.stackexchange.com/transcript/message/12987649#12987649 –  Phil Jan 4 at 21:27
    
I didn't see that :). So the only weird thing is why there were histograms in the first table and not in the clone, I thought gather_schema_stats updated everything, apparently not. –  fejesjoco Jan 4 at 21:30

I emailed Jonathan Lewis about this and got a very helpful reply:

The oddity in the calculation is a consequence of the limits on character-based histograms, see particularly:

http://jonathanlewis.wordpress.com/2010/10/13/frequency-histogram-5/ http://jonathanlewis.wordpress.com/2010/10/19/frequency-histograms-6/

Looking at the example, the query is for an IN list, not for a single row, so my initial guess would be that the optimizer has used a generic strategy for calculating multi-row selectivity rather than having a special case piece of code for an IN list on a primary key. I guess it wouldn't be too hard for them to recognise this case, but the developers have probably not considered it worth the effort.

I highly recommended reading the blog posts he links, they describe in detail the limitation of histograms you are running in to, eg:

Conclusion: If you have fairly long, and similar, strings in a column that is a good candidate for a frequency histogram (e.g. a very descriptive status column) then you have a problem if a value that is very rare looks identical to a very popular value up to the first 32 characters. You may find that the only solution is to change the list of legal values (although various strategies involving virtual columns or function-based indexes can bypass the problem).

share|improve this answer
    
Sadly histograms seem to be a little known feature, I guess it's because it's too deep for an SQL developer and most of the time they just work, but it's good to know there are many resources about it, I just wasn't looking in the right places :). It's pretty bad that Oracle cuts at 32 bytes and makes disastrous decisions based on that. Luckily, I don't need any tweaking, dropping the histograms is a perfect solution. The key values are unique, I always look for 20 values at a time, it works fine with an index only, and it is deterministic. But I won't use long keys next time, that's for sure. –  fejesjoco Jan 6 at 9:08
    
Histograms are pretty well known among DBAs ;) I love the fact that you seem keen to learn deeper stuff and really think you should read JL's book it is very very good. The CBO generally does a great job: there'll always be edge cases which need investigating but it's worth bearing in mind that even without the cut off, estimates are always just estimates. –  Jack Douglas Jan 6 at 9:24
1  
If you run a regular stats job (like the one Oracle runs by default on a clean install), you may find histograms reappear, you might need to look into a way of preventing that (such as LOCK_TABLE_STATS perhaps) –  Jack Douglas Jan 6 at 9:26
    
I mentioned a blog post in my answer, there are instructions on how to prevent histograms for a column. –  fejesjoco Jan 6 at 9:30
1  
@Jack Douglas, thank you for involving J. Lewis and reporting back! –  Dimitre Radoulov Jan 6 at 12:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.