The golden rule of indexing

This is something that I have to remind people of frequently on the OTN so I thought it was worthy of a proper blog post where I can properly demonstrate the point.
So here is this very simple but very important rule:

When you have multiple columns in your index, you can access using the column in the index so long as you use equality predicates on all prior columns in the index

An access predicate is one that can be used to reduce the amount we read from an index, the alternative is a filter predicate which reduces the amount we return from our read. Think how we access a table with an index scan – we only read part of the table, but we filter a table during a full table scan – we read the entire thing (we just return less rows). It’s easier to demonstrate with an example, so let’s make a big table with a few columns.
create table golden_indexes as
with gen as (select /*+materialize*/* from dual connect by rownum <=10000)
select rownum pk_col, sysdate-mod(rownum,365) date_col, trunc(dbms_random.value(0,100)) col_100, dbms_random.string('x',100) padding_col
from   gen
cross join gen 
where rownum <=100000000
/

select count(*) from golden_indexes;

  COUNT(*)
----------
 100000000
 
create index golden_indexes_idx1 on golden_indexes (date_col,col_100);
create index golden_indexes_idx2 on golden_indexes (col_100,date_col);
We have 100,000,000 rows in our table with 100 different values of some number and 365 different values of some date.
We now have a query
select date_col, padding_col 
from   golden_indexes
where  col_100  = 50
and    date_col >= trunc(sysdate)-10 
and    date_col <  trunc(sysdate)-9;
Because we know our data, we know that this query is going to find 100,000,000 / 100 / 365 rows = 2700 rows. This is probably appropriate for an index use rather than a full tablescan – we don’t want to read 100 million rows.
Let’s apply our golden rule with this query to our two indexes, first the one leading date_col:
The first column is date_col, we can use our filter on date_col as an access predicate (there’s no prior columns in the index) so we can use it to provide an index selectivity of 1/365. We can’t apply our filter on col_100 as an access predicate because the filter on date_col is not an equality predicate – it is a range predicate.
Of course, we can still use the col_100 predicate as a filter predicate on the index, it just means we can’t use it to aim our reads against the index. This gives us an index selectivity of 1/365 and table selectivity of 1/365*1/100 = 1/36500
And now for the second index, we can use our col_100 predicate to provide an access predicate giving us an index selectivity of 1/100, we can then apply our date_col predicate as an access predicate as well as the prior filter was equality, this gives us a total index selectivity of 1/100 * 1/365 = 1/36500. No further filters exist so our table selectivity is also 1/36500 (as before)
To demonstrate, we can see the number of leaf blocks in the indexes by querying their stats (they’ll be accurate as we’ve only just built it, real life index stats for you will probably be more inaccurate)
select index_name, blevel, leaf_blocks from user_indexes where table_name = 'GOLDEN_INDEXES' order by 1;


