Query Optimization in Relational Database Systems - Automated Physical Database Design and Tuning - page 32

an extensible prototype developed at IBM in the mid-nineties. Finally, we
discuss in some detail Cascades/Volcano, a transformation-based enumera-
tion algorithm that introduces several concepts that are used in subsequent
chapters. Rather than providing a detailed description of all the features in
these enumeration architectures, we give instead a high-level overview of the
frameworks and focus on the specific components that are relevant to our
discussion.

2.3.1 System-R
System-R was a seminal project that influenced much of the subsequent work
in query optimization. We now present one of the fundamental algorithms
introduced in System-R for the purpose of join enumeration. The join enu-
meration algorithm in System-R uses dynamic programming, and it assumes
that the cost model satisfies the principle of optimality. Specifically, we as-
sume that in order to obtain an optimal plan for a query consisting of k joins
it suces to consider only the optimal plans for query subexpressions that
consist of fewer joins and to extend those plans with additional joins. In other
words, the optimal plan is obtained by combining optimal subplans.
The dynamic programming algorithm, illustrated in Figure 2.6, views the
input as a set of relations to be joined and works in a bottom-

up manner. We assume there is an associative array bestPlan , or each sub-
set of tables

{ R 1 ,... , R n }

. First,
we generate plans for every table in the query (lines 1 and 2). Such access
path selection is encapsulated in function bestAccessPath and consists of
scans, seeks, or, optionally, more complex plans using index intersections and
unions. Then, the dynamic programming algorithm performs n

R , that returns the best calculated plan so far for R

1 iterations
in lines 3 to 8. At the end of the i - th iteration, we produce the optimal
plans for all subexpressions that join i tables. Line 4 considers each subset
R of i tables, and line 5 attempts to further partition each such subset into

−

JoinEnumeration ( { R 1 ,... , R n } :input tables)

foreach R i ∈{ R 1 ,... , R n }

1

bestPlan( { R i } ) = bestAccessPath( R i )

2

for i=2 to n

3

foreach R ⊂{ R 1 ,... , R n } such that | R | =i

4

foreach R ⊂ R such that R =∅

5

candPlan = bestJoinAlternative(bestPlan( R ),
bestPlan( R − R ))

6

if (cost(candPlan) < cost(bestPlan( R ))
// cost(NULL) = ∞

7

bestPlan( R ) = candPlan

8

return bestPlan( { R 1 ,... , R n } )

9

FIGURE 2.6 Dynamic programming algorithm to enumerate joins.