Home > DBA, Oracle, SQL > Day 6: The Twelve Days of SQL: The execution plan is a tree

Day 6: The Twelve Days of SQL: The execution plan is a tree


On the sixth day of Christmas, my true love gave to me
Six geese a-laying.

Day 6: The execution plan is a tree (Day 5: The query cost is only an estimate)(Day 7: EXPLAIN PLAN lies)

An execution plan is a tree. This is not very obvious from the listing of DBMS_XPLAN or EXPLAIN PLAN but some pictures will illustrate the point (click on them to enlarge them). The following query joins the Employees table to the Jobs, Departments, Locations, Countries, and Regions tables. The embedded hints are necessary only for demonstration purposes; they ensured that the query optimizer did precisely what was intended. I conducted my tests using Oracle Database 11g Release 2 and the Developer Days Virtual Machine.

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;

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

Plan hash value: 3611145642

-------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                         | Name              | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time   | A-Rows |   A-Time   | Buffers |
-------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                  |                   |      1 |        |       |     2 (100)|          |      3 |00:00:00.01 |      26 |
|   1 |  NESTED LOOPS                     |                   |      1 |        |       |            |          |      3 |00:00:00.01 |      26 |
|   2 |   NESTED LOOPS                    |                   |      1 |      3 |   726 |     2   (0)| 00:00:01 |      3 |00:00:00.01 |      23 |
|   3 |    NESTED LOOPS                   |                   |      1 |      3 |   645 |     2   (0)| 00:00:01 |      3 |00:00:00.01 |      21 |
|   4 |     NESTED LOOPS                  |                   |      1 |      3 |   528 |     2   (0)| 00:00:01 |      3 |00:00:00.01 |      19 |
|   5 |      NESTED LOOPS                 |                   |      1 |      3 |   384 |     2   (0)| 00:00:01 |      3 |00:00:00.01 |      14 |
|   6 |       NESTED LOOPS                |                   |      1 |      3 |   255 |     2   (0)| 00:00:01 |      3 |00:00:00.01 |       9 |
|   7 |        TABLE ACCESS BY INDEX ROWID| EMPLOYEES         |      1 |      3 |   177 |     2   (0)| 00:00:01 |      3 |00:00:00.01 |       4 |
|*  8 |         INDEX RANGE SCAN          | EMP_DEPARTMENT_IX |      1 |      3 |       |     1   (0)| 00:00:01 |      3 |00:00:00.01 |       2 |
|   9 |        TABLE ACCESS BY INDEX ROWID| JOBS              |      3 |      1 |    26 |     0   (0)|          |      3 |00:00:00.01 |       5 |
|* 10 |         INDEX UNIQUE SCAN         | JOB_ID_PK         |      3 |      1 |       |     0   (0)|          |      3 |00:00:00.01 |       2 |
|  11 |       TABLE ACCESS BY INDEX ROWID | DEPARTMENTS       |      3 |      1 |    43 |     0   (0)|          |      3 |00:00:00.01 |       5 |
|* 12 |        INDEX UNIQUE SCAN          | DEPT_ID_PK        |      3 |      1 |       |     0   (0)|          |      3 |00:00:00.01 |       2 |
|  13 |      TABLE ACCESS BY INDEX ROWID  | LOCATIONS         |      3 |      1 |    48 |     0   (0)|          |      3 |00:00:00.01 |       5 |
|* 14 |       INDEX UNIQUE SCAN           | LOC_ID_PK         |      3 |      1 |       |     0   (0)|          |      3 |00:00:00.01 |       2 |
|* 15 |     INDEX UNIQUE SCAN             | COUNTRY_C_ID_PK   |      3 |      1 |    39 |     0   (0)|          |      3 |00:00:00.01 |       2 |
|* 16 |    INDEX UNIQUE SCAN              | REG_ID_PK         |      3 |      1 |       |     0   (0)|          |      3 |00:00:00.01 |       2 |
|  17 |   TABLE ACCESS BY INDEX ROWID     | REGIONS           |      3 |      1 |    27 |     0   (0)|          |      3 |00:00:00.01 |       3 |
-------------------------------------------------------------------------------------------------------------------------------------------------

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

The above tree is what is called a “deep-left tree.” Notice that DBMS_XPLAN lists the nodes of the tree in “pre-order” fashion (parent, left node, right node). However, the tree is meant to be traversed in “post-order” fashion (left node, parent, right node). Other types of trees are “deep-right trees,” “zigzag trees,” and “bushy trees.” Deep right trees are important in data warehouses to join large fact tables to small dimension tables using hash joins.[1] Using the following hints in the previous query will produce a deep-right tree. It is a very interesting query plan; rows from the Employees table are filtered using five separate hash tables.

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

Plan hash value: 2503296155

