Introduction to Indexes, B* Tree indexes, Index scan methods - Indexes Fundamentals

About Indexes:

•  Indexes are schema object associated with table or cluster that may allow SQL queries to execute more quickly if used properly.
•  Typically Indexes can help optimize your query when properly used. Also Indexes can impact the performance of Insert, Update,Delete operations.

Types of Index:

Indexes can be categorized into following types based on structure.

1. B-Tree Indexes:
• Reverse Key Index
• Descending Index
• B-Tree cluster Index
• Key Compressed Index
• Index Organized Table (IOT).
2. Bitmap and Bitmap Join Indexes
3. Partitioned Indexes

Indexes can also be categorized into following types based on use/characteristics:

1. Composite Index

2. Unique and Non-Unique Index

3. Function Based Index

4. Application Domain Index

5. Invisible Index

6. Virtual Column Index

7. Virtual Index

B* Tree Indexes

B*Tree or Balances Tree indexes are the most commonly used type of indexes in oracle. They are similar in implementation to a binary search tree. Their goal is to minimize the amount of time Oracle spends searching for data. B-trees provide excellent retrieval performance for a wide range of queries, including exact match and range searches.

Typically B Tree indexes are very much useful when you are using B Tree index to retrieve very small number of rows from your table and their are other situation also where B Tree indexes will be very much useful which will be discussed later.

A B-tree index is an ordered list of values divided into ranges. By associating a key with a row or range of rows, B-trees provide excellent retrieval performance for a wide range of queries, including exact match and range searches.

B* Tree Indexes Structure

B Tree Index structure looks like this diagram. A B-tree index has two types of blocks: branch blocks for searching and leaf blocks that store Index Key Values and ROWID. The ROWID points to the table that is indexed. The upper-level branch blocks of a B-tree index contain index data that points to lower-level index blocks. For example the root branch block has an entry 101-200, which points to the rightmost block in the next branch level. This branch block contains entries such as 101-131, 135-167 and 168-200.

A B-tree index is balanced because all leaf blocks automatically stay at the same depth. Thus, retrieval of any record from anywhere in the index takes approximately the same amount of time. The height of the index is the number of blocks required to go from the root block to a leaf block. The branch level is the height minus 1. It does not count the leaf block. So even if we go for Employee ID 5 or Employee ID 400, there will be same number of I/Os or same number of blocks will be visit.

B Tree index does not store any NULL value. Only in case of composite indexes, you can store NULL values as long as one column have non-NULL value. e.g Suppose we have created index on two columns A and B. B may have NULL values, then as long as A has not NULL Values Index will store each value.

Check Branch Level from Indexes:

SELECT INDEX_NAME, BLEVEL, NUM_ROWS

FROM ALL_INDEXES

WHERE TABLE_NAME = 'EMPL_DEMO' AND OWNER = 'HR';

INDEX_NAME BLEVEL NUM_ROWS

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

EMPL_DEMO_ID_INDX 2 20000000

EMPL_COMP_ID_INDX 2 21234000

Height of these Indexes will be Three.

Validate the index height:

ANALYZE INDEX HR.EMPL_DEMO_ID_INDX VALIDATE STRUCTURE;

SELECT NAME, HEIGHT, BR_BLKS, LF_BLKS FROM INDEX_STATE;

NAME HEIGHT BR_BLKS LF_BLKS 

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

EMPL_DEMO_ID_INDX 3 8 4408

This can also been seen as: "Consistent gets" from explain plan statistics. It will be three.

SELECT EMPLOYEE_ID FROM EMPLOYEES WHERE EMPLOYEE_ID =100;

If we make SELECT EMPLOYEE_ID FROM EMPLOYEES WHERE EMPLOYEE_ID =100; there will be three Consistent Gets because it will scan from table only. That's why its operation is "SELECT STATEMENT INDEX UNIQUE SCAN". 

