Characterizing the Search Space - Automated Physical Database Design and Tuning - page 65

ρ 3 = 500x(T, {(z, 1)}, Ø, Ø, Ø, {c,d,e}) R.w=T.z

ρ 4 = (T, {(c, 5000)}, Ø, {({d,e}, 3000)}, Ø, {z})

ρ 2 = 2500x(S, {(y, 0.2)}, Ø, Ø, Ø, Ø)

σ T.c=8 ^ T.d+T.e=100

R.x=S.y

ρ 1 = (R, {(a, 4500)}, {(b, 5000)}, Ø, Ø, {x,w})

T

σ R.a=5 ^ R.b<8

S

R

FIGURE 4.3 Sample requests for different nodes in a subquery.

As an example, request ρ 1 is associated with the selection condition on ta-
ble R and specifies that there are (1) a sargable column a associated with
an equality predicate expecting to return 4,500 tuples, (2) a sargable column
b associated with a range predicate expecting to return 5,000 tuples, (3) no
columns in nonsargable predicates, (4) no order requested, and (5) additional
required columns ρ 2 was generated when the op-

timizer considered an index-based join alternative with R and S as the outer
and inner relations, respectively. Request

w and x . Similarly, request

y is part of an
equality-based predicate that would be executed 2,500 times (once for each
outer row). The average number of tuples matched and returned from S is 0.2,
and therefore the corresponding index join would produce 2

ρ 2 specifies that T 2 .

, 500 · 0 . 2 = 500

rows overall.
From an engineering point of view, the instrumentation approach is ap-
pealing because it is not very intrusive. In fact, the modifications required to
enable this instrumentation are restricted to a single component in the opti-
mizer. From an algorithmic point of view, the instrumentation technique does
not rely on guesswork to reason with access path requests. Since requests are
intercepted during optimization, we do not miss candidates that might not
be apparent by looking at the final execution plan, nor do we propose many
candidates that are syntactically valid but might not be exploitable during
optimization. ∗ From a practical point of view, the number of requests that
are generated for input queries is not very large. As an illustration, Figure 4.4
shows the total number of requests for a typical TPC-H workload. We can
see that even for relatively complex queries, the number of requests is mod-
erate (compare these numbers with the total number of candidate indexes in
Figure 3.2).

∗ Note that we can approximate access path requests from inspecting resulting execution plans
as described in Section 4.1.2. This procedure is not as accurate as the instrumentation-based
approach but requires no changes to the query optimizer.