DB2 Version 9.7 for Linux, UNIX, and Windows

Join methods

The optimizer can choose one of three basic join strategies when queries require tables to be joined: nested-loop join, merge join, or hash join.

Nested-loop join

A nested-loop join is performed in one of the following two ways:

Scanning the inner table for each accessed row of the outer table
For example, column A in table T1 and column A in table T2 have the following values:
Outer table T1: Column A Inner table T2: Column A

2 3

3 2

3 2

3

1
To complete a nested-loop join between tables T1 and T2, the database manager performs the following steps:
1. Read the first row in T1. The value for A is 2.
2. Scan T2 until a match (2) is found, and then join the two rows.
3. Repeat Step 2 until the end of the table is reached.
4. Go back to T1 and read the next row (3).
5. Scan T2 (starting at the first row) until a match (3) is found, and then join the two rows.
6. Repeat Step 5 until the end of the table is reached.
7. Go back to T1 and read the next row (3).
8. Scan T2 as before, joining all rows that match (3).
Performing an index lookup on the inner table for each accessed row of the outer table
This method can be used if there is a predicate of the form:
```
   expr(outer_table.column) relop inner_table.column
```
where relop is a relative operator (for example =, >, >=, <, or <=) and expr is a valid expression on the outer table. For example:
```
   outer.c1 + outer.c2 <= inner.c1
   outer.c4 < inner.c3
```
This method might significantly reduce the number of rows that are accessed in the inner table for each access of the outer table; the degree of benefit depends on a number of factors, including the selectivity of the join predicate.

Outer table T1: Column A	Inner table T2: Column A
2	3
3	2
3	2
	3
	1

When it evaluates a nested-loop join, the optimizer also decides whether to sort the outer table before performing the join. If it sorts the outer table, based on the join columns, the number of read operations against the inner table to access pages on disk might be reduced, because they are more likely to be in the buffer pool already. If the join uses a highly clustered index to access the inner table, and the outer table has been sorted, the number of accessed index pages might be minimized.

If the optimizer expects that the join will make a later sort more expensive, it might also choose to perform the sort before the join. A later sort might be required to support a GROUP BY, DISTINCT, ORDER BY, or merge join operation.

Merge join

A merge join, sometimes known as a merge scan join or a sort merge join, requires a predicate of the form table1.column = table2.column. This is called an equality join predicate. A merge join requires ordered input on the joining columns, either through index access or by sorting. A merge join cannot be used if the join column is a LONG field column or a large object (LOB) column.

In a merge join, the joined tables are scanned at the same time. The outer table of the merge join is scanned only once. The inner table is also scanned once, unless repeated values occur in the outer table. If repeated values occur, a group of rows in the inner table might be scanned again.

For example, column A in table T1 and column A in table T2 have the following values:

Outer table T1: Column A	Inner table T2: Column A
2	1
3	2
3	2
	3
	3

To complete a merge join between tables T1 and T2, the database manager performs the following steps:

Read the first row in T1. The value for A is 2.
Scan T2 until a match (2) is found, and then join the two rows.
Keep scanning T2 while the columns match, joining rows.
When the 3 in T2 is read, go back to T1 and read the next row.
The next value in T1 is 3, which matches T2, so join the rows.
Keep scanning T2 while the columns match, joining rows.
When the end of T2 is reached, go back to T1 to get the next row. Note that the next value in T1 is the same as the previous value from T1, so T2 is scanned again, starting at the first 3 in T2. The database manager remembers this position.

Hash join

A hash join requires one or more predicates of the form table1.columnX = table2.columnY, for which the column types are the same. For columns of type CHAR, the length must be the same. For columns of type DECIMAL, the precision and scale must be the same. For columns of type DECFLOAT, the precision must be the same. The column cannot be a LONG field column or a LOB column.

First, the designated inner table is scanned and rows are copied into memory buffers that are drawn from the sort heap specified by the sortheap database configuration parameter. The memory buffers are divided into sections, based on a hash value that is computed on the columns of the join predicates. If the size of the inner table exceeds the available sort heap space, buffers from selected sections are written to temporary tables.

When the inner table has been processed, the second (or outer) table is scanned and its rows are matched with rows from the inner table by first comparing the hash value that was computed for the columns of the join predicates. If the hash value for the outer row column matches the hash value for the inner row column, the actual join predicate column values are compared.

Outer table rows that correspond to portions of the table that are not written to a temporary table are matched immediately with inner table rows in memory. If the corresponding portion of the inner table was written to a temporary table, the outer row is also written to a temporary table. Finally, matching pairs of table portions from temporary tables are read, the hash values of their rows are matched, and the join predicates are checked.

For the full performance benefit of hash joins, you might need to change the value of the sortheap database configuration parameter and the sheapthres database manager configuration parameter.

Hash join performance is best if you can avoid hash loops and overflow to disk. To tune hash join performance, estimate the maximum amount of memory that is available for sheapthres, and then tune the sortheap parameter. Increase its setting until you avoid as many hash loops and disk overflows as possible, but do not reach the limit that is specified by the sheapthres parameter.

Increasing the sortheap value should also improve the performance of queries that have multiple sorts.