Richard Foote's Oracle Blog

Descending Indexes Solution (Yellow Submarine) September 9, 2011

Answers to the quiz on Descending Indexes and hopefully some useful dangers and tips on using them.

The answer to the first question is Yes, a “normal” Ascending Index can be used by the CBO to retrieve data in descending order and hence possibly avoid a sort. The reason being that leaf blocks in the index structure have effectively two pointers, one that points to the next leaf block in the index structure (except for the very last leaf block) and one that points to the previous block (except for the first leaf block). So the data in an index can be retrieved in either order.

The answer to the second question is Yes as well, a Descending Index can also be used to also retrieve data in either logical order as again all the leaf blocks have the two set of pointers.

That being the case, if an index has just the one column value, does it therefore make any difference which index one creates, ascending or descending ?

Hence my last question. The answer is maybe, as there are a number of fundamental differences in how each type of index is implemented.

Naturally, a little demo to illustrate 🙂

Let’s begin by creating a simple little table and a normal B-Tree index on an ID column, which has monotonically increasing values:

SQL> create table bowie (id number, name varchar2(30));

Table created.

SQL> create index bowie_id_i on bowie(id);

Index created.

SQL> insert into bowie select rownum, 'DAVID BOWIE' from dual connect by level <= 100000;

100000 rows created.

SQL> commit;

Commit complete.

Note the index is indeed a “Normal” B-Tree index and because the indexed values monotonically increase, all index leaf block splits are 90-10 splits resulting a perfectly compact, 100% utilised index structure:

SQL> select index_type from dba_indexes where index_name = 'BOWIE_ID_I';

INDEX_TYPE
---------------------------
NORMAL

SQL> analyze index bowie_id_i validate structure;

Index analyzed.

SQL> select lf_rows, lf_blks, pct_used from index_stats;

   LF_ROWS    LF_BLKS   PCT_USED
---------- ---------- ----------
    100000        199        100

Let’s now run a query to ensure the index is indeed used and that the sort can indeed be avoided. Note I’ve not actually collected any CBO statistics at this stage but I’m definitely using the CBO:

SQL> alter system set optimizer_mode='ALL_ROWS' scope=both;

System altered.

SQL> select * from bowie where id between 42 and 84 order by id desc;

43 rows selected.
Execution Plan
----------------------------------------------------------
Plan hash value: 2771731789

-------------------------------------------------------------------------------------------
| Id  | Operation                    | Name       | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |            |    43 |  1290 |     1   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | BOWIE      |    43 |  1290 |     1   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN DESCENDING| BOWIE_ID_I |    43 |       |     1   (0)| 00:00:01 |
-------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("ID">=42 AND "ID"<=84)
       filter("ID">=42 AND "ID"<=84)

Note
-----
   - dynamic sampling used for this statement
Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          9  consistent gets
          0  physical reads
          0  redo size
       1092  bytes sent via SQL*Net to client
        418  bytes received via SQL*Net from client
          4  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
         43  rows processed

So the execution plan clearly shows the use of the index via an index range scan descending and that there are indeed no sort operations performed. There were no statistics gathered, so the CBO performed some dynamic sampling to determine a taste for the data.

Let’s now change the optimizer_mode to CHOOSE, a common default setting (especially pre 11g, this example is run on a 10.2.0.4 database) and re-run the query:

SQL> select * from bowie where id between 42 and 84 order by id desc;

43 rows selected.
Execution Plan
----------------------------------------------------------
Plan hash value: 3062669298

---------------------------------------------------
| Id  | Operation                    | Name       |
---------------------------------------------------
|   0 | SELECT STATEMENT             |            |
|   1 |  SORT ORDER BY               |            |
|   2 |   TABLE ACCESS BY INDEX ROWID| BOWIE      |
|*  3 |    INDEX RANGE SCAN          | BOWIE_ID_I |
---------------------------------------------------

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

   3 - access("ID">=42 AND "ID"<=84)

Note
-----
   - rule based optimizer used (consider using cbo)
Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          3  consistent gets
          0  physical reads
          0  redo size
       1092  bytes sent via SQL*Net to client
        418  bytes received via SQL*Net from client
          4  SQL*Net roundtrips to/from client
          1  sorts (memory)
          0  sorts (disk)
         43  rows processed

No statistics on the table now means the Rule Based Optimizer kicks in and although a sort operation is performed (as there’s no descending scan), Oracle at least used the index.

OK, let’s now run the exact same sequence of events, but this time using a Descending Index.

SQL> drop table bowie;

Table dropped.

SQL> create table bowie (id number, name varchar2(30));

Table created.

SQL> create index bowie_id_i on bowie(id desc);

Index created.

SQL> insert into bowie select rownum, 'DAVID BOWIE' from dual connect by level <= 100000;

100000 rows created.

SQL> commit;

Commit complete.

So it’s the exact same table and set of data. Let’s now look at the type of index created:

SQL> select index_type from dba_indexes where index_name = 'BOWIE_ID_I';

INDEX_TYPE
---------------------------
FUNCTION-BASED NORMAL

OK, Difference Number 1. A Descending Index is no ordinary “Normal” index, but is implemented as a  “Function-Based Normal” index instead. This means there’ll be a new hidden virtual column created behind the scenes and that the Rule Based Optimizer is going to have an issue here as it can’t cope with Function-based Indexes.

Let’s look at some Index_Stats:

SQL> analyze index bowie_id_i validate structure;

Index analyzed.
SQL> select lf_rows, lf_blks, pct_used from index_stats;

   LF_ROWS    LF_BLKS   PCT_USED
---------- ---------- ----------
    100000        426         50

Difference Number 2: This index is approximately double the size of the previous index and only half as efficient with its storage. Why ? Because as the data is now inserted in reverse logical order, the last index leaf block no longer receives the largest current index value and so 90-10 splits are not performed. As only 50-50 splits are performed, the index structure is left with 50% empty blocks which can not be reused. Unfortunately, a possible candidate for periodic index rebuilds …

Let’s now re-run the query using the CBO:

SQL> select * from bowie where id between 42 and 84 order by id desc;

43 rows selected.
Execution Plan
----------------------------------------------------------
Plan hash value: 3472402785

------------------------------------------------------------------------------------------
| Id  | Operation                   | Name       | Rows  | Bytes | Cost (%CPU)|Time     |
------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |            |   208 |  6240 |     1   (0)|00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| BOWIE      |   208 |  6240 |     1   (0)|00:00:01 |
|*  2 |   INDEX RANGE SCAN          | BOWIE_ID_I |     1 |       |     1   (0)|00:00:01 |
------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access(SYS_OP_DESCEND("ID")>=HEXTORAW('3EAAFF')  AND
              SYS_OP_DESCEND("ID")<=HEXTORAW('3ED4FF') )
       filter(SYS_OP_UNDESCEND(SYS_OP_DESCEND("ID"))>=42 AND
              SYS_OP_UNDESCEND(SYS_OP_DESCEND("ID"))<=84)

Note
-----
   - dynamic sampling used for this statement
Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          9  consistent gets
          0  physical reads
          0  redo size
       1092  bytes sent via SQL*Net to client
        418  bytes received via SQL*Net from client
          4  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
         43  rows processed

Difference Number 3. Although the same execution plan with the same number of consistent gets is performed, the cardinality estimates are not as accurate and the SYS_OP_DESCEND and SYS_OP_UNDESCEND functions are used as access/filter conditions as they’re the functions implemented in the function-based index.

If we run the same query using the Rule Based Optimizer (remember, we “forgot” to collect statistics on the table):

SQL> alter system set optimizer_mode='CHOOSE' scope=both;

System altered.

SQL> select * from bowie where id between 42 and 84 order by id desc;

43 rows selected.
Execution Plan
----------------------------------------------------------
Plan hash value: 2027917145

------------------------------------
| Id  | Operation          | Name  |
------------------------------------
|   0 | SELECT STATEMENT   |       |
|   1 |  SORT ORDER BY     |       |
|*  2 |   TABLE ACCESS FULL| BOWIE |
------------------------------------

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

   2 - filter("ID"<=84 AND "ID">=42)

Note
-----
   - rule based optimizer used (consider using cbo)
Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
        309  consistent gets
          0  physical reads
          0  redo size
       1092  bytes sent via SQL*Net to client
        418  bytes received via SQL*Net from client
          4  SQL*Net roundtrips to/from client
          1  sorts (memory)
          0  sorts (disk)
         43  rows processed

Difference Number 4. The Rule based Optimizer does not support Function-Based Indexes and so the index is now completely ignored. Oracle has no choice here but to perform the much more expensive Full Table Scan, when previously the ascending index was used.

A Descending Index can potentially be useful in a concatenated, multi-column index, in which the columns could be ordered in a combination of ascending/descending order that could in turn return the data in a required specific order, thereby negating the need for a potentially expensive sort operation.

However, with a single column index, one would need to question the need for making such an index descending …

Having fun 🙂 Enjoy your weekend !!

Descending Indexes Quiz (Up On The Ladder) September 8, 2011

OK, you won’t find the answer to these questions on my blog, so using my search facility won’t be of any help 🙂

Actually, it’s quite an easy one this, honest 😉

If you have a query such as:

SELECT * FROM bowie WHERE id BETWEEN 42 and 84 ORDER BY id DESC;

1) Can a default B-Tree index on the single ID column that stores data in Ascending order be used by the CBO to retrieve the data automatically in the required Descending order, without the need for a sort operation ?

2) Can a Descending B-Tree index on the ID column be used by the CBO to retrieve the data automatically in Ascending order, without the need for a sort operation ?

3) Depending on your answers above, what are the differences (if any) between the implementation of an Ascending and Descending index ?

Enjoy !!