Views expressed here are solely that of my own. Please make sure that you test the code/queries that appear on my blog before applying them to the production environment.

Thursday, July 12, 2007

Oracle CBO chooses the wrong index although the statistics are collected on the related table

Hi,

Our system analysis and support team called us, the Oracle DBA team, for a problem. The problem was a report program was running
OK before but it runs very slowly now, but they said that nothing has changed about the program except the data that it selects.
So we examined the situation and these are the things we did.

We traced the situation and found the guilty SQL. It is a simple one as it looks. The table TABLE01 has about 65 million rows.

SELECT SUM (DECODE (b1, 'A', tut1, 0)), SUM (DECODE (b1, 'B', tut1, 0))
FROM table01 t1
WHERE tar1 = to_date('29.06.2007','dd.mm.yyyy')
AND skod1 = NVL(NULL, skod1)
AND htno1 = '22001901'
AND 9000 + dkod1 = 9001
AND NVL (dtkod1, '*') = NVL (NULL, '*')
AND eno1 < 9000;
We looked at the explain plan of that SQL statement,
Plan
SELECT STATEMENT  CHOOSECost: 350  Bytes: 36  Cardinality: 1     
3 SORT AGGREGATE  Bytes: 36  Cardinality: 1    
2 TABLE ACCESS BY INDEX ROWID DBUSER01.TABLE01 Cost: 350  Bytes: 36  Cardinality: 1   
1 INDEX RANGE SCAN NON-UNIQUE DBUSER01.TABLE01_2X Cost: 347  Cardinality: 9  
When we run this query like that, although this SQL statement should not return any rows, we waited for 1 hour but it did not finish, so we killed the session because this is too much time for a report and apperantly there was a problem. Then we looked at the indexes of this table and there was another candidate index for this index and we tried the SQL by giving a hint for this second index.
SELECT /*+ index(t1 TABLE01_4X)*/
SUM (DECODE (b1, 'A', tut1, 0)), SUM (DECODE (b1, 'B', tut1, 0))
FROM table01 t1
WHERE tar1 = to_date('29.06.2007','dd.mm.yyyy')
AND skod1 = NVL(NULL, skod1)
AND htno1 = '22001901'
AND 9000 + dkod1 = 9001
AND NVL (dtkod1, '*') = NVL (NULL, '*')
AND eno1 < 9000;
OOOPPPS !!!, it just finished in 15 miliseconds. So we looked at the explain plan of this SQL statement.
Plan
SELECT STATEMENT  CHOOSECost: 542  Bytes: 36  Cardinality: 1     
3 SORT AGGREGATE  Bytes: 36  Cardinality: 1    
2 TABLE ACCESS BY INDEX ROWID DBUSER01.TABLE01 Cost: 542  Bytes: 36  Cardinality: 1   
1 INDEX RANGE SCAN NON-UNIQUE DBUSER01.TABLE01_4X Cost: 501  Cardinality: 1,452  
Although the cost of the second query (hinted) is higher than than the first one, the second SQL runs much faster. So how can this be, is the Oracle CBO missing something in calculating the cost ? We will see... Lets look at the structures of related indexes.
CREATE INDEX TABLE01_2X ON TABLE01
(htno1, dkod1, skod1);

