Even using this dynamic programming approach, the comparison of all possible join orders was considered by Selinger to be too expensive.
Selinger dealt with the join problem by using heuristics to reduce the search space. The heuristics reduce the number of join order permutations which are considered. Selinger reduced the search space first by considering only left-deep join trees (i.e. precluding the much larger, bushy tree search space). A query tree is left deep if for every join, the right input is not the result of a previous join. Figure 4.1 shows a left deep join tree.
| 4. Related Work: |
<System R>
<Bottom Up>
<Join Order Heuristics>
<Query Blocks>
<Rules>
<Top Down>
<Volcano>
<Phases>
<Specialized Techniques>
<Unique Rules>
4.1: Left-Deep |
|---|
| 
Page 7
|