4 Query Optimizer Concepts

As shown in Figure 4-1, the input to the optimizer is a parsed representation of a SQL statement. Each SELECT block in the original SQL statement is represented internally by a query block. A query block can be a top-level statement, subquery, or unmerged view (see "View Merging").

SELECT first_name, last_name
FROM   hr.employees
WHERE  department_id 
IN     (SELECT department_id 
        FROM   hr.departments 
        WHERE  location_id = 1800);

For each query block, the optimizer generates a query subplan. The database optimizes query blocks separately from the bottom up. Thus, the database optimizes the innermost query block first and generates a subplan for it, and then generates the outer query block representing the entire query.

The number of possible plans for a query block is proportional to the number of objects in the FROM clause. This number rises exponentially with the number of objects. For example, the possible plans for a join of five tables are significantly higher than the possible plans for a join of two tables.

One analogy for the optimizer is an online trip advisor. A cyclist wants to know the most efficient bicycle route from point A to point B. A query is like the directive "I need the most efficient route from point A to point B" or "I need the most efficient route from point A to point B by way of point C." The trip advisor uses an internal algorithm, which relies on factors such as speed and difficulty, to determine the most efficient route. The cyclist can influence the trip advisor's decision by using directives such as "I want to arrive as fast as possible" or "I want the easiest ride possible."

In this analogy, an execution plan is a possible route generated by the trip advisor. Internally, the advisor may divide the overall route into several subroutes (subplans), and calculate the efficiency for each subroute separately. For example, the trip advisor may estimate one subroute at 15 minutes with medium difficulty, an alternative subroute at 22 minutes with minimal difficulty, and so on.

The advisor picks the most efficient (lowest cost) overall route based on user-specified goals and the available statistics about roads and traffic conditions. The more accurate the statistics, the better the advice. For example, if the advisor is not frequently notified of traffic jams, road closures, and poor road conditions, then the recommended route may turn out to be inefficient (high cost).

The selectivity represents a fraction of rows from a row set. The row set can be a base table, a view, or the result of a join. The selectivity is tied to a query predicate, such as last_name = 'Smith', or a combination of predicates, such as last_name = 'Smith' AND job_id = 'SH_CLERK'.

A predicate filters a specific number of rows from a row set. Thus, the selectivity of a predicate indicates how many rows pass the predicate test. Selectivity ranges from 0.0 to 1.0. A selectivity of 0.0 means that no rows are selected from a row set, whereas a selectivity of 1.0 means that all rows are selected. A predicate becomes more selective as the value approaches 0.0 and less selective (or more unselective) as the value approaches 1.0.

The optimizer estimates selectivity depending on whether statistics are available:

• Statistics not available

  Depending on the value of the OPTIMIZER_DYNAMIC_SAMPLING initialization parameter, the optimizer either uses dynamic statistics or an internal default value. The database uses different internal defaults depending on the predicate type. For example, the internal default for an equality predicate (last_name = 'Smith') is lower than for a range predicate (last_name > 'Smith') because an equality predicate is expected to return a smaller fraction of rows.

• Statistics available

  When statistics are available, the estimator uses them to estimate selectivity. Assume there are 150 distinct employee last names. For an equality predicate last_name = 'Smith', selectivity is the reciprocal of the number n of distinct values of last_name, which in this example is .006 because the query selects rows that contain 1 out of 150 distinct values.

  If a histogram exists on the last_name column, then the estimator uses the histogram instead of the number of distinct values. The histogram captures the distribution of different values in a column, so it yields better selectivity estimates, especially for columns that have data skew. See Histograms .

The cardinality is the number of rows returned by each operation in an execution plan. For example, if the optimizer estimate for the number of rows returned by a full table scan is 100, then the cardinality estimate for this operation is 100. The cardinality estimate appears in the Rows column of the execution plan.

The optimizer determines the cardinality for each operation based on a complex set of formulas that use both table and column level statistics, or dynamic statistics, as input. The optimizer uses one of the simplest formulas when a single equality predicate appears in a single-table query, with no histogram. In this case, the optimizer assumes a uniform distribution and calculates the cardinality for the query by dividing the total number of rows in the table by the number of distinct values in the column used in the WHERE clause predicate.

For example, user hr queries the employees table as follows:

SELECT first_name, last_name
FROM   employees
WHERE  salary='10200';

The employees table contains 107 rows. The current database statistics indicate that the number of distinct values in the salary column is 58. Thus, the optimizer calculates the cardinality of the result set as 2, using the formula 107/58=1.84.

