I think that I shall never see A poem lovely as a tree. A tree whose hungry mouth is prest Against the sweet earth's flowing ***; A tree that looks at God all day, And lifts her leafy arms to pray; A tree that may in summer wear A nest of robins in her hair; Upon whose bosom snow has lain; Who intimately lives with rain. Poems are made by fools like me, But only God can make a tree.
—Trees by Joyce Kilmer
Previous installment: SQL Sucks! Next installment: Don’t pre-order your EXPLAIN PLAN First installment: DON’T PANIC
I agree that an Oracle EXPLAIN PLAN is not easy to read. We are not told the order in which steps are executed so we must figure it out ourselves using the subtle indentation of operation names. It doesn’t help that the Oracle documentation incorrectly states that “The execution order in EXPLAIN PLAN output begins with the line that is the furthest indented to the right.” So I have nothing but sympathy for the honest admission by an application developer with fifteen (!) years of Oracle experience that he could not read an EXPLAIN PLAN with more than a few lines of indentation.
Here’s the real scoop. An Oracle EXPLAIN PLAN is a “tree” structure corresponding to a relational algebra expression. It is printed in “pre-order” sequence (visit the root of the tree, then traverse each subtree—if any—in pre-order sequence) but should be read in “post-order” sequence (first traverse each subtree—if any—in post-order sequence, then only visit the root of the tree).
Note the recursive nature of the pre-order and post-order procedures; that is, the phrase “pre-order” is used in the definition of the pre-order procedure and the phrase “post-order” is used in the definition of the post-order procedure. In other words, the procedures are defined in terms of themselves.
Here is an example of a tree structure.
The root of the above tree is labeled P. It has two subtrees whose roots are labeled B and O respectively. The subtree whose root is labeled B has a subtree whose root is labeled A. And so on. Read and re-read the definition of post-order traversal and convince yourself that the nodes should be visited in alphabetical order, that is, the node labeled A should be visited first, the node labeled B should be visited next, and so on. The root note should be visited last.
Now look at the next picture. The single-character labels have been replaced with the names of tables and operations but this does not affect the order in which the nodes should be visited. The red-colored terminal nodes (“leaf nodes”) represent data while the blue-colored non-terminal nodes (non-leaf nodes) represent operations. Non-terminal nodes with just one subtree represent “unary” operations such as Selection and Projection while those with left and right subtrees represent “binary” operations like Union, Difference, and Join. The fact that the subtrees are trees in their own right means that operations can be nested. In other words, a query execution plan corresponds to a nested relational algebra expression.
The tree in Figure 2 is a hypothetical query execution plan for the “common table expression” (CTE) solution to our teaching example “employees who have worked in all accounting job classifications” (see Introduction to Relational Calculus and Relational Algebra). Count the blue-colored non-terminal nodes in the above tree; you should find exactly eleven of them. That’s because there are exactly eleven steps in the CTE solution (see Listing 1). Figure 3 graphically illustrates how the desired result is produced. Note especially that each blue-colored terminal node represents an intermediate table. In fact, we can define a relational database as “a database in which: the data is perceived by the user as tables (and nothing but tables) and the operators available to the user for (for example) retrieval are operators that derive ‘new’ tables from ‘old’ ones.” (An Introduction to Database Systems by Chris Date)
Listing 1: CTE solution
-- Step 1: Projection
( SELECT employee_id FROM employees
-- Step 2: Projection
( SELECT employee_id FROM employees
-- Step 3: Projection
( SELECT job_id FROM jobs
-- Step 4: Selection
( SELECT * FROM all_jobs WHERE job_id LIKE 'AC%'
-- Step 5: Join
( SELECT * FROM all_employees_2 CROSS JOIN selected_jobs
-- Step 6: Projection
( SELECT employee_id, job_id FROM employees
-- Step 7: Projection
( SELECT employee_id, job_id FROM job_history
-- Step 8: Union
( SELECT * FROM current_job_titles
SELECT * FROM previous_job_titles
-- Step 9: Difference
( SELECT * FROM selected_pairings
SELECT * FROM complete_job_history
-- Step 10: Projection
( SELECT employee_id FROM nonexistent_pairings
-- Step 11: Difference
SELECT * FROM all_employees_1
SELECT * FROM ineligible_employees
Figure 3: Visualization of the CTE solution as a tree
Every query execution plan corresponds to a nested relational algebra expression because relational algebra operations are the basic procedures used by Oracle Database after all. The following expression corresponds to the trees shown in Figure 2 and Figure 3. The uppercase abbreviations S, P, U, D, J correspond to the operations Selection, Projection, Union, Difference, and Join respectively while the lowercase abbreviations e, j, and jh correspond to the the tables employees, jobs, and job_history respectively. The outermost operation in the expression corresponds to the root of the tree.
D ( P ( e ) , P ( D ( J ( P ( e ) , S ( P ( j ) ) ) , U ( P ( e ) , P ( jh ) ) ) ) )
I hope that this is beginning to make sense to you. In the next installment, you’ll see that an EXPLAIN PLAN is printed in pre-order sequence but should be read in post-order sequence.
To be continued.
P.S. The relational algebra expression corresponding to the trees shown in Figure 2 and Figure 3 can also be written as follows, though the correspondence with the trees gets obfuscated. As used here, the symbols “-”, “*”, and “U” represent the Difference, Join, and Union operations respectively.
P ( e ) - P ( P ( e) * S ( P ( j ) ) - ( P ( e ) U P ( jh ) )
Copyright © 2014 Iggy Fernandez
The ToadWorld censors have bleeped out one of the words in Joyce Kilmer’s poem.