Optimization of Parallel Execution for Multi-Join Queries.
AbstractIn this paper, we study the subject of exploiting interoperator parallelism to optimize the execution of multi-join queries. Specifically, we focus on two major issues: 1) scheduling the execution sequence of multiple joins within a query, and 2) determining the number of processors to be allocated for the execution of each join operation obtained in 1). For the first issue, we propose and evaluate by simulation several methods to determine the general join sequences, or bushy trees. Despite their simplicity, the heuristics proposed can lead to the general join sequences that significantly outperform the optimal sequential join sequence. The quality of the join sequences obtained by the proposed heuristics is shown to be fairly close to that of the optimal one. For the second issue, it is shown that the processor allocation for exploiting interoperator parallelism is subject to more constraintssuch as execution dependency and system fragmentationthan those in the study of intraoperator parallelism for a single join. The concept of synchronous execution time is proposed to alleviate these constraints. Several heuristics to deal with the processor allocation, categorized by bottom-up and top-down approaches, are derived and are evaluated by simulation. The relationship between issues 1) and 2) is explored. Among all the schemes evaluated, the two-step approach proposed, which first applies the join sequence heuristic to build a bushy tree as if under a single processor system, and then, in light of the concept of synchronous execution time, allocates processors to execute each join in the bushy tree in a top-down manner, emerges as the best solution to minimize the query execution time.
Introduction
There has been a growing interest in applying general purpose parallel machines to database applications
[7, 8, 12, 19, 34, 43, 50]. Several research systems have been developed to explore this
trend, including GAMMA [16], XPRS [49], DBS3 [4], GRACE [31], and BUBBA [6]. Relational
databases have a certain natural affinity to parallelism. Relational operations are set oriented and
this provides the query optimizer lots of flexibility in selecting the parallelizable access path. In
relational database systems, joins are the most expensive operations to execute, especially with the
increases in database size and query complexity [11, 27, 30, 39, 53]. For future database manage-
ment, parallelism has been recognized as a solution for the efficient execution of multi-join queries
[1, 17, 18, 25, 36, 42, 52, 54, 55].
As pointed out in [46], the methods to exploit parallelism in the execution of database operations
in a multiprocessor system can be divided into three categories. First, parallelism can occur in each
operator within a query in such a way that several processors can work, in parallel, on a single
database operation. This form of parallelism is termed intra-operator parallelism and has been
studied extensively. Various solutions for exploiting intra-operator parallelism in multiprocessor
database systems have been reported in the literature. Several algorithms were proposed for parallel
execution of two-way joins in multiprocessor systems [15, 38, 44, 45]. Some researchers further
concerned themselves with multiprocessors of particular architectures such as rings and hypercubes
[3, 40]. The effect of data skew on the performance of parallel joins has also been analyzed in
[14, 32, 51]. The second form of parallelism is termed inter-operator parallelism, meaning that
several operators within a query can be executed in parallel. Third, parallelism can be achieved
by executing several queries simultaneously within a multiprocessor system, which is termed inter-query
parallelism [48]. It can be seen that to exploit the third form of parallelism, one has to
resort to the results derived for inter-operator parallelism within a query. During the past few
years some light has been shed on this issue [13, 21, 22, 37, 42, 46]. As an effort toward this trend,
the objective of this paper is to study and improve the execution of multi-join queries, and devise
efficient schemes to exploit inter-operator parallelism to minimize the query execution time in a
multiprocessor-based database system 1 .
Note that different join execution sequences for a query will result in different execution costs
[47]. Also, the execution time of a join in a multiprocessor system strongly depends on the number
1 The execution time of a query in this paper, similar to that in most related work, means the response time to
complete the query, rather than the total execution time of all processors.
R 5
RR 4
RR 2
RRRR
(a) (b)

Figure

