jump to navigation

Costing Concatenated Indexes With Range Scan Predicates Part I (Nothing To Be Desired) July 22, 2022

Posted by Richard Foote in BLEVEL, CBO, Clustering Factor, Concatenated Indexes, Index Access Path, Index Column Order, Index Column Reorder, Leaf Blocks, Non-Equality Predicates, Oracle, Oracle Cost Based Optimizer, Oracle General, Oracle Indexes, Performance Tuning, Richard Foote Consulting, Richard Foote Training, Richard's Blog.
1 comment so far

In my previous post, I discussed how Automatic Indexing ordered columns when derived from SQLs containing both equality and non-equality predicates.

I’ve since had offline questions asking why indexes are more effective with leading columns addressing the equality predicates rather than the leading columns addressing non-equality predicates. Based on the theory that for everyone who asks a question, there are likely numerous others wondering the same thing, I thought I’ll try to explain things with these posts.

I’ll start by creating the following simple table that has two columns (ID and CODE) that are both highly selective (they both have 10,000 distinct values in a 100,000 rows table, so 10 rows approximately per value):

SQL> CREATE TABLE radiohead (id NUMBER, code NUMBER, name VARCHAR2(42));

Table created.

SQL> INSERT INTO radiohead SELECT mod(rownum,10000)+1,

ceil(dbms_random.value(0,10000)), 'RADIOHEAD' FROM dual CONNECT BY LEVEL <= 100000;

100000 rows created.

SQL> commit;

Commit complete.

I’ll next create an index based on the ID, CODE columns, with importantly the ID column as the leading column:

SQL> CREATE INDEX radiohead_id_code_i ON radiohead(id, code);

Index created.

SQL> exec dbms_stats.gather_table_stats(ownname=>null, tabname=>'RADIOHEAD',

estimate_percent=> null, method_opt=> 'FOR ALL COLUMNS SIZE 1');

PL/SQL procedure successfully completed.

 

When it comes to costing index accesses, some of the crucial statistics including the Blevel, Leaf_Blocks and often most crucial of all, the Clustering_Factor:

SQL> SELECT index_name, blevel, leaf_blocks, clustering_factor FROM user_indexes WHERE index_name = 'RADIOHEAD_ID_CODE_I';

INDEX_NAME               BLEVEL LEAF_BLOCKS CLUSTERING_FACTOR
-------------------- ---------- ----------- -----------------
RADIOHEAD_ID_CODE_I           1         265             99034

 

We begin by running the following query, with an equality predicate on the ID column and a relatively large, non-selective range predicate on the CODE column:

SQL> SELECT * FROM radiohead WHERE id = 42 AND CODE BETWEEN 1000 AND 5000;

Execution Plan
-----------------------------------------------------------------------------------------------------------
| Id  | Operation                           | Name                | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |                     |     4 |    72 |     6   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| RADIOHEAD           |     4 |    72 |     6   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN                  | RADIOHEAD_ID_CODE_I |     4 |       |     2   (0)| 00:00:01 |
-----------------------------------------------------------------------------------------------------------

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          8  consistent gets
          0  physical reads
          0  redo size
        824  bytes sent via SQL*Net to client
        608  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          5  rows processed

As (perhaps) expected, the CBO uses the index to retrieve the small number of rows (just 5 rows).

However, if we run the following query which also returns a small number of rows  (just 4 rows) BUT with the relatively unselective, non-equality predicate based on the leading indexed ID column:

SQL> SELECT * FROM radiohead WHERE id BETWEEN 1000 AND 5000 AND CODE = 140;

Execution Plan
-------------------------------------------------------------------------------
| Id  | Operation         | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |           |     4 |    72 |   105  (11)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| RADIOHEAD |     4 |    72 |   105  (11)| 00:00:01 |
-------------------------------------------------------------------------------

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
        363  consistent gets
          0  physical reads
          0  redo size
        770  bytes sent via SQL*Net to client
        608  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          4  rows processed

We notice (perhaps unexpectedly) that the CBO now ignores the index and uses a Full Table Scan, even though only 4 rows are returned from a 100,000 row table.

This is a common area of confusion. Why does Oracle not use the index when both columns in the index are referenced in the SQL predicates and only a tiny number of rows are returned?

