If all the seas were one sea,
What a great sea that would be!
And if all the trees were one tree,
What a great tree that would be!
And if all the axes were one axe,
What a great axe that would be!
And if all the men were one man,
What a great man he would be!
And if the great man took the great axe,
And cut down the great tree,
And let it fall into the great sea,
What a splish, splash, that would be!

Mother Goose

Previous installment: Don’t pre-order your EXPLAIN PLAN
Next installment: A Forest Hymn
First installment: DON’T PANIC

Test your new found knowledge against different kinds of EXPLAIN PLAN trees. EXPLAIN PLAN trees can be classified into four varieties: deep-left trees, deep-right trees, zigzag trees, and bushy trees. Each of the four queries below 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. The queries are equivalent but hints are used to force a specific kind of plan tree to be used.

Deep-left trees

Deep left trees are very common because of the strategy used by the Oracle optimizer. The optimizer first picks a “driving” table and then begins to join tables to it. This naturally produces the shape in Figure 1.

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

The query plan should be read in the following sequence: 8, 7, 10, 9, 6, 12, 11, 5, 14, 13, 4, 15, 3, 16, 2, 17, 1, 0.

Plan hash value: 3611145642

---------------------------------------------------------------
| Id  | Operation                         | Name              |
---------------------------------------------------------------
|   0 | SELECT STATEMENT                  |                   |
|   1 |  NESTED LOOPS                     |                   |
|   2 |   NESTED LOOPS                    |                   |
|   3 |    NESTED LOOPS                   |                   |
|   4 |     NESTED LOOPS                  |                   |
|   5 |      NESTED LOOPS                 |                   |
|   6 |       NESTED LOOPS                |                   |
|   7 |        TABLE ACCESS BY INDEX ROWID| EMPLOYEES         |
|   8 |         INDEX RANGE SCAN          | EMP_DEPARTMENT_IX |
|   9 |        TABLE ACCESS BY INDEX ROWID| JOBS              |
|  10 |         INDEX UNIQUE SCAN         | JOB_ID_PK         |
|  11 |       TABLE ACCESS BY INDEX ROWID | DEPARTMENTS       |
|  12 |        INDEX UNIQUE SCAN          | DEPT_ID_PK        |
|  13 |      TABLE ACCESS BY INDEX ROWID  | LOCATIONS         |
|  14 |       INDEX UNIQUE SCAN           | LOC_ID_PK         |
|  15 |     INDEX UNIQUE SCAN             | COUNTRY_C_ID_PK   |
|  16 |    INDEX UNIQUE SCAN              | REG_ID_PK         |
|  17 |   TABLE ACCESS BY INDEX ROWID     | REGIONS           |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   8 - access("E"."DEPARTMENT_ID"=90)
  10 - access("J"."JOB_ID"="E"."JOB_ID")
  12 - access("D"."DEPARTMENT_ID"=90)
  14 - access("L"."LOCATION_ID"="D"."LOCATION_ID")
  15 - access("C"."COUNTRY_ID"="L"."COUNTRY_ID")
  16 - access("R"."REGION_ID"="C"."REGION_ID")

Figure 1: Deep-left tree (Click on the image to see the high-resolution version in a new window)

Deep-right trees

Deep-right trees are important in data warehouses to join large fact tables to small dimension tables using hash joins. Using the following hints in the previous query will produce a deep-right tree.

  /*+
  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)
  */

The query plan should be read in the following sequence: 2, 4, 6, 9, 8, 11, 13, 12, 10, 7, 5, 3, 1, 0. It is a very interesting query plan; rows from the Employees table are filtered using five separate hash tables.

Plan hash value: 2503296155

--------------------------------------------------------------
| Id  | Operation                        | Name              |
--------------------------------------------------------------
|   0 | SELECT STATEMENT                 |                   |
|   1 |  HASH JOIN                       |                   |
|   2 |   TABLE ACCESS FULL              | REGIONS           |
|   3 |   HASH JOIN                      |                   |
|   4 |    INDEX FAST FULL SCAN          | COUNTRY_C_ID_PK   |
|   5 |    HASH JOIN                     |                   |
|   6 |     TABLE ACCESS FULL            | LOCATIONS         |
|   7 |     HASH JOIN                    |                   |
|   8 |      TABLE ACCESS BY INDEX ROWID | DEPARTMENTS       |
|   9 |       INDEX UNIQUE SCAN          | DEPT_ID_PK        |
|  10 |      HASH JOIN                   |                   |
|  11 |       TABLE ACCESS FULL          | JOBS              |
|  12 |       TABLE ACCESS BY INDEX ROWID| EMPLOYEES         |
|  13 |        INDEX RANGE SCAN          | EMP_DEPARTMENT_IX |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("R"."REGION_ID"="C"."REGION_ID")
   3 - access("C"."COUNTRY_ID"="L"."COUNTRY_ID")
   5 - access("L"."LOCATION_ID"="D"."LOCATION_ID")
   7 - access("D"."DEPARTMENT_ID"="E"."DEPARTMENT_ID")
   9 - access("D"."DEPARTMENT_ID"=90)
  10 - access("J"."JOB_ID"="E"."JOB_ID")
  13 - access("E"."DEPARTMENT_ID"=90)