CREATE INDEX TABLE01_4X ON TABLE01
(TAR1, skod1);
We collect statistics for the tables in our Oracle database, the Oracle CBO (Cost Base Optimizer) calculates the cost of a SQL statement false and chooses the wrong index, I mean the one that is less efficient. As a result of this behaviour these SQL statements does not finish in a resonable time, causing loss of business. How we collect the statistics is like that, we collect statistics for tables by using the following command :
exec dbms_stats.gather_table_stats(ownname => 'DBUSER01', tabname => 'TABLE01', estimate_percent => 33, cascade => TRUE);
After collecting the statistics we will examine how the CBO calculates the cost. According to Jonathan Lewis, Oracle CBO calculates the cost like below : cost = blevel + ceiling(leaf_blocks * effective index selectivity) + ceiling(clustering_factor * effective table selectivity) Lets calculate the cost of the following SQL
SELECT SUM (DECODE (b1, 'A', tut1, 0)), SUM (DECODE (b1, 'B', tut1, 0))
FROM table01 t1
WHERE tar1 = to_date('29.06.2007','dd.mm.yyyy')
AND skod1 = NVL(NULL, skod1)
AND htno1 = '22001901'
AND 9000 + dkod1 = 9001
AND NVL (dtkod1, '*') = NVL (NULL, '*')
AND eno1 < 9000;
---------------------------------------------------------
Plan
SELECT STATEMENT  CHOOSECost: 350  Bytes: 36  Cardinality: 1     
3 SORT AGGREGATE  Bytes: 36  Cardinality: 1    
2 TABLE ACCESS BY INDEX ROWID DBUSER01.TABLE01 Cost: 350  Bytes: 36  Cardinality: 1   
1 INDEX RANGE SCAN NON-UNIQUE DBUSER01.TABLE01_2X Cost: 347  Cardinality: 9   
---------------------------------------------------------

select owner, index_name, blevel, leaf_blocks, clustering_factor from dba_indexes where index_name = 'TABLE01_2X';
---------------------------------------------------------
OWNER|INDEX_NAME|BLEVEL|LEAF_BLOCKS|CLUSTERING_FACTOR
DBUSER01|TABLE01_2X|3|331491|16303842
effective index selectivity = density of "HTNO1" column effective table selectivity = (density of "DKOD1" column) * (density of "HTNO1" column) * (density of "SKOD1" column)
select column_name, num_distinct, density, num_buckets from dba_tab_columns t1 where t1.table_name = 'TABLE01' 
and t1.column_name in ('DKOD1', 'HTNO1', 'SKOD1')
order by t1.column_name;
---------------------------------------------------------
COLUMN_NAME|NUM_DISTINCT|DENSITY|NUM_BUCKETS
DKOD1|12|0.0833333333333333|1
HTNO1|965|0.00103626943005181|1
SKOD1|73|0.0136986301369863|1
Since the " AND 9000 + dkod1 = 9001" condition equals "function(col) = constant" is has the static selectivity of %1 (0.001) instead of 0.0833333333333333. cost = blevel + ceiling(leaf_blocks * effective index selectivity) + ceiling(clustering_factor * effective table selectivity) cost = 3 + ceiling(331491 * 0.00103626943005181) + ceiling(16303842 * (0.01 * 0.00103626943005181 * 0.0136986301369863)) = 350 ----------------------- Lets calculate the cost of the following SQL
SELECT /*+ index(t1 TABLE01_4X)*/
SUM (DECODE (b1, 'A', tut1, 0)), SUM (DECODE (b1, 'B', tut1, 0))
FROM table01 t1
WHERE tar1 = to_date('29.06.2007','dd.mm.yyyy')
AND skod1 = NVL(NULL, skod1)
AND htno1 = '22001901'
AND 9000 + dkod1 = 9001
AND NVL (dtkod1, '*') = NVL (NULL, '*')
AND eno1 < 9000;
---------------------------------------------------------
Plan
SELECT STATEMENT  CHOOSECost: 542  Bytes: 36  Cardinality: 1     
3 SORT AGGREGATE  Bytes: 36  Cardinality: 1    
2 TABLE ACCESS BY INDEX ROWID DBUSER01.TABLE01 Cost: 542  Bytes: 36  Cardinality: 1   
1 INDEX RANGE SCAN NON-UNIQUE DBUSER01.TABLE01_4X Cost: 501  Cardinality: 1,452  
---------------------------------------------------------

