9 Joins

Nested loops joins are useful when the following conditions are true:

• The database joins small subsets of data, or the database joins large sets of data with the optimizer mode set to FIRST_ROWS (see Table 14-1).

  Note:

  The number of rows expected from the join is what drives the optimizer decision, not the size of the underlying tables. For example, a query might join two tables of a billion rows each, but because of the filters the optimizer expects data sets of 5 rows each.

• The join condition is an efficient method of accessing the inner table.

In general, nested loops joins work best on small tables with indexes on the join conditions. If a row source has only one row, as with an equality lookup on a primary key value (for example, WHERE employee_id=101), then the join is a simple lookup. The optimizer always tries to put the smallest row source first, making it the driving table.

Various factors enter into the optimizer decision to use nested loops. For example, the database may read several rows from the outer row source in a batch. Based on the number of rows retrieved, the optimizer may choose either a nested loop or a hash join to the inner row source (see "Adaptive Plans"). For example, if a query joins departments to driving table employees, and if the predicate specifies a value in employees.last_name, then the database might read enough entries in the index on last_name to determine whether an internal threshold is passed. If the threshold is not passed, then the optimizer picks a nested loop join to departments, and if the threshold is passed, then the database performs a hash join, which means reading the rest of employees, hashing it into memory, and then joining to departments.

If the access path for the inner loop is not dependent on the outer loop, then the result can be a Cartesian product: for every iteration of the outer loop, the inner loop produces the same set of rows. To avoid this problem, use other join methods to join two independent row sources.

Conceptually, nested loops are equivalent to two nested for loops.

For example, if a query joins employees and departments, then a nested loop in pseudocode might be:

FOR erow IN (select * from employees where X=Y) LOOP
  FOR drow IN (select * from departments where erow is matched) LOOP
    output values from erow and drow
  END LOOP
END LOOP

The inner loop is executed for every row of the outer loop. The employees table is the "outer" data set because it is in the exterior for loop. The outer table is sometimes called a driving table. The departments table is the "inner" data set because it is in the interior for loop.

A nested loops join involves the following basic steps:

1. The optimizer determines the driving row source and designates it as the outer loop.

   The outer loop produces a set of rows for driving the join condition. The row source can be a table accessed using an index scan, a full table scan, or any other operation that generates rows.

   The number of iterations of the inner loop depends on the number of rows retrieved in the outer loop. For example, if 10 rows are retrieved from the outer table, then the database must perform 10 lookups in the inner table. If 10,000,000 rows are retrieved from the outer table, then the database must perform 10,000,000 lookups in the inner table.

2. The optimizer designates the other row source as the inner loop.

   The outer loop appears before the inner loop in the execution plan, as follows:

   NESTED LOOPS 
     outer_loop
     inner_loop 
   

3. For every fetch request from the client, the basic process is as follows:

   1. Fetch a row from the outer row source

   2. Probe the inner row source to find rows that match the predicate criteria

   3. Repeat the preceding steps until all rows are obtained by the fetch request

   Sometimes the database sorts rowids to obtain a more efficient buffer access pattern.

The outer loop of a nested loop can itself be a row source generated by a different nested loop. The database can nest two or more outer loops to join as many tables as needed. Each loop is a data access method.

The following template shows how the database iterates through three nested loops:

SELECT STATEMENT
  NESTED LOOPS 3
    NESTED LOOPS 2          - Row source becomes OUTER LOOP 3.1
      NESTED LOOPS 1        - Row source becomes OUTER LOOP 2.1
        OUTER LOOP 1.1
        INNER LOOP 1.2  
      INNER LOOP 2.2
    INNER LOOP 3.2

The database orders the loops as follows:

1. The database iterates through NESTED LOOPS 1:

   NESTED LOOPS 1 
     OUTER LOOP 1.1
     INNER LOOP 1.2
   

   The output of NESTED LOOP 1 is a row source.

2. The database iterates through NESTED LOOPS 2, using the row source generated by NESTED LOOPS 1 as its outer loop:

   NESTED LOOPS 2       
     OUTER LOOP 2.1         - Row source generated by NESTED LOOPS 1
     INNER LOOP 2.2 
   

   The output of NESTED LOOPS 2 is another row source.

3. The database iterates through NESTED LOOPS 3, using the row source generated by NESTED LOOPS 2 as its outer loop:

   NESTED LOOPS 3      
     OUTER LOOP 3.1         - Row source generated by NESTED LOOPS 2
     INNER LOOP 3.2
   

SELECT /*+ ORDERED USE_NL(d) */ e.last_name, e.first_name, d.department_name
FROM   employees e, departments d
WHERE  e.department_id=d.department_id
AND    e.last_name like 'A%';

SQL_ID  ahuavfcv4tnz4, child number 0
-------------------------------------
SELECT /*+ ORDERED USE_NL(d) */ e.last_name, d.department_name FROM
employees e, departments d WHERE  e.department_id=d.department_id AND
 e.last_name like 'A%'
 
Plan hash value: 1667998133
 
----------------------------------------------------------------------------------
|Id| Operation                             |Name      |Rows|Bytes|Cost(%CPU)|Time|
----------------------------------------------------------------------------------
| 0| SELECT STATEMENT                      |             |  |   |5 (100)|        |
| 1|  NESTED LOOPS                         |             |  |   |       |        |
| 2|   NESTED LOOPS                        |             | 3|102|5   (0)|00:00:01|
| 3|    TABLE ACCESS BY INDEX ROWID BATCHED| EMPLOYEES   | 3| 54|2   (0)|00:00:01|
|*4|     INDEX RANGE SCAN                  | EMP_NAME_IX | 3|   |1   (0)|00:00:01|
|*5|    INDEX UNIQUE SCAN                  | DEPT_ID_PK  | 1|   |0   (0)|        |
| 6|   TABLE ACCESS BY INDEX ROWID         | DEPARTMENTS | 1| 16|1   (0)|00:00:01|
----------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   4 - access("E"."LAST_NAME" LIKE 'A%')
       filter("E"."LAST_NAME" LIKE 'A%')
   5 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

Oracle Database 11g introduced a new implementation for nested loops that reduces overall latency for physical I/O. When an index or a table block is not in the buffer cache and is needed to process the join, a physical I/O is required. The database can batch multiple physical I/O requests and process them using a vector I/O instead of one at a time. A vector is an array. The database obtains a set of rowids, and then sends them in an array to the operating system, which performs the read.

As part of the new implementation, two NESTED LOOPS join row sources might appear in the execution plan where only one would have appeared in prior releases. In such cases, Oracle Database allocates one NESTED LOOPS join row source to join the values from the table on the outer side of the join with the index on the inner side. A second row source is allocated to join the result of the first join, which includes the rowids stored in the index, with the table on the inner side of the join.

