Skip Scan

A recent question on OTN asked how you could model a case where Oracle had the choice between a “perfect” index for a range scan and an index that could be used for an index skip scan and choose the latter path even though it was clearly (to the human eye) the less sensible choice. There have been a number of wierd and wonderful anomalies with the index skip scan and bad choice over the years and this particular case is just one of many oddities I have seen in the past – so I didn’t think it would be hard to model one (in fact, I thought I already had at least two examples somewhere in my library – but I couldn’t find them).

Take a data set with two columns, call them id1 and id2, and create indexes on (id1), and (id2, id1). Generate the id1 column as a wide range of cyclic values, generate the id2 set with a small number of repetitive values so that a large number of physically adjacent rows hold the same id2 value. The clustering_factor on the (id1) index will be very large, the clustering_factor on the (id2, id1) index will be relatively small because it will be controlled largely by the repetitive id2 value. Here’s the data set:

rem
rem     Script:         skip_scan_choice_2.sql
rem     Author:         Jonathan Lewis
rem     Dated:          Oct 2012
rem

create table t1
as
with generator as (
        select  --+ materialize
                rownum id 
        from dual 
        connect by 
                level <= 1e4 -- > comment to avoid WordPress format issue
)
select
        rownum - 1                      id,
        mod(rownum - 1,1e4)             id1,
        trunc((rownum - 1)/1e4)         id2,
        lpad(rownum,10,'0')             small_vc
from
        generator       v1,
        generator       v2
where
        rownum <= 1e6 -- > comment to avoid WordPress format issue
;

begin
        dbms_stats.gather_table_stats(
                ownname          => user,
                tabname          =>'T1',
                method_opt       => 'for all columns size 1'
        );
end;
/

create index t1_i1 on t1(id1);
create index t1_i2 on t1(id2,id1);

If you examine the code you will see that id2 repeats each value 10,000 times, and as it does so id1 ranges from 0 to 9,999; this means the index on (id2, id1) will essentially be listing the data in exactly the order it appears in the table, while each entry in the index on (id1) will either be jumping 10,000 rows down the table from the previous one, except of the cases where it jumps from the end of the table to the start of the table. As a quick sanity check on the indexes I’ve created here are the critical index statistics – it can be quite easy to fool yourself that you’ve done what you wanted to when the indexes prove otherwise (for reference, there are 3,872 blocks in the table):

select
        index_name, num_rows, distinct_keys, leaf_blocks, blevel, clustering_factor
from
        user_indexes
where
        table_name = 'T1'
order by
        index_name
;

INDEX_NAME             NUM_ROWS DISTINCT_KEYS LEAF_BLOCKS     BLEVEL CLUSTERING_FACTOR
-------------------- ---------- ------------- ----------- ---------- -----------------
T1_I1                   1000000         10000        2090          2           1000000
T1_I2                   1000000       1000000        2504          2              3872

Now all we have to do is run a suitable query – so here’s a simple query that does the “wrong” thing (in 10.2.0.5). I’ve shown the query (unhinted, then hinted to use the “correct” index) with the output from autotrace, but the plan that appears from autotrace is the same plan that actually gets executed at run-time. I’ve disabled CPU costing to reduce the risk of variation in results, but I see the same effects when any reasonable values for system statistics are used. The text is a straight cut-n-paste from an SQL*Plus session with a little edit to deal with the mess that WordPress makes with angle brackets in the output.

SQL> set autotrace traceonly explain
SQL> select * from t1
  2  where id1 between 501 and 502
  3  ;

Execution Plan
----------------------------------------------------------
Plan hash value: 3617828059

---------------------------------------------------------------------
| Id  | Operation                   | Name  | Rows  | Bytes | Cost  |
---------------------------------------------------------------------
|   0 | SELECT STATEMENT            |       |   299 |  6578 |   290 |
|   1 |  TABLE ACCESS BY INDEX ROWID| T1    |   299 |  6578 |   290 |
|*  2 |   INDEX SKIP SCAN           | T1_I2 |   285 |       |   288 |
---------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("ID1">=501 AND "ID1"<=502) -- added '>' to avoid WordPress format issue
       filter("ID1">=501 AND "ID1"<=502) -- added '>' to avoid WordPress format issue

Note
-----
    - cpu costing is off (consider enabling it)