select owner, index_name, blevel, leaf_blocks, clustering_factor from dba_indexes where index_name = 'TABLE01_4X';
---------------------------------------------------------
OWNER|INDEX_NAME|BLEVEL|LEAF_BLOCKS|CLUSTERING_FACTOR
DBUSER01|TABLE01_4X|3|302597|1791039
effective index selectivity = density of "TAR1" column effective table selectivity = (density of "TAR1" column) * (density of "SKOD1" column)
select column_name, num_distinct, density, num_buckets from dba_tab_columns t1 where t1.table_name = 'TABLE01' 
and t1.column_name in ('TAR1', 'SKOD1')
order by t1.column_name;
---------------------------------------------------------
COLUMN_NAME|NUM_DISTINCT|DENSITY|NUM_BUCKETS
TAR1|608|0.00164473684210526|1
SKOD1|73|0.0136986301369863|1
cost = blevel + ceiling(leaf_blocks * effective index selectivity) + ceiling(clustering_factor * effective table selectivity) cost = 3 + ceiling(302597 * 0.00164473684210526) + ceiling(1791039 * (0.00164473684210526 * 0.0136986301369863)) = 542 ------------------------------ It is obvious that CBO can not choose the optimal index for this SQL, that is "TABLE01_4X". Why ? The answer is that we did not give the CBO the enough info about the structure of the data in table and the indexes. So the solution is, we should collect more data for this table about the distribution of data in that table. What should we do ? We should collect histogram data for this table, lets see the result of collecting histograms for this table. Lets collect histograms for this table.
exec dbms_stats.gather_table_stats('DBUSER01','TABLE01', estimate_percent=>33, cascade => TRUE, method_opt => 'FOR ALL INDEXED COLUMNS SIZE 10');
Lets look at the explain plans : First select is just finished in 15 miliseconds, and the second one does not finish so the problem is solved, our SQL now finishes in 15 msecs.
SELECT SUM (DECODE (b1, 'A', tut1, 0)), SUM (DECODE (b1, 'B', tut1, 0))
FROM table01 t1
WHERE tar1 = to_date('29.06.2007','dd.mm.yyyy')
AND skod1 = NVL(NULL, skod1)
AND htno1 = '22001901'
AND 9000 + dkod1 = 9001
AND NVL (dtkod1, '*') = NVL (NULL, '*')
AND eno1 < 9000;

Plan
SELECT STATEMENT  CHOOSECost: 621  Bytes: 36  Cardinality: 1     
3 SORT AGGREGATE  Bytes: 36  Cardinality: 1    
2 TABLE ACCESS BY INDEX ROWID DBUSER01.TABLE01 Cost: 621  Bytes: 36  Cardinality: 1   
1 INDEX RANGE SCAN NON-UNIQUE DBUSER01.TABLE01_4X Cost: 519  Cardinality: 3,648  

SELECT /*+ index(t1 TABLE01_2X)*/
SUM (DECODE (b1, 'A', tut1, 0)), SUM (DECODE (b1, 'B', tut1, 0))
FROM table01 t1
WHERE tar1 = to_date('29.06.2007','dd.mm.yyyy')
AND skod1 = NVL(NULL, skod1)
AND htno1 = '22001901'
AND 9000 + dkod1 = 9001
AND NVL (dtkod1, '*') = NVL (NULL, '*')
AND eno1 < 9000;

Plan
SELECT STATEMENT  CHOOSECost: 11,248  Bytes: 36  Cardinality: 1     
3 SORT AGGREGATE  Bytes: 36  Cardinality: 1    
2 TABLE ACCESS BY INDEX ROWID DBUSER01.TABLE01 Cost: 11,248  Bytes: 36  Cardinality: 1   
1 INDEX RANGE SCAN NON-UNIQUE DBUSER01.TABLE01_2X Cost: 11,066  Cardinality: 716  
------------------------------ Lets examine the costs of the following SQLs
SELECT SUM (DECODE (b1, 'A', tut1, 0)), SUM (DECODE (b1, 'B', tut1, 0))
FROM table01 t1
WHERE tar1 = to_date('29.06.2007','dd.mm.yyyy')
AND skod1 = NVL(NULL, skod1)
AND htno1 = '22001901'
AND 9000 + dkod1 = 9001
AND NVL (dtkod1, '*') = NVL (NULL, '*')
AND eno1 < 9000;
---------------------------------------------------------
Plan
SELECT STATEMENT  CHOOSECost: 621  Bytes: 36  Cardinality: 1     
3 SORT AGGREGATE  Bytes: 36  Cardinality: 1    
2 TABLE ACCESS BY INDEX ROWID DBUSER01.TABLE01 Cost: 621  Bytes: 36  Cardinality: 1   
1 INDEX RANGE SCAN NON-UNIQUE DBUSER01.TABLE01_4X Cost: 519  Cardinality: 3,648  
---------------------------------------------------------