Consider the query in "Original Implementation for Nested Loops Joins". In the current implementation, the execution plan for this query might be as follows:

-------------------------------------------------------------------------------------
| Id | Operation                    | Name              |Rows|Bytes|Cost%CPU| Time  |
-------------------------------------------------------------------------------------
|  0 | SELECT STATEMENT             |                   | 19 | 722 |  3 (0)|00:00:01|
|  1 |  NESTED LOOPS                |                   |    |     |       |        |
|  2 |   NESTED LOOPS               |                   | 19 | 722 |  3 (0)|00:00:01|
|* 3 |    TABLE ACCESS FULL         | DEPARTMENTS       |  2 |  32 |  2 (0)|00:00:01|
|* 4 |    INDEX RANGE SCAN          | EMP_DEPARTMENT_IX | 10 |     |  0 (0)|00:00:01|
|  5 |   TABLE ACCESS BY INDEX ROWID| EMPLOYEES         | 10 | 220 |  1 (0)|00:00:01|
-------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
   3 - filter("D"."DEPARTMENT_NAME"='Marketing' OR "D"."DEPARTMENT_NAME"='Sales')
   4 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

In this case, rows from the hr.departments table form the outer row source (Step 3) of the inner nested loop (Step 2). The index emp_department_ix is the inner row source (Step 4) of the inner nested loop. The results of the inner nested loop form the outer row source (Row 2) of the outer nested loop (Row 1). The hr.employees table is the outer row source (Row 5) of the outer nested loop.

For each fetch request, the basic process is as follows:

1. The database iterates through the inner nested loop (Step 2) to obtain the rows requested in the fetch:

   1. The database reads the first row of departments to obtain the department IDs for departments named Marketing or Sales (Step 3). For example:

      Marketing,20
      

      This row set is the outer loop. The database caches the data in the PGA.

   2. The database scans emp_department_ix, which is an index on the employees table, to find employees rowids that correspond to this department ID (Step 4), and then joins the result (Step 2).

      The result set has the following form:

      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      

   3. The database reads the next row of departments, scans emp_department_ix to find employees rowids that correspond to this department ID, and then iterates through the loop until the client request is satisfied.

      In this example, the database only iterates through the outer loop twice because only two rows from departments satisfy the predicate filter. Conceptually, the result set has the following form:

      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      .
      .
      .
      Sales,80,employees_rowid
      Sales,80,employees_rowid
      Sales,80,employees_rowid
      .
      .
      .
      

      These rows become the outer row source for the outer nested loop (Step 1). This row set is cached in the PGA.

2. The database organizes the rowids obtained in the previous step so that it can more efficiently access them in the cache.

3. The database begins iterating through the outer nested loop as follows:

   1. The database retrieves the first row from the row set obtained in the previous step, as in the following example:

      Marketing,20,employees_rowid
      

   2. Using the rowid, the database retrieves a row from employees to obtain the requested values (Step 1), as in the following example:

      Michael,Hartstein,13000,Marketing
      

   3. The database retrieves the next row from the row set, uses the rowid to probe employees for the matching row, and iterates through the loop until all rows are retrieved.

      The result set has the following form:

      Michael,Hartstein,13000,Marketing
      Pat,Fay,6000,Marketing
      John,Russell,14000,Sales
      Karen,Partners,13500,Sales
      Alberto,Errazuriz,12000,Sales
      .
      .
      .
      

In some cases, a second join row source is not allocated, and the execution plan looks the same as it did before Oracle Database 11g. The following list describes such cases:

• All of the columns needed from the inner side of the join are present in the index, and there is no table access required. In this case, Oracle Database allocates only one join row source.

• The order of the rows returned might be different from the order returned in releases earlier than Oracle Database 12c. Thus, when Oracle Database tries to preserve a specific ordering of the rows, for example to eliminate the need for an ORDER BY sort, Oracle Database might use the original implementation for nested loops joins.

• The OPTIMIZER_FEATURES_ENABLE initialization parameter is set to a release before Oracle Database 11g. In this case, Oracle Database uses the original implementation for nested loops joins.

In the current release, both the new and original implementation are possible. For an example of the original implementation, consider the following join of the hr.employees and hr.departments tables:

SELECT e.first_name, e.last_name, e.salary, d.department_name
FROM   hr.employees e, hr.departments d
WHERE  d.department_name IN ('Marketing', 'Sales')
AND    e.department_id = d.department_id;

In releases before Oracle Database 11g, the execution plan for this query might appear as follows:

------------------------------------------------------------------------------------------------
| Id  | Operation                   | Name              | Rows  | Bytes | Cost (%CPU)| Time    |
------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |                   |    19 |   722 |     3  (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| EMPLOYEES         |    10 |   220 |     1  (0)| 00:00:01 |
|   2 |   NESTED LOOPS              |                   |    19 |   722 |     3  (0)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL        | DEPARTMENTS       |     2 |    32 |     2  (0)| 00:00:01 |
|*  4 |    INDEX RANGE SCAN         | EMP_DEPARTMENT_IX |    10 |       |     0  (0)| 00:00:01 |
------------------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
   3 - filter("D"."DEPARTMENT_NAME"='Marketing' OR "D"."DEPARTMENT_NAME"='Sales')
   4 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

For each fetch request, the basic process is as follows:

1. The database iterates through the loop to obtain the rows requested in the fetch:

   1. The database reads the first row of departments to obtain the department IDs for departments named Marketing or Sales (Step 3). For example:

      Marketing,20
      

      This row set is the outer loop. The database caches the row in the PGA.

   2. The database scans emp_department_ix, which is an index on the employees.department_id column, to find employees rowids that correspond to this department ID (Step 4), and then joins the result (Step 2).

      Conceptually, the result set has the following form:

      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      

   3. The database reads the next row of departments, scans emp_department_ix to find employees rowids that correspond to this department ID, and iterates through the loop until the client request is satisfied.

      In this example, the database only iterates through the outer loop twice because only two rows from departments satisfy the predicate filter. Conceptually, the result set has the following form:

      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      .
      .
      .
      Sales,80,employees_rowid
      Sales,80,employees_rowid
      Sales,80,employees_rowid
      .
      .
      .
      

2. Depending on the circumstances, the database may organize the cached rowids obtained in the previous step so that it can more efficiently access them.

3. For each employees rowid in the result set generated by the nested loop, the database retrieves a row from employees to obtain the requested values (Step 1).

   Thus, the basic process is to read a rowid and retrieve the matching employees row, read the next rowid and retrieve the matching employees row, and so on. Conceptually, the result set has the following form:

   Michael,Hartstein,13000,Marketing
   Pat,Fay,6000,Marketing
   John,Russell,14000,Sales
   Karen,Partners,13500,Sales
   Alberto,Errazuriz,12000,Sales
   .
   .
   .
   

For some SQL examples, the data is small enough for the optimizer to prefer full table scans and hash joins. However, you can add a USE_NL to instruct the optimizer to change the join method to nested loops. This hint instructs the optimizer to join each specified table to another row source with a nested loops join, using the specified table as the inner table.

The related hint USE_NL_WITH_INDEX ( table index ) hint instructs the optimizer to join the specified table to another row source with a nested loops join using the specified table as the inner table. The index is optional. If no index is specified, then the nested loops join uses an index with at least one join predicate as the index key.

SELECT e.last_name, d.department_name
FROM   employees e, departments d
WHERE  e.department_id=d.department_id;

------------------------------------------------------------------------------
|Id | Operation          | Name        | Rows  | Bytes |Cost(%CPU)| Time     |
------------------------------------------------------------------------------
| 0 | SELECT STATEMENT   |             |       |       |   5 (100)|          |
|*1 |  HASH JOIN         |             |   106 |  2862 |   5  (20)| 00:00:01 |
| 2 |   TABLE ACCESS FULL| DEPARTMENTS |    27 |   432 |   2   (0)| 00:00:01 |
| 3 |   TABLE ACCESS FULL| EMPLOYEES   |   107 |  1177 |   2   (0)| 00:00:01 |
------------------------------------------------------------------------------

SELECT /*+ ORDERED USE_NL(d) */ e.last_name, d.department_name
FROM   employees e, departments d
WHERE  e.department_id=d.department_id;

--------------------------------------------------------------------------------
| Id | Operation          | Name        | Rows  | Bytes |Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|  0 | SELECT STATEMENT   |             |       |       |   34 (100)|          |
|  1 |  NESTED LOOPS      |             |   106 |  2862 |   34   (3)| 00:00:01 |
|  2 |   TABLE ACCESS FULL| EMPLOYEES   |   107 |  1177 |    2   (0)| 00:00:01 |
|* 3 |   TABLE ACCESS FULL| DEPARTMENTS |     1 |    16 |    0   (0)|          |
--------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - filter("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

In general, the optimizer considers a hash join when the following conditions are true:

• A relatively large amount of data must be joined, or a large fraction of a small table must be joined.

• The join is an equijoin.

A hash join is most cost effective when the smaller data set fits in memory. In this case, the cost is limited to a single read pass over the two data sets.

Because the hash table is in the PGA, Oracle Database can access rows without latching them. This technique reduces logical I/O by avoiding the necessity of repeatedly latching and reading blocks in the database buffer cache.

If the data sets do not fit in memory, then the database partitions the row sources, and the join proceeds partition by partition. This can use a lot of sort area memory, and I/O to the temporary tablespace. This method can still be the most cost effective, especially when the database uses parallel query servers.

A hashing algorithm takes a set of inputs and applies a deterministic hash function to generate a hash value between 1 and n, where n is the size of the hash table. In a hash join, the input values are the join keys. The output values are indexes (slots) in an array, which is the hash table.

The database must use a different technique when the hash table does not fit entirely in the PGA. In this case, the database uses a temporary space to hold portions (called partitions) of the hash table, and sometimes portions of the larger table that probes the hash table.

The basic process is as follows:

1. The database performs a full scan of the smaller data set, and then builds an array of hash buckets in both the PGA and on disk.

   When the PGA hash area fills up, the database finds the largest partition within the hash table and writes it to temporary space on disk. The database stores any new row that belongs to this on-disk partition on disk, and all other rows in the PGA. Thus, part of the hash table is in memory and part of it on disk.

2. The database takes a first pass at reading the other data set.

   For each row, the database does the following:

   1. Applies the same hash function to the join column or columns to calculate the number of the relevant hash bucket.

   2. Probes the hash table to determine whether rows exist in the bucket in memory.

      If the hashed value points to a row in memory, then the database completes the join and returns the row. If the value points to a hash partition on disk, however, then the database stores this row in the temporary tablespace, using the same partitioning scheme used for the original data set.

3. The database reads each on-disk temporary partition one by one

4. The database joins each partition row to the row in the corresponding on-disk temporary partition.

The USE_HASH hint instructs the optimizer to use a hash join when joining two tables together. See "Guidelines for Join Order Hints".

A hash join requires one hash table and one probe of this table, whereas a sort merge join requires two sorts. The optimizer may choose a sort merge join over a hash join for joining large amounts of data when any of the following conditions is true:

• The join condition between two tables is not an equijoin, that is, uses an inequality condition such as <, <=, >, or >=.

  In contrast to sort merges, hash joins require an equality condition.

• Because of sorts required by other operations, the optimizer finds it cheaper to use a sort merge.

  If an index exists, then the database can avoid sorting the first data set. However, the database always sorts the second data set, regardless of indexes.

A sort merge has the same advantage over a nested loops join as the hash join: the database accesses rows in the PGA rather than the SGA, reducing logical I/O by avoiding the necessity of repeatedly latching and reading blocks in the database buffer cache. In general, hash joins perform better than sort merge joins because sorting is expensive. However, sort merge joins offer the following advantages over a hash join:

• After the initial sort, the merge phase is optimized, resulting in faster generation of output rows.

• A sort merge can be more cost-effective than a hash join when the hash table does not fit completely in memory.

  A hash join with insufficient memory requires both the hash table and the other data set to be copied to disk. In this case, the database may have to read from disk multiple times. In a sort merge, if memory cannot hold the two data sets, then the database writes them both to disk, but reads each data set no more than once.

As in a nested loops join, a sort merge join reads two data sets, but sorts them when they are not already sorted. For each row in the first data set, the database finds a starting row in the second data set, and then reads the second data set until it finds a nonmatching row. In pseudocode, the high-level algorithm might look as follows:

READ data_set_1 SORT BY JOIN KEY TO temp_ds1
READ data_set_2 SORT BY JOIN KEY TO temp_ds2
 
READ ds1_row FROM temp_ds1
READ ds2_row FROM temp_ds2

WHILE NOT eof ON temp_ds1,temp_ds2
LOOP
    IF ( temp_ds1.key = temp_ds2.key ) OUTPUT JOIN ds1_row,ds2_row
    ELSIF ( temp_ds1.key <= temp_ds2.key ) READ ds1_row FROM temp_ds1
    ELSIF ( temp_ds1.key => temp_ds2.key ) READ ds2_row FROM temp_ds2
END LOOP

For example, the database sorts the first data set as follows:

10,20,30,40,50,60,70

The database sorts the second data set as follows:

20,20,40,40,40,40,40,60,70,70

The database begins by reading 10 in the first data set, and then starts at the beginning of data set 2:

20 too high, stop, get next ds1_row

The database proceeds to the second row of data set 1 (20). The database proceeds through the second data set as follows:

20 match, proceed
20 match, proceed
40 too high, stop, get next ds1_row

The database gets the next row in data set 1, which is 30. The database starts at the number of its last match, which was 20, and then walks through data set 2 looking for a match:

20 too low, proceed
20 too low, proceed
40 too high, stop, get next ds1_row 

The database gets the next row in data set 1, which is 40. The database starts at the number of its last match, which was 20, and then proceeds through data set 2 looking for a match:

20 too low, proceed
20 too low, proceed
40 match, proceed
40 match, proceed
40 match, proceed
40 match, proceed
40 match, proceed
60 too high, stop, get next ds1_row

As the database proceeds through data set 1, the database does not need to read every row in data set 2. This is an advantage over a nested loops join.

SELECT e.employee_id, e.last_name, e.first_name, e.department_id, 
       d.department_name
FROM   employees e, departments d
WHERE  e.department_id = d.department_id
ORDER BY department_id;

--------------------------------------------------------------------------------
|Id| Operation                    | Name        |Rows|Bytes |Cost (%CPU)| Time |
--------------------------------------------------------------------------------
| 0| SELECT STATEMENT             |             |    |      | 5(100)|          |
| 1|  MERGE JOIN                  |             |106 | 4028 | 5 (20)| 00:00:01 |
| 2|   TABLE ACCESS BY INDEX ROWID| DEPARTMENTS | 27 |  432 | 2  (0)| 00:00:01 |
| 3|    INDEX FULL SCAN           | DEPT_ID_PK  | 27 |      | 1  (0)| 00:00:01 |
|*4|   SORT JOIN                  |             |107 | 2354 | 3 (34)| 00:00:01 |
| 5|    TABLE ACCESS FULL         | EMPLOYEES   |107 | 2354 | 2  (0)| 00:00:01 |
--------------------------------------------------------------------------------

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

   4 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")
       filter("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

SELECT /*+ USE_MERGE(d e) NO_INDEX(d) */ e.employee_id, e.last_name, e.first_name, 
       e.department_id, d.department_name
FROM   employees e, departments d
WHERE  e.department_id = d.department_id
ORDER BY department_id;

--------------------------------------------------------------------------------
| Id| Operation           | Name        | Rows  | Bytes | Cost (%CPU)| Time    |
--------------------------------------------------------------------------------
| 0 | SELECT STATEMENT    |             |       |       |     6 (100)|         |
| 1 |  MERGE JOIN         |             |   106 |  9540 |     6  (34)| 00:00:01|
| 2 |   SORT JOIN         |             |    27 |   567 |     3  (34)| 00:00:01|
| 3 |    TABLE ACCESS FULL| DEPARTMENTS |    27 |   567 |     2   (0)| 00:00:01|
|*4 |   SORT JOIN         |             |   107 |  7383 |     3  (34)| 00:00:01|
| 5 |    TABLE ACCESS FULL| EMPLOYEES   |   107 |  7383 |     2   (0)| 00:00:01|
--------------------------------------------------------------------------------

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

   4 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")
       filter("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

The USE_MERGE hint instructs the optimizer to use a sort merge join. In some situations it may make sense to override the optimizer 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.

The optimizer uses a Cartesian join for two row sources in any of the following circumstances:

• No join condition exists.

  In some cases, the optimizer could pick up a common filter condition between the two tables as a possible join condition.

  Note:

  If a Cartesian join appears in a query plan, it could be caused by an inadvertently omitted join condition. In general, if a query joins n tables, then n-1 join conditions are required to avoid a Cartesian join.

• A Cartesian join is an efficient method.

  For example, the optimizer may decide to generate a Cartesian product of two very small tables that are both joined to the same large table.

• The ORDERED hint specifies a table before its join table is specified.

At a high level, the algorithm for a Cartesian join looks as follows, where ds1 is typically the smaller data set, and ds2 is the larger data set:

FOR ds1_row IN ds1 LOOP
  FOR ds2_row IN ds2 LOOP
    output ds1_row and ds2_row
  END LOOP
END LOOP

SELECT e.last_name, d.department_name
FROM   employees e, departments d

--------------------------------------------------------------------------------
| Id| Operation              | Name        | Rows  | Bytes |Cost (%CPU)| Time  |
--------------------------------------------------------------------------------
| 0 | SELECT STATEMENT       |             |       |       |11 (100)|          |
| 1 |  MERGE JOIN CARTESIAN  |             |  2889 | 57780 |11   (0)| 00:00:01 |
| 2 |   TABLE ACCESS FULL    | DEPARTMENTS |    27 |   324 | 2   (0)| 00:00:01 |
| 3 |   BUFFER SORT          |             |   107 |   856 | 9   (0)| 00:00:01 |
| 4 |    INDEX FAST FULL SCAN| EMP_NAME_IX |   107 |   856 | 0   (0)|          |
--------------------------------------------------------------------------------

The ORDERED hint instructs the optimizer to join tables in the order in which they appear in the FROM clause. By forcing a join between two row sources that have no direct connection, the optimizer must perform a Cartesian join.

SELECT /*+ORDERED*/ e.last_name, d.department_name, l.country_id, l.state_province
FROM   employees e, locations l, departments d
WHERE  e.department_id = d.department_id
AND    d.location_id = l.location_id

--------------------------------------------------------------------------------
| Id| Operation             | Name        | Rows  | Bytes |Cost (%CPU)|Time    |
--------------------------------------------------------------------------------
| 0 | SELECT STATEMENT      |             |       |       | 37 (100)|          |
|*1 |  HASH JOIN            |             |   106 |  4664 | 37   (6)| 00:00:01 |
| 2 |   TABLE ACCESS FULL   | DEPARTMENTS |    27 |   513 |  2   (0)| 00:00:01 |
| 3 |   MERGE JOIN CARTESIAN|             |  2461 | 61525 | 34   (3)| 00:00:01 |
| 4 |    TABLE ACCESS FULL  | EMPLOYEES   |   107 |  1177 |  2   (0)| 00:00:01 |
| 5 |    BUFFER SORT        |             |    23 |   322 | 32   (4)| 00:00:01 |
| 6 |     TABLE ACCESS FULL | LOCATIONS   |    23 |   322 |  0   (0)|          |
--------------------------------------------------------------------------------

An equijoin is an inner join whose join condition contains an equality operator. The following example is an equijoin because the join condition contains only an equality operator:

SELECT e.employee_id, e.last_name, d.department_name
FROM   employees e, departments d
WHERE  e.department_id=d.department_id;

In the preceding query, the join condition is e.department_id=d.department_id. If a row in the employees table has a department ID that matches the value in a row in the departments table, then the database returns the joined result; otherwise, the database does not return a result.

A nonequijoin is an inner join whose join condition contains an operator that is not an equality operator. The following query lists all employees whose hire date occurred when employee 176 (who is listed in job_history because he changed jobs in 2007) was working at the company:

SELECT e.employee_id, e.first_name, e.last_name, e.hire_date
FROM   employees e, job_history h
WHERE  h.employee_id = 176
AND    e.hire_date BETWEEN h.start_date AND h.end_date;

In the preceding example, the condition joining employees and job_history does not contain an equality operator, so it is a nonequijoin. Nonequijoins are relatively rare.

Note that a hash join requires at least a partial equijoin. The following SQL script contains an equality join condition (e1.empno = e2.empno) and a nonequality condition:

SET AUTOTRACE TRACEONLY EXPLAIN
SELECT *
FROM   scott.emp e1 JOIN scott.emp e2
ON     ( e1.empno = e2.empno
AND      e1.hiredate BETWEEN e2.hiredate-1 AND e2.hiredate+1 )

The optimizer chooses a hash join for the preceding query, as shown in the following plan:

Execution Plan
----------------------------------------------------------
Plan hash value: 3638257876
 
---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |   174 |     5  (20)| 00:00:01 |
|*  1 |  HASH JOIN         |      |     1 |   174 |     5  (20)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| EMP  |    14 |  1218 |     2   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| EMP  |    14 |  1218 |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - access("E1"."EMPNO"="E2"."EMPNO")
       filter("E1"."HIREDATE">=INTERNAL_FUNCTION("E2"."HIREDATE")-1 AND
              "E1"."HIREDATE"<=INTERNAL_FUNCTION("E2"."HIREDATE")+1)

The database uses this operation to loop through an outer join between two tables. The outer join returns the outer (preserved) table rows, even when no corresponding rows are in the inner (optional) table.

In a standard nested loop, the optimizer chooses the order of tables—which is the driving table and which the driven table—based on the cost. However, in a nested loop outer join, the join condition determines the order of tables. The database uses the outer, row-preserved table to drive to the inner table.

The optimizer uses nested loops joins to process an outer join in the following circumstances:

• It is possible to drive from the outer table to the 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 Example 9-9 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"
FROM   customers c, orders o
WHERE  c.credit_limit > 1000
AND    c.customer_id = o.customer_id(+)
GROUP BY cust_last_name;

The optimizer uses hash joins for processing an outer join when either of the following conditions is met:

• The data volume is large enough to make the hash join method efficient.

• It is not possible to drive from the outer table to the inner table.

The cost determines the order of tables. The outer table, including preserved rows, may be used to build the hash table, or it may be used to probe the hash table.

SELECT cust_last_name, SUM(NVL2(o.customer_id,0,1)) "Count"
FROM   customers c, orders o
WHERE  c.credit_limit > 1000
AND    c.customer_id = o.customer_id(+)
GROUP BY cust_last_name;

--------------------------------------------------------------------------------
| Id  | Operation          | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
 
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
|  0 | SELECT STATEMENT    |           |       |       |     7 (100)|          |
|  1 |  HASH GROUP BY      |           |   168 |  3192 |     7  (29)| 00:00:01 |
|* 2 |   HASH JOIN OUTER   |           |   318 |  6042 |     6  (17)| 00:00:01 |
|* 3 |    TABLE ACCESS FULL| CUSTOMERS |   260 |  3900 |     3   (0)| 00:00:01 |
|* 4 |    TABLE ACCESS FULL| ORDERS    |   105 |   420 |     2   (0)| 00:00:01 |
--------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - access("C"."CUSTOMER_ID"="O"."CUSTOMER_ID")
 
PLAN_TABLE_OUTPUT
-------------------------------------------------------------------------------
   3 - filter("C"."CREDIT_LIMIT">1000)
   4 - filter("O"."CUSTOMER_ID">0)

customers.customer_id = orders.customer_id(+)

SELECT c.cust_last_name, sum(revenue)
FROM   customers c, v_orders o
WHERE  c.credit_limit > 2000
AND    o.customer_id(+) = c.customer_id
GROUP BY c.cust_last_name;

----------------------------------------------------------------------------
| Id  | Operation              |  Name        | Rows  | Bytes | Cost (%CPU)|
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |              |   144 |  4608 |    16  (32)|
|   1 |  HASH GROUP BY         |              |   144 |  4608 |    16  (32)|
|*  2 |   HASH JOIN OUTER      |              |   663 | 21216 |    15  (27)|
|*  3 |    TABLE ACCESS FULL   | CUSTOMERS    |   195 |  2925 |     6  (17)|
|   4 |    VIEW                | V_ORDERS     |   665 | 11305 |            |
|   5 |     HASH GROUP BY      |              |   665 | 15960 |     9  (34)|
|*  6 |      HASH JOIN         |              |   665 | 15960 |     8  (25)|
|*  7 |       TABLE ACCESS FULL| ORDERS       |   105 |   840 |     4  (25)|
|   8 |       TABLE ACCESS FULL| ORDER_ITEMS  |   665 | 10640 |     4  (25)|
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("O"."CUSTOMER_ID"(+)="C"."CUSTOMER_ID")
   3 - filter("C"."CREDIT_LIMIT">2000)
   6 - access("O"."ORDER_ID"="L"."ORDER_ID")
   7 - filter("O"."CUSTOMER_ID">0)

CREATE OR REPLACE view v_orders AS
SELECT l.product_id, SUM(l.quantity*unit_price) revenue, 
       o.order_id, o.customer_id
FROM   orders o, order_items l
WHERE  o.order_id = l.order_id
GROUP BY l.product_id, o.order_id, o.customer_id;

When an outer join cannot drive from the outer (preserved) table to the inner (optional) table, it cannot use a hash join or nested loops joins. In this case, it uses the sort merge outer join.

The optimizer uses sort merge for an outer join in the following cases:

• A nested loops join is inefficient. A nested loops 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 required by other operations.

A full outer join is a combination of the left and right outer joins. In addition to the inner join, rows from both tables that have not been returned in the result of the inner join are preserved and extended with nulls. In other words, full outer joins join tables together, yet show rows with no corresponding rows in the joined tables.

SELECT d.department_id, e.employee_id
FROM   employees e FULL OUTER JOIN departments d
ON     e.department_id = d.department_id
ORDER BY d.department_id;

DEPARTMENT_ID EMPLOYEE_ID
------------- -----------
           10         200
           20         201
           20         202
           30         114
           30         115
           30         116
...
          270
          280
                      178
                      207

125 rows selected.

--------------------------------------------------------------------------------
| Id| Operation               | Name       |Rows |Bytes |Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
| 0 | SELECT STATEMENT        |            | 122 | 4758 |   6  (34)| 00:0 0:01 |
| 1 |  SORT ORDER BY          |            | 122 | 4758 |   6  (34)| 00:0 0:01 |
| 2 |   VIEW                  | VW_FOJ_0   | 122 | 4758 |   5  (20)| 00:0 0:01 |
|*3 |    HASH JOIN FULL OUTER |            | 122 | 1342 |   5  (20)| 00:0 0:01 |
| 4 |     INDEX FAST FULL SCAN| DEPT_ID_PK |  27 |  108 |   2   (0)| 00:0 0:01 |
| 5 |     TABLE ACCESS FULL   | EMPLOYEES  | 107 |  749 |   2   (0)| 00:0 0:01 |
--------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

In Oracle Database 12c, multiple tables may exist on the left of an outer-joined table. This enhancement enables Oracle Database to merge a view that contains multiple tables and appears on the left of outer join.

In releases before Oracle Database 12c, a query such as the following was invalid, and would trigger an ORA-01417 error message:

SELECT t1.d, t3.c
FROM   t1, t2, t3
WHERE  t1.z = t2.z 
AND    t1.x = t3.x (+) 
AND    t2.y = t3.y (+);

Starting in Oracle Database 12c, the preceding query is valid.

A semijoin avoids returning a huge number of rows when a query only needs to determine whether a match exists. With large data sets, this optimization can result in significant time savings over a nested loops join that must loop through every record returned by the inner query for every row in the outer query. The optimizer can apply the semijoin optimization to nested loops joins, hash joins, and sort merge joins.

The optimizer may choose a semijoin in the following circumstances:

• The statement uses either an IN or EXISTS clause.

• The statement contains a subquery in the IN or EXISTS clause.

• The IN or EXISTS clause is not contained inside an OR branch.

The semijoin optimization is implemented differently depending on what type of join is used. The following pseudocode shows a semijoin for a nested loops join:

FOR ds1_row IN ds1 LOOP
  match := false;
  FOR ds2_row IN ds2_subquery LOOP
    IF (ds1_row matches ds2_row) THEN
      match := true;
      EXIT -- stop processing second data set when a match is found
    END IF
  END LOOP
  IF (match = true) THEN 
    RETURN ds1_row
  END IF
END LOOP

In the preceding pseudocode, ds1 is the first data set, and ds2_subquery is the subquery data set. The code obtains the first row from the first data set, and then loops through the subquery data set looking for a match. The code exits the inner loop as soon as it finds a match, and then begins processing the next row in the first data set.

SELECT department_id, department_name 
FROM   departments
WHERE EXISTS (SELECT 1
              FROM   employees 
              WHERE  employees.department_id = departments.department_id)

--------------------------------------------------------------------------------
| Id| Operation          | Name              |Rows|Bytes|Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
| 0 | SELECT STATEMENT   |                   |    |     |    2 (100)|          |
| 1 |  NESTED LOOPS SEMI |                   | 11 | 209 |    2   (0)| 00:00:01 |
| 2 |   TABLE ACCESS FULL| DEPARTMENTS       | 27 | 432 |    2   (0)| 00:00:01 |
|*3 |   INDEX RANGE SCAN | EMP_DEPARTMENT_IX | 44 | 132 |    0   (0)|          |
--------------------------------------------------------------------------------

10,rowid
10,rowid
10,rowid
10,rowid
30,rowid
30,rowid
30,rowid
...

SELECT department_id, department_name
FROM   departments
WHERE  department_id IN 
       (SELECT department_id 
        FROM   employees); 

--------------------------------------------------------------------------------
| Id| Operation          | Name              |Rows|Bytes|Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
| 0 | SELECT STATEMENT   |                   |    |     |    2 (100)|          |
| 1 |  NESTED LOOPS SEMI |                   | 11 | 209 |    2   (0)| 00:00:01 |
| 2 |   TABLE ACCESS FULL| DEPARTMENTS       | 27 | 432 |    2   (0)| 00:00:01 |
|*3 |   INDEX RANGE SCAN | EMP_DEPARTMENT_IX | 44 | 132 |    0   (0)|          |
--------------------------------------------------------------------------------

An antijoin avoids unnecessary processing when a query only needs to return a row when a match does not exist. With large data sets, this optimization can result in significant time savings over a nested loops join that must loop through every record returned by the inner query for every row in the outer query. The optimizer can apply the antijoin optimization to nested loops joins, hash joins, and sort merge joins.

The optimizer may choose an antijoin in the following circumstances:

• The statement uses either the NOT IN or NOT EXISTS clause.

• The statement has a subquery in the NOT IN or NOT EXISTS clause.

• The NOT IN or NOT EXISTS clause is not contained inside an OR branch.

• The statement performs an outer join and applies an IS NULL condition to a join column, as in the following example:

  SET AUTOTRACE TRACEONLY EXPLAIN
  SELECT emp.*
  FROM   emp, dept
  WHERE  emp.deptno = dept.deptno(+)
  AND    dept.deptno IS NULL
  
  Execution Plan
  ----------------------------------------------------------
  Plan hash value: 1543991079
   
  ---------------------------------------------------------------------------
  | Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
  ---------------------------------------------------------------------------
  |   0 | SELECT STATEMENT   |      |    14 |  1400 |     5  (20)| 00:00:01 |
  |*  1 |  HASH JOIN ANTI    |      |    14 |  1400 |     5  (20)| 00:00:01 |
  |   2 |   TABLE ACCESS FULL| EMP  |    14 |  1218 |     2   (0)| 00:00:01 |
  |   3 |   TABLE ACCESS FULL| DEPT |     4 |    52 |     2   (0)| 00:00:01 |
  ---------------------------------------------------------------------------
   
  Predicate Information (identified by operation id):
  ---------------------------------------------------
   
     1 - access("EMP"."DEPTNO"="DEPT"."DEPTNO")
   
  Note
  -----
     - dynamic statistics used: dynamic sampling (level=2)
  

The antijoin optimization is implemented differently depending on what type of join is used. The following pseudocode shows an antijoin for a nested loops join:

FOR ds1_row IN ds1 LOOP
  match := true;
  FOR ds2_row IN ds2 LOOP
    IF (ds1_row matches ds2_row) THEN
      match := false;
      EXIT -- stop processing second data set when a match is found
    END IF
  END LOOP
  IF (match = true) THEN 
    RETURN ds1_row
  END IF
END LOOP

In the preceding pseudocode, ds1 is the first data set, and ds2 is the second data set. The code obtains the first row from the first data set, and then loops through the second data set looking for a match. The code exits the inner loop as soon as it finds a match, and begins processing the next row in the first data set.

SELECT department_id, department_name 
FROM   departments
WHERE EXISTS (SELECT 1
              FROM   employees 
              WHERE  employees.department_id = departments.department_id)

--------------------------------------------------------------------------------
| Id| Operation          | Name              |Rows|Bytes |Cost(%CPU)| Time     |
--------------------------------------------------------------------------------
| 0 | SELECT STATEMENT   |                   |    |      |   2 (100)|          |
| 1 |  NESTED LOOPS SEMI |                   | 11 |  209 |   2   (0)| 00:00:01 |
| 2 |   TABLE ACCESS FULL| DEPARTMENTS       | 27 |  432 |   2   (0)| 00:00:01 |
|*3 |   INDEX RANGE SCAN | EMP_DEPARTMENT_IX | 44 |  132 |   0   (0)|          |
--------------------------------------------------------------------------------

10,rowid
10,rowid
10,rowid
10,rowid
30,rowid
30,rowid
30,rowid
...

For semijoins, IN and EXISTS are functionally equivalent. However, NOT IN and NOT EXISTS are not functionally equivalent. The difference is because of nulls. If a null value is returned to a NOT IN operator, then the statement returns no records. To see why, consider the following WHERE clause:

WHERE department_id NOT IN (null, 10, 20)

The database tests the preceding expression as follows:

WHERE (department_id != null) 
AND   (department_id != 10) 
AND   (department_id != 20)

For the entire expression to be true, each individual condition must be true. However, a null value cannot be compared to another value, so the department_id !=null condition cannot be true, and thus the whole expression cannot be true. The following techniques enable a statement to return records even when nulls are returned to the NOT IN operator:

• Apply an NVL function to the columns returned by the subquery.

• Add an IS NOT NULL predicate to the subquery.

• Implement NOT NULL constraints.

In contrast to NOT IN, the NOT EXISTS clause only considers predicates that return the existence of a match, and ignores any row that does not match or could not be determined because of nulls. If at least one row in the subquery matches the row from the outer query, then NOT EXISTS returns false. If no tuples match, then NOT EXISTS returns true. The presence of nulls in the subquery does not affect the search for matching records.

In releases earlier than Oracle Database 11g, the optimizer could not use an antijoin optimization when nulls could be returned by a subquery. However, starting in Oracle Database 11g, the ANTI NA (and ANTI SNA) optimizations described in the following sections enable the optimizer to use an antijoin even when nulls are possible.

SELECT department_id, department_name
FROM   departments
WHERE  department_id NOT IN 
       (SELECT department_id 
        FROM   employees);

--------------------------------------------------------------------------------
| Id| Operation              | Name              |Rows|Bytes|Cost (%CPU)| Time |
--------------------------------------------------------------------------------
| 0 | SELECT STATEMENT       |                   |    |     | 4(100)|          |
|*1 |  FILTER                |                   |    |     |       |          |
| 2 |   NESTED LOOPS ANTI SNA|                   | 17 | 323 | 4 (50)| 00:00:01 |
| 3 |    TABLE ACCESS FULL   | DEPARTMENTS       | 27 | 432 | 2  (0)| 00:00:01 |
|*4 |    INDEX RANGE SCAN    | EMP_DEPARTMENT_IX | 41 | 123 | 0  (0)|          |
|*5 |   TABLE ACCESS FULL    | EMPLOYEES         |  1 |   3 | 2  (0)| 00:00:01 |
--------------------------------------------------------------------------------
 
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter( IS NULL)
   4 - access("DEPARTMENT_ID"="DEPARTMENT_ID")
   5 - filter("DEPARTMENT_ID" IS NULL)

SELECT department_id, department_name
FROM   departments
WHERE  department_id NOT IN 
       (SELECT department_id 
        FROM   employees
        WHERE  department_id IS NOT NULL);

--------------------------------------------------------------------------------
|Id| Operation          | Name              | Rows| Bytes | Cost (%CPU)| Time  |
--------------------------------------------------------------------------------
| 0| SELECT STATEMENT   |                   |     |       |  2 (100)|          |
| 1|  NESTED LOOPS ANTI |                   |  17 |   323 |  2   (0)| 00:00:01 |
| 2|   TABLE ACCESS FULL| DEPARTMENTS       |  27 |   432 |  2   (0)| 00:00:01 |
|*3|   INDEX RANGE SCAN | EMP_DEPARTMENT_IX |  41 |   123 |  0   (0)|          |
--------------------------------------------------------------------------------
 
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - access("DEPARTMENT_ID"="DEPARTMENT_ID")
       filter("DEPARTMENT_ID" IS NOT NULL)

SELECT department_id, department_name
FROM   departments d
WHERE  NOT EXISTS
       (SELECT null
        FROM   employees e
        WHERE  e.department_id = d.department_id)

--------------------------------------------------------------------------------
| Id| Operation          | Name              | Rows  | Bytes | Cost (%CPU)|Time|
--------------------------------------------------------------------------------
| 0 | SELECT STATEMENT   |                   |       |       | 2 (100)|        |
| 1 |  NESTED LOOPS ANTI |                   |    17 |   323 | 2   (0)|00:00:01|
| 2 |   TABLE ACCESS FULL| DEPARTMENTS       |    27 |   432 | 2   (0)|00:00:01|
|*3 |   INDEX RANGE SCAN | EMP_DEPARTMENT_IX |    41 |   123 | 0   (0)|        |
--------------------------------------------------------------------------------
 
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

A Bloom filter tests one set of values to determine whether they are members another set, for example, set (10,20,30,40) and set (10,30,60,70). The filter determines that 60 and 70 are guaranteed not to be members of the first set, and that 10 and 30 are probably members. Bloom filters are especially useful when the amount of memory needed to store the filter is small relative to the amount of data in the data set, and when most data is expected to fail the membership test.

Oracle Database uses Bloom filters to various specific goals, including the following:

• Reduce the amount of data transferred to slave processes in a parallel query, especially when the database discards most rows because they do not fulfill a join condition

• Eliminate unneeded partitions when building a partition access list in a join, known as partition pruning

• Test whether data exists in the server result cache, thereby avoiding a disk read

• Filter members in Exadata cells, especially when joining a large fact table and small dimension tables in a star schema

Bloom filters can occur in both parallel and serial processing.

A Bloom filter uses an array of bits to indicate inclusion in a set. For example, 8 elements (an arbitrary number used for this example) in an array are initially set to 0:

e1 e2 e3 e4 e5 e6 e7 e8
 0  0  0  0  0  0  0  0

This array represents a set. To represent an input value i in this array, three separate hash functions (an arbitrary number used for this example) are applied to i, each generating a hash value between 1 and 8:

f1(i) = h1
f2(i) = h2
f3(i) = h3

For example, to store the value 17 in this array, the hash functions set i to 17, and then return the following hash values:

f1(17) = 5
f2(17) = 3
f3(17) = 5

In the preceding example, two of the hash functions happened to return the same value of 5, known as a hash collision. Because the distinct hash values are 5 and 3, the 5th and 3rd elements in the array are set to 1:

e1 e2 e3 e4 e5 e6 e7 e8
 0  0  1  0  1  0  0  0

Testing the membership of 17 in the set reverses the process. To test whether the set excludes the value 17, element 3 or element 5 must contain a 0. If a 0 is present in either element, then the set cannot contain 17. No false negatives are possible.

To test whether the set includes 17, both element 3 and element 5 must contain 1 values. However, if the test indicates a 1 for both elements, then it is still possible for the set not to include 17. False positives are possible. For example, the following array might represent the value 22, which also has a 1 for both element 3 and element 5:

e1 e2 e3 e4 e5 e6 e7 e8
 1  0  1  0  1  0  0  0

The optimizer automatically determines whether to use Bloom filters. To override optimizer decisions, use the hints PX_JOIN_FILTER and NO_PX_JOIN_FILTER.

The following dynamic performance views contain metadata about Bloom filters:

• V$SQL_JOIN_FILTER

  This view shows the number of rows filtered out (FILTERED column) and tested (PROBED column) by an active Bloom filter.

• V$PQ_TQSTAT

  This view displays the number of rows processed through each parallel execution server at each stage of the execution tree. You can use it to monitor how much Bloom filters have reduced data transfer among parallel processes.

In an execution plan, a Bloom filter is indicated by keywords JOIN FILTER in the Operation column, and the prefix :BF in the Name column, as in the 9th step of the following plan snippet:

----------------------------------------------------------------------------
| Id  | Operation                  | Name     |    TQ  |IN-OUT| PQ Distrib |
----------------------------------------------------------------------------
...
|   9 |      JOIN FILTER CREATE    | :BF0000  |  Q1,03 | PCWP |            |

In the Predicate Information section of the plan, filters that contain functions beginning with the string SYS_OP_BLOOM_FILTER indicate use of a Bloom filter.

The following parallel query joins the sales fact table to the products and times dimension tables, and filters on fiscal week 18:

SELECT /*+ parallel(s) */ p.prod_name, s.quantity_sold
FROM   sh.sales s, sh.products p, sh.times t 
WHERE  s.prod_id = p.prod_id
AND    s.time_id = t.time_id
AND    t.fiscal_week_number = 18;

Querying DBMS_XPLAN.DISPLAY_CURSOR provides the following output:

SELECT * FROM
  TABLE(DBMS_XPLAN.DISPLAY_CURSOR(format => 'BASIC,+PARALLEL,+PREDICATE'));

EXPLAINED SQL STATEMENT:
------------------------
SELECT /*+ parallel(s) */ p.prod_name, s.quantity_sold FROM sh.sales s,
sh.products p, sh.times t WHERE s.prod_id = p.prod_id AND s.time_id =
t.time_id AND t.fiscal_week_number = 18
 
Plan hash value: 1183628457
 
----------------------------------------------------------------------------
| Id  | Operation                  | Name     |    TQ  |IN-OUT| PQ Distrib |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT           |          |        |      |            |
|   1 |  PX COORDINATOR            |          |        |      |            |
|   2 |   PX SEND QC (RANDOM)      | :TQ10003 |  Q1,03 | P->S | QC (RAND)  |
|*  3 |    HASH JOIN BUFFERED      |          |  Q1,03 | PCWP |            |
|   4 |     PX RECEIVE             |          |  Q1,03 | PCWP |            |
|   5 |      PX SEND BROADCAST     | :TQ10001 |  Q1,01 | S->P | BROADCAST  |
|   6 |       PX SELECTOR          |          |  Q1,01 | SCWC |            |
|   7 |        TABLE ACCESS FULL   | PRODUCTS |  Q1,01 | SCWP |            |
|*  8 |     HASH JOIN              |          |  Q1,03 | PCWP |            |
|   9 |      JOIN FILTER CREATE    | :BF0000  |  Q1,03 | PCWP |            |
|  10 |       BUFFER SORT          |          |  Q1,03 | PCWC |            |
|  11 |        PX RECEIVE          |          |  Q1,03 | PCWP |            |
|  12 |         PX SEND HYBRID HASH| :TQ10000 |        | S->P | HYBRID HASH|
|* 13 |          TABLE ACCESS FULL | TIMES    |        |      |            |
|  14 |      PX RECEIVE            |          |  Q1,03 | PCWP |            |
|  15 |       PX SEND HYBRID HASH  | :TQ10002 |  Q1,02 | P->P | HYBRID HASH|
|  16 |        JOIN FILTER USE     | :BF0000  |  Q1,02 | PCWP |            |
|  17 |         PX BLOCK ITERATOR  |          |  Q1,02 | PCWC |            |
|* 18 |          TABLE ACCESS FULL | SALES    |  Q1,02 | PCWP |            |
----------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - access("S"."PROD_ID"="P"."PROD_ID")
   8 - access("S"."TIME_ID"="T"."TIME_ID")
  13 - filter("T"."FISCAL_WEEK_NUMBER"=18)
  18 - access(:Z>=:Z AND :Z<=:Z)
       filter(SYS_OP_BLOOM_FILTER(:BF0000,"S"."TIME_ID"))

A single server process scans the times table (Step 13), and then uses a hybrid hash distribution method to send the rows to the parallel execution servers (Step 12). The processes in set Q1,03 create a bloom filter (Step 9). The processes in set Q1,02 scan sales in parallel (Step 18), and then use the Bloom filter to discard rows from sales (Step 16) before sending them on to set Q1,03 using hybrid hash distribution (Step 15). The processes in set Q1,03 hash join the times rows to the filtered sales rows (Step 8). The processes in set Q1,01 scan products (Step 7), and then send the rows to Q1,03 (Step 5). Finally, the processes in Q1,03 join the products rows to the rows generated by the previous hash join (Step 3).

The basic process looks as follows:

Description of the illustration tgsql_vm_082.eps

Partition-wise joins reduce query response time by minimizing the amount of data exchanged among parallel execution servers when joins execute in parallel. This technique significantly reduces response time and improves the use of CPU and memory. In Oracle Real Application Clusters (Oracle RAC) environments, partition-wise joins also avoid or at least limit the data traffic over the interconnect, which is the key to achieving good scalability for massive join operations.

When the database serially joins two partitioned tables without using a partition-wise join, a single server process performs the join, as shown in Figure 9-6. In this example, the join is not partition-wise because the server process joins every partition of table t1 to every partition of table t2.

Figure 9-6 Join That Is Not Partition-Wise

Description of "Figure 9-6 Join That Is Not Partition-Wise"