# Index design: discard and sort

Designing an index is not done through “trial and error”. This kind of strategy seems to doom many engineered indexes to imprecision, explosion, and locking issues. Designing a precise index very often tends to be a “kill two birds with one stone” strategy.  In this article I am going to show you how to design a single index with which

Designing an index is not done through “trial and error”. This kind of strategy seems to doom many engineered indexes to imprecision, explosion, and locking issues. Designing a precise index very often tends to be a “kill two birds with one stone” strategy.  In this article I am going to show you how to design a single index with which I intend to cover a where clause predicate on column c1 and avoid a sorting cost of an order by operation on column c2.

## The Quiz

What is the best index you would have come up with to cover the following query?

`select * from t1 where c1 =:a order by c2;`

### A word of caution

An order by operation is problematic when we want to display a large volume of data in a sorted order. Or when a query generates a small number of ordered rows but is executed a huge number of times. Let’s suppose that we are in one of those kinds of situations and we are asked to optimize the above query with a single index.

Results presented in this article have been done on 11.2.0.3.0 with a 32K block size. I have also conducted the same experiment in 11.2.0.3.0 and 12.0.1.0.1 with 8K block size. Although timing and number of generated buffers are not identical I came to approximately the same conclusion about the efficiency of the designed indexes.

To answer this question we need to observe carefully the predicate part which, in this case, is composed of a where clause on the c1 column coupled with an order by operation requested on a different column (c2).

Our main goal here would be, obviously, to help the CBO achieve a sorted result set without the overhead of obeying the requested order by operation.

We all know that rows are inserted in a precise order in an index. This is why the CBO is able to take advantage of these index ordered entries to satisfy the user requested sort.

This is what I am going to illustrate with the following example implemented on 11.2.0.3.0

```create table t1
as select
rownum                   id1,
case
when mod(rownum,1000)= 0
then 42
else 1
end                      id2,
from dual
connect by level <= 1e6;

alter table t1 add constraint t1_pk primary key (id1);

BEGIN
dbms_stats.gather_table_stats
(user
,'t1'
,method_opt       => 'FOR ALL COLUMNS SIZE 1'
,estimate_percent => DBMS_STATS.AUTO_SAMPLE_SIZE
END;
/```

I’ve created a simple table on which I have collected statistics without histograms:

• `(method_opt => 'FOR ALL COLUMNS SIZE 1')`

And, as far as I have set the global preference approximate_ndv to true:

```SQL> select dbms_stats.get_prefs ('approximate_ndv') ndv from dual;
NDV
----
TRUE```

I left the sampling decision in the hands of Oracle:

• `(estimate_percent => DBMS_STATS.AUTO_SAMPLE_SIZE)`

As such, collecting statistics will be performed very quickly and with a far better precision when compared to the sampling I would have manually entered.

You might have already noticed that I managed to create a skewed id2 column on which I haven’t collected histograms:

```SQL> select id2, count(1) from t1 group by id2;

ID2   COUNT(1)
---------- ----------
1     999000
42       1000

SQL> select
column_name
,num_distinct
,histogram
from user_tab_col_statistics
where table_name = 'T1'
and column_name  = 'ID2';

COLUMN_NAME  NUM_DISTINCT HISTOGRAM
------------ ------------ ----------
ID2           2           NONE```

Put this on hold, we will come back to it later in this article.

Now, I am going to execute the following query and display its corresponding execution plan:

```SQL> select * from t1 where id2 = 42 order by id1 desc;
-----------------------------------------------------------------------------------------------
| Id  | Operation                   | Name  | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |       |      1 |        |   1000 |00:00:00.52 |   36232 |
|*  1 |  TABLE ACCESS BY INDEX ROWID| T1    |      1 |    500K|   1000 |00:00:00.52 |   36232 |
|   2 |   INDEX FULL SCAN DESCENDING| T1_PK |      1 |   1000K|   1000K|00:00:00.15 |     515 |
-----------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter("ID2"=42)```

Four immediate points can be derived from the above execution plan:

• Oracle starts by doing an index full scan descending (ID = 2) on the primary key index and feeds back its parent operation (ID =1) with a bunch of 1000K rowids
• Using these 1000k rowids Oracle scanned the t1 table(ID = 1)  and throw away 99,9% of the generated rows when applying the filter (id2 =42)
• There is a massive increase of logical I/O (36232) during this table access
• Thanks to the Full scan of the primary key index the order by operation has been avoided

I have highlighted the E-Rows and the A-Rows information of operation ID = 1 to show how the CBO has completely messed up its initial estimations. This is mainly due to the skewed column id2 on which I haven’t collected any histograms.

Back to our initial goal which is to engineer and index covering the predicate part on column id2 and avoiding the order by operation on column id1. Here below the first index I came up with:

`SQL> create index t1_ind_id1_fbi on t1(id2,id1 desc);`

In passing, spot how I’ve managed to name my index (t1_ind_id1_fbi) so that it immediately indicates its type (a function-based index because of the desc clause I have added in its definition).

```SQL> select index_name, index_type
from user_indexes
where table_name = 'T1';

INDEX_NAME     INDEX_TYPE
-------------- ---------------------
T1_IND_ID1_FBI FUNCTION-BASED NORMAL
T1_PK          NORMAL```

Re-executing the original query gives us the following execution plan:

```SQL> select * from t1 where id2 = 42 order by id1 desc;

--------------------------------------------------------------------------------------------------------
| Id  | Operation                   | Name           | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
--------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |                |      1 |        |   1000 |00:00:00.01 |    1005 |
|   1 |  TABLE ACCESS BY INDEX ROWID| T1             |      1 |    500K|   1000 |00:00:00.01 |    1005 |
|*  2 |   INDEX RANGE SCAN          | T1_IND_ID1_FBI |      1 |    500K|   1000 |00:00:00.01 |       5 |
--------------------------------------------------------------------------------------------------------

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

This execution plan highlights six points:

• An index range scan access on the newly created function based index has been done
• An absence of a sort operation thanks to the new index range scan access instead of the previous full scan primary key index
• A noticeable reduction in the execution time
• Thanks to the new precise index, Oracle started with a small number of rows (1,000 rows) and kept with this small number of rows all over the other operations.
• A massive reduction of consistent gets from 36232 to 1005 buffers
• The CBO is still wrongly estimating the operations that filter on the skewed id2 column (500K instead of 1000 rows)

This was a typical example on how we can design an index so that we can achieve two goals with one index:

• Cover the predicate on column id2 with a precise index (where id2 =42)
• Avoid the cost of sorting id1 column by taking advantage of the ordered key in the index (order by id1 desc)

However, I was still wondering what if I had created the following normal b-tree index instead of the above `T1_IND_ID1_FBI` function-based one?

```SQL> create index t1_ind_id1_ni on t1(id2, id1); -- there is no desc for id1 column
-- “ni” stands for normal index```

Will this new index allow the CBO to avoid the order by operation?

```SQL> select * from t1 where id2 = 42 order by id1 desc;

--------------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name          | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
--------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |               |      1 |        |   1000 |00:00:00.01 |    1005 |
|   1 |  TABLE ACCESS BY INDEX ROWID | T1            |      1 |    500K|   1000 |00:00:00.01 |    1005 |
|*  2 |   INDEX RANGE SCAN DESCENDING| T1_IND_ID1_NI |      1 |    500K|   1000 |00:00:00.01 |       5 |
--------------------------------------------------------------------------------------------------------

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

Yes it does. The b-tree index (`T1_IND_ID1_NI`) is also able to allow the CBO to avoid the order by operation by scanning the index in descending order as shown by operation 2 in the immediate preceding execution plan. This has been made possible thanks to the existence of two pointers in the index leaf blocks (blocks where the real indexed values are located). Each leaf block (except the extreme ones) has a pointer backward and a pointer forward to its immediate neighbour block so that Oracle can traverse the index structure in both directions, ascending and descending.

