Oracle Index Internals and Access Paths

TL;DR

Oracle indexes are like book indexes, speeding up data retrieval by providing quick pointers to rows. They're typically B-tree structures that organize data logically, allowing Oracle to find rows efficiently without scanning whole tables. Access paths determine how Oracle uses these indexes (or doesn't) to fulfill your query requests.

1. The Mental Model

Imagine you're looking for a specific topic in a very thick textbook. Instead of reading every page, you'd use the index at the back. Oracle indexes work similarly, giving the database engine a fast way to jump directly to the relevant data rows instead of scanning the entire table.

2. The Core Material

Oracle indexes are primarily implemented as B-tree structures. A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. For indexes, this means finding data is super fast!

How B-Tree Indexes Work

Photo by Tima Miroshnichenko on Pexels

A B-tree index consists of:

• Root Block: The very top block in the index structure. Oracle always starts its search here.
• Branch Blocks: These blocks point to lower-level branch blocks or leaf blocks. They help navigate the tree.
• Leaf Blocks: These are the lowest level blocks. They contain the indexed column values in sorted order and the ROWID for the actual table row. The ROWID is like a physical address for a row in a table.

When you query an indexed column, Oracle traverses the B-tree from the root, through branch blocks, until it reaches the leaf block containing your value. Once it finds the entry in the leaf block, it gets the ROWID and then goes directly to the table block to retrieve the full row.

Index Scan Types (Access Paths)

Photo by Chris F on Pexels

Oracle uses different "access paths" to retrieve data. These determine how it will use an index (or not) to get your data.

1. Index Unique Scan: This is the fastest access path. It's used when you query a UNIQUE or PRIMARY KEY indexed column with an equality condition (e.g., WHERE employee_id = 100). Oracle knows it will find at most one row.

2. Index Range Scan: Used when you query an indexed column with a range of values (e.g., WHERE salary > 50000) or for non-unique indexes. Oracle finds the starting point in the index and then scans forward through the leaf blocks until the condition is no longer met.

3. Index Full Scan: Oracle reads all the leaf blocks in the index in sorted order. This is typically used when a query needs all the data from an index and the index already provides the data in the required sort order, avoiding a separate sort operation.

4. Index Skip Scan: This is clever! If your index is composite (on multiple columns, e.g., (gender, department_id)) and your query only uses the second or subsequent column (e.g., WHERE department_id = 20), Oracle might "skip" the leading column if there aren't too many distinct values for it, trying different values for the first column.

5. Table Access By Index ROWID: After Oracle finds the ROWID(s) in the index leaf block(s), it then uses these ROWIDs to go to the actual table blocks to fetch the full rows. This is the "table lookup" part.

6. Full Table Scan: This isn't an index access path, but it's important to mention. If no suitable index exists or if the query optimizer determines that reading the entire table is more efficient (e.g., you're retrieving a very large percentage of the rows), Oracle will read every block in the table.

Here's how Oracle decides:

flowchart TD
    A["Query Sent to Oracle"] --> B{Optimizer Checks Conditions};
    B -- Is there an index on the column(s)? --> C{Is it an equality on UNIQUE/PK?};
    C -- Yes --> D["Index Unique Scan"];
    C -- No, but range or non-unique --> E["Index Range Scan"];
    E --> G["Table Access By Index ROWID"];
    D --> G;
    G --> H["Return Results"];
    B -- No suitable index or too many rows --> F["Full Table Scan"];
    F --> H;

When to Use Indexes

Photo by Element5 Digital on Pexels

• High selectivity: When your query returns a small percentage of rows from a large table.
• WHERE clauses: Especially with equality or range conditions.
• ORDER BY clauses: An index can provide pre-sorted data, avoiding a separate sort.
• JOIN conditions: Indexes on join columns improve join performance.
• DISTINCT clauses: Can be faster if the indexed columns cover the distinct values.

Overhead of Indexes

Photo by Element5 Digital on Pexels

While indexes speed up reads, they have a cost:

• Storage: Indexes consume disk space.
• Maintenance: Every INSERT, UPDATE, or DELETE on the indexed columns requires Oracle to update the index, which adds overhead to DML operations.
• Optimizer Choice: Sometimes Oracle might choose not to use an index if it thinks a full table scan is faster (e.g., querying for 90% of rows).

3. Worked Example

Let's say you have a large EMPLOYEES table with millions of rows and columns like employee_id (PRIMARY KEY), first_name, last_name, salary, department_id.

Scenario 1: Fast Lookup

SELECT first_name, last_name, salary
FROM employees
WHERE employee_id = 1001;

Oracle will perform an Index Unique Scan on the employee_id primary key index. It finds the ROWID for employee_id = 1001 very quickly, then does a Table Access By Index ROWID to fetch the first_name, last_name, and salary from the actual table row. This is super efficient.

Scenario 2: Range Query

Suppose there's a non-unique index on department_id.

SELECT first_name, last_name
FROM employees
WHERE department_id = 50;

Oracle will perform an Index Range Scan on the department_id index. It finds all ROWIDs associated with department_id = 50 in the index's leaf blocks, then does Table Access By Index ROWID for each found ROWID to retrieve first_name and last_name. If department 50 has many employees (e.g., 20% of the table), Oracle might still opt for a Full Table Scan if it's deemed faster than hopping back and forth between the index and the table blocks repeatedly.

Scenario 3: No Index / Full Table Scan

SELECT employee_id, first_name
FROM employees
WHERE last_name LIKE 'Smi%';

If there's no index on last_name, or if the index isn't suitable for a LIKE predicate with a leading wildcard (e.g., %mith), Oracle will likely perform a Full Table Scan on the employees table, reading every row to find matches. This can be very slow for large tables. If there is an index on last_name and the LIKE predicate doesn't start with a wildcard (e.g., 'Smi%'), an Index Range Scan would be used.

4. Key Takeaways

• Oracle indexes, primarily B-trees, dramatically speed up data retrieval by acting as sorted pointers to table rows.
• Leaf blocks of a B-tree index store indexed values and the ROWID, which is a physical address for the table row.
• Different access paths (e.g., Index Unique Scan, Index Range Scan, Full Table Scan) dictate how Oracle retrieves data.
• The Oracle Optimizer intelligently chooses the best access path based on statistics, query conditions, and available indexes.
• Indexes are most effective for highly selective queries (returning a small percentage of rows) and for WHERE, ORDER BY, and JOIN clauses.
• While indexes improve read performance, they add overhead to DML operations (INSERT, UPDATE, DELETE) due to maintenance.
• Always check your execution plan to understand which access path Oracle is actually using.

Common Mistakes to Avoid:
- Creating too many indexes; they consume space and slow down DML.
- Indexing low-selectivity columns (e.g., a "gender" column with only two values in a large table).
- Assuming Oracle will always use an index just because one exists; the optimizer decides.
- Not rebuilding indexes after massive deletes or updates, which can leave them fragmented.

5. Now Try It

Choose a table in your Oracle schema (or create a simple EMPLOYEES table if you don't have one). Create an index on a non-primary key column, then run a SELECT statement using a WHERE clause on that indexed column. After that, remove the index and run the same SELECT statement.

To succeed, you should be able to:
1. See a noticeable difference in query execution time (though for small tables, it might be minimal).
2. Use EXPLAIN PLAN FOR followed by your SELECT statement and then SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY); to view the execution plan and confirm that Oracle used an INDEX SCAN when the index was present, and a FULL TABLE SCAN when it was not.