SQL 101: Deep Left Trees, Deep Right Trees, and Bushy Trees! Oh, My!
An Oracle EXPLAIN PLAN can be a “deep left tree,” a “deep right tree,” or a “bushy tree.” Deep left trees are probably the most common because of an inherent bias of the Oracle optimizer. Consider the following query which joins the Employees table in the HR sample schema to the Jobs, Departments, Locations, Countries, and Regions tables and lists all employees in Department 90. I took the liberty of adding hints to force Oracle to do precisely what I needed it to do.
SELECT /*+ LEADING (e j d l c r) USE_NL(j) USE_NL(d) USE_NL(l) USE_NL(c) USE_NL(r) */ e.first_name, e.last_name, e.salary, j.job_title, d.department_name, l.city, l.state_province, c.country_name, r.region_name FROM employees e, jobs j, departments d, locations l, countries c, regions r WHERE e.department_id = 90 AND j.job_id = e.job_id AND d.department_id = e.department_id AND l.location_id = d.location_id AND c.country_id = l.country_id AND r.region_id = c.region_id;
Here are the query results and the EXPLAIN PLAN.
FIRST_NAME LAST_NAME SALARY JOB_TITLE DEPARTMENT_NAME CITY STATE_PROVINCE COUNTRY_NAME REGION_NAME -------------------- ------------------------- ---------- ----------------------------------- ------------------------------ ------------------------------ ------------------------- ---------------------------------------- ------------------------- Steven King 24000 President Executive Seattle Washington United States of America Americas Neena Kochhar 17000 Administration Vice President Executive Seattle Washington United States of America Americas Lex De Haan 17000 Administration Vice President Executive Seattle Washington United States of America Americas
---------------------------------------------------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time | A-Rows | A-Time | Buffers | Reads | ---------------------------------------------------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | | | 14 (100)| | 3 |00:00:00.05 | 26 | 32 | | 1 | NESTED LOOPS | | 1 | | | | | 3 |00:00:00.05 | 26 | 32 | | 2 | NESTED LOOPS | | 1 | 3 | 387 | 14 (0)| 00:00:01 | 3 |00:00:00.04 | 23 | 24 | | 3 | NESTED LOOPS | | 1 | 3 | 345 | 11 (0)| 00:00:01 | 3 |00:00:00.04 | 21 | 23 | | 4 | NESTED LOOPS | | 1 | 3 | 300 | 11 (0)| 00:00:01 | 3 |00:00:00.04 | 19 | 22 | | 5 | NESTED LOOPS | | 1 | 3 | 231 | 8 (0)| 00:00:01 | 3 |00:00:00.03 | 14 | 13 | | 6 | NESTED LOOPS | | 1 | 3 | 174 | 5 (0)| 00:00:01 | 3 |00:00:00.02 | 9 | 11 | | 7 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES | 1 | 3 | 93 | 2 (0)| 00:00:01 | 3 |00:00:00.01 | 4 | 2 | |* 8 | INDEX RANGE SCAN | EMP_DEPARTMENT_IX | 1 | 3 | | 1 (0)| 00:00:01 | 3 |00:00:00.01 | 2 | 1 | | 9 | TABLE ACCESS BY INDEX ROWID| JOBS | 3 | 1 | 27 | 1 (0)| 00:00:01 | 3 |00:00:00.01 | 5 | 9 | |* 10 | INDEX UNIQUE SCAN | JOB_ID_PK | 3 | 1 | | 0 (0)| | 3 |00:00:00.01 | 2 | 1 | | 11 | TABLE ACCESS BY INDEX ROWID | DEPARTMENTS | 3 | 1 | 19 | 1 (0)| 00:00:01 | 3 |00:00:00.01 | 5 | 2 | |* 12 | INDEX UNIQUE SCAN | DEPT_ID_PK | 3 | 1 | | 0 (0)| | 3 |00:00:00.01 | 2 | 1 | | 13 | TABLE ACCESS BY INDEX ROWID | LOCATIONS | 3 | 1 | 23 | 1 (0)| 00:00:01 | 3 |00:00:00.01 | 5 | 9 | |* 14 | INDEX UNIQUE SCAN | LOC_ID_PK | 3 | 1 | | 0 (0)| | 3 |00:00:00.01 | 2 | 1 | |* 15 | INDEX UNIQUE SCAN | COUNTRY_C_ID_PK | 3 | 1 | 15 | 0 (0)| | 3 |00:00:00.01 | 2 | 1 | |* 16 | INDEX UNIQUE SCAN | REG_ID_PK | 3 | 1 | | 0 (0)| | 3 |00:00:00.01 | 2 | 1 | | 17 | TABLE ACCESS BY INDEX ROWID | REGIONS | 3 | 1 | 14 | 1 (0)| 00:00:01 | 3 |00:00:00.01 | 3 | 8 | ----------------------------------------------------------------------------------------------------------------------------------------------------------
The above EXPLAIN PLAN doesn’t look very left-leaning but the picture below makes the point clear. To increase the size, you can click on it and zoom in using your browser. An Oracle query plan really has a tree-structure and the EXPLAIN PLAN lists the nodes in “preorder” sequence; that is, the parent node is listed before its children. The nodes are actually processed in “postorder” sequence; that is child nodes are processed before their parent. As seen in the picture, the actual order in which the nodes are processed is 8, 7, 10, 9, 6, 12, 11, 5, 14, 13, 4, 15, 3, 16, 2, 17, 1, 0.
Deep right trees are also possible and are important in data warehouses to join large fact tables to small dimension tables using hash joins. I rewrote my query with the USE_HASH and SWAP_JOIN_INPUTS hints to force Oracle to use a deep right tree.
SELECT /*+ LEADING (e j d l c r) USE_HASH(j) SWAP_JOIN_INPUTS(j) USE_HASH(d) SWAP_JOIN_INPUTS(d) USE_HASH(l) SWAP_JOIN_INPUTS(l) USE_HASH(c) SWAP_JOIN_INPUTS(c) USE_HASH(r) SWAP_JOIN_INPUTS(r) */ e.first_name, e.last_name, e.salary, j.job_title, d.department_name, l.city, l.state_province, c.country_name, r.region_name FROM employees e, jobs j, departments d, locations l, countries c, regions r WHERE e.department_id = 90 AND j.job_id = e.job_id AND d.department_id = e.department_id AND l.location_id = d.location_id AND c.country_id = l.country_id AND r.region_id = c.region_id;
The query results obviously won’t change but here is the EXPLAIN PLAN and its graphical representation. The nodes are processed in the order 2, 4, 6, 9, 8, 11, 13, 12, 10, 7, 5, 3, 1, and 0.
--------------------------------------------------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time | A-Rows | A-Time | Buffers | Reads | --------------------------------------------------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | | | 16 (100)| | 3 |00:00:00.03 | 28 | 23 | |* 1 | HASH JOIN | | 1 | 3 | 387 | 16 (19)| 00:00:01 | 3 |00:00:00.03 | 28 | 23 | | 2 | TABLE ACCESS FULL | REGIONS | 1 | 4 | 56 | 3 (0)| 00:00:01 | 4 |00:00:00.01 | 7 | 6 | |* 3 | HASH JOIN | | 1 | 3 | 345 | 12 (17)| 00:00:01 | 3 |00:00:00.02 | 21 | 17 | | 4 | INDEX FULL SCAN | COUNTRY_C_ID_PK | 1 | 25 | 375 | 1 (0)| 00:00:01 | 25 |00:00:00.01 | 1 | 1 | |* 5 | HASH JOIN | | 1 | 3 | 300 | 11 (19)| 00:00:01 | 3 |00:00:00.02 | 20 | 16 | | 6 | TABLE ACCESS FULL | LOCATIONS | 1 | 23 | 529 | 3 (0)| 00:00:01 | 23 |00:00:00.01 | 7 | 6 | |* 7 | HASH JOIN | | 1 | 3 | 231 | 7 (15)| 00:00:01 | 3 |00:00:00.01 | 13 | 10 | | 8 | TABLE ACCESS BY INDEX ROWID | DEPARTMENTS | 1 | 1 | 19 | 1 (0)| 00:00:01 | 1 |00:00:00.01 | 2 | 2 | |* 9 | INDEX UNIQUE SCAN | DEPT_ID_PK | 1 | 1 | | 0 (0)| | 1 |00:00:00.01 | 1 | 1 | |* 10 | HASH JOIN | | 1 | 3 | 174 | 6 (17)| 00:00:01 | 3 |00:00:00.01 | 11 | 8 | | 11 | TABLE ACCESS FULL | JOBS | 1 | 19 | 513 | 3 (0)| 00:00:01 | 19 |00:00:00.01 | 7 | 6 | | 12 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES | 1 | 3 | 93 | 2 (0)| 00:00:01 | 3 |00:00:00.01 | 4 | 2 | |* 13 | INDEX RANGE SCAN | EMP_DEPARTMENT_IX | 1 | 3 | | 1 (0)| 00:00:01 | 3 |00:00:00.01 | 2 | 1 | ---------------------------------------------------------------------------------------------------------------------------------------------------------
Oracle has a deep bias against bushy trees because they would increase the search space tremendously though someday Oracle may consider using them to handle “snowstorm queries.” However, Oracle is forced to use them when a view is unmergeable. I rewrote my query with an inline view that joins the Departments, Locations, Countries, and Regions tables and I made it unmergeable using the NO_MERGE hint.
SELECT
/*+
LEADING(e j d)
USE_NL(j)
USE_NL(d)
*/
e.first_name,
e.last_name,
e.salary,
j.job_title,
d.department_name,
d.city,
d.state_province,
d.country_name,
d.region_name
FROM
employees e,
jobs j,
(
SELECT
/*+
NO_MERGE
LEADING(d l c r)
USE_NL(l)
USE_NL(c)
USE_NL(r)
*/
d.department_id,
d.department_name,
l.city,
l.state_province,
c.country_name,
r.region_name
FROM
departments d,
locations l,
countries c,
regions r
WHERE
l.location_id = d.location_id
AND c.country_id = l.country_id
AND r.region_id = c.region_id
) d
WHERE
e.department_id = 90
AND j.job_id = e.job_id
AND d.department_id = e.department_id;
Here is the EXPLAIN PLAN for the above query and its graphical representation. The nodes are processed in the order 4, 3, 6, 5, 2, 12, 11, 14, 13, 10, 15, 9, 17, 16, 8, 7, 1, and 0.
--------------------------------------------------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time | A-Rows | A-Time | Buffers | Reads | --------------------------------------------------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | | | 14 (100)| | 3 |00:00:00.20 | 26 | 32 | | 1 | NESTED LOOPS | | 1 | 3 | 465 | 14 (0)| 00:00:01 | 3 |00:00:00.20 | 26 | 32 | | 2 | NESTED LOOPS | | 1 | 3 | 174 | 5 (0)| 00:00:01 | 3 |00:00:00.13 | 9 | 11 | | 3 | TABLE ACCESS BY INDEX ROWID | EMPLOYEES | 1 | 3 | 93 | 2 (0)| 00:00:01 | 3 |00:00:00.06 | 4 | 2 | |* 4 | INDEX RANGE SCAN | EMP_DEPARTMENT_IX | 1 | 3 | | 1 (0)| 00:00:01 | 3 |00:00:00.02 | 2 | 1 | | 5 | TABLE ACCESS BY INDEX ROWID | JOBS | 3 | 1 | 27 | 1 (0)| 00:00:01 | 3 |00:00:00.06 | 5 | 9 | |* 6 | INDEX UNIQUE SCAN | JOB_ID_PK | 3 | 1 | | 0 (0)| | 3 |00:00:00.02 | 2 | 1 | | 7 | VIEW | | 3 | 1 | 97 | 3 (0)| 00:00:01 | 3 |00:00:00.08 | 17 | 21 | | 8 | NESTED LOOPS | | 3 | 1 | 71 | 3 (0)| 00:00:01 | 3 |00:00:00.08 | 17 | 21 | | 9 | NESTED LOOPS | | 3 | 1 | 57 | 2 (0)| 00:00:01 | 3 |00:00:00.05 | 12 | 12 | | 10 | NESTED LOOPS | | 3 | 1 | 42 | 2 (0)| 00:00:01 | 3 |00:00:00.04 | 10 | 11 | | 11 | TABLE ACCESS BY INDEX ROWID| DEPARTMENTS | 3 | 1 | 19 | 1 (0)| 00:00:01 | 3 |00:00:00.01 | 5 | 2 | |* 12 | INDEX UNIQUE SCAN | DEPT_ID_PK | 3 | 1 | | 0 (0)| | 3 |00:00:00.01 | 2 | 1 | | 13 | TABLE ACCESS BY INDEX ROWID| LOCATIONS | 3 | 1 | 23 | 1 (0)| 00:00:01 | 3 |00:00:00.02 | 5 | 9 | |* 14 | INDEX UNIQUE SCAN | LOC_ID_PK | 3 | 1 | | 0 (0)| | 3 |00:00:00.01 | 2 | 1 | |* 15 | INDEX UNIQUE SCAN | COUNTRY_C_ID_PK | 3 | 1 | 15 | 0 (0)| | 3 |00:00:00.01 | 2 | 1 | | 16 | TABLE ACCESS BY INDEX ROWID | REGIONS | 3 | 1 | 14 | 1 (0)| 00:00:01 | 3 |00:00:00.02 | 5 | 9 | |* 17 | INDEX UNIQUE SCAN | REG_ID_PK | 3 | 1 | | 0 (0)| | 3 |00:00:00.02 | 2 | 1 | ---------------------------------------------------------------------------------------------------------------------------------------------------------
Happy Holidays.
P.S. The program that I used to generate the above pictures can be downloaded from https://iggyfernandez.files.wordpress.com/2010/11/enhanced-plan.doc. It prompts for a SQL_ID and CHILD_NUMBER, retrieves the basic plan information from V$SQL_PLAN_STATISTICS_ALL, determines the order in which the steps are executed, computes the execution time for each step, and labels the nodes in the graph. It’s a longish script but I’ve modularized it using common table expressions and provided a lot of inline comments. I hope you find it useful. Feedback and suggestions are welcome.
Leave a comment
So Many Oracle Manuals, So Little Time 
Iggy,
I’ve been looking at the last Plan (bushy tree) and i couldn’t understand what Start = 3 means for steps 6,7,8,9. Can you pls explain?
Many thanks,
Dani
Iggy,
Once again, many thanks for this excellent post. It made me understand the terms “Deep Left Tree”, “Deep Right Tree” and “Bushy Trees” clearly.
Dany,
The “Starts=3” against those steps (and some other steps) indicates how many times that particular step was invoked. If you see, the step 6 (which leads to step 5) is driven by the NESTED LOOP join in step 2. The NESTED LOOP join in step 2 uses step 3 as the driving row source and since it produces 3 rows, the step 6 (and 5) are invoked for each of the 3 rows and hence the “Starts=3”. Similarly, stpes 7 onwards are driven by the NESTED LOOP join in step 1. The NESTED LOOP join in step 1 uses step 2 as the driving row source and since it produces 3 rows, the step 7 onwards are invoked for each of the 3 rows and hence the “Starts=3”. Hope this helps (or else Iggy would be able to explain it much better).
Thank you Narendra. You’re very welcome.
Very interesting try of visualization.
I’d like to try it(Grpahviz) myself someday!
Good Explanation with diagrams.
Thank You.
Similar diagrams are available in the Plan tab of SQL Monitor reports as well.
Yes, diagrams are available in Oracle Enterprise Manager 11g Tuning Pack. I’ve provided a picture at https://iggyfernandez.files.wordpress.com/2010/11/monitored-sql-execution-details.jpg with the table names blacked out.
Thank you very much Narendra! and Iggy of course 🙂
Very Interesting. Thanks for all the information
I can’t Find that Script. I think link is broken
Thanks, Taral. The link https://iggyfernandez.files.wordpress.com/2010/11/enhanced-plan.doc works for me. Contact me at iggy_fernandez@hotmail.com and I’ll send it to you by email. Cheers.
Hi Iggy,
Nice write up on the left deep, right deep and busy joins. I tried to access your tool but getting an error on that URL. I tried some of these layouts in DB Optimizer and blogged about it here: http://dboptimizer.com/2011/12/09/right-deep-left-deep-and-bushy-joins/
– Kyle