The above engineered two types of composite indexes paved the way to the following question:

Since both indexes, the function-based index (T1_IND_ID1_FBI) and the b-tree one (T1_IND_ID1_NI), achieved the initial desire of discarding and sorting with approximatively the same amount of time and energy (in this case of course), which type of index would you prefer?

I have two reasons to prefer the normal b-tree index in this particular situation. The first one is that with the b-tree index I can eventually “kill three birds with one stone”. A very plausible situation is the presence of a foreign key (id2, id1) on the t1 table. In this case, with the b-tree index I have created above I would have been able to:

• filter on id2
• avoid the sorting cost of the order by id1 operation
• cover the foreign key lock and deadlock threat when deleting from the parent table the t1 table is referencing.

The function-based index (`id2, id1 desc`) is not able to cover the t1 table foreign key threat because it doesn’t start with the couple of foreign key columns (id2,id1).

The second reason to prefer the b-tree index to the function-based one (in this case) is due to the hidden column which goes hand-in-hand with the function-based index creation:

```SQL> SELECT
column_name
FROM
user_tab_cols
WHERE table_name = 'T1'
AND HIDDEN_COLUMN = 'YES';

COLUMN_NAME
-------------
SYS_NC00005\$```

I wrote above that the function-based index (id2, id1 desc) doesn’t start with the plausible foreign key column (id2, id1. Here is the proof:

```SQL> select index_name, column_name, column_position, descend
from user_ind_columns
where index_name = 'T1_IND_ID1_FBI';

INDEX_NAME        COLUMN_NAME     COLUMN_POSITION DESCEND
----------------- --------------- --------------- ----------
T1_IND_ID1_FBI    ID2                           1 ASC
T1_IND_ID1_FBI    SYS_NC00005\$                  2 DESC```

Thanks to the desc clause in the index definition, the internal index columns expression looks now as (id2, SYS_NC00005\$) instead of (id2, id1 desc). And this is the main reason why this index doesn’t cover the foreign key (id2, id1) lock and deadlock threat.

To take advantage of the function-based index, we very often need an extra step to collect statistics on the hidden column by means of the following call to the dbms_stats package:

```BEGIN
dbms_stats.gather_table_stats
(user
,'t1'
,method_opt       => 'FOR ALL HIDDEN COLUMNS SIZE 1'
,estimate_percent => DBMS_STATS.AUTO_SAMPLE_SIZE
END;
/```

Having exposed my b-tree index preference motivations (in this particular case), I still have a supplementary question:

What, if instead of a composite index on (id2, id1) I created only one single column index on (id2)?  Will the CBO be able to use the primary key index on (id1) in its attempt to avoid the order by operation and the second one on (id2) in its attempt to cover the where clause on id2?

```SQL> drop index T1_IND_ID1_NI;
SQL> drop index T1_IND_ID1_FBI;

SQL> create index t1_ind_id2 on t1(id2);

SQL> select index_name
,column_name
,column_position
from
user_ind_columns
where table_name = 'T1';

INDEX_NAME COLUMN_NAM COLUMN_POSITION
---------- ---------- ---------------
T1_PK      ID1                      1
T1_IND_ID2 ID2                      1

SQL> select * from t1 where id2 = 42 order by id1 desc;

-----------------------------------------------------------------------------------------------
| Id  | Operation                   | Name  | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-----------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |       |      1 |        |   1000 |00:00:00.51 |   36232 |
|*  1 |  TABLE ACCESS BY INDEX ROWID| T1    |      1 |    500K|   1000 |00:00:00.51 |   36232 |
|   2 |   INDEX FULL SCAN DESCENDING| T1_PK |      1 |   1000K|   1000K|00:00:00.15 |     515 |
-----------------------------------------------------------------------------------------------

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

1 - filter("ID2"=42)```

Note how the CBO is unable to combine simultaneously the t1_ind_id2 (id2) index to filter t1 table using the predicate id2 = 42 and the t1_pk primary key index to avoid the sort operation. Using this pair of indexes, the initial high number of Logical I/O (36232) is back.

Even though the CBO visited the primary index and walks its leaf block in the key order (INDEX FULL SCAN ) without any sorting, it has no way to merge the ordered rowids of operation (ID =2) with those filtered from the t1 table access by rowid at operation (ID = 1).

There exists, nevertheless, a way to avoid the order by operation with the pair of indexes we have at our disposal. We need to re-write the query to give the CBO another possible path as shown below:

```SQL> with
got_my_id2_rowid as
(select rowid, t1.* from t1 where id2 = 42)
,got_my_id1_rowid as
(select /*+ no_merge */ rowid from t1 order by id1)
select
t1.id1
,t1.id2
,t1.small_vc
from
got_my_id2_rowid t1
, got_my_id1_rowid t2
where
t1.rowid = t2.rowid;```

I built two “with subqueries“, one to get the ordered rowids by id1 (`got_my_id1_rowid`) and the other  to get the t1 table rowids to satisfy the predicate part where id2=42 (got_my_id2_rowid). I have also added the no_merge hint in the `got_my_id1_rowid` factored subquery so that it will not be merged with the remaining one.

And here is the execution plan I got in 11.2.0.3.0:

```-----------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name       | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-----------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |            |      1 |        |   1000 |00:00:00.66 |    1518 |
|*  1 |  HASH JOIN                   |            |      1 |    500K|   1000 |00:00:00.66 |    1518 |
|   2 |   VIEW                       |            |      1 |   1000K|   1000K|00:00:00.22 |     513 |
|   3 |    INDEX FULL SCAN           | T1_PK      |      1 |   1000K|   1000K|00:00:00.10 |     513 |
|   4 |   TABLE ACCESS BY INDEX ROWID| T1         |      1 |    500K|   1000 |00:00:00.01 |    1005 |
|*  5 |    INDEX RANGE SCAN          | T1_IND_ID2 |      1 |    500K|   1000 |00:00:00.01 |       5 |
-----------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):

---------------------------------------------------
1 - access("T1".ROWID="T2".ROWID)
5 - access("ID2"=42)```

The two ”with subqueries” have been hash joined together using their corresponding rowid as a join column. The probe table gives the rowids satisfying the id2 = 42 where clause using the corresponding index on (id2) while the build table gives the rowids ordered by id1 using the primary key index on (id1). The Logical I/O using this refactored query dropped to 1518 from 32232 original buffer gets.

When observing operation 5 in the above plan I asked myself: Why, despite the CBO wrongly estimating to buffer 500,000 rows at this step, does it nevertheless decide to use an index range scan to honour this operation? In passing with both 11.2.0.3.0 and 12.0.1.1 8K block size, the same operation has been honored via a table full scan. I kept this question open for another investigation.

Finally, whether this query rewrite represents a good strategy or not depends on your specific case and what you will be confronted to. I have to confess that there are cases (particularly under first_rows mode) where the CBO prefers an INDEX FULL SCAN access to avoid an order by operation whatever the cost of that INDEX FULL SCAN operation is.

### Tackling the CBO wrong estimation

Because of the data skew of the id2 column, the CBO has been wrongly estimating, in almost all the above execution plans whatever the index it has used, the cardinality of the operations that filter on the id2 column. One solution would be to gather adequate histograms on this column. But being in an index design path, I would prefer to tackle this issue using a virtual column which I will be adequately indexing. Something like this:

`SQL> alter table t1 add derived_id2 number generated always as (case when id2 = 42 then 42 else null end) virtual;`

I added a virtual column on t1 table which will hold the value 42 when it is filled up with 42 and null when filled up with a different value:

```SQL> desc t1
Name                             Null?    Type
-------------------------------  -------- -------------------
1      ID1                             NOT NULL NUMBER
2      ID2                                      NUMBER
3      SMALL_VC                                 VARCHAR2(10 CHAR)
5      DERIVED_ID2                              NUMBER```

The next step is to create a new composite index using the virtual column coupled with the id1 column on which we want a sort:

`SQL> create index t1_derived_id2_ind on t1(derived_id2, id1) compress;`

And to collect fresh statistics for the virtual column and its associated index:

```SQL> begin
dbms_stats.gather_table_stats
(user,
't1',
method_opt => 'for columns derived_id2 size 1',
no_invalidate => false
);
end;
/```

Now that I have put the scenario in place I am going to realize it

```SQL> select * from t1 where derived_id2 = 42 order by id1 desc;

------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name               | Starts | E-Rows | A-Rows | Buffers |
------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                    |      1 |        |   1000 |    1004 |
|   1 |  TABLE ACCESS BY INDEX ROWID | T1                 |      1 |   1000 |   1000 |    1004 |
|*  2 |   INDEX RANGE SCAN DESCENDING| T1_DERIVED_ID2_IND |      1 |   1000 |   1000 |       4 |
------------------------------------------------------------------------------------------------

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

Note how, with the help of the virtual column and its corresponding index, the CBO is doing a perfect estimation which ultimately leads almost always to an optimal execution plan.

## The last observation

I have managed to create the `DERIVED_ID2` virtual column so that it holds only my `ID2` critical value (42) which I needed to cover. All other id2 values are seen by this new virtual column as null. However when I’ve created the composite `T1_DERIVED_ID2_IND(DERIVED_ID2,ID1)` index, the “null” id2 values have been inserted in this index because they are protected by the id1 not null column. The immediate consequence is that I lost the advantage of not indexing the huge number of “null” `DERIVED_ID2` column. This paved again the path for my last question:

What if in this case, I opted for a single index on derived_id2 column? Will I take advantage of the small size of that index?

```SQL> create index t1_derived_id2_ind_bis on t1(derived_id2);

SQL> SELECT
index_name,
blevel,
leaf_blocks,
distinct_keys,
num_rows,
clustering_factor
FROM user_indexes
WHERE table_name = 'T1';

INDEX_NAME             BLEVEL   LEAF_BLOCKS  DISTINCT_KEYS NUM_ROWS    CLUSTERING_FACTOR
---------------------  -------- ----------   -----------   ----------  ----------------
T1_PK                  1         512         1000000       1000000      35715
T1_DERIVED_ID2_IND     1         785         1000000       1000000      36715
T1_DERIVED_ID2_IND_BIS 0         1           1             1000         1000

SQL> alter index T1_DERIVED_ID2_IND invisible;

SQL> select * from t1 where derived_id2 = 42 order by id1 desc;

---------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name                   | Starts | E-Rows | A-Rows | Buffers|
---------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                        |      1 |        |   1000 |    1001|
|   1 |  SORT ORDER BY               |                        |      1 |   1000 |   1000 |    1001|
|   2 |   TABLE ACCESS BY INDEX ROWID| T1                     |      1 |   1000 |   1000 |    1001|
|*  3 |    INDEX RANGE SCAN          | T1_DERIVED_ID2_IND_BIS |      1 |   1000 |   1000 |       1|
---------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
3 - access("DERIVED_ID2"=42)```

There is a reduction of the number of consistent gets using this new index that is worth checking before taking the final index design decision.

## Conclusion

Engineering an index should be dictated first by the query predicate part (where clause, group by and order by). Look carefully to the column you will use as the leading edge of the index. They should be the ones on which an equality predicate is applied. You should also have a “kill two birds with one stone” design strategy as far as with one index you can cover multiple queries, avoid redundant indexes and cover the foreign key lock threat. Do not forget the benefit an indexed virtual column could have on helping the CBO make good guesses (estimations) and producing attractive small indexes.

If a switch in the column order is still able to guaranty the precision and the use of the index then start your index with the column having the lowest number of distinct values. As such you can efficiently compress your index and give a CBO an extra possible path represented by the index skip scan.