How the Query Optimizer Executes Join Statements
To choose an execution plan for a join statement, the optimizer must make these interrelated decisions:· Access Paths
· Join Method
Join methods include nested loop, sort merge, cartesian, and hash joins.
· Join Order
How the Query Optimizer Chooses Execution Plans for Joins
The optimizer estimates costs in the following ways:· The cost of a nested loops operation is based on the cost of reading each selected row of the outer table and each of its matching rows of the inner table into memory. The optimizer estimates these costs using the statistics in the data dictionary.
· The cost of a sort merge join is based largely on the cost of reading all the sources into memory and sorting them.
· The cost of a hash join is based largely on the cost of building a hash table on one of the input sides to the join and using the rows from the other of the join to probe it.
The optimizer also considers other factors when determining the cost of each operation. For example:· A smaller sort area size is likely to increase the cost for a sort merge join because sorting takes more CPU time and I/O in a smaller sort area.
· A larger multiblock read count is likely to decrease the cost for a sort merge join in relation to a nested loop join. If a large number of sequential blocks can be read from disk in a single I/O, then an index on the inner table for the nested loop join is less likely to improve performance over a full table scan. The multiblock read count is specified by the initialization parameter
With the query optimizer, the optimizer's choice of join orders can be overridden with the DB_FILE_MULTIBLOCK_READ_COUNT.ORDERED hint. If the ORDERED hint specifies a join order that violates the rule for an outer join, then the optimizer ignores the hint and chooses the order. Also, you can override the optimizer's choice of join method with hints.Nested Loop Joins
Nested loop joins are useful when small subsets of data are being joined and if the join condition is an efficient way of accessing the second table.A nested loop join involves the following steps:
1. The optimizer determines the driving table and designates it as the outer table.
2. The other table is designated as the inner table.
3. For every row in the outer table, Oracle accesses all the rows in the inner table. The outer loop is for every row in outer table and the inner loop is for every row in the inner table. The outer loop appears before the inner loop in the execution plan, as follows:
NESTED LOOPS outer_loop inner_loop Nested Loop Example
...| 2 | NESTED LOOPS | | 3 | 141 | 7 (15)||* 3 | TABLE ACCESS FULL | EMPLOYEES | 3 | 60 | 4 (25)|| 4 | TABLE ACCESS BY INDEX ROWID| JOBS | 19 | 513 | 2 (50)||* 5 | INDEX UNIQUE SCAN | JOB_ID_PK | 1 | | |...In this example, the outer loop retrieves all the rows of the employees table.For every employee retrieved by the outer loop, the inner loop retrieves the associated row in the
jobs table.Nested Loop Join Hints
If the optimizer is choosing to use some other join method, you can use the
USE_NL(table1 table2) hint, where table1 and table2 are the aliases of the tables being joined.Hash Joins
Hash joins are used for joining large data sets. The optimizer uses the smaller of two tables or data sources to build a hash table on the join key in memory. It then scans the larger table, probing the hash table to find the joined rows.This method is best used when the smaller table fits in available memory. The cost is then limited to a single read pass over the data for the two tables.
When the Optimizer Uses Hash Joins
The optimizer uses a hash join to join two tables if they are joined using an equijoin and if either of the following conditions are true:· A large amount of data needs to be joined.
· A large fraction of a small table needs to be joined.
In below Example, the table
orders is used to build the hash table, and order_items is the larger table, which is scanned later.SELECT o.customer_id, l.unit_price * l.quantity FROM orders o ,order_items l WHERE l.order_id = o.order_id;--------------------------------------------------------------------------| Id | Operation | Name | Rows | Bytes | Cost (%CPU)|--------------------------------------------------------------------------| 0 | SELECT STATEMENT | | 665 | 13300 | 8 (25)||* 1 | HASH JOIN | | 665 | 13300 | 8 (25)|| 2 | TABLE ACCESS FULL | ORDERS | 105 | 840 | 4 (25)|| 3 | TABLE ACCESS FULL | ORDER_ITEMS | 665 | 7980 | 4 (25)|--------------------------------------------------------------------------Predicate Information (identified by operation id):--------------------------------------------------- 1 - access("L"."ORDER_ID"="O"."ORDER_ID")Hash Join Hints
Apply the
USE_HASH hint to instruct the optimizer to use a hash join when joining two tables togetherSort Merge Joins
Sort merge joins can be used to join rows from two independent sources. Hash joins generally perform better than sort merge joins. On the other hand, sort merge joins can perform better than hash joins if both of the following conditions exist:· The row sources are sorted already.
· A sort operation does not have to be done.
However, if a sort merge join involves choosing a slower access method (an index scan as opposed to a full table scan), then the benefit of using a sort merge might be lost.Sort merge joins are useful when the join condition between two tables is an inequality condition (but not a nonequality) like <, <=, >, or >=. Sort merge joins perform better than nested loop joins for large data sets. You cannot use hash joins unless there is an equality condition.
In a merge join, there is no concept of a driving table. The join consists of two steps:
1. Sort join operation: Both the inputs are sorted on the join key.
2. Merge join operation: The sorted lists are merged together.
If the input is already sorted by the join column, then a sort join operation is not performed for that row source.When the Optimizer Uses Sort Merge Joins
The optimizer can choose a sort merge join over a hash join for joining large amounts of data if any of the following conditions are true:· The join condition between two tables is not an equi-join.
· Because of sorts already required by other operations, the optimizer finds it is cheaper to use a sort merge than a hash join.
Sort Merge Join Hints
To instruct the optimizer to use a sort merge join, apply theUSE_MERGE hint. You might also need to give hints to force an access path.There are situations where it is better to override the optimize with the
USE_MERGE hint. For example, the optimizer can choose a full scan on a table and avoid a sort operation in a query. However, there is an increased cost because a large table is accessed through an index and single block reads, as opposed to faster access through a full table scan.Cartesian Joins
A Cartesian join is used when one or more of the tables does not have any join conditions to any other tables in the statement.The optimizer joins every row from one data source with every row from the other data source, creating the Cartesian product of the two sets.
When the Optimizer Uses Cartesian Joins
The optimizer uses Cartesian joins when it is asked to join two tables with no join conditions. In some cases, a common filter condition between the two tables could be picked up by the optimizer as a possible join condition. In other cases, the optimizer may decide to generate a Cartesian product of two very small tables that are both joined to the same large table.Cartesian Join Hints
Applying the
ORDERED hint, instructs the optimizer to use a Cartesian join. By specifying a table before its join table is specified, the optimizer does a Cartesian join.Outer Joins
An outer join extends the result of a simple join. An outer join returns all rows that satisfy the join condition and also returns some or all of those rows from one table for which no rows from the other satisfy the join condition.Nested Loop Outer Joins
The optimizer uses nested loop joins to process an outer join in the following circumstances:· It is possible to drive from the outer table to inner table.
· Data volume is low enough to make the nested loop method efficient.
For an example of a nested loop outer join, you can add the USE_NL hint to instruct the optimizer to use a nested loop. For example:SELECT /*+ USE_NL(c o) */ cust_last_name, sum(nvl2(o.customer_id,0,1)) "Count"Hash Join Outer Joins
Sort Merge Outer Joins
When an outer join cannot drive from the outer (preserved) table to the inner (optional) table, it cannot use a hash join or nested loop joins. Then it uses the sort merge outer join for performing the join operation.The optimizer uses sort merge for an outer join:
· If a nested loop join is inefficient. A nested loop join can be inefficient because of data volumes.
· The optimizer finds it is cheaper to use a sort merge over a hash join because of sorts already required by other operations.
No comments:
Post a Comment