Database Reference
In-Depth Information
1
4
5
σ
2
σ
2 = 0.001
|S
C
|
= 1000
|S
AB
|
|S
C
|
2
|S
AB
|
= 100
2
λ
ab =
r
1
λ
ab =
r
10
λ
c =600
1
4
5
σ
1
σ
1 = 0.0045
|S
B
|
= 80
Path
I
Path
A
Path
B
Path
C
|S
A
|
|S
B
|
1
|S
A
|
= 100
1
Resources used (X
I
)
15
16
10
Output rate r
I
root
4
5
1
11
11
λ
a= 500
λ
b=700
Path Productivity
ρ
p
(Path
I
) 0.266
0.312 0.1
(a) Parameter assignment
(b) Path-wise throughput
Fig. 7.
Example 2-join plan
Fig. 8.
Path productivity table
Definition 4.
The
path productivity
of Path
I
, denoted by
ρ
p
(Path
I
)
, is its contribution
to the query throughput
per tuple t processed
6
within Path
I
.
I
n
φ
I
n
φ
p
n
S
n
|
−
1
ρ
p
(Path
I
)
=
(
σ
×|
)
×
(
)
=
(
)
.
(7)
I
I
n
I
I
n
1
+φ
1
+...+φ
1
+φ
1
+...+φ
−
1
−
1
If X
I
resources are assigned to Path
I
, the component X
I
n
assigned to the root half-way
join may be computed using Eq. 6. The throughput contribution by processing the X
I
resources along Path
I
, denoted as (r
I
p
n
S
n
|
X
I
n
. Therefore, by Def. 4, the
root
)=(
σ
×|
)
×
ρ
p
(Path
I
)=
r
I
productivity of Path
I
X
I
,asgiveninEq.7.
In our example plan (Fig. 4.b), X
B
resources allocated to Path
B
will be divided among
λ
b
and
can be computed as
root
λ
ab
. By Eq. 6, an effective division of X
B
over Path
B
will be
λ
b
=(X
B
/6) and
λ
ab
X
B
/6). Using Eq. 7, the total throughput contribution (r
B
=(5
×
root
) achieved is estimated
X
B
/6)
). Thus, if X
B
λ
b
gets 100, then producing
as (5
×
×
(
σ
×|
S
C
|
= 600 tuples/sec,
C
λ
ab
gets 500 tuples/sec (= X
B
λ
b
)anda
r
1
= 500 tuples/sec as intermediate output.
-
producer-consumer match
is achieved between
1
and
2
.
Discussion.
The path productivity
ρ
p
metric defaults to the notion of half-way join
productivity
ρ
h
(Sec. 3) when applied to a single operator.
ρ
h
is a
local
operator level
metric whereas
p
metric establishes the contribution of a complete input path to the
query
throughput r
root
. The former takes only the tuples directly input into the half-way
join into consideration, whereas the
ρ
ρ
p
metric instead considers all the tuples processed
anywhere along the path, be it at the leaf, the intermediate and the root operators.
4.2
Path Productivity-Based Join Adaptation
Given plan Q with k input paths, namely, Path
A
,Path
B
,...,andPath
k
, their path produc-
tivities can be computed using Formula 7. The 2-join plan in Fig. 7 may be translated
into a
path productivity table
(Fig. 8). This translation is based on the
input rates
,the
selectivities
and the
state sizes
along each path within the plan. For each input path
Path
I
,the
path productivity table
lists (a.)
the resources used
(X
I
), (b.)
the query output
rate
(r
I
root
) achieved using X
I
ρ
p
(Path
I
).
resources, and (c.)
the path productivity
(
In Fig. 7.b) for Path
A
, the resources X
A
= 15 tuples/sec may be divided across the
λ
a
=11and
λ
ab
= 4. The throughput contribution of Path
A
,
two half-way joins such that
6
Tuple t refers to either a leaf or an intermediate tuple in Path
I
.
