Databases Reference
In-Depth Information
physical operators, and are organized into groups of equivalent alternatives, such that
each alternative in the same group produces the same results. Alternatives in the same
group also share the same logical properties and, in the same way that operators can
reference other operators on a relational tree, groups can also reference other groups in
the memo structure.
A new memo structure is created for each optimization. The Query Optimizer first
copies the original query tree's logical expressions into the memo structure, placing
each operator from the query tree in its own group, and then triggers the entire optimi-
zation process. During this process, transformation rules are applied to generate all the
alternatives, starting with these initial logical expressions.
As the transformation rules produce new alternatives, these are added to their equivalent
groups. Transformation rules may also produce a new expression which is not
equivalent to any existing group, and which causes a new group to be created. As I
mentioned, each alternative in a group is a simple logical or physical expression, like
a join or a scan, and a plan will be built using a combination of these alternatives. The
number of these alternatives, and even groups, in a memo structure can be huge.
Although there is the possibility that different combinations of transformation rules may
end up producing the same expressions, the memo structure is designed to avoid both
the duplication of these alternatives and redundant optimizations. By doing this, it saves
memory and is more efficient, as it does not have to search the same plan alternatives
more than once.
Although both logical and physical alternatives are kept in the memo structure, only the
physical alternatives are costed. Thus, at the end of the optimization process, the memo
contains all of the alternatives considered by the Query Optimizer, but only one plan is
selected, based on its cost.
Now, I will show a simplified example of how the memo structure is built for a simple
query, using listing 5-19.
