Databases Reference
In-Depth Information
generated as an output. For example, for the commutativity rule, which is explained later,
a transformation rule can be defined as:
Expr1 join Expr2 - > Expr2 join Expr1
.
SQL Server will match the pattern
Expr1 join Expr2
, like in
Individual join Customer
,
and will produce the equivalent expression,
Customer join Individual
. The two
expressions are equivalent because both return exactly the same results.
Initially, the query tree contains only logical expressions, and transformation rules are
applied to these logical expressions to generate either logical or physical expressions. As
an example, a logical expression can be the definition of a logical join, whereas a physical
expression could be an actual join implementation, like a Merge Join or a Hash Join. Bear
in mind that transformation rules cannot be applied to physical expressions.
The main types of transformation rules include simplification, exploration and imple-
mentation rules. Simplification rules produce simpler logical trees as their outputs,
and are mostly used during the simplification phase, before the full optimization.
Exploration rules, also called logical transformation rules, generate logical equivalent
alternatives; and implementation rules, or physical transformation rules, are used to
obtain physical alternatives. Both exploration and implementation rules are executed
during the full optimization phase.
Examples of exploration rules include the commutativity and associativity rules, which
are used in join optimization. Commutativity and associativity rules are defined as
A join
B - > B join A
and
(A join B) join C - > A join (B join C)
respectively. The commutativity
rule,
A join B - > B join A
, means that
A join B
is equivalent to
B join A
, and joining
the tables A and B in any order will return the same results. Also note that applying
the commutativity rule twice will generate the original expression again; that is, if you
initially apply this transformation to obtain
B join A
, and then later apply the same
transformation, you can obtain
A join B
again. However, the Query Optimizer can
handle this problem in order to avoid duplicated expressions. In the same way, the
associativity rule shows that
(A join B) join C
is equivalent to
A join (B join C)
as they
also both produce the same results.
