Query Optimization in Relational Database Systems - Automated Physical Database Design and Tuning - page 36

belongs to group 2. In this way, a MEMO compactly represents a potentially
very large number of operator trees. Also note that the children of physical
groupExpressions also point to the most e cient groupExpression in the cor-
responding groups . For instance, groupExpression 3.8 represents a hash join
operator whose left-hand child is the second groupExpression in group 1 and
whose right-hand child is the second groupExpression in group 2.
In addition to representing operator trees, the MEMO provides basic in-
frastructure for management of groupExpression properties. There are two
kinds of properties. On one hand, logical properties are shared by all
groupExpressions in a group and are therefore associated with the group itself.
Examples of logical properties are the cardinality of a group , the tables over
which the group operates, and the columns that are output by the group .On
the other hand, physical properties are specific to physical groupExpressions
and typically vary within a group . Examples of physical properties are the
order of tuples in the result of a physical groupExpression (analogous to an
interesting order in System-R) and the cost of the best execution plan rooted
at a groupExpression .

2.3.3.2 Optimization Tasks

The enumeration algorithm in Cascades is divided into several tasks . Initially,
the logical operator tree describing the input query is copied into the initial
MEMO (see Figure 2.7b for an example). Then, the optimizer schedules the
optimization of the group corresponding to the root of the original query
tree ( group 5 in the figure). This task in turn triggers the optimization of
smaller and smaller operator subtrees and eventually returns the most e cient
execution plan for the input query. This execution plan is copied out from the
final MEMO and passed to the execution engine. Figure 2.8 shows the five types
of tasks in a Cascades-based optimizer and the dependencies among them.
We next describe each of these tasks in some detail.

OptimizeGroup: This task takes as inputs a group G , a cost-bound UB ,
and a set of required physical properties RP . It returns the most e-
cient execution plan (if one exists) that implements group G , costs no

OptimizeInputs

OptimizeGroup ApplyRule

ExploreGroup ExploreExpression

FIGURE 2.8 Optimization tasks in a Cascades optimizer.