Oracle Version: 11gR2 (22.214.171.124.0) - 64bit
OS: Linux Fedora Core 17 (x86_64)
Currently, I'm reading the online Database Concepts book in order to understand better how things work in oracle. At the time of writing I'm reading Chapter 3: 3 Indexes and Index-Organized Tables. There are some concepts which I think I need your help to understand and I appreciate if you could kindly give me a hand.
As I understand a B-Tree structure (index) is stored in RAM as a sorted data structure which makes searching much faster.
I'm not sure to understand properly the definition of "Full Index Scan" and "Fast Full Index Scan".
According to the documentation, here is how a "Full Index Scan" has been defined
In a full index scan, the database reads the entire index in order. A full index scan is available if a predicate (WHERE clause) in the SQL statement references a column in the index, and in some circumstances when no predicate is specified. A full scan can eliminate sorting because the data is ordered by index key.
Suppose that an application runs the following query:
Code: Select all
SELECT department_id, last_name, salary
WHERE salary > 5000
ORDER BY department_id, last_name;
Also assume that department_id, last_name, and salary are a composite key in an index. Oracle Database performs a full scan of the index, reading it in sorted order (ordered by department ID and last name) and filtering on the salary attribute. In this way, the database scans a set of data smaller than the employees table, which contains more columns than are included in
the query, and avoids sorting the data.
I'm going to write down here, what I understand from the above definition and would like to ask you to kindly read my description in order to see whether my understanding of Index Full Scan is correct.
What I understand from the above description is that given a composite index formed by (department_id, last_name, salary), oracle looks to the query and sees that the WHERE clause includes the salary which is one component of the given composite index. So a Index Full Scan is to be done. There is however an ORDER BY clause in the above SQL query (ORDER BY department_id, salary)
this means that the entire index is to be read in ascending order for both department_id and salary.
Consequently here is how I think oracle proceeds:
Step1: starts from the Root of the B-Tree index.
Step2: Because of ORDER BY department_id, last_name in the above SQL query oracle chooses the left-most branch block followed by the left-most leaf block where smallest index data (key, rowId) are stored, I say smallest from an data order point of view (Likewise it would have been Right-most if the ORDER BY clause in the query had been ORDER BY department_id DESC, salary DESC). This takes one logical I/O operation for reaching the root of the B-Tree index and one or several logical I/O operations (depending on the height of the B-Tree) for reaching the left-most and down-most (decision) branch block (so the next level will be the leafs level).
Step3: Again, after one logical I/O operation, oracle arrives finally at the left-most leaf block in the Tree.
Step4: The leaf blocks are double linked (so depending to the current position we may be able to go either to left or right). We're at the left-most leaf block. Each leaf-block is read by a single logical I/O one by one from the left-most leaf block to the right-most leaf-block so N logical I/O operations assuming that there are N leafs block, one for reading the entire of each leaf block.
NOTE1: Because the data in each leaf block is already sorted, there is no need to perform an ORDER BY. Therefore the only use of the ORDER BY clause in the above SQL query (ORDER BY department_id, last_name) is to tell oracle whether the scan is to be started from the left-most leaf block towards the right-most or vice versa. Once this decision has been made, oracle doesn't apply the ORDER BY to the result of the above SQL query as data in the leaf blocks are already sorted. The data is read leaf block by leaf block from left to right and every (key, rowId) where the salary component of the composite key satisfies the predicate (WHERE salary > 5000) is returned.
NOTE2: For a Index Full Scan, all columns of the index must be present in the SELECT statement, otherwise there won't be a Full Index scan
Do you think that my above mentioned description (Description1) about the Index Full Scan is correct?
Later, I will add to this topic the Index Fast Full Scan, but for now I prefer to concentrate only on the first part.
Thank you very much for your help.