However if perform SELECT * FROM EMPLOYEES WHERE EMPLOYEE_ID =100; consistent Gets will be 4 in this case. 4th gets because now it will go to table. Here operation will be TABLE ACCESS BY INDEX ROWID INDEX UNIQUE SCAN

Index Scan Method

Index Scan is the method to retrieve a row by traversing through the index, using the indexed column values (index keys) specified by the statement. Basic concept of Index Scan is:

•  The index scan first locate the root block of the index.
•  The descends through the branch level of the index.
•  Then goes to the particular leaf block that have first possible entry (the start key) that you have mentioned in query predicates.
•  Then it walks along a chain of leaf block until it reaches the entry that is the last possible entry (the stop key) that matches your predicates.
•  For each index entry, if it requires, it visits a table block.

Different type of Index Scan Methods:

Full Index Scan:

In a full index scan, the database reads the entire index in sorted order of the indexed key.

A Full Index Scan is performed in cases like you are selecting the whole indexed column and using a order by with that column. All of the columns in the ORDER BY clause must in the index. The order of the columns in the ORDER BY clause must match the order of the leading index column.

Example: 

SELECT EMPLOYEE_ID FROM EMPLOYEES ORDER BY EMPLOYEE_ID;

Fast Full Index Scan:

• A Fast Full Index Scan in which the database access the data in the index itself without accessing the table, and the database reads the index blocks in no particular order. This is the optimal access method when all of the information required to answer a query is contained in indexed columns. In Fast Full Index Scan multiblock read happens.
• The Index must contain all columns needed for the query. 
• A row containing all nulls must not appear in the query result set.
• A GROUP BY clause is present in the query, and the columns in the GROUP BY clause are present in the index.

CREATE INDEX EMPL_COMP_INDX ON EMPLOYEE(DEPARTMENT_ID, EMAIL, SALARY);

SELECT DEPARTMENT_ID, SUM(SALARY)

FROM EMPLOYEES

GROUP BY DEPARTMENT_ID;

It is not visiting the table, it is doing INDEX FAST FULL SCAN and getting the data from index itself then it is doing HASH GROUP by to give you the aggregated result.

Index Range Scan

An Index Range Scan is an ordered scan of an index. It happens when index is scanned for a range of values, when you are using a range predicate.

One or more leading columns of an Index are specified in condition like:

indexed_col = :b1;

indexed_col <= :b1;

indexed_col > :b1;

BETWEEN, LIKE conditions;

AND combination of any of the preceding conditions for leading column in the index.

SELECT * FROM EMPLOYEES

WHERE EMPLOYEE_ID < 1000;

Range scan will work as shown in below image above. If we look for data of Employees with ID between 100-200, the data retrieval will be as shown in image. 

Index Unique Scan

The database performs a Unique scan when a predicate references all of the columns in a UNIQUE index key using an equality operator. An Index Unique Scan stop processing as soon as it finds the first record because no other record is possible, as you are accessing using Unique Index it will not have duplicate value.

SELECT * FROM EMPLOYEES WHERE EMPLOYEE_ID = 100;

It is doing Index Unique Scan on EMPL_DEMO_ID_INDX and getting the ROWID, then accessing the table using the particular ROWID.

Index Skip Scan

In Index Skip Scan Oracle "skips" leading edge predicate in a composite index. 

Oracle mainly uses skip scan in cases like you have created a composite index on 2 columns, and the leading column may have very less number of distinct values and the other column may have more distinct values and the leading column is not used in query predicate.

Composite Index creates is: 
CREATE INDEX MGR_LOGIN_COMP_INDX ON EMPLOYEES(MANAGER_NAME, LOGIN);

Here manager_Name will have repeatative values and "Login" will have less repeative values or it will have all distinct values. 

Now execution of query:

SELECT * FROM EMPLOYEES WHERE LOGIN='James@453';

You can see it is doing INDEX SKIP SCAN. Only LoginId has been used in query and not the Manager_Name column, then it is doing the Index Skip Scan

Source: https://www.youtube.com/user/Anindya007das