Home > Oracle, SQL > SQL 101: Deep Left Trees, Deep Right Trees, and Bushy Trees! Oh, My!

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.

Categories: Oracle, SQL
  1. DanyC
    November 28, 2010 at 5:08 am

    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

  2. Narendra
    November 28, 2010 at 5:46 am

    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).

  3. Iggy Fernandez
    November 28, 2010 at 9:33 am

    Thank you Narendra. You’re very welcome.

  4. Dion Cho
    November 28, 2010 at 9:07 pm

    Very interesting try of visualization.

    I’d like to try it(Grpahviz) myself someday!

  5. November 29, 2010 at 12:17 am

    Good Explanation with diagrams.
    Thank You.

  6. November 29, 2010 at 7:50 pm

    Similar diagrams are available in the Plan tab of SQL Monitor reports as well.

  7. Iggy Fernandez
    November 29, 2010 at 9:17 pm

    Greg Rahn :

    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.

  8. DanyC
    November 30, 2010 at 2:01 am

    Narendra :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 very much Narendra! and Iggy of course🙂

  9. October 28, 2011 at 7:02 am

    Very Interesting. Thanks for all the information

    I can’t Find that Script. I think link is broken

  10. Iggy Fernandez
    November 1, 2011 at 6:26 pm

    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.

  11. December 9, 2011 at 3:40 pm

    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

  1. December 9, 2011 at 3:22 pm
  2. May 5, 2014 at 12:28 pm
  3. August 1, 2016 at 3:22 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: