jump to navigation

Descending Indexes Solution (Yellow Submarine) September 9, 2011

Posted by Richard Foote in Descending Indexes, Oracle Indexes, Quiz.
trackback

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 !!

About these ads

Comments»

1. Marcus Mönnig - September 9, 2011

Did I get this right? The type of the index created depends on the currently active optimizer_mode? (Or was this a difference due to different Oracle versions?) I didn’t know that DDL is influenced by the optimizer mode.

Richard Foote - September 10, 2011

Hi Marcus

No, the type of index doesn’t depending on the optimizer mode, it depends on whether the index is asc or desc.

However, if the index is desc and therefore a function-based index, then it can not be considered or used by the RBO.

2. Brian Tkatch - September 9, 2011

Good exlanation, thanx!

Richard Foote - September 10, 2011

Hi Brian

No worries, I’ll mention it in Chaper 4 of the book which covers B-Tree index options ;)

Jim Dickson - April 27, 2012

“No worries, I’ll mention it in Chaper 4 of the book …”

I didn’t realise you were writing a book – when can we expect it to be released, or have I missed something?

3. Yogesh Tiwari - September 9, 2011

We didnt calculate statistics, any particular reason? Also, are we concluding that desc index would have bigger size, and might need constant monitoring, as it may appear to be rebuild candidate frequently?

Richard Foote - September 10, 2011

Hi Yogesh

Yes, I deliberately didn’t collect statistics because I wanted to show what the impact would be if one “accidentally” used the RBO with the optimizer mode set to CHOOSE. If I had collected stats, then the CBO would have been used regardless, unless I specifically set the mode to use the RBO, which would have removed the “accidental” nature of what could have happended with a desc index.

4. Yogesh Tiwari - September 9, 2011

By the way, I really enjoy these quizzes. I may not post, to make my presence felt.

I like Charles quizzes too, though, I dont really post. ;)

Discussion on both these blogs are really enriching.

Thanks, keep them coming.

Richard Foote - September 10, 2011

Hi Yogesh

Thank-you for the nice comments. I think having a little quiz is quite a nice technique to get people thinking about a topic first, before I go in and discuss it. It hopefully makes people think about things a little differently, especially some of the assumptions we all make.

I’ll try and keep them coming :)

5. Henry Poras - September 10, 2011

Richard,

Thanks for the quizzes. We were discussing this at work and it seems that if you have an ascending index with and ORDER BY DESC, you won’t do a full sort but will still need a kind of “MiniSort”. Because the leaf blocks have two pointers, Oracle can read the blocks in reverse order. However, we assumed that the block scan itself is still done in the same direction (i.e. top to bottom) in both cases. This would require a touch more CPU for the ORDER BY DESC case to reverse the data retrieved from the block before moving on. Of course much cheaper than a real sort where you first get the entire result set.

I’m wondering if this would be noticeable either with a very large index or lots of loops. If I have a chance I’ll try testing next week.

Richard Foote - September 10, 2011

Hi Henry

I’d be interested in your test results ;)

Jonathan Lewis - September 10, 2011

Henry,

Oracle doesn’t scan index leaf blocks, it walks through the row directory in order and, because of the way it updates the row directory as it inserts rows, this walk through the row directory makes the index entries appear in order. I would be very surprised if Oracle did any sorting to get the data in “the opposite” order, I would expect it simply to switch to walking the row directory in reverse order.

Richard Foote - September 14, 2011

Hi Jonathan

Yes, I agree. It would be odd if having created the index range scan descending code, Oracle didn’t perform an efficient and somewhat obvious scan of the leaf block.

6. Randolf Geist - September 10, 2011

It’s an interesting little detail that the difference in the cardinality estimates comes from the fact that the descending index is not considered for dynamic sampling whereas the normal index does, hence the improved cardinality estimate.

The result of the dynamic sampling on the table itself is the same in both cases and is a bit misleading because of the default sample level and the nature of the example chosen.