The answer comes down to the very unselective non-equality predicate (ID BETWEEN 1000 AND 5000) being serviced by the leading column (ID) of the index.

The “ID BETWEEN 1000 AND 5000” predicate basically covers 40% of all known ID values, which means Oracle must now read 40% of all Leaf Blocks within the index (one leaf block at a time), starting with ID =1000 and ending with ID = 5000. Although there are very few rows that then subsequently match up with the other (CODE = 140) predicate based on the second column (CODE) of the index, these relatively few values could exist anywhere within the 40% ID range.

Therefore, when costing the reading of the actual index, the CBO basically stops its calculations after the non-equality predicate on this leading ID column and indeed estimates that a full 40% of the index itself must be scanned.

If we force the CBO into a range scan via a basic index hint:

SQL> SELECT /*+ index(r) */ * FROM radiohead r WHERE id BETWEEN 1000 AND 5000 AND CODE = 140;

Execution Plan
-----------------------------------------------------------------------------------------------------------
| Id  | Operation                           | Name                | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |                     |     4 |    72 |   116   (4)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| RADIOHEAD           |     4 |    72 |   116   (4)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN                  | RADIOHEAD_ID_CODE_I |     4 |       |   112   (4)| 00:00:01 |
-----------------------------------------------------------------------------------------------------------

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
        114  consistent gets
          0  physical reads
          0  redo size
        806  bytes sent via SQL*Net to client
        608  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          4  rows processed

We notice that the overall cost of this index based plan is 116, greater than the 105 cost of the Full Table Scan (and hence why the Full Table Scan was selected). We also notice that the vast majority of this 116 cost can be attributed to the index scan itself in the plan, which has a cost of 112.

If you have a calculator handy, this is basically how these costs are derived.

Range Selectivity = (Max Range Value–Min Range Value)/(Max Column Value–Min Column Value)

Effective Index Selectivity = Range Selectivity + 2 x ID density (as a BETWEEN clause was used which is inclusive of Min/Max range)

= (5000-1000)/(10000-1) + 2 x (1/10000)

= 0.40004 + 0.0002

= 0.40024

Effective Table Selectivity = ID selectivity (as above) x CODE selectivity

= 0.40024 x (1/10000)

= 0.40024 x 0.0001

= 0.000040024

These selectivities are then inserted into the following index costing formula:

Index IO Cost = blevel +

ceil(effective index selectivity x leaf_blocks) +

ceil(effective table selectivity x clustering_factor)

 

Index IO Cost = 1  +  ceil(0.40024 x 265) + ceil(0.000040024 x 99034)

= 1 + 107 + 4

= 108 + 4 = 112.

 

Index Access Cost = IO Costs + CPU Costs (in this plan, 4% of total costs)

= (108 + (112 x 0.04)) + (4 + (4 x 0.04))

= (108 + 4) + (4 + 0)

= 112 + 4

= 116

 

So we can clearly see how the CBO has made its calculations, come up with its costs and has decided that the Full Table Scan is indeed the cheaper alternative with the current index in place.

So Automatic Indexing is doing the right thing, by creating an index with the leading column based on the equality predicate and the second indexed column based on the unselective non-equality predicate.

I’ll expand on this point in an upcoming Part II post.

BLEVEL 1 => BLEVEL 2 (Teenage Wildlife) August 23, 2011

Posted by Richard Foote in BLEVEL, CBO, Oracle Indexes.
4 comments

Jonathan Lewis recently wrote a really nice blog piece blevel=1 on the dangers of an index toggling between BLEVEL 1 and BLEVEL 2. I thought it would be useful to demonstrate this issue with a quick demo (Note: this example is on 11.2.0.1, with an 8K block size).
 
First, create a simple little table with 336,000 rows and an index on an ID number column:

  
SQL> create table major_tom (id number, code number, name varchar2(30));
 
Table created.
 
SQL> create index major_tom_i on major_tom(id);
 
Index created.
 
SQL> insert into major_tom select rownum, mod(rownum,100), 'GROUND CONTROL' from dual connect by level <=336000;
 
336000 rows created.
 
SQL> commit;
 
Commit complete.
 
