Databases Reference
In-Depth Information
Figure 5-1:
Query tree representation.
Transformation Rules
The SQL Server Query Optimizer uses transformation rules to explore the search space;
that is, to explore the set of possible execution plans for a specific query. Transformation
rules are based on relational algebra, taking a relational operator tree and generating
equivalent alternatives, in the form of equivalent relational operator trees. At the
most fundamental level, a query consists of logical expressions, and applying these
transformation rules will generate equivalent logical and physical alternatives, which
are stored in memory, in a structure called the memo, for the entire duration of the
optimization process. As already mentioned, and explained later in this chapter, the
Query Optimizer uses three optimization stages, and different transformation rules are
applied in each stage.
Each transformation rule has a pattern and a substitute. The pattern is the expression
to be analyzed and matched, and the substitute is the equivalent expression that it is
