Database Reference

In-Depth Information

To obtain this cost, we calculate
cost

(either by using

optimization calls or by leveraging the cost model of the optimizer). Therefore,

we derive the cost of a nonatomic configuration
C
for an
UPDATE
query
q
as

(

q

,
{

I

}
)
−

cost

(

q

,
∅
)

C
)
+

cost

(

q

,

C

)

=

min
C
⊂
C
∧
atomic
(
C
)
cost

(

q

,

cost

(

q

,
{

I

}
)

I

∈

inner
SELECT

,
∅
)

So far we have discussed the definition of atomic configurations and how

they can be used to avoid some optimization calls but have given no proce-

dure to identify such configurations for a given query. We next introduce two

approaches to address this issue.

−

cost

(

q

5.2.1.1

Static Strategy Based on Query

Processor Restrictions

The characteristics of the query processor can determine what constitutes an

atomic configuration. Suppose, for instance, that for any execution plan for

q
, the DBMS will not use more than
j
indexes per table. This restriction

reflects the design point in the DBMS that no more than a small number

of indexes may be intersected to identify tuples of one table (query engines

that do not support index intersection strategies result in
j

1). In these

scenarios, we can easily determine whether a given configuration
C
is atomic

and, if not, generate all atomic configurations that consist of subsets of indexes

from
C
. Once we characterize the space of atomic configurations, these can be

evaluated on demand during the search strategy. Specifically, when we need to

evaluate
cost

=

(

,

)

, we first optimize
q
under all atomic configurations that

are subsets of
C
and have not yet been evaluated and then derive the cost of

q
under
C
. While initially there would be more optimization calls for atomic

configurations than the originally requested ones, the trend eventually reverses

as atomic configurations represent a small fraction of the search space.

q

C

5.2.1.2

Adaptive Strategy Based on Index Benefit Graphs

The previous technique makes assumptions on the characteristics of the query

processor. We now describe an alternative approach that detects atomic con-

figurations for a query based on interaction among indexes. Specifically, we

leverage the concept of an
index benefit graph
(or
IBG
for short), which

eciently encodes the properties of optimal plans under reasonably “well-

behaved” query optimizers.

The
IBG
for a query
q
is a directed graph, where each node is defined

by (1) a subset
C
of indexes, (2) the indexes
U

C
that were part of the

plan for
q
under configuration
C
, and (3) the estimated cost of such a plan.

Additionally, there is a directed edge between nodes
N
1
=
(

⊆

C
1
,

U
1
,

cost
1
)

and

N
2

=
(

C
2
,

U
2
,

cost
2
)

if
C
1

=

C
2
∪{

I

}

for some
I

∈

U
1
. Figure 5.2 shows an

IBG
for indexes

, where the used indexes
U
are underlined, and

plan costs are shown in parentheses within each node. Based on the definition

{

I
1
,

I
2
,

I
3
,

I
4
}

Search WWH ::

Custom Search