select owner, index_name, blevel, leaf_blocks, clustering_factor from dba_indexes where index_name = 'TABLE01_4X';
---------------------------------------------------------
OWNER|INDEX_NAME|BLEVEL|LEAF_BLOCKS|CLUSTERING_FACTOR
DBUSER01|TABLE01_4X|3|303888|1796569
effective index selectivity = density of "TAR1" column effective table selectivity = (density of "TAR1" column) * (density of "SKOD1" column)
select column_name, num_distinct, density, num_buckets from dba_tab_columns t1 where t1.table_name = 'TABLE01' 
and t1.column_name in ('TAR1', 'SKOD1')
order by t1.column_name;
---------------------------------------------------------
COLUMN_NAME|NUM_DISTINCT|DENSITY|NUM_BUCKETS
TAR1|608|0.00169779286926995|10
SKOD1|73|0.0333333333333333|8
cost = blevel + ceiling(leaf_blocks * effective index selectivity) + ceiling(clustering_factor * effective table selectivity) cost = 3 + ceiling(303888 * 0.00169779286926995) + ceiling(1796569 * (0.00169779286926995 * 0.0333333333333333)) = 621 ----------------------
SELECT /*+ index(t1 TABLE01_2X)*/
SUM (DECODE (b1, 'A', tut1, 0)), SUM (DECODE (b1, 'B', tut1, 0))
FROM table01 t1
WHERE tar1 = to_date('29.06.2007','dd.mm.yyyy')
AND skod1 = NVL(NULL, skod1)
AND htno1 = '22001901'
AND 9000 + dkod1 = 9001
AND NVL (dtkod1, '*') = NVL (NULL, '*')
AND eno1 < 9000;
---------------------------------------------------------
Plan
SELECT STATEMENT  CHOOSECost: 11,248  Bytes: 36  Cardinality: 1     
3 SORT AGGREGATE  Bytes: 36  Cardinality: 1    
2 TABLE ACCESS BY INDEX ROWID DBUSER01.TABLE01 Cost: 11,248  Bytes: 36  Cardinality: 1   
1 INDEX RANGE SCAN NON-UNIQUE DBUSER01.TABLE01_2X Cost: 11,066  Cardinality: 716  
---------------------------------------------------------

