Oracle Tuning Tip#13: Index Range Scan Descending

TOPIC:

Index Range Scan Descending

DEFINITION:

Index Range Scan Descending is one of the index access methods supported by Oracle.

Index Range Scan Descending means the retrieval of one or more ROWIDs from an index. Index Range Scan Descending is applicable to both B*Tree Unique Index and B*Tree Non-Unique Index unlike Index Unique Scan, where it is applicable only to B*Tree Unique Index. This retrieves the index data in the descending order unlike Index Range Scan where it retrieves the data in the same order as of index table.

LITTLE-KNOWN FACTS TO BE REMEMBERED:

• ·         By seeing this index scan name, we would think that there would be an another index scan called “Index Range Scan Ascending” but it is actually not. This index scan name might be little confusing but ideal name for this index scan should be “Index Range Scan Reverse”. Reason is, this index scan suffices both these scenarios. 1) if index is created in the ascending order, with this index scan, we can retrieve the index data in the descending order. 2) if index is created in the descending order, with this index scan, we can retrieve the data in the ascending order.
• ·         If Oracle has to follow Index Range Scan Descending, if B*Tree Unique index is created on the table, then in the SQL, any non-equality operator must be used like <=, <, >, >=, IN, BETWEEN. In addition to this, in the ORDER BY clause, we should mention the reverser order (please check the first point). If any of these operators is used, it means more than one index record is going to be referred in the index table in the reverse order and in turn which returns more than one ROWID (because in the unique index, single index value is mapped to single ROWID. So if 5 index records are accessed, it means 5 ROWIDs are retrieved).  It is explained in EXAMPLE section.
• ·         If Oracle has to follow Index Range Scan Descending, if B*Tree Non-Unique index is created on the table, then in the SQL, any non-equality operator can be used like <=, <, >, >=, IN, BETWEEN. In addition to this, in the ORDER BY clause, we should mention the reverser order (please check the first point If any of these operators is used, it means more than one index record is going to be referred in the index table in the reverse order and in turn which returns more than one ROWID (because in the non-unique index, single index value is mapped to more than one ROWID. So if 5 index records are accessed, it means it can return more than 5 ROWIDs). It is explained in EXAMPLE section.

ADVANTAGE:

• ·         Generally, TEMP tablespace is used for sorting of records. If Oracle follows Index Range Scan Descending, then it won’t consume any memory from TEMP tablespace. Because sorting is taken care by reading the index table in the reverse order itself.
• ·         Query retrieval will be fast if Index Range Scan is followed since the required ROWID can be accessed from the index table.
• ·         In this index access method, random search is made to look for the indexed values instead of sequential search. Performance gain is achieved since the random search (which is used while searching for the data in this unique index table) is much faster than the sequential search (which is used while searching for the data in data table directly)
• ·         In some cases, if all the required columns to be displayed available in the index table itself, then Oracle don’t need to refer the actual data table at all.

DISADVANTAGE:

• ·         If Oracle has to follow this Index Range Scan Descending, then index table has to be created in advance before executing this query. This index table consumes considerable amount of memory.

HOW TO VERIFY:

How to verify whether Oracle follows index range scan Descending or not while executing the sql query. If a query follows this, then you will find similar execution plan like this,

--------------------------------------------------------------------------------------------------------

| Id  | Operation                               | Name                         |    Rows    |

--------------------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT                        |                              |            |

|   1 |  TABLE ACCESS (BY INDEX ROWID)          | EMP                          |            |

|   2 |   INDEX (RANGE SCAN DESCENDING)         | EMP_NO_INDX                  |            |

In the explain plan, whenever it follows the index range scan descending against either an unique index or a non-unique index, it displays the keyword (RANGE SCAN DESCENDING) in the operation column against the index name in both the cases.

EXAMPLE:

Create an employee table and inserts 10 records. The table will look like this,

DATA TABLE:

ROWID	empid	column2	column3	column4	deptid
AAAAA1	5	..	..	..	SALES
AAAAA2	10	..	..	..	HR
AAAAA3	9	..	..	..	ADMIN
AAAAA4	4	..	..	..	SALES
AAAAA5	6	..	..	..	FINANCE
AAAAA6	7	..	..	..	HR
AAAAA7	1	..	..	..	HR
AAAAA8	8	..	..	..	SALES
AAAAA9	2	..	..	..	FINANCE
AAAAA10	3	..	..	..	ADMIN

TESTCASE-I: (for the unique index)

Fire this query against this table where the requirement is to display all the attributes of the employees whose empid should be greater than or equal to “7” but less than or equal to“9”

and display the records in the descending order of employee ids.

Select * from emp where empid  between 7 and 9 order by empid desc;

Before execute this query, create an unique index on this table for empid column. (create unique index emp_no_indx on emp(empid)).

Index table will logically look like this,

UNIQUE INDEX TABLE:

INDEX	ROWID
1	AAAAA7
2	AAAAA9
3	AAAAA10
4	AAAAA4
5	AAAAA1
6	AAAAA5
7	AAAAA6
8	AAAAA8
9	AAAAA3
10	AAAAA2

First column (INDEX) : it stores all the values of empid column in the ascending order.

Second column (ROWID) : it stores the ROWID of the corresponding record.

When oracle executes this sql, first it looks for any index which has already been created on this “empid” column. It comes to know that the index, “emp_no_indx” has already been created on “empid” column. So, oracle refers the index table first before hitting the actual data table. Since we have mentioned the descending order in the order by clause of the select statement, Oracle reads the index table in the bottom-up approach instead of normal top-down approach. Since we are looking for the range of empids:”7,8,9”, oracle hits index table first, starts with the index value, “9” and ends with the index value, “7” so it gets the corresponding ROWIDs (AAAAA3, AAAAA8, AAAAA6). When oracle searches for the value in this index table, it follows random search (i.e. binary search) to go to the corresponding first required index record (since we are looking for the range of index records in the descending order), in this case it is 9^th index record. Using this binary search, Oracle is intelligent enough to go to the 9^th index record directly in the index table. After that, it does only the sequential search to retrieve the two remaining index records (8^th and 7^th index records) since index values are kept in the sorted order so it doesn’t need to go for the random search for these two . (because optimizer is very sure than 8 and 7 should come immediately before 9)

After the getting the required ROWIDs (AAAAA3, AAAAA8, AAAAA6), oracle directly refers 3^rd, 8^th and 6^th records of the data table since it knows the exact locations.  With this, it doesn’t refer the remaining 7 table records. Now, explain table will look like this,

--------------------------------------------------------------------------------------------------------

| Id  | Operation                                                     | Name                                             | Rows  |

--------------------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT                                   |                                                          |     1       |

|   1 |  TABLE ACCESS (BY INDEX ROWID)      | EMP                                                |     1       |

|   2 |   INDEX (RANGE SCAN DESCENDING)| EMP_NO_INDX (UNIQUE)     |     1       |

Explain tells us that the index (EMP_NO_INDX) which is of unique type, it is being accessed via “Index Unique Scan Descending” method. If B*Tree unique index goes for Index Range Scan Descending, then in the ROWS column of the explain plan, only the value, ‘1’ would be displayed because each index record returns only one ROWID and 3 index records are accessed in the reverse order. That’s why it is called as “Index Range Scan Descending” access method.

TESTCASE-II: (for the non-unique index)

Fire this query against this table where the requirement is to display the all the attributes of an employee whose deptid is either “ADMIN” or “FINANCE” and display the records in the descending order of department id.

Select * from emp where deptid in (‘ADMIN’,’FINANCE’);

Before execute this query, create a non-unique index on this table for deptid column. (create index dept_id_indx on emp(deptid)).

Index table will logically look like this,

NON-UNIQUE INDEX TABLE:

INDEX	ROWID
ADMIN	AAAAA3
	AAAAA10
FINANCE	AAAAA5
	AAAAA9
HR	AAAAA2
	AAAAA6
	AAAAA7
SALES	AAAAA1
	AAAAA4
	AAAAA8

First column (INDEX) : it stores all the distinct values of deptid column in the ascending order.

Second column (ROWID) : it stores the ROWID of the corresponding records but all the ROWIDs for a single index value are grouped together.

When oracle executes this sql, first it looks for any index which has already been created on this “deptid” column. It comes to know that the index, “dept_id_indx” has already been created on “deptid” column. So, oracle refers the index table first before hitting the actual data table. Since we have mentioned the descending order in the order by clause of the select statement, Oracle reads the index table in the bottom-up approach instead of normal top-down approach. Since we are looking for the group of deptids, (’ADMIN’ and ‘FINANCE’), oracle hits index table first , starts with the index value, “FINANCE” and ends with the index value, “ADMIN” so it gets the corresponding ROWIDs (AAAAA5, AAAAA9, AAAAA3, AAAAA10). When oracle searches for the value in this index table, it follows random search (i.e. binary search) to go to the corresponding first required index record (since we are looking for the range of index records in the descending order), in this case it is 2^nd index record. Using this binary search, Oracle is intelligent enough to go to the 2^nd index record directly in the index table. After that, it does only the sequential search to retrieve the other remaining index record (1^st index record) since index values are kept in the sorted order so it doesn’t need to go for the random search for this . (because optimizer is very sure that “ADMIN” should come before “FINANCE”)

After the getting the required ROWIDs (AAAAA5,AAAAA9,AAAAA3,AAAAA10), oracle directly refers the 5^th, 9^th, 3^rd and 10^th records of the data table since it knows the exact locations. With this, it doesn’t refer the remaining 6 table records. Now, explain table will look like this,

--------------------------------------------------------------------------------------------------------

| Id  | Operation                                                     | Name                                                    | Rows  |

--------------------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT                                   |                                                                 |     4       |

|   1 |  TABLE ACCESS (BY INDEX ROWID)      |EMP                                                        |     4       |

|   2 |   INDEX (RANGE SCAN DESCENDING)| DEPT_ID_INDX (NON-UNIQUE) |     4       |

Explain tells us that the index (DEPT_ID_INDX) which is of non-unique type, it is being accessed via “Index Unique Scan Descending” method. If B*Tree non-unique index goes for Index Range Scan Descending, then in the ROWS column of the explain plan, only the value, ‘4’ would be displayed because the index table has returned 4 ROWIDs. That’s why it is called as “Index Range Scan Descending” access method.