Database Reference
In-Depth Information
bestCostForConfiguration
(n:Node in AND/OR graph for query q,
C:Configuration)
return
cost
(
q
,
C
)
01
if
nis
APR
i
02
return
leafNodeCalculation(
APR
i
,C)
// (Section 5.2.2)
03
else if
n is AND( op,
{
g
1
,g
2
,
...
,g
n
}
)
04
return
localCost
(
op
)+
i
bestCostForConfiguration
(g
i
,C)
05
else
//nis
OR
(
{
g
1
,g
2
,
...
,g
n
}
)
return
min
i
bestCostForConfiguration
(g
i
,C)
06
FIGURE 5.11
Reoptimizing queries in
CPQO
. (Used with permission from
Bruno N. & Nehme, R. In
Proceedings of the ACM International Conference
on Management of Data [SIGMOD]
, 2008.)
structure (the notation 7
.
{
1
,
2
,
3
}
in physical operators refers to the set of
groupExpressions
, and the best alternative for an
OR
node is
shown with a bold arrow). In summary, the
CMEMO
structure is effectively the
AND/OR
graph induced from the final
MEMO
produced by a
CPQO
optimizer.
{
7
.
1
,
7
.
2
,
7
.
3
}
5.4.2 Fast Reoptimization in CPQO
The
CMEMO
encapsulates all the optimization state that is possible to
obtain without knowing a specific configuration instance. Additionally,
it
contains
enough
information
to
derive
configuration-specific
execu-
tion subplans. For a given configuration
C
and
CMEMO
M
, algorithm
(
)
bestCostForConfiguration(
r oot
,
C
)
in Figure 5.11 returns the cost
of the best execution plan for the query represented by
M
under configura-
tion
C
. The algorithm operates depending on the type of input node
n
.If
n
is a leaf node (i.e., an
APR
node), we estimate the cost of the best configu-
ration as explained in Section 5.2.2. Otherwise, if it is an internal
AND
node,
we calculate the best cost by adding to the
localCost
of the
groupExpression
in
n
the sum of the best costs of each of
n
's children (calculated recursively).
Finally, if
n
is an
OR
node, we return the minimum cost among the choices.
M
5.4.3 Handling Updates
So far we implicitly discussed
SELECT
-only workloads. In reality,
CPQO
must
take into consideration
UPDATE
queries as well. The main impact of an update
query is that some (or all) indexes defined over the updated table must also
be updated as a side effect. To address updates,
CPQO
similarly modifies
the configuration-dependent implementation rules that deal with updates and
replaces them with internal
UAPR
nodes that encode the relevant update
information. At reoptimization time, we calculate the cost of updating all
relevant indexes in the configuration for each
UAPR
node in a similar way to
what was described for regular
APR
nodes earlier in this section.
Search WWH ::
Custom Search