SQL> select /*+ index_rs_asc(t1(id1)) */ * from t1
  2  where id1 between 501 and 502
  3  ;

Execution Plan
----------------------------------------------------------
Plan hash value: 1429545322

---------------------------------------------------------------------
| Id  | Operation                   | Name  | Rows  | Bytes | Cost  |
---------------------------------------------------------------------
|   0 | SELECT STATEMENT            |       |   299 |  6578 |   303 |
|   1 |  TABLE ACCESS BY INDEX ROWID| T1    |   299 |  6578 |   303 |
|*  2 |   INDEX RANGE SCAN          | T1_I1 |   300 |       |     3 |
---------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("ID1">=501 AND "ID1"<=502)

Note
-----
    - cpu costing is off (consider enabling it)

I have to say I was expecting to have to play around a little bit with unpeeked bind variables, or scalar subqueries in the where clause to get Oracle to pick the wrong index, but in the latest version of 10.2.0.5 this wasn’t necessary. (I chose this version, by the way, because the question on OTN related to 10gR2.)

If you think carefully about the arithmetic of the skip scan execution plan, you’ll notice a couple of oddities. The cost of the index probe is 288, but the optimizer should know from the column statistics that there are 100 distinct values for id2 and might, therefore, calculate the cost as 100 (plus a bit), because it will have to find 100 leaf blocks. [See Footnote for newer versions of Oracle]

The second oddity is that the cost of finding the estimated 299 rows in the table seems to have been calculated by applying the table selectivity (derived from the predicate id1 between 501 and 502) to the clustering_factor of the (id2, id1) index – which isn’t a good idea given the extreme difference between the two available clustering factors. Without looking at the (id1) clustering_factor, perhaps Oracle should have taken the cost of (id2 = constant and id1 between 501 and 502) and multiplied the result by the number of distinct values of id2.

If you’re wondering why the estimated cardinality is (nearly) 300, by the way, this is simply the standard selectivitity calculation: (range required by predicate)/(total range of column) + 1/num_distinct + 1/num_distinct that you get from a between clause. Of course, once you’ve got a model – especially a model that seems to do the wrong thing – you might as well run it on as many sensible versions of Oracle as possible to see how things change over time. My example didn’t change on 11.1.0.7, but on 11.2.0.3 the cost of the skip scan increased slightly, just enough to make the “expected” range scan appear. I didn’t bother to pursue this in detail, butI did have a couple of other scenarios to play around with that I might write up some time soon.

I’ll leave you with one interesting thought. The skip scan is, in effect, a query that probes the index for every possible value of the leading edge – so what to do you think the costs will show if I write a query that explicity runs my range scan on id1 for every value that is currently in id2. (Logically it’s not the same query, of course, but coincidentally it is temporarily equivalent.)

SQL> set autotrace traceonly explain
SQL>
SQL> select
  2          *
  3  from t1
  4  where
  5          id2 in (
  6                   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
  7                  10,11,12,13,14,15,16,17,18,19,
  8                  20,21,22,23,24,25,26,27,28,29,
  9                  30,31,32,33,34,35,36,37,38,39,
 10                  40,41,42,43,44,45,46,47,48,49,
 11                  50,51,52,53,54,55,56,57,58,59,
 12                  60,61,62,63,64,65,66,67,68,69,
 13                  70,71,72,73,74,75,76,77,78,79,
 14                  80,81,82,83,84,85,86,87,88,89,
 15                  90,91,92,93,94,95,96,97,98,99
 16          )
 17  and     id1 between 501 and 502
 18  ;

Execution Plan
----------------------------------------------------------
Plan hash value: 2879882323