Figure 2: Deep-right tree (Click on the image to see the high-resolution version in a new window)

Zigzag trees

Hash tables are best constructed from the smaller of the inputs so Oracle will switch the order of the inputs when it believes it is necessary. Zigzag trees are therefore very common. The following hints will result in a zigzag tree.

  /*+
  LEADING (e j d l c r)
  USE_HASH(j) SWAP_JOIN_INPUTS(j)
  USE_HASH(d) NO_SWAP_JOIN_INPUTS(d)
  USE_HASH(l) SWAP_JOIN_INPUTS(l)
  USE_HASH(c) NO_SWAP_JOIN_INPUTS(c)
  USE_HASH(r) SWAP_JOIN_INPUTS(r)
  */

The query plan should be read in the following sequence: 2, 5, 8, 10, 9, 7, 12, 11, 6, 4, 13, 3, 1, 0.

Plan hash value: 72990389

--------------------------------------------------------------
| Id  | Operation                        | Name              |
--------------------------------------------------------------
|   0 | SELECT STATEMENT                 |                   |
|   1 |  HASH JOIN                       |                   |
|   2 |   TABLE ACCESS FULL              | REGIONS           |
|   3 |   HASH JOIN                      |                   |
|   4 |    HASH JOIN                     |                   |
|   5 |     TABLE ACCESS FULL            | LOCATIONS         |
|   6 |     HASH JOIN                    |                   |
|   7 |      HASH JOIN                   |                   |
|   8 |       TABLE ACCESS FULL          | JOBS              |
|   9 |       TABLE ACCESS BY INDEX ROWID| EMPLOYEES         |
|  10 |        INDEX RANGE SCAN          | EMP_DEPARTMENT_IX |
|  11 |      TABLE ACCESS BY INDEX ROWID | DEPARTMENTS       |
|  12 |       INDEX UNIQUE SCAN          | DEPT_ID_PK        |
|  13 |    INDEX FAST FULL SCAN          | COUNTRY_C_ID_PK   |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("R"."REGION_ID"="C"."REGION_ID")
   3 - access("C"."COUNTRY_ID"="L"."COUNTRY_ID")
   4 - access("L"."LOCATION_ID"="D"."LOCATION_ID")
   6 - access("D"."DEPARTMENT_ID"="E"."DEPARTMENT_ID")
   7 - access("J"."JOB_ID"="E"."JOB_ID")
  10 - access("E"."DEPARTMENT_ID"=90)
  12 - access("D"."DEPARTMENT_ID"=90)

Figure 3: Zigzag tree (Click on the image to see the high-resolution version in a new window)

Bushy trees

The optimizer does not generally consider bushy trees because they increase the search space beyond its capabilities. However, it is forced to use a bushy tree when faced with an unmergeable view. 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;

The query plan should be read in the following sequence: 4, 3, 6, 5, 2, 12, 11, 14, 13, 10, 15, 9, 17, 16, 8, 7, 1, 0.

Plan hash value: 3870228517

--------------------------------------------------------------
| Id  | Operation                        | Name              |
--------------------------------------------------------------
|   0 | SELECT STATEMENT                 |                   |
|   1 |  NESTED LOOPS                    |                   |
|   2 |   NESTED LOOPS                   |                   |
|   3 |    TABLE ACCESS BY INDEX ROWID   | EMPLOYEES         |
|   4 |     INDEX RANGE SCAN             | EMP_DEPARTMENT_IX |
|   5 |    TABLE ACCESS BY INDEX ROWID   | JOBS              |
|   6 |     INDEX UNIQUE SCAN            | JOB_ID_PK         |
|   7 |   VIEW                           |                   |
|   8 |    NESTED LOOPS                  |                   |
|   9 |     NESTED LOOPS                 |                   |
|  10 |      NESTED LOOPS                |                   |
|  11 |       TABLE ACCESS BY INDEX ROWID| DEPARTMENTS       |
|  12 |        INDEX UNIQUE SCAN         | DEPT_ID_PK        |
|  13 |       TABLE ACCESS BY INDEX ROWID| LOCATIONS         |
|  14 |        INDEX UNIQUE SCAN         | LOC_ID_PK         |
|  15 |      INDEX UNIQUE SCAN           | COUNTRY_C_ID_PK   |
|  16 |     TABLE ACCESS BY INDEX ROWID  | REGIONS           |
|  17 |      INDEX UNIQUE SCAN           | REG_ID_PK         |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("E"."DEPARTMENT_ID"=90)
   6 - access("J"."JOB_ID"="E"."JOB_ID")
  12 - access("D"."DEPARTMENT_ID"=90)
  14 - access("L"."LOCATION_ID"="D"."LOCATION_ID")
  15 - access("C"."COUNTRY_ID"="L"."COUNTRY_ID")
  17 - access("R"."REGION_ID"="C"."REGION_ID")

Figure 4: Bushy tree (Click on the image to see the high-resolution version in a new window)

To be continued.

Previous installment: Don’t pre-order your EXPLAIN PLAN
Next installment: A Forest Hymn
First installment: DON’T PANIC

Copyright © 2014 Iggy Fernandez