Database Reference
In-Depth Information
Sort
[D]
Sort
[D]
Filter
[A<10 and B<10 and A+C=8]
Filter
[A+C=8]
Filter
[A+C=8]
Index Scan
[R(D,A,B,C,E)]
Index Join
[RID]
Index Join
Index
Intersection
RID
Lookup
Index Seek
[R(A)<10]
RID
Lookup
Index Seek
[R(A)<10]
Index Seek
[R(B)<10]
(a)
(b)
(c)
FIGURE 4.1
Alternative index strategies for the same single-table access
path request. (Used with permission from Bruno, N. & Chaudhuri, S. In
Proceedings of the ACM International Conference on Management of Data
[SIGMOD],
2005.)
This approach is also used to generate index-based join plans (which im-
plement joins between an arbitrary outer relation and a single-table inner
relation that is repeatedly accessed using an index to obtain join matches). In
this case, the access path generation module works with the inner table only,
and the joined column in the table is considered part of a sargable (equality)
predicate. For instance, consider the query fragment
(Q
Q.
x
=
T
.
y
T
)
, where
Q
represents an arbitrary complex expression that returns the outer relation
in the index-based join. Conceptually, the optimizer passes to the access path
selection module the single-table expression
σ
T
.
y
=
?
(
T
)
and proceeds as before,
considering
T
y
a column in a sargable predicate with an (unspecified) con-
stant value, which would be evaluated multiple times (once per each tuple
returned by
Q
).
.
4.1.3.2
Instrumenting the Optimizer
Figure 4.2 shows how a query optimizer can be instrumented to enable reason-
ing with access path requests. Every time the optimizer issues an access path
request through an implementation rule, we obtain the information that is rel-
evant to such requests and store it at the root of the originating logical plan. At
the end of optimization, we return, along with the execution plan, the set of all
index requests generated during optimization. Intuitively, each index request
encodes the properties of any index strategy that might implement the subtree
Search WWH ::
Custom Search