select owner, index_name, blevel, leaf_blocks, clustering_factor from dba_indexes where index_name = 'TABLE01_2X';
---------------------------------------------------------
OWNER|INDEX_NAME|BLEVEL|LEAF_BLOCKS|CLUSTERING_FACTOR
DBUSER01|TABLE01_2X|3|331864|16304224
effective index selectivity = density of "HTNO1" column effective table selectivity = (density of "DKOD1" column) * (density of "HTNO1" column) * (density of "SKOD1" column)
select column_name, num_distinct, density, num_buckets from dba_tab_columns t1 where t1.table_name = 'TABLE01' 
and t1.column_name in ('DKOD1', 'HTNO1', 'SKOD1')
order by t1.column_name;
---------------------------------------------------------
COLUMN_NAME|NUM_DISTINCT|DENSITY|NUM_BUCKETS
DKOD1|12|0.0384615384615385|2
HTNO1|968|0.0333333333333333|9
SKOD1|73|0.0333333333333333|8
Since the " AND 9000 + dkod1 = 9001" condition equals "function(col) = constant" is has the static selectivity of %1 (0.001) instead of 0.0833333333333333. cost = blevel + ceiling(leaf_blocks * effective index selectivity) + ceiling(clustering_factor * effective table selectivity) cost = 3 + ceiling(331864 * 0.0333333333333333) + ceiling(16304224 * (0.01 * 0.0333333333333333 * 0.0333333333333333)) = 11248 -------------------------- How the histograms caused the CBO to choose the righr index ? Lets look at the histogram data.
select * from dba_tab_histograms t1 where t1.table_name = 'TABLE01' 
and t1.column_name in ('TAR1','HTNO1', 'DKOD1', 'SKOD1')
order by t1.column_name, t1.endpoint_number ;
---------------------------------------------
OWNER|TABLE_NAME|COLUMN_NAME|ENDPOINT_NUMBER|ENDPOINT_VALUE|ENDPOINT_ACTUAL_VALUE
DBUSER01|TABLE01|DKOD1|8|1|
DBUSER01|TABLE01|DKOD1|9|2|
DBUSER01|TABLE01|DKOD1|10|21|
DBUSER01|TABLE01|HTNO1|0|2.50227984373754E35|
DBUSER01|TABLE01|HTNO1|1|2.60632781273513E35|
DBUSER01|TABLE01|HTNO1|2|2.60632860505268E35|
DBUSER01|TABLE01|HTNO1|3|2.60775139366763E35|
DBUSER01|TABLE01|HTNO1|5|2.65906207772846E35|
DBUSER01|TABLE01|HTNO1|6|2.76351807179888E35|
DBUSER01|TABLE01|HTNO1|7|2.76351807179912E35|
DBUSER01|TABLE01|HTNO1|8|2.81462815943683E35|
DBUSER01|TABLE01|HTNO1|9|2.81462815943707E35|
DBUSER01|TABLE01|HTNO1|10|2.97121551998981E35|
DBUSER01|TABLE01|TAR1|0|2453374|
DBUSER01|TABLE01|TAR1|1|2453502|
DBUSER01|TABLE01|TAR1|2|2453599|
DBUSER01|TABLE01|TAR1|3|2453689|
DBUSER01|TABLE01|TAR1|4|2453790|
DBUSER01|TABLE01|TAR1|5|2453889|
DBUSER01|TABLE01|TAR1|6|2453973|
DBUSER01|TABLE01|TAR1|7|2454060|
DBUSER01|TABLE01|TAR1|8|2454141|
DBUSER01|TABLE01|TAR1|9|2454218|
DBUSER01|TABLE01|TAR1|10|2454292|
DBUSER01|TABLE01|SKOD1|0|8345|
DBUSER01|TABLE01|SKOD1|3|9000|
DBUSER01|TABLE01|SKOD1|4|9050|
DBUSER01|TABLE01|SKOD1|5|9159|
DBUSER01|TABLE01|SKOD1|6|9170|
DBUSER01|TABLE01|SKOD1|7|9300|
DBUSER01|TABLE01|SKOD1|8|9412|
DBUSER01|TABLE01|SKOD1|9|9631|
DBUSER01|TABLE01|SKOD1|10|9892|
Lets look at the densities before and after the histograms. Before
select owner, index_name, blevel, leaf_blocks, clustering_factor from dba_indexes where index_name = 'TABLE01_2X';
---------------------------------------------------------
OWNER|INDEX_NAME|BLEVEL|LEAF_BLOCKS|CLUSTERING_FACTOR
DBUSER01|TABLE01_2X|3|331491|16303842
DBUSER01|TABLE01_4X|3|302597|1791039

