Achieving High Freshness and Optimal Throughput in CPU-Limited Execution of Multi-join Continuous Queries - Advances in Databases - page 63

We evaluate three distinct settings of the freshness predicate, namely, 1.5 ×

of the window size. The higher the freshness predicate, the more tolerant the user query
is to staleness. For each freshness value, we count the number of stale tuples produced
by each technique. The three freshness predicate values (x-axis) are plotted against the
average fraction of stale tuples/min (y-axis).
For the linear plan (Fig. 14.a), as the freshness predicate is relaxed from 1.5

× ,3 × ,and5

× ×

,
there is a marked drop in number of stale tuples. The JDA M strategy produces high
amounts of stale tuples. In absence of GH-WMSCP, even GrePP produces a substantial
amount of stale tuples. The trend is similar in the bushy plan (Fig. 14.b). However, an
even larger number of stale results are produced in the bushy plan as compared to the
linear plan.

to 5

Resource Utilization for Satisfying Freshness. We aim to evaluate the fraction of
the available resources allocated by JAQPOT towards freshness fulfillment. For these
experiments, we run JAQPOT (GH-WMSCP + GrePP) for several settings of the linear
and the bushy plans by changing the query parameters, including different

μ values. We

again evaluate three distinct freshness settings, namely, 1.5 × ,3 × ,and5 × of the window

predicates.
In Fig. 14.c, the freshness predicate (x-axis) is plotted against the fraction of re-
sources used for satisfying freshness. We find that as the freshness predicate is relaxed,
the demand for resources requirement also reduces drastically. For freshness tolerance
of 5

, the linear plan utilizes only 3% and 5% resources for freshness, respectively. Fur-
ther, as the bushy plan faces higher risk for staleness, the bushy plan uses significantly
larger portions of resources for freshness (35% for 1.5

×

). Thus, most reasonable fresh-
ness predicates may be fulfilled by allocating less than 10% of

×

on average. Moreover,
our proposed solution is guaranteed to find the best solution, if one exists. The proof can
be easily implied from optimality of the set-cover [18] and the knapsack [14] solvers.

μ

Infeasible plans. Among the plans we evaluated, we periodically found some infeasible
plans, i.e., whose freshness predicates were not achievable under existing conditions. In
particular, about 8% of the evaluated plans were infeasible, 85% of which were for the
rigid freshness predicate 1.5

and 65% were for the bushy plans.
Experimental Conclusions. The findings of our experimental study are:

×

1. JAQPOT continuously produces near-optimal throughput even in bursty streams.
2. JAQPOT consistently outperforms the state-of-the-art

ρ

h -based JDA M policy by

6 times higher throughput for all tested cases.
3. JAQPOT performs better in linear plans compared to bushy plans, as bushy plans
utilize more resources for freshness fulfillment.
4. In CPU-limited processing, result staleness problem is further aggravated if through-
put optimizing techniques are employed.
5. For all satisfiable cases, JAQPOT guarantees a throughput optimizing allocation.

producing 2 ∼

6 Related Work

Load shedding [4, 16] is popular in CPU-limited scenarios. Shedding directly drops
the tuples from the streams and the data is permanently lost. Shedding solutions, with