Oracle introduced with the 10.2.0.4 patch set a
significant change how non-existing values are treated when there is a frequency histogram on a column / expression. See Jonathan Lewis'
blog post which is probably the most concise description of the issue. In a nutshell the change is about the following (quoted from Jonathan's post): "If the value you supply does not appear in the histogram, but is inside the low/high range of the histogram then the cardinality will be half the cardinality of the least frequently occurring value that is in the histogram".
I'm still a bit puzzled why Oracle introduced such a significant change to the optimizer with a patch set, but one of the most obvious reasons might be that the change allows to generate frequency histograms using a rather low sample size, because there is no longer a similar threat as before when the frequency histogram misses one of the existing values (which would then return an estimate of 1 if they didn't appear in the histogram).
In fact when using the default DBMS_STATS.AUTO_SAMPLE_SIZE Oracle exactly does this: It uses by default a quite low sample size to perform the additional runs required for each histogram - probably an attempt to minimize the additional work that needs to be done for histogram generation.
In it is however quite interesting to see how exactly this behaviour together with the new treatment of non-existing values can turn into a threat as a
recent thread on OTN demonstrated.
Consider the following scenario: You have a column with a highly skewed data distribution; there is a single, very popular value, and a few other, very unpopular values.
Now you have a query type that filters on this column and frequently searches for non-existing values. In order to speed up the query an index has been created on the column, and in order to make the optimizer aware of the fact that the data distribution is highly skewed a histogram is generated, so that the optimizer should favor the index only for those unpopular respectively non-existing values.
The following test case (run on 11.1.0.7) emulates this scenario:
create table t1 (
id number(*, 0)
, t_status number(*, 0)
, vc varchar2(100)
);
-- 1 million rows
-- One very popular value
-- Two very unpopular values
-- in column T_STATUS
insert /*+ append */ into t1 (id, t_status, vc)
with generator as (
select /*+ materialize */
level as id
from
dual
connect by
level <= 10000
)
select /*+ use_nl(v1, v2) */
rownum as id
, case
when rownum <= 10
then 1
when rownum <= 20
then 2
else 0
end as t_status
, rpad('x', 100) as vc
from
generator v1
, generator v2
where
rownum <= 1000000;
commit;
create index t1_idx on t1 (t_status);
exec dbms_stats.gather_table_stats(null, 'T1', method_opt => 'for all columns size 1 for columns t_status size 254')
The first interesting point are the generated column statistics:
SQL>
SQL> -- Note that the basic column statistics
SQL> -- are generated with a much higher sample size
SQL> -- The histogram however was created with a sample size
SQL> -- of 5,000 rows only
SQL> -- Therefore we get three distinct values but only a single bucket
SQL> -- But not always => Potential instability issue
SQL> select
2 column_name
3 , num_distinct
4 , sample_size
5 from
6 user_tab_col_statistics
7 where
8 table_name = 'T1';
COLUMN_NAME NUM_DISTINCT SAMPLE_SIZE
--------------- ------------ -----------
ID 1000000 1000000
T_STATUS 3 5499
VC 1 1000000
SQL>
SQL> -- This results in a single bucket
SQL> -- But not always => Potential instability issue
SQL> select
2 column_name
3 , endpoint_number
4 , endpoint_value
5 from
6 user_tab_histograms
7 where
8 table_name = 'T1'
9 and column_name = 'T_STATUS';
COLUMN_NAME ENDPOINT_NUMBER ENDPOINT_VALUE
--------------- --------------- --------------
T_STATUS 5499 0
Notice the inconsistency: The basic column statistics (number of distinct values, low value, high value) obviously have been generated with a much higher sample size (in fact a compute in this case) than the histogram on T_STATUS. The histogram therefore misses the unpopular values and consists only of a single value - the very popular one.
Now watch closely what happens to the cardinality estimates of the non-existing values:
SQL>
SQL> -- The popular value
SQL> explain plan for
2 select
3 *
4 from
5 t1
6 where
7 t_status = 0
8 ;
Explained.
SQL>
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 3617692013
--------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 999K| 102M| 4319 (2)| 00:00:52 |
|* 1 | TABLE ACCESS FULL| T1 | 999K| 102M| 4319 (2)| 00:00:52 |
--------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter("T_STATUS"=0)
13 rows selected.
SQL>
SQL> -- A non-existing value
SQL> explain plan for
2 select
3 *
4 from
5 t1
6 where
7 t_status = 1000
8 ;
Explained.
SQL>
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 3617692013
--------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 500K| 51M| 4316 (2)| 00:00:52 |
|* 1 | TABLE ACCESS FULL| T1 | 500K| 51M| 4316 (2)| 00:00:52 |
--------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter("T_STATUS"=1000)
13 rows selected.
SQL>
SQL> -- Two non-existing values
SQL> explain plan for
2 select
3 *
4 from
5 t1
6 where
7 t_status in (1000, 2000)
8 ;
Explained.
SQL>
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 3617692013
--------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1000K| 102M| 4325 (3)| 00:00:52 |
|* 1 | TABLE ACCESS FULL| T1 | 1000K| 102M| 4325 (3)| 00:00:52 |
--------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter("T_STATUS"=1000 OR "T_STATUS"=2000)
13 rows selected.
SQL>
Ouch, ouch: Whereas the estimate for the popular value is correct, the estimates for the unpopular values are totally way-off - in fact using an IN clause with two non-existing values gets an estimate of all rows contained in the table.
The explanation: Since the least popular value is the single bucket covering virtually all rows, half of it is still 50% of the total cardinality - so two non-existing values in an IN clause end up with a selectivity of 1.
Furthermore the usual decay to values outside the low/high column values doesn't apply here either - no matter what non-existing values get used, the overestimation stays the same.
Update April 2012: It's probably worth to point out that this behaviour of ignoring the low/high values can only be observed when the basic column statistics Number of Distinct Values (NDV) is not consistent with the corresponding histogram. If both are consistent (for example, both show one distinct value) then the out-of-range detection will work as expected.
This also means that since in 10.2 the histogram and the basic column statistics tend to be more consistent than in 11g due to the new AUTO_SAMPLE_SIZE algorithm the problem by default doesn't show up in 10.2.
These overestimates have obviously a significant impact - here the suitable index doesn't get used - more complex plans might turn even into a complete disaster.
The default behaviour that histograms are generated with a much lower sample size than the basic column statistics also introduces a kind of instability - try to run the example several times. Sometimes one of the unpopular values might be caught by the default histogram generation, sometimes not. The effect is dramatic: If one of the unpopular values gets caught, the estimates will be reasonable again, since then the least popular value do have a very low cardinality - if not, you get exactly the opposite result just demonstrated.
If the old behaviour gets re-activated, the results are as expected with the same set of statistics:
SQL>
SQL> -- Switch off new behaviour
SQL> alter session set "_fix_control" = '5483301:off';
Session altered.
SQL>
SQL> -- The popular value
SQL> explain plan for
2 select
3 *
4 from
5 t1
6 where
7 t_status = 0
8 ;
Explained.
SQL>
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 3617692013
--------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 999K| 102M| 4319 (2)| 00:00:52 |
|* 1 | TABLE ACCESS FULL| T1 | 999K| 102M| 4319 (2)| 00:00:52 |
--------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter("T_STATUS"=0)
13 rows selected.
SQL>
SQL> -- A non-existing value
SQL> explain plan for
2 select
3 *
4 from
5 t1
6 where
7 t_status = 1000
8 ;
Explained.
SQL>
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 546753835
--------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 107 | 4 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID| T1 | 1 | 107 | 4 (0)| 00:00:01 |
|* 2 | INDEX RANGE SCAN | T1_IDX | 1 | | 3 (0)| 00:00:01 |
--------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - access("T_STATUS"=1000)
14 rows selected.
SQL>
SQL> -- Two non-existing values
SQL> explain plan for
2 select
3 *
4 from
5 t1
6 where
7 t_status in (1000, 2000)
8 ;
Explained.
SQL>
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 3743026710
---------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 107 | 5 (0)| 00:00:01 |
| 1 | INLIST ITERATOR | | | | | |
| 2 | TABLE ACCESS BY INDEX ROWID| T1 | 1 | 107 | 5 (0)| 00:00:01 |
|* 3 | INDEX RANGE SCAN | T1_IDX | 1 | | 4 (0)| 00:00:01 |
---------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("T_STATUS"=1000 OR "T_STATUS"=2000)
15 rows selected.
Switching back to the former treatment that non-existing values lead to an estimate of 1 will fix this issue, however since this has a potential impact on every execution plan thorough regression testing would be required with this used as a global setting.
Increasing the sample size is another option, if it ensures that unpopular values get caught by the histogram generation, so that the least popular value of the histogram is one with a low cardinality. Note however that this will increase the amount of work necessary to gather the statistics for the histograms.
SQL>
SQL> -- Gather statistics with 100% sample size
SQL> exec dbms_stats.gather_table_stats(null, 'T1', estimate_percent => null, method_opt => 'for all columns size 1 for columns t_status size 254')
PL/SQL procedure successfully completed.
SQL>
SQL> -- Now the statistics are more representative
SQL> select
2 column_name
3 , num_distinct
4 , sample_size
5 from
6 user_tab_col_statistics
7 where
8 table_name = 'T1';
COLUMN_NAME NUM_DISTINCT SAMPLE_SIZE
--------------- ------------ -----------
ID 1000000 1000000
T_STATUS 3 1000000
VC 1 1000000
SQL>
SQL> -- The histogram now covers also the unpopular values
SQL> select
2 column_name
3 , endpoint_number
4 , endpoint_value
5 from
6 user_tab_histograms
7 where
8 table_name = 'T1'
9 and column_name = 'T_STATUS';
COLUMN_NAME ENDPOINT_NUMBER ENDPOINT_VALUE
--------------- --------------- --------------
T_STATUS 999980 0
T_STATUS 999990 1
T_STATUS 1000000 2
SQL>
SQL> -- Switch back on new behaviour
SQL> alter session set "_fix_control" = '5483301:on';
Session altered.
SQL>
SQL> -- A non-existing value
SQL> explain plan for
2 select
3 *
4 from
5 t1
6 where
7 t_status = 1000
8 ;
Explained.
SQL>
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 546753835
--------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 107 | 4 (0)| 00:00:01 |
| 1 | TABLE ACCESS BY INDEX ROWID| T1 | 1 | 107 | 4 (0)| 00:00:01 |
|* 2 | INDEX RANGE SCAN | T1_IDX | 1 | | 3 (0)| 00:00:01 |
--------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - access("T_STATUS"=1000)
14 rows selected.
SQL>
SQL> -- Two non-existing values
SQL> explain plan for
2 select
3 *
4 from
5 t1
6 where
7 t_status in (1000, 2000)
8 ;
Explained.
SQL>
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 3743026710
---------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 107 | 5 (0)| 00:00:01 |
| 1 | INLIST ITERATOR | | | | | |
| 2 | TABLE ACCESS BY INDEX ROWID| T1 | 1 | 107 | 5 (0)| 00:00:01 |
|* 3 | INDEX RANGE SCAN | T1_IDX | 1 | | 4 (0)| 00:00:01 |
---------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("T_STATUS"=1000 OR "T_STATUS"=2000)
15 rows selected.
As suggested by Jonathan Lewis in the OTN thread, another elegant solution to the problem of searching for non-existing values would be to add a virtual column that filtered out the popular values. This approach has several advantages if applicable: The index maintained is very small, minimizes the maintenance effort (and might also address index-efficiency related issues in case of frequent updates to the column) and solves the histogram issue since the histogram will only cover the unpopular values:
SQL>
SQL> -- Add a virtual column (the same could be achieved using a function-based index instead for pre-11g versions)
SQL> alter table t1 add (t_status_unpop as (case when t_status != 0 then t_status end));
Table altered.
SQL>
SQL> exec dbms_stats.gather_table_stats(null, 'T1', method_opt => 'for columns t_status_unpop size 254')
PL/SQL procedure successfully completed.
SQL>
SQL> -- Since the virtual column only covers
SQL> -- the unpopular values, the histogram
SQL> -- will be very precise even with a low sample size
SQL> select
2 column_name
3 , num_distinct
4 , sample_size
5 from
6 user_tab_col_statistics
7 where
8 table_name = 'T1';
COLUMN_NAME NUM_DISTINCT SAMPLE_SIZE
--------------- ------------ -----------
ID 1000000 1000000
T_STATUS 3 1000000
VC 1 1000000
T_STATUS_UNPOP 2 20
SQL>
SQL> -- The histogram only covers the unpopular values
SQL> select
2 column_name
3 , endpoint_number
4 , endpoint_value
5 from
6 user_tab_histograms
7 where
8 table_name = 'T1'
9 and column_name = 'T_STATUS_UNPOP';
COLUMN_NAME ENDPOINT_NUMBER ENDPOINT_VALUE
--------------- --------------- --------------
T_STATUS_UNPOP 10 1
T_STATUS_UNPOP 20 2
SQL>
SQL> -- Two non-existing values
SQL> -- So we don't run into the same problem here
SQL> -- The estimate is reasonable for non-existing values
SQL> explain plan for
2 select
3 *
4 from
5 t1
6 where
7 t_status_unpop in (1000, 2000)
8 ;
Explained.
SQL>
SQL> select * from table(dbms_xplan.display);
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 3617692013
--------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 108 | 4470 (6)| 00:00:54 |
|* 1 | TABLE ACCESS FULL| T1 | 1 | 108 | 4470 (6)| 00:00:54 |
--------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter("T_STATUS_UNPOP"=1000 OR "T_STATUS_UNPOP"=2000)
13 rows selected.
I haven't created an index on the virtual column, but the estimate is correct and a suitable index would get used if it existed.