Cardinality estimates must be as accurate as possible because they influence all aspects of the execution plan. Cardinality is important when the optimizer determines the cost of a join. For example, in a nested loops join of the employees and departments tables, the number of rows in employees determines how often the database must probe the departments table. Cardinality is also important for determining the cost of sorts.

The optimizer cost model accounts for the I/O, CPU, and network resources that a query is predicted to use. The cost is an internal numeric measure that represents the estimated resource usage for a plan. The lower the cost, the more efficient the plan.

The execution plan displays the cost of the entire plan, which is indicated on line 0, and each individual operation. For example, the following plan shows a cost of 14.

EXPLAINED SQL STATEMENT:
------------------------
SELECT prod_category, AVG(amount_sold) FROM   sales s, products p WHERE
 p.prod_id = s.prod_id GROUP BY prod_category
 
Plan hash value: 4073170114
 
----------------------------------------------------------------------
| Id  | Operation                | Name                 | Cost (%CPU)|
----------------------------------------------------------------------
|   0 | SELECT STATEMENT         |                      |    14 (100)|
|   1 |  HASH GROUP BY           |                      |    14  (22)|
|   2 |   HASH JOIN              |                      |    13  (16)|
|   3 |    VIEW                  | index$_join$_002     |     7  (15)|
|   4 |     HASH JOIN            |                      |            |
|   5 |      INDEX FAST FULL SCAN| PRODUCTS_PK          |     4   (0)|
|   6 |      INDEX FAST FULL SCAN| PRODUCTS_PROD_CAT_IX |     4   (0)|
|   7 |    PARTITION RANGE ALL   |                      |     5   (0)|
|   8 |     TABLE ACCESS FULL    | SALES                |     5   (0)|
----------------------------------------------------------------------

The cost is an internal unit that you can use for plan comparisons. You cannot tune or change it.

The access path determines the number of units of work required to get data from a base table. The access path can be a table scan, a fast full index scan, or an index scan.

• Table scan or fast full index scan

  During a table scan or fast full index scan, the database reads multiple blocks from disk in a single I/O. Therefore, the cost of the scan depends on the number of blocks to be scanned and the multiblock read count value.

• Index scan

  The cost of an index scan depends on the levels in the B-tree, the number of index leaf blocks to be scanned, and the number of rows to be fetched using the rowid in the index keys. The cost of fetching rows using rowids depends on the index clustering factor.

The join cost represents the combination of the individual access costs of the two row sets being joined, plus the cost of the join operation.

The ability of the optimizer to adapt a plan, based on information learned during execution, can greatly improve query performance. Adaptive plans are useful because the optimizer occasionally picks a suboptimal default plan because of a cardinality misestimate. The ability to adapt the plan at run time based on actual execution statistics results in a more optimal final plan. After choosing the final plan, the optimizer uses it for subsequent executions, thus ensuring that the suboptimal plan is not reused.

An adaptive plan contains multiple predetermined subplans, and an optimizer statistics collector. A subplan is a portion of a plan that the optimizer can switch to as an alternative at run time. For example, a nested loops join could be switched to a hash join during execution. An optimizer statistics collector is a row source inserted into a plan at key points to collect run-time statistics. These statistics help the optimizer make a final decision between multiple subplans.

During statement execution, the statistics collector gathers information about the execution, and buffers some rows received by the subplan. Based on the information observed by the collector, the optimizer chooses a subplan. At this point, the collector stops collecting statistics and buffering rows, and permits rows to pass through instead. On subsequent executions of the child cursor, the optimizer continues to use the same plan unless the plan ages out of the cache, or a different optimizer feature (for example, adaptive cursor sharing or statistics feedback) invalidates the plan.

The database uses adaptive plans when OPTIMIZER_FEATURES_ENABLE is 12.1.0.1 or later, and the OPTIMIZER_ADAPTIVE_REPORTING_ONLY initialization parameter is set to the default of false (see "Controlling Adaptive Optimization").

The following query shows a join of the order_items and product_information tables.

SELECT product_name  
FROM   order_items o, product_information p  
WHERE  o.unit_price = 15 
AND    quantity > 1  
AND    p.product_id = o.product_id

An adaptive plan for this statement shows two possible plans, one with a nested loops join and the other with a hash join.