------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                        | Name              | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time   | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                 |                   |      1 |        |       |    16 (100)|          |      3 |00:00:00.28 |      31 |
|*  1 |  HASH JOIN                       |                   |      1 |      3 |   726 |    16  (19)| 00:00:01 |      3 |00:00:00.28 |      31 |
|   2 |   TABLE ACCESS FULL              | REGIONS           |      1 |      4 |   108 |     3   (0)| 00:00:01 |      4 |00:00:00.01 |       7 |
|*  3 |   HASH JOIN                      |                   |      1 |      3 |   645 |    12  (17)| 00:00:01 |      3 |00:00:00.28 |      24 |
|   4 |    INDEX FAST FULL SCAN          | COUNTRY_C_ID_PK   |      1 |     25 |   975 |     2   (0)| 00:00:01 |     25 |00:00:00.01 |       4 |
|*  5 |    HASH JOIN                     |                   |      1 |      3 |   528 |    10  (20)| 00:00:01 |      3 |00:00:00.23 |      20 |
|   6 |     TABLE ACCESS FULL            | LOCATIONS         |      1 |     23 |  1104 |     3   (0)| 00:00:01 |     23 |00:00:00.01 |       7 |
|*  7 |     HASH JOIN                    |                   |      1 |      3 |   384 |     6  (17)| 00:00:01 |      3 |00:00:00.12 |      13 |
|   8 |      TABLE ACCESS BY INDEX ROWID | DEPARTMENTS       |      1 |      1 |    43 |     0   (0)|          |      1 |00:00:00.01 |       2 |
|*  9 |       INDEX UNIQUE SCAN          | DEPT_ID_PK        |      1 |      1 |       |     0   (0)|          |      1 |00:00:00.01 |       1 |
|* 10 |      HASH JOIN                   |                   |      1 |      3 |   255 |     6  (17)| 00:00:01 |      3 |00:00:00.08 |      11 |
|  11 |       TABLE ACCESS FULL          | JOBS              |      1 |     19 |   494 |     3   (0)| 00:00:01 |     19 |00:00:00.01 |       7 |
|  12 |       TABLE ACCESS BY INDEX ROWID| EMPLOYEES         |      1 |      3 |   177 |     2   (0)| 00:00:01 |      3 |00:00:00.01 |       4 |
|* 13 |        INDEX RANGE SCAN          | EMP_DEPARTMENT_IX |      1 |      3 |       |     1   (0)| 00:00:01 |      3 |00:00:00.01 |       2 |
------------------------------------------------------------------------------------------------------------------------------------------------

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)

Query plans that use hash joins can be zigzag trees because hash tables are best constructed from the smaller of two inputs. 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)
  */

Plan hash value: 72990389

------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                        | Name              | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time   | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                 |                   |      1 |        |       |    16 (100)|          |      3 |00:00:00.14 |      30 |
|*  1 |  HASH JOIN                       |                   |      1 |      3 |   726 |    16  (19)| 00:00:01 |      3 |00:00:00.14 |      30 |
|   2 |   TABLE ACCESS FULL              | REGIONS           |      1 |      4 |   108 |     3   (0)| 00:00:01 |      4 |00:00:00.01 |       7 |
|*  3 |   HASH JOIN                      |                   |      1 |      3 |   645 |    12  (17)| 00:00:01 |      3 |00:00:00.14 |      23 |
|*  4 |    HASH JOIN                     |                   |      1 |      3 |   528 |    10  (20)| 00:00:01 |      3 |00:00:00.14 |      18 |
|   5 |     TABLE ACCESS FULL            | LOCATIONS         |      1 |     23 |  1104 |     3   (0)| 00:00:01 |     23 |00:00:00.01 |       7 |
|*  6 |     HASH JOIN                    |                   |      1 |      3 |   384 |     6  (17)| 00:00:01 |      3 |00:00:00.11 |      11 |
|*  7 |      HASH JOIN                   |                   |      1 |      3 |   255 |     6  (17)| 00:00:01 |      3 |00:00:00.09 |       9 |
|   8 |       TABLE ACCESS FULL          | JOBS              |      1 |     19 |   494 |     3   (0)| 00:00:01 |     19 |00:00:00.01 |       7 |
|   9 |       TABLE ACCESS BY INDEX ROWID| EMPLOYEES         |      1 |      3 |   177 |     2   (0)| 00:00:01 |      3 |00:00:00.01 |       2 |
|* 10 |        INDEX RANGE SCAN          | EMP_DEPARTMENT_IX |      1 |      3 |       |     1   (0)| 00:00:01 |      3 |00:00:00.01 |       1 |
|  11 |      TABLE ACCESS BY INDEX ROWID | DEPARTMENTS       |      1 |      1 |    43 |     0   (0)|          |      1 |00:00:00.01 |       2 |
|* 12 |       INDEX UNIQUE SCAN          | DEPT_ID_PK        |      1 |      1 |       |     0   (0)|          |      1 |00:00:00.01 |       1 |
|  13 |    INDEX FAST FULL SCAN          | COUNTRY_C_ID_PK   |      1 |     25 |   975 |     2   (0)| 00:00:01 |     25 |00:00:00.01 |       5 |
------------------------------------------------------------------------------------------------------------------------------------------------

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)

