Indexes and Sorts (Chant Of The Ever Circling Skeletal Family)

In my previous post regarding Reading 100% of Data via an Index, one of the examples I described was the scenario where an index was used to avoid a sort.

Index entries are always logically stored in the same order as the indexed columns (except of course when using a Reverse Key Index). Therefore if an index range scan is used to retrieve data, the data is returned in indexed column order. Sorts are relatively expensive operations, so if data needs to be retrieved in a specific order, the CBO can use the fact indexes return sorted data to its advantage and can potentially avoid performing the sort operation.

However, there’s a common misconception that if an appropriate index exists, Oracle will always use the index to avoid the sort. This is simply not true. Oracle will only use the index to avoid a sort if the costs of doing so is less than other alternatives. It could well be that the cost of performing say a Full Table Scan plus an associated sort might well be less than performing a really expensive and inefficient index range scan without the need for a sort. It depends on the relative costs of each possible option.

This Indexes and Sorts Part I Demo sets up a scenario and shows how an index can be used to select 100% of all rows in a table. However, note that the index in question has an excellent Clustering Factor with the rows stored in the table in basically the same order as that of the index. An index range scan of the whole table in this case is relatively efficient in that Oracle only needs to generally access each specific block the once. Therefore reading the entire table via an index and thus preventing the sort operation has a lesser cost than a potentially more efficient FTS but with the additional sorting overhead.

One of the more common reasons why an index is ignored when it possibly appears it should be used is due to the possibility of NULL values in the result set. As previously discussed, index entries that consist of nothing but NULLs are not indexed. Therefore an attempt to read all values from a table that has the potential to include NULL values may not use an associated index as the index may not reference all the required rows. The query either needs to be modified to exclude NULL values or the column(s) need to have a NOT NULL constraint for an index to be considered in this scenario.

This Indexes and Sorts Part II Demo shows how an index can not be used to eliminate a sort operation as the query result set could potentially return NULL values as the associated column does not have a NOT NULL constraint. By rewriting the query to exclude NULL values, the index is subsequently used by the CBO to retrieve all data, thus eliminating the sort operation.

Another perhaps more common reason why an index is not used to retrieve data in the index order, thus eliminating the need for a sort is that the cost of using the index to retrieve the necessary data is too costly and the savings in not performing the sort don’t outweigh the additional overheads of using the inefficient index. If an index has a very poor Clustering Factor, it can be extremely expensive for the CBO to use the index to retrieve data as most visits to the table requires a different table block to be accessed. In an extreme scenario, it may be necessary to read and re-read the same table block as many times as there are rows in the block and it may require as many distinct table block visits as there are rows in the table to retrieve all necessary rows via an index.

The cost of reading the table and the number of table block visits calculated by the CBO when using an index range scan is basically the selectivity of the query multiplied by the Clustering Factor of the index. Therefore the Clustering Factor is a crucial variable in deciding whether it’s actually worth using the index to prevent the sort or whether it’s actually less costly to use an alternative access path, such as perhaps an efficient FTS and subsequent sort.

The Indexes and Sorts Part III Demo is similar to the previous Part I demo except it uses a table that is ordered differently thus making the associated index result in a dreadful Clustering Factor. Consequently, the same query that previously used the index and no sort suddenly uses a FTS and a subsequent sort to read the entire table. However, even a query that only retrieves 10% of the data still uses a FTS and a subsequent sort. In fact even a query that retrieves just 1% of the data performs a FTS and subsequent sort. In this specific example, it wasn’t until approximately 0.11% of data was retrieved that the CBO decided it was cheaper to use the index and eliminate the sort than to use a FTS and subsequent sort.

The key message here is that yes, an index can be used to retrieve data in the specific order of the index and thus eliminate a sort operation. However, it will only do so if the cost of reading the necessary data via the index is less than alternative access paths, including the feared FTS, plus associated sort. If an index has a poor Clustering Factor, it is less likely to be considered as a method of eliminating a sort operation.