Monday, October 11, 2010

Oracle Tuning Tip#12: Index Range Scan


TOPIC:
Index Range Scan

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

Index Range Scan means the retrieval of one or more ROWIDs from an index. Indexed values are generally scanned in ascending order.
Index Range Scan 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.

LITTLE-KNOWN FACTS TO BE REMEMBERED:
  • ·         If Oracle has to follow Index Range Scan, if B*Tree Unique index is created on the table, then in the SQL, any non-equality operator must be used like <=, <, >, >=, IN, BETWEEN. If any of these operators is used, it means more than one index record is going to be referred in the index table 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, if B*Tree Non-Unique index is created on the table, then in the SQL, it can have equality operator (=). If this is used, it means only one index record is going to be referred in the index table 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). Non-Unique Index still goes for the index range scan even if you have used equality operator (=) in the SQL though single index value is mapped to single ROWID only in the non-unique index table . It is explained in EXAMPLE section.
  • ·         If Oracle has to follow Index Range Scan, 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. If any of these operators is used, it means more than one index record is going to be referred in the index table and in turn which returns more than one ROWID (because in the 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)
  • ·         Sometimes, Optimizer may not opt for the index range scan (you can verify this by seeing explain plan) though B*Tree Non-Unique index is created on the required columns and these columns are referred in the SQL. Reason is, Optimizer might have evaluated like the cost of accessing all the required data table records through index table are costlier than going for the full table scan directly. Possibility of this scenario is very high if SQL tries to retrieve more than 30% (approximately) of actual table records.
ADVANTAGE:
  • ·         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, 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 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)                            | EMP_NO_INDX                          |            |

In the explain plan, whenever it follows the index range scan against either an unique index or a non-unique index, it displays the keyword (RANGE SCAN) 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
..
..
..
SALES
AAAAA6
7
..
..
..
HR
AAAAA7
1
..
..
..
HR
AAAAA8
8
..
..
..
SALES
AAAAA9
2
..
..
..
ADMIN
AAAAA10
3
..
..
..
ADMIN

TESTCASE-I: (for the unique index)
Fire this query against this table where the requirement is to display the all the attributes of an employee whose empid should be greater than or equal to “7” but less than or equal to“9”
Select * from emp where empid  between 7 and 9;

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 are looking for the range of empids:”7,8,9”, oracle hits index table first, starts with the index value, “7” and ends with the index value, “9” so it gets the corresponding ROWIDs (AAAAA6, AAAAA8, AAAAA3). 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 this case it is 7th index record. Using this binary search, Oracle is intelligent enough to go to the 7th index record directly in the index table. So, it won’t touch the first 6 index records. After that, it does only the sequential search to retrieve the two remaining index records (8th and 9th 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 9 should come immediately after 7)

After the getting the required ROWIDs (AAAAA6, AAAAA8, AAAAA3), oracle directly refers 3rd, 6th and 8th record 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)                            | 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” method. If B*Tree unique index goes for Index Range Scan, then in the ROWS column of the explain plan, only the value, ‘1’ would be displayed because each index record returns only one ROWID but 3 index records are accessed. That’s why it is called as “Index Range Scan” 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 “HR”
Select * from emp where deptid = ‘HR’;

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
AAAAA9
AAAAA10
HR
AAAAA2
AAAAA6
AAAAA7
SALES
AAAAA1
AAAAA4
AAAAA5
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 are looking for the deptid:’HR’, oracle hits index table first and get the corresponding ROWIDs (AAAAA2,AAAAA6, AAAAA7). When oracle searches for the value in this index table, it follows random search (i.e. binary search) to go to the corresponding index record. Using this binary search, Oracle is intelligent enough to go to the 2nd  index record directly in the index table. So, it won’t touch the remaining 2 index records.

After the getting the required ROWIDs (AAAAA2,AAAAA6, AAAAA7), oracle directly refers the 2nd, 6th and 7th 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                               |                                                                    |     3       |
|   1 |  TABLE ACCESS (BY INDEX ROWID)  | EMP                                                          |     3       |
|   2 |   INDEX (RANGE SCAN)                        | DEPT_ID_INDX (NON-UNIQUE)    |     3       |

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


1 comment:

  1. Thank you so much! Great explaination

    ReplyDelete