--------------------------------------------------------------------------------------
| Id  | Operation                    | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |       |   296 |  6512 |   102   (0)| 00:00:02 |
|   1 |  INLIST ITERATOR             |       |       |       |            |          |
|   2 |   TABLE ACCESS BY INDEX ROWID| T1    |   296 |  6512 |   102   (0)| 00:00:02 |
|*  3 |    INDEX RANGE SCAN          | T1_I2 |   297 |       |   100   (0)| 00:00:02 |
--------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access(("ID2"=0 OR "ID2"=1 OR "ID2"=2 OR "ID2"=3 OR "ID2"=4 OR "ID2"=5
              OR "ID2"=6 OR "ID2"=7 OR "ID2"=8 OR "ID2"=9 OR "ID2"=10 OR "ID2"=11 OR
              "ID2"=12 OR "ID2"=13 OR "ID2"=14 OR "ID2"=15 OR "ID2"=16 OR "ID2"=17 OR
              "ID2"=18 OR "ID2"=19 OR "ID2"=20 OR "ID2"=21 OR "ID2"=22 OR "ID2"=23 OR
              "ID2"=24 OR "ID2"=25 OR "ID2"=26 OR "ID2"=27 OR "ID2"=28 OR "ID2"=29 OR
              "ID2"=30 OR "ID2"=31 OR "ID2"=32 OR "ID2"=33 OR "ID2"=34 OR "ID2"=35 OR
              "ID2"=36 OR "ID2"=37 OR "ID2"=38 OR "ID2"=39 OR "ID2"=40 OR "ID2"=41 OR
              "ID2"=42 OR "ID2"=43 OR "ID2"=44 OR "ID2"=45 OR "ID2"=46 OR "ID2"=47 OR
              "ID2"=48 OR "ID2"=49 OR "ID2"=50 OR "ID2"=51 OR "ID2"=52 OR "ID2"=53 OR
              "ID2"=54 OR "ID2"=55 OR "ID2"=56 OR "ID2"=57 OR "ID2"=58 OR "ID2"=59 OR
              "ID2"=60 OR "ID2"=61 OR "ID2"=62 OR "ID2"=63 OR "ID2"=64 OR "ID2"=65 OR
              "ID2"=66 OR "ID2"=67 OR "ID2"=68 OR "ID2"=69 OR "ID2"=70 OR "ID2"=71 OR
              "ID2"=72 OR "ID2"=73 OR "ID2"=74 OR "ID2"=75 OR "ID2"=76 OR "ID2"=77 OR
              "ID2"=78 OR "ID2"=79 OR "ID2"=80 OR "ID2"=81 OR "ID2"=82 OR "ID2"=83 OR
              "ID2"=84 OR "ID2"=85 OR "ID2"=86 OR "ID2"=87 OR "ID2"=88 OR "ID2"=89 OR
              "ID2"=90 OR "ID2"=91 OR "ID2"=92 OR "ID2"=93 OR "ID2"=94 OR "ID2"=95 OR
              "ID2"=96 OR "ID2"=97 OR "ID2"=98 OR "ID2"=99) AND "ID1">=501 AND "ID1"<=502)

Unfortunately the costing isn’t consistent with the skip scan costing.

Footnote:

I haven’t looked at the 10053 trace files for these plans – they take a lot of time to read and don’t often help very much, so it’s the sort of thing I do only if I think it’s necessary to solve an important production problem or (if I’m doing some R&D) it looks like it might be entertaining.

Update (May 2018)

I’ve just been looking at skip scans, and come back to this older article. Re-running the basic test on 12.2.0.1 I found that the cost of the plan using the index skip scan had dropped to 104 (of which 102 was the cost of the skip scan itself ); working backwards from there, this change appeared had appeared by 11.2.0.4

Update (Feb 2021)

Thanks to a twitter conversation on skip scans I’ve come back to this note. Nothing has changed since the May 2018 update, but I thought I’d include the basic plans from 19c (19.3.0.0). In the following output I’ve enabled CPU costing with my “standard” set of values for system stats. Apart from that I’ve made no changes to the code.

begin
        dbms_stats.set_system_stats('MBRC',16);
        dbms_stats.set_system_stats('MREADTIM',10);
        dbms_stats.set_system_stats('SREADTIM',5);
        dbms_stats.set_system_stats('CPUSPEED',500);
exception
        when others then null;
end;
/

============
Default plan
============
---------------------------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |   300 |  6900 |   104   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |   300 |  6900 |   104   (0)| 00:00:01 |
|*  2 |   INDEX SKIP SCAN                   | T1_I2 |   300 |       |   102   (0)| 00:00:01 |
---------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("ID1">=501 AND "ID1"<=502)
       filter("ID1"<=502 AND "ID1">=501)

=================
Hinted range scan
=================
---------------------------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |   300 |  6900 |   305   (1)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |   300 |  6900 |   305   (1)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN                  | T1_I1 |   300 |       |     3   (0)| 00:00:01 |
---------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("ID1">=501 AND "ID1"<=502)