SQL> exec dbms_stats.gather_table_stats(ownname=>null, tabname=> 'MAJOR_TOM', cascade=> true, estimate_percent=>null, method_opt=>'FOR ALL COLUMNS SIZE 1');
 
PL/SQL procedure successfully completed.
 
SQL> select blevel, leaf_blocks, clustering_factor from dba_indexes where index_name='MAJOR_TOM_I';
 
    BLEVEL LEAF_BLOCKS CLUSTERING_FACTOR
---------- ----------- -----------------
         1         671              1296

 
Note the index has 671 leaf blocks and a Blevel=1. This of course means the index basically consists of a Root Block, which in turn references all its 671 leaf blocks. Therefore to read a specific index entry, requires a read of the index root block followed by a read of the specific index leaf block. That’s 2 reads in total.
 
Let’s run a query to return one row (note the ID column is effectively unique although I’ve only created a non-unique index):
 

SQL> select * from major_tom where id = 42;
 

Execution Plan
----------------------------------------------------------
Plan hash value: 4155681103
 
-------------------------------------------------------------------------------------------
| Id  | Operation                   | Name        | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |             |     1 |    23 |     2   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| MAJOR_TOM   |     1 |    23 |     2   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | MAJOR_TOM_I |     1 |       |     1   (0)| 00:00:01 |
-------------------------------------------------------------------------------------------
 

Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - access("ID"=42)
 

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          4  consistent gets
          0  physical reads
          0  redo size
        531  bytes sent via SQL*Net to client
        395  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

 
 

Note: The cost of using the index is just 1 not 2 as perhaps expected. This is due to the CBO ignoring the Blevel in its calculations when the Blevel = 1.  As the index is relatively small, the CBO takes the approach that the root block is very likely already cached and so is not worth costing.
 
As the data is perfectly evenly distributed and effectively unique, the CBO has correctly estimated the number of returned rows as just 1. Therefore, the overall cost of the execution plan is just 2, 1 to read the leaf block and 1 to read the table block.
 
Notice that the number of consistent gets is 4. 1 to read the index root block, 1 for the index leaf block, 1 for the table block and as the index is non-unique, 1 for an additional fetch performed to check the index again that there are no further rows to be returned.
 
If we now create another table of 1M rows that will be used in a join operation:
 

 
SQL> create table ziggy (id number, code number, name varchar2(30));
 
Table created.
 
SQL> insert into ziggy select rownum, mod(rownum,10000), 'ZIGGY STARDUST' from dual connect by level <= 1000000;
 
1000000 rows created.
 
SQL> exec dbms_stats.gather_table_stats(ownname=>null, tabname=> 'ZIGGY', cascade=> true, estimate_percent=>null, method_opt=>'FOR ALL COLUMNS SIZE 1');
 
PL/SQL procedure successfully completed.

If we now join these 2 tables and select a moderate number of rows:
 

 
SQL> select * from ziggy z, major_tom m where z.id = m.id and z.code in (42, 4242);
 
68 rows selected.
 

Execution Plan
----------------------------------------------------------
Plan hash value: 2011771477
 
--------------------------------------------------------------------------------------------
| Id  | Operation                    | Name        | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |             |   200 |  9400 |  1372   (2)| 00:00:17 |
|   1 |  NESTED LOOPS                |             |       |       |            |          |
|   2 |   NESTED LOOPS               |             |   200 |  9400 |  1372   (2)| 00:00:17 |
|*  3 |    TABLE ACCESS FULL         | ZIGGY       |   200 |  4800 |  1105   (2)| 00:00:14 |
|*  4 |    INDEX RANGE SCAN          | MAJOR_TOM_I |     1 |       |     1   (0)| 00:00:01 |
|   5 |   TABLE ACCESS BY INDEX ROWID| MAJOR_TOM   |     1 |    23 |     2   (0)| 00:00:01 |
--------------------------------------------------------------------------------------------
 

Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - filter("Z"."CODE"=42 OR "Z"."CODE"=4242)
   4 - access("Z"."ID"="M"."ID")
 

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
       4175  consistent gets
       4024  physical reads
          0  redo size
       1950  bytes sent via SQL*Net to client
        395  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
         68  rows processed

The CBO goes for a Nested Loop join, primarily because the inner table is only accessed a relatively small number of times AND because the cost of doing so via the index is so damn cheap.
 
However, if we add just a few more rows and collect fresh statistics …
 

 
SQL> insert into major_tom select rownum+336000, mod(rownum,100), 'GROUND CONTROL' from dual connect by level <=500;
 
500 rows created.
 
SQL> commit;
 
Commit complete.
 
SQL> exec dbms_stats.gather_table_stats(ownname=>null, tabname=> 'MAJOR_TOM', cascade=> true, estimate_percent=>null, method_opt=>'FOR ALL COLUMNS SIZE 1');
 
PL/SQL procedure successfully completed.
 

SQL> select blevel, leaf_blocks, clustering_factor from dba_indexes where index_name='MAJOR_TOM_I';
 
    BLEVEL LEAF_BLOCKS CLUSTERING_FACTOR
---------- ----------- -----------------
         2         672              1298

The index has now toggled over to become a Blevel 2 index. We only added a handful of rows resulting in just the one additional index leaf block, but 672 is just too many to be referenced within the one index root block in this example. The root block has split, two new index branches have been created that now reference the leaf blocks and the root block now only references the two new branch blocks.
 
Overall, the changes are quite minor but the ramifications can be quite dramatic …
 
If we now select one row again:
 

 
SQL> select * from major_tom where id = 42;
 

Execution Plan
----------------------------------------------------------
Plan hash value: 4155681103
 
-------------------------------------------------------------------------------------------
| Id  | Operation                   | Name        | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |             |     1 |    23 |     4   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| MAJOR_TOM   |     1 |    23 |     4   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | MAJOR_TOM_I |     1 |       |     3   (0)| 00:00:01 |
-------------------------------------------------------------------------------------------
 

Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - access("ID"=42)
 

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          5  consistent gets
          0  physical reads
          0  redo size
        531  bytes sent via SQL*Net to client
        395  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

The cost of the index has now jumped up by 2 from 1 to 3 with the overall costs up from 2 to 4, even though the index is practically the same size. As the Blevel is now 2, the CBO now includes the cost of the Blevel in its calculations. The cost associated with accessing the root block and a branch block all now count. Although overall the costs are still low, this increase actually represents a 100% increase in the use of the index for an equality search.
 
This increase can be significant if the index needs to be accessed multiple times. Let’s now re-run the join query:
 

 
SQL> select * from ziggy z, major_tom m where m.id = z.id and z.code in (42, 4242);
 
68 rows selected.
 

Execution Plan
----------------------------------------------------------
Plan hash value: 1928189744
 
--------------------------------------------------------------------------------
| Id  | Operation          | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           |   200 |  9400 |  1485   (2)| 00:00:18 |
|*  1 |  HASH JOIN         |           |   200 |  9400 |  1485   (2)| 00:00:18 |
|*  2 |   TABLE ACCESS FULL| ZIGGY     |   200 |  4800 |  1105   (2)| 00:00:14 |
|   3 |   TABLE ACCESS FULL| MAJOR_TOM |   336K|  7558K|   378   (1)| 00:00:05 |
--------------------------------------------------------------------------------
 

Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - access("M"."ID"="Z"."ID")
   2 - filter("Z"."CODE"=42 OR "Z"."CODE"=4242)
 

Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
       5366  consistent gets
       4024  physical reads
          0  redo size
       1964  bytes sent via SQL*Net to client
        395  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
         68  rows processed

Although it’s retrieving exactly the same data, the execution plan has changed significantly. The Nested Loop join is no longer as appealing to the CBO as the cost of accessing the inner table via the index has now effectively doubled. The CBO has now gone for a Hash Join, accessing both tables via Full Tables Scans. The overall cost of the Nested Loop plan was 1372, but this has increased to over 1485, the cost of the now so-called more efficient Hash Join plan.
 
If you have indexes that are on the boundary of increasing from a blevel=1 to a blevel=2, execution plans can potentially change significantly based on the differences in how indexes get costed. This can be especially troublesome when such indexes get regularly rebuilt as they may toggle between Blevel 1 and 2 based on associated space savings and can sometimes result in unpredictable performance depending on when new statistics get collected.
 
I liken it to a child growing up from being a young kid to a teenager. It may only be a difference of a year or so but boy, can the differences be dramatic !!