The query optimizer has a deep bias against bushy trees because they increase the search space tremendously though someday they may be considered for “snowstorm queries.” However, the query optimizer is forced to use a bushy tree 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;

Plan hash value: 3870228517

------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                        | Name              | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time   | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                 |                   |      1 |        |       |     2 (100)|          |      3 |00:00:00.01 |      26 |
|   1 |  NESTED LOOPS                    |                   |      1 |      3 |   546 |     2   (0)| 00:00:01 |      3 |00:00:00.01 |      26 |
|   2 |   NESTED LOOPS                   |                   |      1 |      3 |   255 |     2   (0)| 00:00:01 |      3 |00:00:00.01 |       9 |
|   3 |    TABLE ACCESS BY INDEX ROWID   | EMPLOYEES         |      1 |      3 |   177 |     2   (0)| 00:00:01 |      3 |00:00:00.01 |       4 |
|*  4 |     INDEX RANGE SCAN             | EMP_DEPARTMENT_IX |      1 |      3 |       |     1   (0)| 00:00:01 |      3 |00:00:00.01 |       2 |
|   5 |    TABLE ACCESS BY INDEX ROWID   | JOBS              |      3 |      1 |    26 |     0   (0)|          |      3 |00:00:00.01 |       5 |
|*  6 |     INDEX UNIQUE SCAN            | JOB_ID_PK         |      3 |      1 |       |     0   (0)|          |      3 |00:00:00.01 |       2 |
|   7 |   VIEW                           |                   |      3 |      1 |    97 |     0   (0)|          |      3 |00:00:00.01 |      17 |
|   8 |    NESTED LOOPS                  |                   |      3 |      1 |   157 |     0   (0)|          |      3 |00:00:00.01 |      17 |
|   9 |     NESTED LOOPS                 |                   |      3 |      1 |   130 |     0   (0)|          |      3 |00:00:00.01 |      12 |
|  10 |      NESTED LOOPS                |                   |      3 |      1 |    91 |     0   (0)|          |      3 |00:00:00.01 |      10 |
|  11 |       TABLE ACCESS BY INDEX ROWID| DEPARTMENTS       |      3 |      1 |    43 |     0   (0)|          |      3 |00:00:00.01 |       5 |
|* 12 |        INDEX UNIQUE SCAN         | DEPT_ID_PK        |      3 |      1 |       |     0   (0)|          |      3 |00:00:00.01 |       2 |
|  13 |       TABLE ACCESS BY INDEX ROWID| LOCATIONS         |      3 |      1 |    48 |     0   (0)|          |      3 |00:00:00.01 |       5 |
|* 14 |        INDEX UNIQUE SCAN         | LOC_ID_PK         |      3 |      1 |       |     0   (0)|          |      3 |00:00:00.01 |       2 |
|* 15 |      INDEX UNIQUE SCAN           | COUNTRY_C_ID_PK   |      3 |      1 |    39 |     0   (0)|          |      3 |00:00:00.01 |       2 |
|  16 |     TABLE ACCESS BY INDEX ROWID  | REGIONS           |      3 |      1 |    27 |     0   (0)|          |      3 |00:00:00.01 |       5 |
|* 17 |      INDEX UNIQUE SCAN           | REG_ID_PK         |      3 |      1 |       |     0   (0)|          |      3 |00:00:00.01 |       2 |
------------------------------------------------------------------------------------------------------------------------------------------------

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

You may ask the question; how many different trees are possible for any given query. The answer is very large. There are N! (N factorial) ways in which N tables can be joined in deep-left fashion or deep-right fashion. The total number of ways in which N tables can be joined is (2(N-1))!/(N-1)! (http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics). For five tables that’s 1,680 and for six tables it’s 30,240.

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.

Day 5: The query cost is only an estimate

Day 7: EXPLAIN PLAN lies

1 “A dimensional database design has a fixed structure that has no alternative join paths. This greatly simplifies the optimization and evaluation of queries on these schemas. There is only one basic evaluation approach, along with a ‘bail out’ option. First, you evaluate the constraints on all of the dimension tables. Then you prepare a long sorted list of composite keys to the fact table. You scan the fact table composite index in sorted order once, fetching all of the required records into the answer set. Period. The only exception to scanning the fact table index occurs when you notice that your dimensional constraints are so weak that you have an unreasonably long list of composite candidate keys. ‘Unreasonably long’ should be several times the number of actual records in the fact table. At this point—and before attempting to scan the index—you bail out to a relation scan in which you look at every fact table record without using any indexes.” (Ralph Kimball, Is ER Modeling Hazardous to DSS?, DBMS and Internet Systems, October 1995)

Categories: DBA, Oracle, SQL
  1. No comments yet.
  1. No trackbacks yet.

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: