Oracle Optimizer's Join Method

A join method is the mechanism for joining two row sources. Depending on the statistics, the optimizer chooses the method with the lowest estimated cost.

This section contains the following topics:

• Nested Loops Joins
• Hash Joins
• Sort Merge Joins
• Cluster Joins

Nested Loop Join

Suppose somebody gave you a telephone book and a list of 20 names to look up, and then asked you to write down each person’s name and corresponding telephone number. You would probably go down the list of names, looking up each one in the telephone book one at a time. This task would be pretty easy because the telephone book is alphabetized by name. Moreover, somebody looking over your shoulder could begin calling the first few numbers you write down while you are still looking up the rest. This scene describes a NESTED LOOPS join.

In a NESTED LOOPS join, Oracle reads the first row from the first row source and then checks the second row source for matches. All matches are then placed in the result set and Oracle goes on to the next row from the first row source. This continues until all rows in the first row source have been processed. The first row source is often called the outer or driving table, whereas the second row source is called the inner table. Using a NESTED LOOPS join is one of the fastest methods of receiving the first records back from a join.

NESTED LOOPS joins are ideal when the driving row source (the records you are looking for) is small and the joined columns of the inner row source are uniquely indexed or have a highly selective nonunique index. NESTED LOOPS joins have an advantage over other join methods in that they can quickly retrieve the first few rows of the result set without having to wait for the entire result set to be determined. This situation is ideal for query screens where an end user can read the first few records retrieved while the rest are being fetched. NESTED LOOPS joins are also flexible in that any two-row sources can always be joined by NESTED LOOPS—regardless of join condition and schema definition.

However, NESTED LOOPS joins can be very inefficient if the inner row source (second table accessed) does not have an index on the joined columns or if the index is not highly selective. If the driving row source (the records retrieved from the driving table) is quite large, other join methods may be more efficient.

Figure 1 below illustrates the method of executing the query shown next where the DEPT table is accessed first and the result is then looped through the EMP table with a NESTED LOOPS join. The type of join performed can be forced with a hint and will vary due to different variables on your system.

Oracle SORT-MERGE Joins

Suppose two salespeople attend a conference and each collect over 100 business cards from potential new customers. They now each have a pile of cards in random order, and they want to see how many cards are duplicated in both piles. The salespeople alphabetize their piles, and then they call off names one at a time. Because both piles of cards have been sorted, it becomes much easier to find the names that appear in both piles. This example describes a SORT-MERGE join.

In a SORT-MERGE join, Oracle sorts the first row source by its join columns, sorts the second row source by its join columns, and then merges the sorted row sources together. As matches are found, they are put into the result set. SORT-MERGE joins can be effective when lack of data selectivity or useful indexes render a NESTED LOOPS join inefficient, or when both of the row sources are quite large (greater than 5 percent of the blocks accessed).

However, SORT-MERGE joins can be used only for equijoins (WHERE D.deptno = E.deptno, as opposed to WHERE D.deptno >= E.deptno). SORT-MERGE joins require temporary segments for sorting (if SORT_AREA_SIZE or the automatic memory parameters like MEMORY_TARGET are set too small). This can lead to extra memory utilization and/or extra disk I/O in the temporary tablespace. Table 1 below illustrates the method of executing the query shown next when a SORT-MERGE join is performed.

 

Table 1. SORT-MERGE join

Oracle HASH Joins

HASH joins are the usual choice of the Oracle optimizer when the memory is set up to accommodate them. In a HASH join, Oracle accesses one table (usually the smaller of the joined results) and builds a hash table on the join key in memory. It then scans the other table in the join (usually the larger one) and probes the hash table for matches to it. Oracle uses a HASH join efficiently only if the parameter PGA_AGGREGATE_TARGET is set to a large enough value. If MEMORY_TARGET is used, the PGA_AGGREGATE_TARGET is included in the MEMORY_TARGET, but you may still want to set a minimum.

If you set the SGA_TARGET, you must set the PGA_AGGREGATE_TARGET as the SGA_TARGET does not include the PGA (unless you use MEMORY_TARGET as just described). The HASH join is similar to a NESTED LOOPS join in the sense that there is a nested loop that occurs—Oracle first builds a hash table to facilitate the operation and then loops through the hash table. When using an ORDERED hint, the first table in the FROM clause is the table used to build the hash table.

HASH joins can be effective when the lack of a useful index renders NESTED LOOPS joins inefficient. The HASH join might be faster than a SORT-MERGE join, in this case, because only one row source needs to be sorted, and it could possibly be faster than a NESTED LOOPS join because probing a hash table in memory can be faster than traversing a b-tree index.

As with SORT-MERGE joins and CLUSTER joins, HASH joins work only on equijoins. As with SORT-MERGE joins, HASH joins use memory resources and can drive up I/O in the temporary tablespace if the sort memory is not sufficient (which can cause this join method to be extremely slow).

Finally, HASH joins are available only when cost-based optimization is used (which should be 100 percent of the time for your application running on Oracle 11g).

Table 1 illustrates the method of executing the query shown in the listing that follows when a HASH join is used.

Table 1. HASH join

 

Oracle CLUSTER Joins

A CLUSTER join in Oracle is really just a special case of the NESTED LOOPS join that is not used very often. If the two row sources being joined are actually tables that are part of a cluster, and if the join is an equijoin between the cluster keys of the two tables, then Oracle can use a CLUSTER join. In this case, Oracle reads each row from the first row source and finds all matches in the second row source by using the CLUSTER index.

CLUSTER joins are extremely efficient because the joining rows in the two row sources will actually be located in the same physical data block. However, clusters carry certain caveats of their own, and you cannot have a CLUSTER join without a cluster. Therefore, CLUSTER joins are not very commonly used.