------------------------------------------------------------------------------------------------
|Id | Operation          | Name         |Starts|E-Rows|A-Rows|A-Time|Buff|Reads|OMem|1Mem|O/1/M|
------------------------------------------------------------------------------------------------
| 0| SELECT STATEMENT   |                     |1| | 13|00:00:00.10 |21 |17 |      |      |     |
|*1|  HASH JOIN         |                     |1|4| 13|00:00:00.10 |21 |17 | 2061K| 2061K|1/0/0|
|*2|   TABLE ACCESS FULL| ORDER_ITEMS         |1|4| 13|00:00:00.07 | 5 | 4 |      |      |     |
| 3|   TABLE ACCESS FULL| PRODUCT_INFORMATION |1|1|288|00:00:00.03 |16 |13 |      |      |     |
------------------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - access("P"."PRODUCT_ID"="O"."PRODUCT_ID")
   2 - filter(("O"."UNIT_PRICE"=15 AND "QUANTITY">1))
 
 
PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------------------
Note
-----
   - this is an adaptive plan

A nested loops join is preferable if the database can avoid scanning a significant portion of product_information because its rows are filtered by the join predicate. If few rows are filtered, however, then scanning the right table in a hash join is preferable.

The following graphic shows the adaptive process. For the query in the preceding example, the adaptive portion of the default plan contains two subplans, each of which uses a different join method. The optimizer automatically determines when each join method is optimal, depending on the cardinality of the left side of the join.

The statistics collector buffers enough rows coming from the order_items table to determine which join method to use. If the row count is below the threshold determined by the optimizer, then the optimizer chooses the nested loops join; otherwise, the optimizer chooses the hash join. In this case, the row count coming from the order_items table is above the threshold, so the optimizer chooses a hash join for the final plan, and disables buffering.

Description of the illustration tgsql_vm_076.eps

After the optimizer determines the final plan, DBMS_XPLAN.DISPLAY_CURSOR displays the hash join. The Note section of the execution plan indicates whether the plan is adaptive, as shown in the following sample plan:

------------------------------------------------------------------------------------------------
|Id| Operation          | Name         |Starts|E-Rows|A-Rows|A-Time |Buff|Reads|OMem|1Mem|O/1/M|
------------------------------------------------------------------------------------------------
| 0| SELECT STATEMENT   |                     | 1|   |  13 |00:00:00.10|21|17|     |     |     |
|*1|  HASH JOIN         |                     | 1| 4 |  13 |00:00:00.10|21|17|2061K|2061K|1/0/0|
|*2|   TABLE ACCESS FULL| ORDER_ITEMS         | 1| 4 |  13 |00:00:00.07| 5| 4|     |     |     |
| 3|   TABLE ACCESS FULL| PRODUCT_INFORMATION | 1| 1 | 288 |00:00:00.03|16|13|     |     |     |
------------------------------------------------------------------------------------------------ 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - access("P"."PRODUCT_ID"="O"."PRODUCT_ID")
   2 - filter(("O"."UNIT_PRICE"=15 AND "QUANTITY">1))
 
 
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------
Note
-----
   - this is an adaptive plan

Typically, parallel execution requires data redistribution to perform operations such as parallel sorts, aggregations, and joins. Oracle Database can use many different data distributions methods. The database chooses the method based on the number of rows to be distributed and the number of parallel server processes in the operation.

For example, consider the following alternative cases:

• Many parallel server processes distribute few rows.

  The database may choose the broadcast distribution method. In this case, each row in the result set is sent to each of the parallel server processes.

• Few parallel server processes distribute many rows.

  If a data skew is encountered during the data redistribution, then it could adversely effect the performance of the statement. The database is more likely to pick a hash distribution to ensure that each parallel server process receives an equal number of rows.

The hybrid hash distribution technique is an adaptive parallel data distribution that does not decide the final data distribution method until execution time. The optimizer inserts statistic collectors in front of the parallel server processes on the producer side of the operation. If the actual number of rows is less than a threshold, defined as twice the degree of parallelism (DOP) chosen for the operation, then the data distribution method switches from hash to broadcast. Otherwise, the distribution method is a hash.

Figure 4-6 depicts a hybrid hash join between the departments and employees tables, with a query coordinator directing 8 PX server processes. A statistics collector is inserted in front of the parallel server processes scanning the departments table. The distribution method is based on the run-time statistics. In the example shown in Figure 4-6, the number of rows is below the threshold (8), which is twice the DOP (4), so the optimizer chooses a broadcast technique for the departments table.

Figure 4-6 Adaptive Parallel Query

Description of "Figure 4-6 Adaptive Parallel Query"

Contrast the broadcast distribution example in Figure 4-6 with an example that returns a greater number of rows. In the following plan, the threshold is 8, or twice the specified DOP of 4. However, because the statistics collector (Step 10) discovers that the number of rows (27) is greater than the threshold (8), the optimizer chooses a hybrid hash distribution rather than a broadcast distribution. (The time column should show 00:00:01, but shows 0:01 so the plan can fit the page.)

