DB2 Version 9.7 for Linux, UNIX, and Windows

Strategies for selecting optimal joins

The optimizer uses various methods to select an optimal join strategy for a query. Among these methods, which are determined by the optimization class of the query, are several search strategies, star-schema joins, early out joins, and composite tables.

The join-enumeration algorithm is an important determinant of the number of plan combinations that the optimizer explores.

Greedy join enumeration
- Is efficient with respect to space and time requirements
- Uses single direction enumeration; that is, once a join method is selected for two tables, it is not changed during further optimization
- Might miss the best access plan when joining many tables. If your query joins only two or three tables, the access plan that is chosen by greedy join enumeration is the same as the access plan that is chosen by dynamic programming join enumeration. This is particularly true if the query has many join predicates on the same column that are either explicitly specified, or implicitly generated through predicate transitive closure.
Dynamic programming join enumeration
- Is not efficient with respect to space and time requirements, which increase exponentially as the number of joined tables increases
- Is efficient and exhaustive when searching for the best access plan
- Is similar to the strategy that is used by DB2® for z/OS

Star-schema joins

The tables that are referenced in a query are almost always related by join predicates. If two tables are joined without a join predicate, the Cartesian product of the two tables is formed. In a Cartesian product, every qualifying row of the first table is joined with every qualifying row of the second table. This creates a result table that is usually very large, because its size is the cross product of the size of the two source tables. Because such a plan is unlikely to perform well, the optimizer avoids even determining the cost of this type of access plan.

The only exceptions occur when the optimization class is set to 9, or in the special case of star schemas. A star schema contains a central table called the fact table, and other tables called dimension tables. The dimension tables have only a single join that attaches them to the fact table, regardless of the query. Each dimension table contains additional values that expand information about a particular column in the fact table. A typical query consists of multiple local predicates that reference values in the dimension tables and contains join predicates connecting the dimension tables to the fact table. For these queries, it might be beneficial to compute the Cartesian product of multiple small dimension tables before accessing the large fact table. This technique is useful when multiple join predicates match a multicolumn index.

The DB2 data server can recognize queries against databases that were designed with star schemas having at least two dimension tables, and can increase the search space to include possible plans that compute the Cartesian product of dimension tables. If the plan that computes the Cartesian product has the lowest estimated cost, it is selected by the optimizer.

This star schema join strategy assumes that primary key indexes are used in the join. Another scenario involves foreign key indexes. If the foreign key columns in the fact table are single-column indexes, and there is relatively high selectivity across all dimension tables, the following star-schema join technique can be used:

Process each dimension table by:
- Performing a semi-join between the dimension table and the foreign key index on the fact table
- Hashing the record ID (RID) values to dynamically create a bitmap
For each bitmap, use AND predicates against the previous bitmap.
Determine the surviving RIDs after processing the last bitmap.
Optionally sort these RIDs.
Fetch a base table row.
Rejoin the fact table with each of its dimension tables, accessing the columns in dimension tables that are needed for the SELECT clause.
Reapply the residual predicates.

This technique does not require multicolumn indexes. Explicit referential integrity constraints between the fact table and the dimension tables are not required, but are recommended.

The dynamic bitmaps that are created and used by star-schema join techniques require sort heap memory, the size of which is specified by the sortheap database configuration parameter.

Early out joins

The optimizer might select an early out join when it detects that each row from one of the tables only needs to be joined with at most one row from the other table.

An early out join is possible when there is a join predicate on the key column or columns of one of the tables. For example, consider the following query that returns the names of employees and their immediate managers.

   select employee.name as employee_name,
       manager.name as manager_name
     from employee as employee, employee as manager
     where employee.manager_id = manager.id

Assuming that the ID column is a key in the EMPLOYEE table and that every employee has at most one manager, this join avoids having to search for a subsequent matching row in the MANAGER table.

An early out join is also possible when there is a DISTINCT clause in the query. For example, consider the following query that returns the names of car makers with models that sell for more than $30000.

   select distinct make.name
     from make, model
     where
       make.make_id = model.make_id and
       model.price > 30000

For each car maker, we only need to determine whether any one of its manufactured models sells for more than $30000. Joining a car maker with all of its manufactured models selling for more than $30000 is unnecessary, because it does not contribute towards the accuracy of the query result.

An early out join is also possible when the join feeds a GROUP BY clause with a MIN or MAX aggregate function. For example, consider the following query that returns stock symbols with the most recent date before the year 2000, for which a particular stock's closing price is at least 10% higher than its opening price:

   select dailystockdata.symbol, max(dailystockdata.date) as date
     from sp500, dailystockdata
     where
       sp500.symbol = dailystockdata.symbol and
       dailystockdata.date < '01/01/2000' and
       dailystockdata.close / dailystockdata.open >= 1.1
     group by dailystockdata.symbol

The qualifying set is the set of rows from the DAILYSTOCKDATA table that satisfies the date and price requirements and joins with a particular stock symbol from the SP500 table. If the qualifying set from the DAILYSTOCKDATA table (for each stock symbol row from the SP500 table) is ordered as descending on DATE, it is only necessary to return the first row from the qualifying set for each symbol, because that first row represents the most recent date for a particular symbol. The other rows in the qualifying set are not required.

Composite tables

When the result of joining a pair of tables is a new table (known as a composite table), this table usually becomes the outer table of a join with another inner table. This is known as a composite outer join. In some cases, particularly when using the greedy join enumeration technique, it is useful to make the result of joining two tables the inner table of a later join. When the inner table of a join consists of the result of joining two or more tables, this plan is known as a composite inner join. For example, consider the following query:

   select count(*)
     from t1, t2, t3, t4
     where
       t1.a = t2.a and
       t3.a = t4.a and
       t2.z = t3.z

It might be beneficial to join table T1 and T2 (T1xT2), then join T3 and T4 (T3xT4), and finally, to select the first join result as the outer table and the second join result as the inner table. In the final plan ( (T1xT2) x (T3xT4) ), the join result (T3xT4) is known as a composite inner join. Depending on the query optimization class, the optimizer places different constraints on the maximum number of tables that can be the inner table of a join. Composite inner joins are allowed with optimization classes 5, 7, and 9.