select column_name, num_distinct, density, num_buckets from dba_tab_columns t1 where t1.table_name = 'TABLE01' 
and t1.column_name in ('DKOD1', 'HTNO1', 'SKOD1', 'TAR1')
order by t1.column_name;
---------------------------------------------------------
COLUMN_NAME|NUM_DISTINCT|DENSITY|NUM_BUCKETS
DKOD1|12|0.0833333333333333|1
HTNO1|965|0.00103626943005181|1
TAR1|608|0.00164473684210526|1
SKOD1|73|0.0136986301369863|1
After
select owner, index_name, blevel, leaf_blocks, clustering_factor from dba_indexes where index_name = 'TABLE01_2X';
---------------------------------------------------------
OWNER|INDEX_NAME|BLEVEL|LEAF_BLOCKS|CLUSTERING_FACTOR
DBUSER01|TABLE01_2X|3|331864|16304224
DBUSER01|TABLE01_4X|3|303888|1796569

select column_name, num_distinct, density, num_buckets from dba_tab_columns t1 where t1.table_name = 'TABLE01' 
and t1.column_name in ('DKOD1', 'HTNO1', 'SKOD1', 'TAR1')
order by t1.column_name;
---------------------------------------------------------
COLUMN_NAME|NUM_DISTINCT|DENSITY|NUM_BUCKETS
DKOD1|12|0.0384615384615385|2
HTNO1|968|0.0333333333333333|9
TAR1|608|0.00169779286926995|10
SKOD1|73|0.0333333333333333|8
As we can see the leaf_blocks and clustering_factor values of the indexes are changed a bit, but these are not so important in cost calculation, but the densities of the indexed columns are much more effective in cost calculation. Lets examine them closer. Before the histograms the densities of all the colums are equal to 1/num_distinct of the respective columns.
select column_name, num_distinct, density, 1/numdistinct density_calculated from dba_tab_columns t1 where t1.table_name = 'TABLE01' 
and t1.column_name in ('DKOD1', 'HTNO1', 'SKOD1', 'TAR1')
order by t1.column_name;
---------------------------------------------------------
COLUMN_NAME|NUM_DISTINCT|DENSITY|DENSITY_CALCULATED
DKOD1|12|0.0833333333333333|0.0833333333333333
HTNO1|965|0.00103626943005181|0.00103626943005181
TAR1|608|0.00164473684210526|0.00164473684210526
SKOD1|73|0.0136986301369863|0.0136986301369863
After collecting the histograms the densities of all the colums are NOT equal to 1/num_distinct of the respective columns.
select column_name, num_distinct, density, 1/numdistinct density_calculated from dba_tab_columns t1 where t1.table_name = 'TABLE01' 
and t1.column_name in ('DKOD1', 'HTNO1', 'SKOD1', 'TAR1')
order by t1.column_name;
---------------------------------------------------------
COLUMN_NAME|NUM_DISTINCT|DENSITY|DENSITY_CALCULATED
DKOD1|12|0.0384615384615385|0.0833333333333333
HTNO1|968|0.0333333333333333|0.00103305785123967
TAR1|608|0.00169779286926995|0.00164473684210526
SKOD1|73|0.0333333333333333|0.0136986301369863

Since the "DKOD1" column has the static selectivity of 0.01, the selectivities of the other columns
are effective role in the calculation of cost. As we see after the histograms, the density of "HTNO1"
and "SKOD1" columns are increased, the density of "TAR1" is decreased a little bit. Since the "SKOD1"
column exists in both indexes we should examine the densities of the "HTNO1" and "TAR1" columns.

In normal case, I mean statistics without histograms, the CBO assumes a smooth distribution of data values of
a column between minimum and maximum values. But in reality there are fluctuation in the distribution of data
for some columns. I mean some values appears rarely but some data appears frequently in distribution. So the CBO
can not determine this distribution without having histogram data on these columns. The calculation of density of
these columns in case of histograms is a very complex algorithm so we should not bother about it.

This case show the importance of histograms where there is skewed data in indexed columns.

Regards
Ural Ural

2 comments:

Tonguç said...

Nice article Ural, but in order to improve reading maybe you may prefer to give the examples by links to some text files. Really tiring to read all :)

Best regards,
Tonguc

pbsl said...

you have a nice site. thanks for sharing this valuable resources. keep it up. anyway, various kinds of ebooks are available here

http://feboook.blogspot.com