EXPLAIN PLAN FOR 
  SELECT /*+ parallel(4) full(e) full(d) */ department_name, sum(salary)
  FROM   employees e, departments d
  WHERE  d.department_id=e.department_id
  GROUP BY department_name;

Plan hash value: 2940813933
-----------------------------------------------------------------------------------------------
|Id|Operation                          | Name    |Rows|Bytes|Cost |Time| TQ |IN-OUT|PQ Distrib|
-----------------------------------------------------------------------------------------------
| 0|SELECT STATEMENT                   |DEPARTMENTS| 27|621 |6(34)|0:01|     |    |           |
| 1| PX COORDINATOR                    |           |   |    |     |    |     |    |           |
| 2|  PX SEND QC (RANDOM)              | :TQ10003  | 27|621 |6(34)|0:01|Q1,03|P->S| QC (RAND) |
| 3|   HASH GROUP BY                   |           | 27|621 |6(34)|0:01|Q1,03|PCWP|           |
| 4|    PX RECEIVE                     |           | 27|621 |6(34)|0:01|Q1,03|PCWP|           |
| 5|     PX SEND HASH                  | :TQ10002  | 27|621 |6(34)|0:01|Q1,02|P->P| HASH      |
| 6|      HASH GROUP BY                |           | 27|621 |6(34)|0:01|Q1,02|PCWP|           |
|*7|       HASH JOIN                   |           |106|2438|5(20)|0:01|Q1,02|PCWP|           |
| 8|        PX RECEIVE                 |           | 27|432 |2 (0)|0:01|Q1,02|PCWP|           |
| 9|         PX SEND HYBRID HASH       | :TQ10000  | 27|432 |2 (0)|0:01|Q1,00|P->P|HYBRID HASH|
|10|          STATISTICS COLLECTOR     |           |   |    |     |    |Q1,00|PCWC|           |
|11|           PX BLOCK ITERATOR       |           | 27|432 |2 (0)|0:01|Q1,00|PCWC|           |
|12|            TABLE ACCESS FULL      |DEPARTMENTS| 27|432 |2 (0)|0:01|Q1,00|PCWP|           |
|13|        PX RECEIVE                 |           |107|749 |2 (0)|0:01|Q1,02|PCWP|           |
|14|         PX SEND HYBRID HASH (SKEW)| :TQ10001  |107|749 |2 (0)|0:01|Q1,01|P->P|HYBRID HASH|
|15|          PX BLOCK ITERATOR        |           |107|749 |2 (0)|0:01|Q1,01|PCWC|           |
|16|           TABLE ACCESS FULL       |EMPLOYEES  |107|749 |2 (0)|0:01|Q1,01|PCWP|           |
-----------------------------------------------------------------------------------------------

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

   7 - access("D"."DEPARTMENT_ID"="E"."DEPARTMENT_ID")

Note
-----
   - Degree of Parallelism is 4 because of hint

32 rows selected.

During the compilation of a SQL statement, the optimizer decides whether to use dynamic statistics by considering whether the available statistics are sufficient to generate an optimal execution plan. If the available statistics are insufficient, then the optimizer uses dynamic statistics to augment the statistics. One type of dynamic statistics is the information gathered by dynamic sampling. The optimizer can use dynamic statistics for table scans, index access, joins, and GROUP BY operations, thus improving the quality of optimizer decisions.

Whereas adaptive plans help decide between multiple subplans, they are not feasible for all kinds of plan changes. For example, a query with an inefficient join order might perform suboptimally, but adaptive plans do not support adapting the join order during execution. In these cases, the optimizer considers automatic reoptimization. In contrast to adaptive plans, automatic reoptimization changes a plan on subsequent executions after the initial execution.

At the end of the first execution of a SQL statement, the optimizer uses the information gathered during execution to determine whether automatic reoptimization is worthwhile. If execution informations differs significantly from optimizer estimates, then the optimizer looks for a replacement plan on the next execution. The optimizer uses the information gathered during the previous execution to help determine an alternative plan. The optimizer can reoptimize a query several times, each time learning more and further improving the plan.

A SQL plan directive is additional information that the optimizer uses to generate a more optimal plan. For example, during query optimization, when deciding whether the table is a candidate for dynamic statistics, the database queries the statistics repository for directives on a table. If the query joins two tables that have a data skew in their join columns, a SQL plan directive can direct the optimizer to use dynamic statistics to obtain an accurate cardinality estimate.The optimizer collects SQL plan directives on query expressions rather than at the statement level. In this way, the optimizer can apply directives to multiple SQL statements. The database automatically maintains directives, and stores them in the SYSAUX tablespace. You can manage directives using the package DBMS_SPD.