Database Reference
In-Depth Information
These relaxations are
mutually complementary
and their benefit is twofold. First,
multiple cycles may be scheduled together. Second, as fractional resource assignment
is allowed, high productivity paths consuming resources X
I
, that would
otherwise be eliminated in the
discrete model
, may now be assigned resources. Also
in a real-world CPU-limited scenario, the resources are more likely to be an esti-
mated
greater than
μ
μ
value available over a duration spanning multiple cycles rather than being a
distinct
value available to each cycle. Under this
continuous execution model
, our
JDA-Knapsack
Problem 1 now exhibits both the
greedy choice property
and the
op-
timal substructure property
[14]. This implies that we can now use a
greedy knapsack
solver
, henceforth referred to as
Gre
edy
P
ath
P
roductivity-based
Multi-Join Adaptation
(
GrePP
), to tackle our problem.
For our running example in Fig. 7, GrePP selects the most productive path, Path
B
(Fig. 8), and allocates all of
μ
λ
b
gets 20.62 tuples/sec and
λ
ab
gets 9.38 tuples/sec. The estimated query throughput r
GrePP
μ
(=30 tuples/sec) such that
root
is 9.38 tuples/sec and is
greater than that in the
discrete model
. It is guaranteed to be
optimal
[14].
GrePP runs
in
(k
log
(k)) time [14] for a plan joining k streams and thus is independent of
μ
.
4.3
Satisfying Freshness in Multi-join Queries
The throughput optimizing allocation by GrePP may still suffer from
result staleness
.
We allow users to supply the
freshness
predicates (Def. 1) for each input stream. Now,
we extend our
path-productivity based
model to incorporate this notion of
freshness
.
The key idea here is that the
freshness predicates
defined over streams are fulfilled
by translating them into
refresh rates
for the join states inside the plan. By Def. 1,
tuple t
I
I
),
where t
I
.ts denotes the arrival time of t
I
. To enforce this constraint, every tuple t
I
from
stream I and all its intermediate joined tuples must be purged from the plan by (t
I
.ts
+
from stream I must not be part of the joined results beyond time (t
I
.ts +
F
I
) time (or tuple for count-based freshness). In Fig. 9.a, stream C contributes the
singleton t
C
, the intermediate t
CD
and t
CDE
tuples, get stored in
own
states S
C
,S
CD
and
S
CDE
, respectively. State S
C
gets refreshed by incoming tuples at
F
c
tuples/sec, whereas
the intermediate states intermediate states S
CD
and S
CDE
get refreshed with tuples t
CD
and t
CDE
λ
λ
cde
, respectively.
Such intermediate states, such as S
CD
and S
CDE
, are called
staleness susceptible states
(highlighted in Fig. 9.a). In a steady stream,
λ
cd
at a rate dependent on the portion of
μ
allocated to
and
S
C
S
CD
λ
cd
S
CDE
λ
cde
λ
c
,
and
denote the time duration
for which a singleton t
C
and its corresponding t
CD
and t
CDE
tuples will remain in their
(
S
C
λ
c
F
C
for stream C,
F
C
≥
respective
own
states S
C
,S
CD
,S
CDE
. To satisfy the predicate
S
CD
λ
cd
S
CDE
λ
cde
+
+
).
S
j
λ
j
,where
λ
j
and
S
j
denote the
probe allowance
and the
own
join state, respectively, at j
th
operator along
Pa th
I
, storing intermediate tuples having t
I
I
I
n
j
Lemma 1.
To fulfill the freshness predicate
F
for stream I,
F
≥Σ
=
1
tuples.
I
Using Lemma 1, the
freshness
predicate
F
on any stream I can only be fulfilled by al-
λ
j
to each operator j along Path
I
locating sufficient resources
so that its
own
join states