1: Illustration of different join sequences.
of processors allotted for the execution of that join [32]. For instance, a 40 second execution time
of a join on 4 processors may increase to 60 seconds if only 2 processors are used. Thus, the subject
of exploiting inter-operator parallelism for the execution of a multi-join query comprises two major
issues: (i) join sequence scheduling, or query plan generation, i.e., scheduling the execution sequence
of joins in the query, and (ii) processor allocation, i.e., determining the number of processors for
each join obtained in (i) so that the execution time required for the query can be minimized. Clearly,
the join method affects the optimization procedure to exploit parallelism. Under hash joins, we
have the opportunity of using pipelining to improve the performance [15, 21], whereas such an
opportunity is not available when a join method like the sort-merge join is employed. Note that
pipelining causes the effects on join sequence scheduling and processor allocation to be entangled,
and the resulting cost model of each join and the criteria for processor allocation in the presence
of pipelining will thus be intrinsically different from those developed without using pipelining.
As a result, join methods without and with pipelining have to be dealt with separately for best
optimization results. In this paper, we shall focus on the join methods without pipelining, such as
the sort-merge join that is in fact the most prevalent join method in existing database softwares,
and develop a specific solution procedure. Readers interested in optimization on pipelining multiple
joins, which calls for a different procedure due to its different problem formulation, are referred to
[9, 26, 35,
First, for the issue of join sequence scheduling, we develop and evaluate by simulation several
heuristics to determine the join sequence for a multi-join query with the focus on minimizing
the total amount of work required 2 . Specifically, we investigate two sorts of join sequences, namely
sequential join sequences and general join sequences. A join sequence in which the resulting relation
of an intermediate join can only be used in the next join is termed a sequential join sequence. An
example of a sequential join sequence can be found in Figure 1a where every non-leaf node (internal
node) represents the resulting relation from joining its child nodes. A join sequence in which the
resulting relation of a join is not required to be only used in the next join is termed a general join
sequence. For example, the sequence of joins specified by the join sequence tree in Figure 1b is a
general join sequence. Such an execution tree of a general join sequence is called a bushy tree [22],
or composite inners [41].
Note that the bushy tree join sequences did not attract as much attention as sequential ones
in the literature. As a matter of fact, it was generally deemed sufficient, by many researchers,
to explore only sequential join sequences for desired performance in the last decade. This can be
in part explained by the reasons that in the past the power/size of a multiprocessor system was
limited, and that the query structure used to be too simple to require further parallelizing as a
bushy tree. It is noted, however, that these two limiting factors have been phased out by the rapid
increase in the capacity of multiprocessors and the trend for queries to become more complicated
nowadays, thereby justifying the necessity of exploiting bushy trees. Consequently, we propose
and evaluate by simulation several join sequence heuristics in this paper to efficiently determine
general join sequences of good efficiency. As can be seen from our results, the heuristics proposed,
despite their simplicity, result in general join sequences which significantly outperform the optimal
sequential join sequence. This is especially true for complex queries. More importantly, it is shown
that the quality of the general join sequences obtained by the proposed heuristics is fairly close to
that of the optimal general join sequence, meaning that by employing appropriate heuristics we
can avoid excessive search cost and obtain join sequences with very high quality.
Next, we explore the issue of processor allocation for join operations. In the study of intra-operator
parallelism, the objective is usually to determine the processor allocation which achieves
the minimum execution time of a single join. Such a selection is referred to as operational point
selection in this paper. However, in exploiting inter-operator parallelism, we, in contrast, are dealing
with the execution of a complex query with multiple joins where different joins are allowed to be
2 Note that "minimizing the total amount of work in a join sequence" is only for join sequence scheduling, and
should not be confused with the overall objective to minimize the query execution time.
executed in parallel in different clusters of processors. As will be seen later, minimizing the execution
time of a multi-join query, in addition to the operational point selection as in the study of intra-operator
parallelism, requires more factors, such as execution dependency and system fragmentation,
to be considered. Execution dependency means that some joins cannot be performed until their
operands generated by prior joins are available. Also, after a sequence of processor allocation and
release, there might be a few processors left idle since they do not form a cluster large enough
to execute any remaining join efficiently. This phenomenon is termed system fragmentation [11].
Clearly, execution dependency and system fragmentation, as well as the operational point selection,
have to be taken into account for a better processor allocation strategy, thus complicating the
minimization procedure for the query execution time. To deal with this problem, we propose and
evaluate several heuristics to determine the number of processors for each join. The processor
allocation heuristics proposed can be divided into two categories: (1) the bottom up approach,
where the number of processors allocated to each internal node (join) in a bushy tree is determined
as the bushy tree is being built bottom up, and (2) the top down approach, which, in light of the
concept of synchronous execution time, determines the processor allocation based on a given bushy
tree. The concept of synchronous execution time is employed to deal with processor allocation so
that input relations for each join can be made available approximately the same time. It is shown
that the concept of synchronous execution time will significantly alleviate execution dependency
and system fragmentation, and hence improve the query execution time.
Note that to conduct performance study on the execution of a multi-join query, the schemes
on join sequence scheduling and processor allocation are integrated to form a final scheduler. As
shown by our simulation results, the join sequence scheduling is in general the dominating factor
for the query execution time whereas processor allocation becomes significant as the number of
processors and query complexity increase. Thus, as confirmed by our simulation, among all the
schemes investigated, the two-step approach of first applying the join sequence heuristics to build
a bushy tree as if under a single processor system, and then determining the processor allocation
in light of the concept of synchronous execution time for the bushy tree built emerges as the best
solution to minimize the query execution time.
This paper is organized as follows. The notation and assumptions used are given in Section
2. In Section 3, we study several join sequence heuristics. Sequential and general join sequences
are addressed in Sections 3.1 and 3.2 respectively, and simulation results are presented in Section
3.3. Processor allocation is dealt with in Section 4. Bottom up and top down approaches are
respectively developed in Sections 4.1 and 4.2, followed by their simulation results in Section 4.3.
This paper concludes with Section 5.
Preliminaries
In this study, we assume that a query is of the form of conjunctions of equi-join predicates and
all attributes are renamed in such a way that two join attributes have the same attribute name
if and only if they have a join predicate between them. A join query graph can be denoted by a
graph is the set of nodes and E is the set of edges. Each node in a join query
graph represents a relation. Two nodes are connected by an edge if there exists a join predicate on
some attribute of the two corresponding relations. An edge between R i and R j in a query graph
is said to be shrunken if that edge is removed from the graph and R i and R j are merged together.
Notice that when a join operation between the two relations R i and R j in a given query graph is
carried out, we can obtain the resulting query graph by shrinking the edges between R i and R j
and merging the two relations together to represent the resulting relation from the join operation.
We use jR i j to denote the cardinality of a relation R i and jAj to denote the cardinality of the
domain of an attribute A. The notation (R i ,R j ) is used to mean the join between R i and R j , and
denotes the resulting relation of (R i ,R j ). For notational simplicity, we denote the execution
tree in Figure 1a as ((((R 1 ,R 2 ),R 3 ),R 4 ),R 5 ), and that in Figure 1b as ((R 1 ,R 2 ),((R 3 ,R 4 ),R 5 )). As in
most prior work on the execution of database operations in multiprocessor systems, we assume that
the execution time incurred is the primary cost measure for the processing of database operations.
In that sense, it has been shown that the join is the most expensive operation and that the cost
of executing a join operation can mainly be expressed in terms of the cardinalities of the relations
involved. Also, we focus on the execution of complex queries, which becomes increasingly important
nowadays in real databases due to the use of views [53]. As mentioned earlier, different join
methods and different multiprocessor systems will result in different execution costs for a join, and
we shall address the join methods without utilizing pipelining, such as the sort-merge join, in this
paper. The effect of pipelining is examined in [9, 35]. It is worth mentioning that due to its stable
performance, the sort-merge join is the most prevalent join method used in some database products
to handle both equal and nonequal join queries [2, 24]. The hash-based join, though having good
average performance, suffers from the problem of hash bucket overflow and is thus avoided by many
commercial database products. The architecture assumed in this study is a multiprocessor-based
database system with shared disks and memory [5]. The cost function of joining R i and R j can then
be expressed by jR which is general and reasonable for joining large relations by
the sort-merge join [28, 29, 51]. Also, all the processors are assumed to be identical and the amount
of memory available to execute a join is assumed to be in proportion to the number of processors
involved.
To facilitate our discussion, the performance of a scheduling scheme is assessed by the average
execution time of plans generated by this scheduling scheme. The efficiency of the join sequence,
measured by its execution on a single processor system, is termed join sequence efficiency, and the
effectiveness of processor allocation, determined by the speedup achieved over the single processor
case, is termed processor allocation efficiency. The overall efficiency for dealing with the above
two issues then depends on the two factors. Note that to best assess the performance impact
of certain factors in a complicated database system, it is generally required to fix some factors,
and evaluate only the interesting ones. Similarly to most other work in performance, we adopt the
above approach in this paper and concentrate on investigating the effects of join sequence scheduling
and processor allocation. It is hence assumed that we have several shared disks and enough disk
bandwidth for I/O operations. The effect of resource (i.e., disk/network bandwidth) contention,
which is modeled in [18], is assumed to have similar effects on the schemes evaluated, and thus
not addressed in this paper. It is noted that even when the disk bandwidth is a bottleneck, join
sequence scheduling schemes generating smaller intermediate relations will in general tend to have
better performance. In that case, however, the data placement in disks will become an important
issue for performance improvement, which is beyond the scope of this paper. Also, we refer readers
interested in such issues as execution for a single sort-merge join and the use of indices to improve
one join operation to prior work on intra-operator parallelism [28, 29, 51]. Optimization on these
issues is system dependent, and in fact orthogonal to the relative performance among schemes
evaluated in this paper. Besides, we assume that the values of attributes are uniformly distributed
over all tuples in a relation and that the values of one attribute are independent of those in another.
The cardinalities of the resulting relations from join operations can thus be estimated according to
the formula in [10], which is given in the Appendix for reference. Note that this assumption is not
essential but will simplify our presentation. Also, all tuples are assumed to have the same size. In
the presence of certain database characteristics and data skew, we only have to modify the formula
for estimating the cardinalities of resulting relations from joins accordingly [20, 23] when applying
our join sequence scheduling and processor allocation schemes. Results on the effect of data skew
can be found in [27, 51].
3 Determining the Execution Sequence of Joins
In this section, we shall propose and evaluate various join sequence heuristics. Specifically, we focus
on sequential join sequences in Section 3.1 and general join sequences, i.e., bushy trees, in Section
3.2. Simulation results by different heuristics are given in Section 3.3. For the objective of showing
the effect of a join sequence on the total work incurred, we in this section consider the execution
of joins under a single processor system. The join sequence efficiencies of various join sequences
are compared with one another. Clearly, our results in this section on improving the join sequence
efficiency are applicable to both multiprocessor and single processor systems. The combined effects
of join sequence scheduling and processor allocation are discussed in Section 4.
3.1 Schemes for Sequential Join Sequences
First, we investigate the sequential join sequences resulted by the following two methods: (1) the
greedy method, denoted by SGD , and (2) the optimal permutation, denoted by SOPT , where S
means "sequential join sequence" and the subscripts mean the methods used.
The greedy scheme SGD can be outlined as follows. First, the scheme starts with the join which
requires the minimal execution cost. Then, the scheme tries to join the composite with the relation
which has the minimal-cost join with the existing composite. The above step is repeated until
all joins are finished. It can be seen that the complexity of SGD is O(jV j 2 ). Moreover, we also
investigate the optimal sequential join sequence which can be obtained by the optimal permutation
of relations to be joined. It can be seen that the number of different sequential join sequences for a
query of n relations is n!, which is half of the total number of permutations of n objects since the
first two relations can be interchanged. To evaluate the optimal sequential join sequence in Section
3.3 where different join sequences are compared by simulation, we implemented scheme SOPT in
which the technique of branch and bound is used to avoid exhaustive enumeration and reduce the
cost of search. For better readability, the implementation detail of SOPT , which is irrelevant to the
quality of the join sequence resulted, is not included in this paper.
To show the resulting join sequences by SGD and SOPT , consider the query in Figure 2a whose
profile is given in Table 1. From the operations of SGD and the formula in the Appendix, it
can be seen that the join between R 2 and R 4 is the one with the minimal cost among all joins.
After the join (R 2 ,R 4 ), the resulting query graph and its profile are given respectively in Figure
2b and

Table

2 where R 2 now represents the resulting composite. Then, it can be verified that
R 5 is the relation which will have the minimal-cost join with R 2 , and the execution of (R 2 ,R 5 )
R
RRR
A
ER
R
RRR
A
ER
G
(a) (b)

Figure

2: Two states of an example query graph: (a) the original graph, (b) the resulting graph
after joining R 2 and R 4 .
in Figure 2b is performed. Following the above procedure, we have the resulting join sequence
by SGD , (((((R 2 ,R 4 ),R 5 ),R 6 ),R 3 ),R 1 ) whose total cost is 45,246.43. On the other hand, it can
be obtained that for the query in Figure 2a, the optimal sequential join sequence by SOPT is
cost is 36,135.92, which is less than that required by SGD .
It is interesting to see that the first join performed by SOPT is (R 1 ,R 3 ), rather than (R 2 ,R 4 ) which
is the first one chosen by SGD .
cardinality 118 102 106 100 131 120
(a). Cardinalities of relations.
attribute A B C D E F G
cardinality 19 15 17 19
(b). Cardinalities of attributes.

Table

1: The profile of the query in Figure 2a.
cardinality 118 680 106 131 120
(a). Cardinalities of relations.
attribute A B C D E G
cardinality 19 15 17 19
(b). Cardinalities of attributes.

Table

2: The profile of the query in Figure 2b.
3.2 Schemes for General Join Sequences
It can be seen from the cost function presented in Section 2 that the joins whose operands are of
larger sizes usually have higher costs. This observation suggests the following heuristic to explore the
general join sequence in order to reduce the total cost incurred. First, we perform the minimal-cost
join, and then, from the resulting query, choose the minimal-cost join to perform. This procedure
repeats until all joins are finished. Note that this heuristic, though efficient, is greedy in nature
in that only "local optimality" is considered, and thus need not lead to a resulting join sequence
with the minimal cost. Based on this heuristic, scheme GMC , where G means that the resulting
sequence is a general join sequence and the subscript MC stands for "the join with minimal cost",
is outlined below. It can be seen that unlike SGD , the resulting composite of a join by GMC need
not participate in the next join.
scheme to execute the join with the minimal cost. */
begin
1. repeat until jV
2. begin
3. Choose the join R i 1 R j from G=(V,E) such that
4. Perform R i
5. Merge R i and R j to R min(i;j) . Update the profile accordingly.
For the example query in Figure 2a, it can be verified from Figure 2b and Table 2 that after
the first minimal-cost join (R 2 ,R 4 ) is performed, the next minimal-cost join to be executed by GMC
is (R 5 ,R 6 ), rather than (R 2 ,R 5 ) as in SGD . The resulting sequence is (((R 2 ,R 4 ),(R 5 ,R 6 )),(R 1 ,R 3
whose total cost is 13,958.62, significantly less than those required by SGD and SOPT . The execution
RRR 5
R 6
RR 2
RRRRRRRRRRR
(a)RRRRR 6
R
OPT
(b) MC
G
(d) OPT
G
(c) MR
G

Figure

3: Different execution trees resulted by different join sequence heuristics.
trees resulted by SOPT and GMC are shown in Figures 3a and 3b, respectively. It can be seen that
the complexity of the scheme is O(jV rather close to O(jV required by SGD 3 .
Note that in a sequence of joins, the cardinalities of intermediate relations resulting from the
early joins affect the costs of joins to be performed later. Since the objective taken is to minimize
the total cost required to perform a sequence of joins, one may want to execute the joins which
produce smaller resulting relations first. In view of this fact, we develop and evaluate the following
heuristic scheme which is a variation of GMC , namely the minimal resulting relation (GMR ). Instead
of finding the minimal-cost join as in GMC , the scheme GMR searches for the join which results
in the minimal resulting relation 4 . Clearly, the heuristic scheme GMR is of the same complexity,
O(jV jjEj), as scheme GMC . Algorithmic form of GMR is similar to the one of GMC , except that
the statement 3 in GMC is changed to 3A below.
3A. (for GMR Choose the join (R i ,R j ) from G=(V,E) such that jR i
3 For the simulation in [11], the run times required by the two schemes are almost the same.
4 Another heuristic choosing the join (R i ,R j ) with the minimal expansion (i.e., (jR i
evaluated [11], and found to provide mediocre performance. Its
results are thus not reported in this paper.
Following GMR , the resulting join sequence for the query in Figure 2a is ((((R 1 ,R 3 ),R 6 ),R 5 ),(R 2 ,R 4 )),
whose bushy tree is shown in Figure 3c. The associated cost is 13,288.38, showing a better join
sequence efficiency than the one obtained by GMC . This fact can be further justified by the simulation
results in Section 3.3. Moreover, to assess the performance of the heuristics, we implemented
scheme GOPT to determine the optimal general join sequence for a multi-join query. Same as in
SOPT , we enumerate possible candidate sequences in our implementation of GOPT and employ the
technique of branch and bound to prune the search. Using GOPT , we obtain that the optimal
general join sequence for the query in Figure 2a is ((R
shown in Figure 3d, requiring only a cost of 13,013.57, which is in fact rather close to those obtained
by GMC and GMR . Clearly, such an optimal scheme, though leading to the optimal solution se-
quence, will incur excessive computational overhead which is very undesirable in some applications
and might outweigh the improvement it could have over the heuristic schemes. As can be seen in
the following, the heuristic schemes GMC and GMR , despite their simplicity, perform significantly
better than SGD and SOPT , and result in join sequences whose execution costs are reasonably close
to that of the optimal one.
3.3 Simulation Results for Join Sequence Heuristics
Simulations were performed to evaluate the heuristic schemes for query plan generation. The
simulation program was coded in C, and input queries were generated as follows. The number of
relations in a query was pre-determined. The occurrence of an edge between two relations in the
query graph was determined according to a given probability, denoted by prob. Without loss of
generality, only queries with connected query graphs were deemed valid and used for our study. To
determine the structure of a query and also the cardinalities of relations and attributes involved, we
referenced prior work on workload characterization [53] and a workload obtained from a Canadian
insurance company. To make the simulation be feasibly conducted, we scaled the average number
of tuples in a relation down from one million to two thousand. The cardinalities of attributes were
also scaled down accordingly so that the join selectivities could still reflect the reality.
Based on the above, the cardinalities of relations and attributes were randomly generated from
a uniform distribution within some reasonable ranges. The number of relations in a query, denoted
by n, is chosen to be 4, 6, 8 and 10, respectively. For each value of n, 300 queries were randomly
generated. For each query, the five scheduling schemes, i.e., SGD , SOPT , GMC , GMR and GOPT , are
performed to determine join sequences to execute the query. When two relations not having join
predicates are to be joined together, a Cartesian product is performed. From our simulation, we
found that relative performance of these schemes is not sensitive to the density of the query graph,
i.e., the number of edges in the graph 5 . The average execution cost for join sequences obtained
5 Note that the "absolute" performance of these scheduling schemes is highly dependent uopn the query complexity.
relation no. SGD SOPT GMC GMR GOPT

Table

3: The average execution cost for join sequences obtained by each scheme.
from each scheme when prob=0.32 is shown in Table 3. Also, we divide the average execution costs
of the first four schemes by that of GOPT for a comparison purpose, and show the results associated
with

Table

3 in Figure 4.
From

Table

3 and Figure 4, it can be seen that except for GOPT , the join sequence efficiency of
join sequences obtained by GMR is the best among those obtained by the four remaining schemes,
and then, in order, those by GMC , SOPT and SGD . The join sequence efficiencies of the sequences
resulted by GMC and GMR are quite close to the optimal one and significantly better than those
by SGD and SOPT , especially when the number of relations increases. For the sizes of queries
simulated here, the run times of SGD , GMC and GMR under the RS/6000 environment are very
close to one another whereas those of SOPT and GOPT are larger than them by more than three
orders of magnitude due to their exponential complexity.
4 Processor Allocation for Executing Each Join
As pointed out in Section 1, to minimize the execution time of a multi-join query, it is necessary to
address the following three issues: operational point selection, execution dependency and system
fragmentation. Note that the execution time required for a join operation within a multiprocessor
system depends on the number of processors allocated to perform the join, and their relationship
can be modeled by an operational curve 6 , as evidenced in prior results on intra-operator parallelism
[32, 51]. Basically, increasing the number of processors will reduce the execution time of a join until
a saturation point is reached, above which point adding more processors to execute the join will,
on the contrary, increase its execution time. This is mainly due to the combining effects of limited
parallelism exploitable and excessive communication and coordination overhead over too many
processors. An example of an operational curve for this phenomenon is shown by the solid curve
in

Figure

5, where a dotted curve xy=30 is given for reference. In such a curve, the operational
point chosen from the curve, depending on the design objective, is generally between the point
Discussions on this issue can be found in [33, 41].
6 Note that every join has its operational curve.
n=4 n=6 n=8 n=1026n: the number of relations involved
to
the
minimal
cost
required S
1.07 1.07
1.08 1.061.76
1.26 1.112.82

Figure

4: Performance results of different join sequence heuristics.
which minimizes the execution time of the join, referred to as the minimum time point, denoted by
and the one which optimizes execution efficiency, i.e., minimizes the product of the number of
processors and the execution time, referred to as the best efficiency point, denoted by p B .
Formally, the execution efficiency of allocating k processors to execute a join is defined as
exe. time on one proc.
k * exe. time on k proc. to represent the efficiency of such an allocation. For example,
for the operational curve in Figure 5. To improve the processor allocation efficiency, we
not only have to utilize the information provided in the operational curve for the operational
point selection, but are also required to comply with execution dependency and avoid system
fragmentation as much as possible so as to minimize the execution time of the query.
Consequently, we propose and evaluate in the following several heuristics to determine the
number of processors allocated for the execution of each join. The heuristics proposed can be divided
into two categories: (1) the bottom up approach, which, presented in Section 4.1, determines the
join sequence and processor allocation at the same time, i.e., processors are allotted when a bushy
tree is being built, and (2) the top down approach, which, presented in Section 4.2, determines
the processor allocation based on a given bushy tree. The effectiveness of these heuristics will be
evaluated by simulation in Section 4.3.
Y
the number of processors
execution
time

Figure

5: An example operational curve of a join in a multiprocessor system.
4.1 Bottom Up Approach for Processor Allocation
We introduce below four heuristics for the bottom up approach to determine the processor allocation

(a). Sequential execution (SE):
This heuristic is to use all the processors in the system to execute each join in the query sequen-
tially. It can be seen that inter-operator parallelism is absent when this heuristic is used, and the
join sequence is the key factor to the performance in such a case.
(b). Fixed cluster size
This heuristic is to allocate a fixed number of processors for the execution of each join to avoid
system fragmentation. Clearly, by taking the total number of processors as the cluster size, we
have a special case equivalent to heuristic SE.
Note that by using the above heuristics, system fragmentation is avoided since a fixed number
of processors are always released together for a later use. Moreover, under heuristic SE, execution
dependency is inherently observed, since join operations are executed sequentially. However, the
two heuristics may suffer from poor operational point selection because the information provided
cardinality 100 85 93 106 102 90 101 94
(a). Cardinalities of relations.
attribute A B C D E F G H I J K
cardinality 9 8 7 9 9
(b). Cardinalities of attributes.

Table

4: The profile of the query in Figure 6.
by the operational curve is not utilized to determine the operational point of a join.
(c). Minimum time point (MT):
This heuristic is based on the minimum time point in the operational curve, i.e., the number of
processors used to execute the corresponding join operation is p M . Note that even though this
operational point obtains the minimum execution time for each join, it may not minimize the
execution time of a multi-join query as a whole due to the effect of execution dependency and
system fragmentation.
(d). Time-efficiency point (TE):
Recall that the best efficiency point is the operational point where processors are most efficiently
used to execute the join. However, as can be seen in Figure 5, a scheme based on the the best
efficiency point might suffer from execution dependency, since some join operating at its best
efficiency point might take a long execution time to complete due to a small number of processors
used to execute the operation, thus causing long waiting time for subsequent joins. On the other
hand, a scheme based on MT may not use processors efficiently since it may require too many
processors to reach the minimum time point. Clearly, the number of processors associated with
an operational point which can strike a compromise between the execution time and the processor
efficiency should be within the region [p B , p M ]. In view of this, we shall use a combination of
the minimum time point and the best efficiency point, termed as the time-efficiency point, as a
heuristic for our study, i.e., the number of processors, k*p M +(1\Gammak)*p B , is used to execute each
join operation, where 0-k-1.
Note that the above heuristics for processor allocation can be combined with the schemes
for scheduling join sequences developed in Section 3 to form a final scheduler which handles the
scheduling and processor allocation of a multi-join query in a multiprocessor system. That is, we
use a join sequence heuristic, say GMR , to determine the next join to be considered and employ the
A
F
RRR
R
JR
G

Figure

A query to show processor allocation.
appropriate processor allocation heuristic to determine the number of processors to be allocated
for the execution of that join. The operations for the processor allocation and deallocation can be
outlined as follows where the processor allocation heuristic, denoted by h P , can be any of SE, FS,
MT and described above and h P (J) is the number of processors allocated to execute a join J
under the heuristic h P .
Processor Allocation:
/* P is the number of processors available and initialized as the total numbers of processors. */
1: Use the join sequence heuristic to determine the next join operation J such that h P (J)-P
and execution dependency is observed, i.e., the two input relations of J are available then. If
no such a join exists, go to processor deallocation.
Step 2: Allocate h P (J) processors to execute the join J. P:=P\Gammah P (J).
Step 3: Update the profile by marking J as an ongoing join.
Step 4: Determine the completion time of J and record it in the completion time list of ongoing
joins.
Step 5: Go to Step 1.
Processor Deallocation:
1: From the completion time list, determine the next completion of an ongoing join, say J.
Step 2: Update the profile to reflect that J is completed. P:=P+h P (J).
Step 3: If there is any executable join in the updated query profile, go to processor allocation.
Step 4: Go to Step 1.
It can be seen that using the above procedures, the execution tree can be built bottom up. To
demonstrate the processor allocation and deallocation, we shall show the operations using heuristics
SE and TE. The operations by FS and ME follow similarly. Consider the query in Figure 6 with
the profile in Table 4. In light of the results on parallelizing sort and join phases [29, 51], the
operational curve of a join can be modeled as a hyperbolic function below,
where N p is the number of processors employed, parameters a, b and c are determined by the path
length of the system in processing and joining tuples [28, 32, 51], and parameter d is determined
by the inter-processor communication protocol. Also, as observed in [32], for sort-merge join, runs
for sorting are usually memory intensive. In view of this and the fact that the amount of memory
available is in proportion to the number of processors involved, we have, for each join, the minimal
number of processors required for its execution according to the sizes of its operands. p B for each
operational curve formulated above can thus be determined for our study. We then ignore the
operational area where the number of processors is less than p B , and consider only the operational
region [p B ,p M ] for efficient execution. Without loss of generality, GMR is used to determine the
next join operation to be executed 7 . Then, for heuristics SE in a multiprocessor system of 32 nodes
with a=b=c=1 and d=20, we have the execution sequence as shown in Table 5a, where the column
is the cumulative execution cost of R i , and will be used in Section 4.2 to implement top
down approaches. The bushy tree and its corresponding processor allocation by SE is shown in
Figure 7a. The execution scenarios using the time-efficiency point are shown in Table 5b, where the
time-efficiency point used is determined by 0.3p B +0.7pM 8 . The bushy tree and its corresponding
processor allocation by TE is shown in Figure 7b. Note that though the same scheme GMR is used
to determine the next join to be performed in both cases, the resulting join sequences are different
from each other due to different processor allocation scenarios. It can be seen that the bushy tree
in Figure 7b is different from the one in Figure 7a.
4.2 Top Down Approach for Processor Allocation
It can be seen that when an execution tree is built bottom up, the following two constraints have
to be followed: (1) execution dependency is observed, i.e., the operands of the join selected to be
7 The corresponding simulation results by using GMC do not provide additional information, and are thus omitted
in this paper.
8 Different values for k have been evaluated. The choice for k=0.3 is made for its reasonably good performance.
join sequence proc. no. starting time end time resulting R i
(R
(R 4 ,R 5 )
(R
(R
(R
(R
(R
(a) SE.
join sequence proc. no. starting time end time resulting R i
(R
(R
(R 6 ,R 8
(R 4 ,R 5
(R
(R
(R
(b) TE.
join sequence proc. no. starting time end time resulting R i
(R
(R 4 ,R 5
(R
(R
(R
(R
(R
(c) ST SE .
join sequence proc. no. starting time end time resulting R i
(R
(R
(R 6 ,R 8
(R 4 ,R 5
(R
(R
(R
(d) ST

Table

5: Execution sequence for different heuristic.
(a) SER 3
R 6
R 8
RR 7
RR 5
R
(b) TER 7
RR 3
RR 5
RRR
(20)RRRRRRRRRRRRRR

Figure

7: Bottom up processor allocation.
performed next do not depend on the resulting relation of any ongoing join, and (2) the processor
requirement is satisfied according to the processor allocation heuristic employed, i.e., the number
of processors required by that join is not larger than the number of processors available then. As
can be seen in Table 5a and 5b, the above two constraints lengthen the execution time of a query
and degrade the performance of a scheduler since the first constraint causes long waiting time for
some operands, and the second can result to the existence of idle processors. In view of these, one
naturally wants to achieve some degree of execution synchronization, meaning that processors are
allocated to joins in such a way that the two input relations of each join can be made available
approximately the same time. Also, idleness of processors should be avoided. As a result, we
propose the top down approach for the processor allocation which uses the concept of synchronous
execution time to alleviate the two constraints and improve the query execution time.
To describe the processor allocation using the synchronous execution time, consider the bushy
tree in Figure 7a for example. Recall that every internal node in the bushy tree corresponds to a
join operation, and we determine the number of processors allocated to each join in the manner of
top down. Clearly, all processors are allocated to the join associated with the root in the bushy
tree since it is the last join to be performed. Then, those processors allocated to the join on the
root are partitioned into two clusters which are assigned to execute the joins associated with the
two child nodes of the root in the bushy tree in such a way that the two joins can be completed
approximately the same time. The above step for partitioning the processors for the root is then
applied to all internal nodes in the tree in a top down manner until each internal node (join) is
assigned with a number of processors. More formally, define the cumulative execution costs of an
internal node as the sum of the execution costs of all joins in the subtree under that internal node.
Also, define the cumulative execution cost of a leaf node (an original relation) as zero. Let R i
be a relation associated with an internal node in the bushy tree and R x and R y be the relations
corresponding to its two child nodes. Then, the cumulative execution cost of the node with R i ,
denoted by W(R i ), is determined by,
(R
Note that the cumulative execution cost of each node can be determined when the bushy tree is
built bottom up. The cumulative execution costs of internal nodes for the bushy trees in Figures
7a and 7b can be found in Tables 5a and 5b, respectively. Then, it is important to see that to
achieve the synchronous execution time, when partitioning the processors of a node into two clusters
for its child nodes, one has to take into account the cumulative execution costs of the two child
nodes, rather than the execution costs of the two joins associated with the two child nodes. Let R i
be a relation associated with an internal node in the bushy tree and R x and R y be the relations
corresponding to its two child nodes such that W(R x Denote the number of processors
allocated to perform the join generating R i as P(R i ). Then, P(R x ) and P(R y ) are determined,
respectively, by,
(R x
(R (R y ) e and P (R y (R x
Since W(R y )=0 if R y is an original relation, we know that when only one child node corresponds
to a join and the other is a leaf node, the former inherits all processors. Note that if the number
of processors allocated to an internal node (join) of a bushy tree, say r processors, exceeds that
required for the minimum time point, we shall employ p M processors to perform that join whereas
using r processors for the subsequent partitioning for the subtree under that internal node. Also,
when the number of processors passed to an internal node in a lower level of the tree is too few to
be further partitioned for efficient execution of joins, sequential execution for the joins in its child
nodes is employed for a better performance. Clearly, there are many different bushy execution trees
for a query. It can be seen that the problem of determining the optimal bushy tree to minimize the
execution time by the concept of synchronous execution time is of exponential complexity. For an
efficient solution, we apply the concept of synchronous execution time to the bushy trees obtained
by the heuristics introduced in Section 4.1.
As pointed out before, different bottom up processor allocation heuristics used may result in
different bushy trees even when the same join sequence heuristic is applied. It is important to see
that although execution time for the sequence in Table 5a (by SE) is larger than that in Table 5b
(by TE), the join sequence efficiency of the bushy tree in Figure 7a is in fact better than that of
the tree in Figure 7b, as shown by their cumulative execution costs in Tables 5a and 5b. Note that
the constraints on execution dependency can get introduced when a bushy tree is being built by
heuristic TE, as well as by FS and MT. Such constraints are absent when heuristic SE is employed
to form the bushy tree. (This explains why the tree in Figure 7a is different from that in Figure 7b.)
Thus, the bushy tree by SE is in fact superior to those by other heuristics in that the former has a
better join sequence efficiency owing to full exploitation of the join sequence heuristics. Therefore,
we shall apply the concept the synchronous execution time to the bushy tree built by SE, denoted
by ST SE . For a comparison purpose, we also investigate the use of the synchronous execution time
on the bushy tree built by TE, denoted by ST
The execution scenario using the heuristic ST SE is shown in Table 5c, and the corresponding
bushy tree and processor allocation is shown in Figure 8a. In spite of the fact that the bushy
tree in Figure 8a is the same as that in Figure 7a, the resulting execution times differ due to the
difference in processor allocation. It can be seen that under ST SE , processors are allocated to the
execution of each join in such a way that two joins generating the two operands for a later join can
be completed approximately the same time, thus alleviating execution dependency. Moreover, since
the processors allocated to a node in a bushy tree are partitioned for the allocation to its child
nodes, system fragmentation is eased. This explains why ST SE outperforms SE despite both of
them have the identical bushy trees and the same join sequence efficiency. The execution scenario
using the heuristic ST execution time is shown in Table 5d. The bushy tree and its processor
allocation by ST is shown in Figure 8b which has the same bushy tree as the one in Figure 7b, but
differs from the latter in processor allocation. It is important to see that despite outperforms
SE, ST SE performs better than ST in fact is the best one among the processor allocation
heuristics evaluated in Section 4.3.
4.3 Simulation Results for Processor Allocation
The query generation scheme employed in Section 3.3 is used to produce input queries for simulation
in this subsection. As in Section 3.3, 300 queries with a given number of relations involved were
randomly generated with the occurrence of an edge in the query graph also determined by a given
probability prob. For each query, the six scheduling schemes, according to the heuristics of SE, FS,
MT, TE, ST SE and ST respectively, are performed to determine the number of processors for
each join to execute the query. As in Section 3.3, the simulation results here also indicate that the
above heuristics are not sensitive to different values of prob. Thus, we shall only show the results for
prob=0.30 in the following. For a multiprocessor of 48 nodes, the average execution times obtained
(a)R 3
R 6
R 8
RRR 5
R
RR 5
RRR
ST (b)
STR 4
RRRRRRRRRRRRRRR

Figure

8: Top down processor allocation (synchronous execution time).
by each heuristic for queries of 10, 15, 20 and 25 relations are shown in Table 6a. It can be seen
that heuristic SE, i.e., the one using intra-operator parallelism only, performs well when the number
of relations is 10, but performs worse when the number of relations increases. This agrees with
our intuition since as the number of relations increases, the opportunity to exploit inter-operator
parallelism increases and the constraint imposed by execution dependency becomes relatively less
severe. Also, heuristic FS is in general outperformed by others due mainly to execution dependency
and poor operational points selection. Among the heuristics on bottom up approaches, the shortest
execution time is usually achieved by heuristic TE, especially when the number n is large. This
can be explained by the same reason as mentioned above, i.e., that execution dependency is eased
when the number of relations is large, and thus performs best for its best usage of processors.
Also, from 300 randomly generated queries, the average execution times obtained by the six
heuristics for a query of 15 relations is shown in Table 6b where the number of processors in the
system is varied from 16 to 64. It can be seen that when the number of processors increases,
heuristic SE suffers from the inefficient use of processors, and is thus outperformed by heuristics
MT, TE, ST SE and ST by a wide margin. It can also be observed that heuristic which uses
processors efficiently to achieve a nearly minimum execution time performs well when the number
of processors is large. Clearly, the more processors are in the system, the more parallelism can
be exploited by heuristic TE. However, MT performs better than when pn=64, which can
relation no. SE FS MT
n=15 9041.1 20828.7 7659.9 7135.4 5990.2 6284.5
(a) When the number of processors is 48.
proc. no. SE FS MT
pn=48 9041.1 20828.7 7695.9 7135.4 5990.2 6284.5
(b). When the number of relations is 15.

Table

The average execution time for each heuristic.
be explained by the fact that when the supply of processors is sufficient, achieving minimum time
point (by MT) becomes a better heuristic than using processors efficiently (by TE). In all, when the
number of processors is small, utilizing intra-operator parallelism (i.e., SE) will suffice to provide
a reasonably good performance. On the other hand, for a large multiprocessor system, one has
to resort to inter-operator parallelism to fully exploit the resources in the system. Note, however,
that without using synchronous execution time, ME and TE, though having a good operational
point selection for each join, cannot improve the query response time in a global sense due to the
nature of a bottom up approach, and are thus outperformed by ST SE and ST This fact strongly
justifies the necessity of taking execution dependency and system fragmentation into consideration
when inter-operator parallelism is exploited.
As mentioned earlier, although SE is outperformed by due to its poor operational point
selection, ST SE remedies this defect by properly reallocating processors using the concept of synchronous
execution time. ST SE can thus outperform ST TE . It is worth mentioning that the
sequential join sequences, such as the one shown in Figure 3a, will not benefit from the concept of
synchronous execution time, since in this case, joins have to be executed sequentially and there is
no inter-operator parallelism exploitable. This fact, together with the fact that the sequential join
sequences usually suffer from poor join sequence efficiency, accounts for the importance of exploring
the general join sequences.
Note that similar to the heuristics in Section 3, the heuristics we investigated here are very
straightforward and require little implementation overhead. In all, our results showed that the join
sequence efficiency is in general the dominating factor for the query execution time whereas the
processor allocation efficiency becomes significant as the number of processors and query complexity
increase. This suggests that for an efficient solution, one can attempt to optimize the join sequence
efficiency by building a good bushy tree first and then improve the processor allocation efficiency by
appropriately allocating processors for the execution of each join. This is in fact how the heuristic
ST SE is constructed.
5 Conclusion
In this paper we dealt with two major issues to exploit inter-operator parallelism within a multi-join
query: (i) join sequence scheduling and (ii) processor allocation. For the first issue, we explored
the general join sequence so as to exploit the parallelism achievable in a multiprocessor system.
Heuristics GMC and GMR were derived and evaluated by simulation. The heuristics proposed,
despite their simplicity, were shown to lead to general join sequences whose join sequence efficiencies
are close to that of the optimal one (GOPT ), and significantly better than what is achievable by the
optimal sequential join sequence (S OPT ), particularly when the number of relations in the query is
large.
Moreover, we explored the issue of processor allocation. In addition to the operational point
selection needed for intra-operator parallelism, we identified and investigated two factors: execution
dependency and system fragmentation, which are shown to be important when exploiting inter-operator
parallelism. Several processor allocation heuristics, categorized by bottom up and top
down approaches, were proposed and evaluated by simulation. To form a final scheduler to perform
a multi-join query, we combined the results on join sequence scheduling and processor allocation.
Among all the schemes evaluated, the two-step approach by ST SE , which (1) first applies the join
sequence heuristic to build a bushy tree to minimize the total amount of work required as if under
a single processor system, and then, (2) in light of the concept of synchronous execution time,
allocates processors to the internal nodes of the bushy tree in a top down manner, is shown to be
the best solution to minimize the query execution time.



--R

Parallel Database Systems
An Overview of DB2 Parallel Edition.
Database Operations in a Cube-Connected Multiprocessor System
A Parallel Database System for Shared Store.
A Performance Comparison of Two Architectures for Fast Transaction Processing.
Prototyping Bubba
The Development of the CROSS8 and HC16-186 (Data- base) Computers
Parallel Features of NonStop SQL.
Applying Segmented Right-Deep Trees to Pipelining Multiple Hash Joins
Combining Join and Semijoin Operations for Distributed Query Processing.
Scheduling and Processor Allocation for Parallel Execution of Multi-Join Queries
Informix Parallel Data Query.

Practical Skew Handling in Parallel Joins.
Multiprocessor Hash-Based Join Algorithms

Parallel Database Systems: The Future of High Performance Database Systems.
Query Optimization for Parallel Execution.

On the Effect of Join Operations on Relation Sizes.
Dataflow Query Processing Using Multiprocessor Hash-Partitioned Algorithms

Sequential Sampling Procedures for Query Size Estimation.
Exploiting Inter-Operator Parallelism in XPRS
On Parallel Execution of Multiple Pipelined Hash Joins.
Considering Data Skew Factor in Multi-way Join Query Optimization for Parallel Execution
System Issues in Parallel Sorting for Database Systems.
Percentile Finding Algorithm for Multiple Sorted Runs.
Query Optimization in Database Systems.
Architecture and Performance of Relational Algebra Machine GRACE.
Effectiveness of Parallel Joins.
On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces.
Oracle Parallel RDBMS on Massively Parallel Systems.
On Optimal Processor Allocation to Support Pipelined Hash Joins.
Exploiting Database Parallelism In A Message-Passing Multiprocessor
Optimization of Multi-Way Join Queries for Parallel Execution

Join Processing in Relational Databases.

Measuring the Complexity of Join Enumeration in Query Opti- mization
Parallelism in Relational Data Base Systems: Architectural Issues and Design Approaches.
The Kendall Square Query Decomposer.
Design and Evaluation of Parallel Pipelined Join Algorithms.
A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment
Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines.
Access Path Selection in a Relational Database Management System.
Multiple Query Optimization.
The Design of XPRS.

A Parallel Sort Merge Join Algorithm for Managing Data Skew.
A Hierarchical Approach to Parallel Multiquery Scheduling.
On Workload Characterization of Relational Database Environments.
Parallel Query Processing.
Parallel Query Processing in DBS3.
--TR

--CTR
Anindya Datta , Debra VanderMeer , Krithi Ramamritham, Parallel Star Join Efficient Query Processing in Data Warehouses and OLAP, IEEE Transactions on Knowledge and Data Engineering, v.14 n.6, p.1299-1316, November 2002
Ming-Syan Chen , Hui-I Hsiao , Philip S. Yu, On applying hash filters to improving the execution of multi-join queries, The VLDB Journal  The International Journal on Very Large Data Bases, v.6 n.2, p.121-131, May 1997
Wen-Chih Peng , Ming-Syan Chen, Query Processing in a Mobile Computing Environment: Exploiting the Features of Asymmetry, IEEE Transactions on Knowledge and Data Engineering, v.17 n.7, p.982-996, July 2005
Shortening Matching Time in OPS5 Production Systems, IEEE Transactions on Software Engineering, v.30 n.7, p.448-457, July 2004
Chang-Hung Lee , Ming-Syan Chen, Processing Distributed Mobile Queries with Interleaved Remote Mobile Joins, IEEE Transactions on Computers, v.51 n.10, p.1182-1195, October 2002
Julian R. Ullmann, Partition search for non-binary constraint satisfaction, Information Sciences: an International Journal, v.177 n.18, p.3639-3678, September, 2007
multi-join query;system fragmentation;synchronous execution time;execution dependency;bushy trees