The CBO and Indexes: An Introduction (Absolute Beginners)

One of the more common questions I get asked and one of the most common questions asked in the various Oracle related forums is the general question of why doesn’t the CBO choose to use a particular index. There are various reasons why an index might be ignored but generally and rather simplistically (for now), the answer is often simply because the CBO considers the cost of using the index to be more expensive than other alternatives.

As one would expect with the CBO, the cost is a rather important consideration and yet many don’t understand what the costs associated with an execution plan actually means and represents. Some people think the costs associated with an execution plan are basically meaningless and are only used by the CBO in “mysterious ways”. Some people even go so far as to suggest that the CBO sucks and recommend all sorts of inappropriate ways to force Oracle to use an index.

It all comes back to simply not understanding CBO fundamentals and how Oracle costs the basic use of an index.

In reality of course, the CBO doesn’t “suck” with 10g, in fact it’s actually extremely clever and resourceful when it comes to determining appropriate, efficient execution plans. If the CBO is armed with “accurate enough” statistics, it will generally do a remarkably good job. The costs and the associated cardinality of the various steps within an execution plan provide valuable information on why the CBO has made its decisions.

So I thought I might discuss the CBO a little and start with a very basic introduction into how the CBO costs an index to get this message across.

The basic formula for costing an index based range scan is:

basic index range scan cost = index blevel + ceil(index selectivity x leaf blocks) + ceil(table selectivity x clustering factor)

Note there are various slight variations and interpretations of this formula from database version to database version and for differing specific scenarios, which can vary the resultant costs marginally. All the following examples are from a windows based 10.2.0.3 database.

So from an index perspective, the index blevel, the number of leaf blocks and the clustering factor are all statistics that directly influence the cost of using the index. However, just as important are the associated selectivities of accessing both the index and the table. These statistics are often based on the associated column statistics (but not always) and if Oracle gets these selectivities wrong, then the CBO will generate wrong costings and all bets are off regarding the appropriateness of the resultant execution plan.

OK, let’s create a nice, simple little scenario which will be the basis of future demos.

SQL> CREATE TABLE bowie_stuff AS SELECT (mod(rownum,100)+1)*10 id, 'Ziggy Stardust' name FROM dual CONNECT BY LEVEL <= 100000;

Table created.

SQL> CREATE INDEX bowie_stuff_i ON bowie_stuff(id);

Index created.

We’ll use the BOWIE_STUFF table in future demos, but for now I’m after a relatively large index with an excellent clustering factor. So I’ll create a second table, ordered on the ID column and double it’s size …

SQL> CREATE TABLE bowie_stuff2 AS SELECT * FROM bowie_stuff ORDER BY id;

Table created.

SQL> INSERT INTO bowie_stuff2 SELECT * FROM bowie_stuff2;

100000 rows created.

SQL> commit;

Commit complete.

SQL> CREATE INDEX bowie_stuff2_i ON bowie_stuff2(id);

Index created.

SQL> exec dbms_stats.gather_table_stats(ownname=> null, tabname=> 'BOWIE_STUFF2', cascade=> true, estimate_percent=> null, method_opt=> 'FOR ALL COLUMNS SIZE 1');

PL/SQL procedure successfully completed.

If we now look at some of the key statistics, we note the following:

SQL> SELECT table_name, blocks, num_rows FROM user_tables WHERE table_name = 'BOWIE_STUFF2'; 
TABLE_NAME   BLOCKS NUM_ROWS
------------ ------ --------
BOWIE_STUFF2    659   200000

The table has 200,000 rows and consists of 659 data blocks.

SQL> SELECT column_name, num_distinct, density, num_nulls FROM user_tab_col_statistics WHERE table_name = 'BOWIE_STUFF2' and column_name = 'ID';
COLUMN_NAME NUM_DISTINCT DENSITY NUM_NULLS
----------- ------------ ------- ---------
ID                   100     .01         0

The indexed ID column has 100 distinct values, which are perfectly evenly distributed.  The density of the ID is an “accurate” 0.01 with a selectivity of 1%, so a selection of one distinct value will return 200,000 x 0.01 = 2,000 rows. Nice easy numbers …

SQL> SELECT index_name, blevel, leaf_blocks, num_rows, distinct_keys, clustering_factor FROM user_indexes WHERE index_name = 'BOWIE_STUFF2_I';

