Database Reference
In-Depth Information
Assuming that the optimizer returns the access path requests associated
with each index-based subtree in the query execution plan, we can transform
the relevant subplans by simply reimplementing each request based on the set
of available indexes. Consider a physical request
ρ
×
(
,
,
,
,
,
)
(see
Section 4.1.3), and suppose that we want to calculate the cost of an alternative
subplan that uses index
I
=
N
T
E
R
P
O
A
c
n
)
to implement
ρ
. In order to do so,
we can conceptually simulate the implementation rules in the optimizer that
produced
ρ
in the first place and can approximate what the optimizer would
have obtained under the hypothetical configuration that contains index
I
.As
an example, let
I
ρ
be the longest prefix
(
=
T
(
c
1
,... ,
c
k
)
that appears in
E
(equality
predicates), optionally followed by
c
k
+
1
if
c
k
+
1
appears in
R
(range predicate).
We can then implement
ρ
by (1) seeking
I
with the predicates associated
with columns in
I
ρ
, (2) filtering the remaining predicates in
E
c
1
,... ,
P
that
can be answered with all columns in
I
, (3) looking up a primary index to
retrieve columns that are required by
∪
R
∪
ρ
but not available in
I
, (4) filtering
the remaining predicates in
E
P
, and (5) optionally sorting the result
if
O
is not already satisfied. Figure 5.6a shows the pattern for single-index
execution plans that implement this logical tree.
As
∪
R
∪
a
simple
example,
consider
the
single-table
logical
expression
d
(σ
a
+
b
=
2
∧
c
=
4
(
T
))
and the associated request
ρ
=
(
T
,
E
=
{
c
}
,
R
=
∅
,
P
=
{
(
(note that there is a sort requirement of col-
umn
d
). Figure 5.6b shows the resulting execution subplan for an index
a
,
b
)
}
,
O
=
{
d
}
,
A
=
{
a
,
b
,
d
}
)
Sort
Filter
Remaining
Predicates
Sort
[d]
Fetch Cols in
EURUPUOUA
Index Join
Filter
Available
Predicates in
E U R U P
Filter
[a+b=2]
Filter
[c=4 AND a+b=2]
RID Lookup
Index Seek/Scan
(cols in Ip)
Index Seek
[c=4]
Index Scan
(a) Original pattern.
(b)
I
1
(
c
,
a
,
b
).
(c)
I
2
(
d
,
c
,
b
,
a
).
FIGURE 5.6
Generic plan pattern to implement local transformations.
Search WWH ::
Custom Search