Database Reference
In-Depth Information
10.1.1 Instrumenting the Optimizer
The alerter leverages information gathered during regular query optimization
by reusing the instrumentation-based approach of Section 4.1.3. Figure 10.2a
illustrates some access path requests intercepted for a three-way join query.
Request
ρ 1 is associated with the selection condition on table T 1 and specifies
that (1) there is one equality predicate on column T 1 .
a returning 2,500 tuples,
(2) the additional required columns are T 1 .
x , and (3) the sub-
plan would be executed once at runtime. Similarly, request ρ 2 was generated
when the optimizer considered an index-based join alternative with T 1 and
T 2 as the outer and inner relations, respectively. It specifies that T 2 .
a , T 1 .w , and T 1 .
y is part
of an equality-based predicate that would be executed 2,500 times (once per
outer row) and produce 500 rows overall. There is no request for the join at
the top right of Figure 10.2a because an index-based implementation requires
the inner relation to be a base table.
Rather than gathering all possible requests for a given query, we keep only
those that are associated with an operator in the final execution plan. For
the plan in Figure 10.2b, such requests are
. The reason for this
restriction is twofold. First, returning requests for all subplans enumerated
by the optimizer imposes a larger overhead on top of regular optimization.
Second, requests associated with the final plan are sucient to reason in
terms of local plan transformations (see Section 5.2.2.1) and thus infer plan
costs without performing additional optimizer calls (we discuss this issue in
the next section).
It is important to note that some requests might conflict with others.
For instance, requests
{ ρ 1 2 3 5 }
ρ 5 in Figure 10.2b are mutually exclusive. In
other words, if a plan implements
ρ 3 and
ρ 3 (that is, contains an index-based join
with T 3 as the inner table), it could not simultaneously implement
ρ 5 .As
another example, request
ρ 5 in Figure 10.2b would conflict with a request
ρ 6
} ) rooted at the Scan(T 3 )
operator (we do not show ρ 6 in Figure 10.2 for simplicity). The reason is that
any execution plan uses one access path for each table. We can implement
either ρ 6 (by scanning an index on T 3 and filtering T 3 .b = 8 on the fly) or ρ 5
(by directly seeking valid tuples in T 3 ).
To explicitly represent these relationships, we encode the requests in an
AND/OR tree, where internal nodes indicate whether the respective subtrees
can be satisfied simultaneously ( AND ) or are mutually exclusive ( OR ). The
AND/OR tree is built by traversing the execution plan in postorder. Figure 10.3
illustrates how to generate the AND/OR tree for an input execution plan P .
Intuitively, if P is a single node, we return a simple AND/OR tree with the
request (if any) of such node (case 1 in Figure 10.3). Otherwise, if P 's root
= (
T 3 ,
E
=∅ ,
R
=∅ ,
P
=∅ ,
O
=∅ ,
A
={
b
,
z
The AND/OR tree can be seen as a restriction of the CMEMO structure of Chapter 5 considering
only the final execution plan.
Search WWH ::




Custom Search