Nested loop join implementation

Index nested loop join implementation

During the join, Db2 for i:

1. Accesses the first primary table row selected by the predicates local to the primary table.
2. Builds a key value from the join columns in the primary table.
3. Chooses the access to the first secondary table:
   • If using an index, Radix Index Probe is used to locate the first row satisfying the join condition for the secondary table. The probe uses an index with keys matching the join condition or local row selection columns of the secondary table.
   • Applies bitmap selection, if applicable.

     All rows that satisfy the join condition from each secondary dial are located using an index. Rows are retrieved from secondary tables in random sequence. This random disk I/O time often accounts for a large percentage of the processing time of the query. Since a given secondary dial is searched once for each row selected from the primary and the preceding secondary dials that satisfy the join condition for each of the preceding secondary dials, many searches could be against the later dials. Any inefficiencies in the processing of the later dials can significantly inflate the query processing time. This reason is why attention to performance considerations for join queries can reduce the run time of a join query from hours to minutes.

     If an efficient index cannot be found, a temporary index could be created. Some join queries build temporary indexes over secondary dials even when an index exists for all the join keys. Because efficiency is important for secondary dials of longer running queries, the optimizer could build a temporary index containing only entries with local row selection for that dial. This preprocessing of row selection allows the database manager to process row selection in one pass instead of each time rows are matched for a dial.

   • If using a Hash Table Probe, a hash temporary result table is created containing all rows from local selection against the table on the first probe. The structure of the hash table is such that rows with the same join value are loaded into the same hash table partition (clustered). The location of the rows for any given join value can be found by applying a hashing function to the join value.
     A nested loop join using a Hash Table Probe has several advantages over a nested loop join using an Index Probe:

     • The structure of a hash temporary result table is simpler than the structure of an index. Less CPU processing is required to build and probe a hash table.
     • The rows in the hash result table contain all the data required by the query. There is no need to access the dataspace of the table with random I/O when probing the hash table.
     • Like join values are clustered, so all matching rows for a given join value can typically be accessed with a single I/O request.
     • The hash temporary result table can be built using SMP parallelism.
     • Unlike indexes, entries in hash tables are not updated to reflect changes of column values in the underlying table. The existence of a hash table does not affect the processing cost of other updating jobs in the system.
   • If using a Sorted List Probe, a sorted list result is created containing all the rows from local selection against the table on the first probe. The structure of the sorted list table is such that rows with the same join value are sorted together in the list. The location of the rows for any given join value can be found by probing using the join value.
   • If using a Table Scan, locate the first row that satisfies the join condition or local row selection columns of the secondary table. The join could be implemented with a table scan when the secondary table is a user-defined table function.
4. Determines if the row is selected by applying any remaining selection local to the first secondary dial.

   If the secondary dial row is not selected then the next row that satisfies the join condition is located. Steps 1 through 4 are repeated until a row that satisfies both the join condition and any remaining selection is selected from all secondary tables

5. Returns the result join row.
6. Processes the last secondary table again to find the next row that satisfies the join condition in that dial.

   During this processing, when no more rows satisfying the join condition can be selected, the processing backs up to the logical previous dial. It attempts to read the next row that satisfies its join condition.

7. Ends processing when all selected rows from the primary table are processed.

Note the following characteristics of a nested loop join:

• If ordering or grouping is specified, and all the columns are over a single table eligible to be the primary, then the optimizer costs the join with that table as the primary table, performing the grouping and ordering with an index.
• If ordering and grouping is specified on two or more tables or if temporary objects are allowed, Db2 for i breaks the processing of the query into two parts:
  1. Perform the join selection, omitting the ordering or grouping processing, and write the result rows to a temporary work table. This method allows the optimizer to consider any table of the join query as a candidate for the primary table.
  2. Perform the ordering or grouping on the data in the temporary work table.

Queries that cannot use hash join

Hash join cannot be used for queries that:

• Hash join cannot be used for queries involving physical files or tables that have read triggers.
• Require that the cursor position is restored as the result of the SQL ROLLBACK HOLD statement or the ROLLBACK CL command. For SQL applications using commitment control level other than *NONE, this method requires that *ALLREAD be specified as the value for the ALWBLK precompiler parameter.
• Hash join cannot be used for a table in a join query where the join condition something other than an equals operator.
• CQE does not support hash join if the query contains any of the following:
  • Subqueries unless all subqueries in the query can be transformed to inner joins.
  • UNION or UNION ALL
  • Perform left outer or exception join.
  • Use a DDS created join logical file.