INDEX_NAME                         BLEVEL LEAF_BLOCKS
------------------------------ ---------- -----------
GOLDEN_INDEXES_IDX1                     3      306612
GOLDEN_INDEXES_IDX2                     3      306605
We should expect to read 306612 / 365 = 840 blocks in our index range scan using the first index and read 306605 / 36500 = 9 blocks in our range scan of our second index. All index range scans start with traversing the branch blocks of an index so we should expect to read a block per level of the index, both are 3 in this case.
We can demonstrate this by using row source execution statistics (discussed in https://ctandrewsayer.wordpress.com/2017/03/21/4-easy-lessons-to-enhance-your-performance-diagnostics/)
set serverout off
select /*+index_rs_asc(gi golden_indexes_idx1) NO_INDEX_SS(gi golden_indexes_idx1) gather_plan_statistics*/
       count(*)
from   golden_indexes gi
where  col_100  = 50
and    date_col >= trunc(sysdate)-10 
and    date_col <  trunc(sysdate)-9;
select * from table(dbms_xplan.display_cursor(format=>'allstats typical last'));

Plan hash value: 2147962759

------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name                | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time   | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |                     |      1 |        |       |  1691 (100)|          |      1 |00:00:00.05 |     844 |
|   1 |  SORT AGGREGATE    |                     |      1 |      1 |    11 |            |          |      1 |00:00:00.05 |     844 |
|*  2 |   FILTER           |                     |      1 |        |       |            |          |   2710 |00:00:00.06 |     844 |
|*  3 |    INDEX RANGE SCAN| GOLDEN_INDEXES_IDX1 |      1 |     55 |   605 |  1691   (1)| 00:00:01 |   2710 |00:00:00.05 |     844 |
------------------------------------------------------------------------------------------------------------------------------------

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

   2 - filter(TRUNC(SYSDATE@!)-9>TRUNC(SYSDATE@!)-10)
   3 - access("DATE_COL">=TRUNC(SYSDATE@!)-10 AND "COL_100"=50 AND "DATE_COL"<TRUNC(SYSDATE@!)-9)
       filter("COL_100"=50)

      
select /*+index(gi golden_indexes_idx2) gather_plan_statistics*/
       count(*)
from   golden_indexes gi
where  col_100  = 50
and    date_col >= trunc(sysdate)-10 
and    date_col <  trunc(sysdate)-9;
select * from table(dbms_xplan.display_cursor(format=>'allstats typical last'));

Plan hash value: 1778390985

------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name                | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time   | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |                     |      1 |        |       |    20 (100)|          |      1 |00:00:00.01 |      12 |
|   1 |  SORT AGGREGATE    |                     |      1 |      1 |    11 |            |          |      1 |00:00:00.01 |      12 |
|*  2 |   FILTER           |                     |      1 |        |       |            |          |   2710 |00:00:00.01 |      12 |
|*  3 |    INDEX RANGE SCAN| GOLDEN_INDEXES_IDX2 |      1 |     55 |   605 |    20   (0)| 00:00:01 |   2710 |00:00:00.01 |      12 |
------------------------------------------------------------------------------------------------------------------------------------

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

   2 - filter(TRUNC(SYSDATE@!)-9>TRUNC(SYSDATE@!)-10)
   3 - access("COL_100"=50 AND "DATE_COL">=TRUNC(SYSDATE@!)-10 AND "DATE_COL"<TRUNC(SYSDATE@!)-9)

The plan helps us out, it tells us what it is using as an access predicate and what gets used as a filter predicate in the predicates section. Unfortunately for us, it includes filter predicates in the access predicates (IMO this is a mistake).

The row source stats demonstrate that the work done by range scan is much less when the columns are ordered with the columns used in equality predicates first. See how our buffers on the index range scan lines are almost exactly what I mentioned before. This is fairly conclusive that Oracle was able to limit what it read from the index using the predicate only when prior predicates are equalities.

You’ll notice I’ve used a no_index_ss hint in the first query, this was because otherwise the CBO decided it was a good idea to skip scan the index because there are few distinct values in our range it decided that it could just skip around them (which is sensible but probably not realistic where you have dates that have time elements that vary). I’ll make a note of this and hopefully give it the attention it deserves in another post.
Something else that will have a large influence on our cost in using the two indexes here is the clustering factor – we are going to 2710 rows (although the optimizer has only predicted 55) it would certainly be better if these rows were clustered in few blocks rather than spread to 2710 different blocks. Because my data was generated to have the interesting data all over the table, the clustering factors of both indexes were huge. I didn’t share these stats as they would certainly not be representative of your real data, my tables took hours to generate and index on my little Surface Pro and I didn’t have time to make it more realistic – another time (or homework for the reader)?
The problem with real data is that usually the clustering factor of your indexes leading with a date column (which usually relates in some way to insert date) will have a much lower clustering factor than if it began with your equality predicate column. The reality is that using either index you will visit the same table blocks so both clustering factors should be the same. If you expect to return a large number of rows from an index and you find that the CBO tries to avoid the real best index you may need to play with the clustering factor of the index manually – in this case you would copy the clustering factor from the reverse ordered index, or you would increase the clustering factor manually for the “bad” index (or just not make it!). 12c introduced some new functionality for clustering factor statistics gathering that I haven’t yet played with – maybe Oracle has solved this problem, I will update if I find a nice solution.

Summary

Stick the columns you do range scans on last in the index, filters that get equality predicates should come first. 
Of course, there’s always rare cases when this doesn’t apply. One example, if you wish to support order by queries without a sort then the columns should be in the same order as they appear in your order by clause. 
-Aside
You’ll notice I changed my query to do a count(*) rather than selecting actual columns from the table; this was not just to reduce output. When going between the index and table, Oracle releases it’s pins on the index buffers, this means you’ll see more consistent reads in this situation. When Oracle uses the index access by batch rowid (new for 12.1), Oracle will keep reading from the index until it has a sufficient batch of rowids (I’m not completely clear on the full mechanics) before going to the table, so we only have to release and reget our index lead blocks rarely.
Advertisements