When you are joining four or fewer tables, Adaptive Server considers all possible permutations of join orders for the tables. However, due to the iterative nature of Adaptive Server’s optimizer, queries on more than four tables examine join order combinations in sets of two to four tables at a time. This grouping during join order costing is used because the number of permutations of join orders multiplies with each additional table, requiring lengthy computation time for large joins. The method the optimizer uses to determine join order has excellent results for most queries and requires much less CPU time than examining all permutations of all combinations.
If the number of tables in a join is greater than 25, Adaptive Server automatically reduces the number of tables considered at a time. Table 6-1 shows the default values.
Tables joined |
Tables considered at a time |
|---|---|
4 – 25 |
4 |
26 – 37 |
3 |
38 – 50 |
2 |
The optimizer starts by considering the first two to four tables, and determining the best join order for those tables. It remembers the outer table from the best plan involving the tables it examined and eliminates that table from the set of tables. Then, it optimizes the best set of tables out of the remaining tables. It continues until only two to four tables remain, at which point it optimizes them.
For example, suppose you have a select statement with the following from clause:
from T1, T2, T3, T4, T5, T6
The optimizer looks at all possible sets of 4 tables taken from these 6 tables. The 15 possible combinations of all 6 tables are:
T1, T2, T3, T4 T1, T2, T3, T5 T1, T2, T3, T6 T1, T2, T4, T5 T1, T2, T4, T6 T1, T2, T5, T6 T1, T3, T4, T5 T1, T3, T4, T6 T1, T3, T5, T6 T1, T4, T5, T6 T2, T3, T4, T5 T2, T3, T4, T6 T2, T3, T5, T6 T2, T4, T5, T6 T3, T4, T5, T6
For each one of these combinations, the optimizer looks at all the join orders (permutations). For each set of 4 tables, there are 24 possible join orders, for a total of 360 (24 * 15) permutations. For example, for the set of tables T2, T3, T5, and T6, the optimizer looks at these 24 possible orders:
T2, T3, T5, T6 T2, T3, T6, T5 T2, T5, T3, T6 T2, T5, T6, T3 T2, T6, T3, T5 T2, T6, T5, T3 T3, T2, T5, T6 T3, T2, T6, T5 T3, T5, T2, T6 T3, T5, T6, T2 T3, T6, T2, T5 T3, T6, T5, T2 T5, T2, T3, T6 T5, T2, T6, T3 T5, T3, T2, T6 T5, T3, T6, T2 T5, T6, T2, T3 T5, T6, T3, T2 T6, T2, T3, T5 T6, T2, T5, T3 T6, T3, T2, T5 T6, T3, T5, T2 T6, T5, T2, T3 T6, T5, T3, T2
Let’s say that the best join order is determined to be:
T5, T3, T6, T2
At this point, T5 is designated as the outermost table in the query.
The next step is to choose the second-outermost table. The optimizer eliminates T5 from consideration as it chooses the rest of the join order. Now, it has to determine where T1, T2, T3, T4, and T6 fit into the rest of the join order. It looks at all the combinations of four tables chosen from these five:
T1, T2, T3, T4 T1, T2, T3, T6 T1, T2, T4, T6 T1, T3, T4, T6 T2, T3, T4, T6
It looks at all the join orders for each of these combinations, remembering that T5 is the outermost table in the join. Let’s say that the best order in which to join the remaining tables to T5 is:
T3, T6, T2, T4
So the optimizer chooses T3 as the next table after T5 in the join order for the entire query. It eliminates T3 from consideration in choosing the rest of the join order.
The remaining tables are:
T1, T2, T4, T6
Now we’re down to 4 tables, so the optimizer looks at all the join orders for all the remaining tables. Let’s say the best join order is:
T6, T2, T4, T1
This means that the join order for the entire query is:
T5, T3, T6, T2, T4, T1