The reason for not using dynamic sampling on the descending index is also interesting: The dynamic sampling code uses the original predicates (between 42 and 84) and not the actual ones that are then applied to the descending index (the SYS_OP… stuff), so it obviously doesn’t consider the index as candidate for sampling.

May be something that could be improved resp. made more consistent in future releases.

Randolf

Richard Foote - September 10, 2011

Hi Randolf

The number of times I’ve typed your name as Gandolf, only to go back and correct myself !!

Good point, I made the point of the differences in cardinality estimates because in some scenarios, it can make a significant difference to the overall exectuion plan.

It’s tricky when Oracle makes a dymanic change (eg. convert the index to specifically use a function) but not make the same change when processing the query itself (eg. the predicate remains the same). Dynamic sampling becomes non-viable (on the index), so I agree a nice enhancement would be to more consistent (one way or the other) in this regard.

7. Jonathan Lewis - September 10, 2011

Richard,
I think you’ve said this in one of your other posts on descending indexes, but you forgot to mention here that the descending column is a one’s-bit complement of the original value, stored in ascending order, with a 0xff appended.

This means the index will be one byte larger for each row for each descending column – and that’s a pretty good reason for not making every column in an index descending. (Plus there are cases – possibly fixed in 11.2 – where descending indexes won’t be used for plans which would be considered for ascending indexes.)

Richard Foote - September 14, 2011

Hi Jonathan

Yes, that extra byte when multiplied by many index entries all adds up and can make a difference. Hopefully this blog piece will make people think a tad before just assigning or creating unnecessary descending indexes.

8. Connor - September 12, 2011

Plus little other things might pop up when you least expect them:

SQL> drop table T purge;

Table dropped.

SQL> create table T as
2 select rownum x from dual
3 connect by level create index IX on T ( x );

Index created.

SQL> alter table T enable row movement;

Table altered.

SQL> alter table T shrink space;

Table altered.

SQL> drop index IX;

Index dropped.

SQL> create index IX on T ( x desc);

Index created.

SQL> alter table T shrink space;
alter table T shrink space
*
ERROR at line 1:
ORA-10631: SHRINK clause should not be specified for this object

zhwsh - September 13, 2011

I don’t know why if you create fbi index,you ‘ll run
“alter table T shrink space”;

zhwsh - September 13, 2011

occur:
ERROR at line 1:
ORA-10631: SHRINK clause should not be specified for this object

Richard Foote - September 14, 2011

Thanks Connor, that’s one I didn’t pick up :)

9. Richard Foote - September 14, 2011

Hi Zhwsh

It’s an undocumented “feature” ;)

10. Richard Foote - May 7, 2012

@Jim

No, despite friendly pressures and various offers, I have no plans to write a book :)

11. alin - October 25, 2012

Hi Richard.

you said:
“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. ”

can please explain what you mean by 90-10 and 50-50 splits. I did not get what happens when you insert in the index in reversed order.

Thanks

Richard Foote - November 9, 2012

Hi Alin

Generally when an index leaf block fills, Oracle will logically add a new leaf block into the index structure, placing 50% of the data from the full block into this new block and so leaving 50% behind. This is known as a 50-50 block split as it leave both blocks 50% full/empty.

However, when the newly inserted index entry is the maximum entry in the index and the end-most leaf block is full, then Oracle simply allocates a new end-most leaf block and inserts this new entry into this empty block, leaving all the data from the full block alone. This is known as a 90-10 block split and generally occurs when the index values are monotontically increasing.

Once you make an index a reverse index, this inserting the maximum index entry into the end-most leaf block no longer occurs (as the index values are now basically randomised) and so the majority of block splits are now 50-50.

alin - November 9, 2012

Thanks for your answer, Richard. I must say that this is the best Oracle blog I’ve read.

12. Richard Foote - November 9, 2012

Thanks Alin, that’s very kind of you to say so.

13. Ascending או Descending אינדקס, זה באמת משנה .. ? | הבלוג של רם קדם - December 15, 2012

[...] נוסף אודות ה Descending Index מומלץ בחום להכנס לפוסט הבא אשר נכתב ע"י Richard [...]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,895 other followers

%d bloggers like this: