Designing a Cost Model - Automated Physical Database Design and Tuning - page 82

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 }