INDEX_NAME      BLEVEL LEAF_BLOCKS
-------------- ------- -----------
BOWIE_STUFF2_I       2         605  

NUM_ROWS DISTINCT_KEYS CLUSTERING_FACTOR
-------- ------------- -----------------  
200000           100               854

The index has a blevel of 2, it has 605 leaf blocks and a rather good clustering factor of just 854 (note the rows in the table were basically inserted in ID order).

OK, we now have all the information we need.

Note to start with, I’ll only use the “older” IO costing model by setting the following parameter:

SQL> alter session set "_optimizer_cost_model" = io;

Session altered.

As we’ll see in future posts, the use of the CPU costing model actually has minimal effect on many index related access costings but we’ll use the IO costing model as a starting point.

This first equality SQL demo shows the costings in relation to a simple, single value equality predicate (I’ve linked to a PDF to preserve formatting).

OK, 2 important pieces of information to note. Firstly, the CBO has got the expected cardinality (2000 rows) spot on.

As the stats are 100% accurate and the values are perfectly evenly distributed, this is to be expected. If Oracle gets the cardinality correct, we can be reasonably confident that the CBO to have made a reasonable decision here.

As previously mentioned, there are 100 distinct values of which we want one of those those values. Oracle has calculated the selectivity of the query to be 1/100 = 1% or a value of 0.01 (as defined in the density column statistic). The expected number of rows is therefore 200,000 x 0.01 = 2000. Like I said, spot on.

Secondly, the CBO has calculated the cost of the index range scan to be 9 and the overall cost of the query to be 18. How has the CBO derived these costings ? Well as it’s a simple, single column index and associated query predicate, we can plug in the 0.01 selectivity into the above formula as follows:

index blevel + ceil(index selectivity x leaf blocks) + ceil(table selectivity x clustering factor)

2 + ceil(0.01 x 605) + ceil(0.01 x 854) = 2 + 7 + 9 =    9 + 9 = 18

So we can see that the costs associated with accessing just the index:

blevel + ceil(index selectivity x leaf blocks) = 2 + ceil(0.01 x 605) = 2 + 7 = 9

indeed comes to a total of 9

and the overall cost of the execution plan indeed does come to 18.

The CBO costings all do actually make sense and add up as expected.

In this second IN list demo, we’re just going to expand on things a touch by selecting 3 distinct values in a IN list. However, the actual principles and cost calculations are basically the same.

This time we’re after 3 possible values as listed in the IN clause. So that’s 3 out of the 100 possible values, 3/100 = 3% or 0.03. The required cardinality is therefore 200,000 rows x 0.03 = 6000 which again Oracle has got spot on. Usually a good sign that the CBO has made a reasonable decision.

This time the costs have come to 23 for the index range scan part of the execution plan and 49 overall. Again using our basic formula:

index blevel + ceil(index selectivity x leaf blocks) + ceil(table selectivity x clustering factor)

2 + 3 x ceil(0.01 x 605) + ceil(0.03 x 854) = 2 + 3×7 + 26 = 2 + 21 + 26 = 23 + 26 = 49.

So the cost associated with the index is indeed 23 and the overall cost of the query is indeed 49. Again, all these CBO costings make sense. These costings aren’t meaningless, internal numbers but values that give us a useful insight into how and why the CBO has come to a specific cost and so to a specific execution plan.

Note BTW, one of those subtle differences in how the formula is implemented with 10g (from say 9i) is the fact the selectivity is calculated for the index by performing the CEIL function for one value first and then multiplied by the overall number of expected values in the IN list:

2 + 3 x  ceil(0.01 x 605) = 23

rather than determining and using the total index selectivity within the CEIL function:

2 +  ceil(0.03 x 605) = 21

The net result being such costs are going to be just that little bit higher in 10g than they would have been in 9i.

So indeed, these things can all change a little from release to release but the basic principle is still the same. Feed the CBO acurate enough statistics and it’ll likely do the right thing. If it doesn’t, understanding the CBO and how it costs various execution plans will help to determine what the issues might be. Huge clues are provided by the costings and cardinality estimates in the associated query execution plans. 

I’ll expand on all this is future posts but for more information on this subject, I highly recommend the writings of Wolfgang Breitling (and his excellent paper “A Look Under The Hood Of The CBO: The 10053 Event” in particular) and the writings of Jonathan Lewis (and his excellent book “Cost-Based Oracle Fundamentals” in particular).

Like I said, this is only meant as an introduction, more to come …