In a mobile-cloud database environment, different users on multiple mobile devices request services executed on a cloud. During those requests, queries are executed to obtain data, stored on the cloud and partly in caches on the mobile devices. The process of choosing an optimal query execution plan during a query optimization process is difficult because of multiple objectives involved regarding multiple non-static pricing models and different user constrains, such as monetary cost, query execution time and mobile device energy consumption. This paper provides a strategy of how to incorporate those various objectives in this decision process, based on a weighted-sum model, to achieve a good query execution plan. The experimental performance studies show that comparing with strategies, the proposed strategy is able to achieve its goal while incurs almost no additional overhead.
In a mobile-cloud database environment [
Current decision strategies mostly focus on a single main
objective, such as execution time, and order further objectives,
like monetary cost and energy consumption, in a descending
order. This strategy is called lexicographical ordering [
Laurent d'Orazio2 2 Consider the three query execution plans (QEPs) with their costs for monetary costs (M), execution time (T) and energy consumption (E) shown in Figure 1. Focusing on a single objective always leads to the decision to select either plan QEP1 or QEP2 for execution since those QEPs have a minimum cost in one of the three objectives. Since QEP3 does not have a minimum value in any of the three costs, it will never be selected although it is a competitive choice considering all three objectives on the same level of importance. Therefore, a strategy which considers all objectives at the same time is needed in order to make a comprehensive decision.
QEP1: {M= $0.080; T= 0.5s; E= 0.012 mA} QEP2: {M= $0.050; T= 3.0s; E= 0.300 mA} QEP3: {M= $0.055; T= 0.6s; E= 0.013 mA}
Figure 1 Execution Plan Costs Example
An existing optimization strategy which incorporates multiple
objectives is called the Weighted Sum Model [
To fit in the context of Query Optimization, the Normalized
Weighted Sum Algorithm (NWSA), which is proposed in this
paper, uses the Weighted Sum Model as basis but makes major
changes to cover the weaknesses of it and to fit in the
mobilecloud database environment. To cover multiple units for different
objectives, the values are normalized to a user-defined maximum.
This process eliminates units and results in distribution on a
percentage basis. Additionally, user weights are implemented to
situational stress on objectives, according to user preferences and
needs. These strategies adapt the ideas of a user based decision
[
Experiments are conducted to study the performance of NWSA.
The experimental results show that NWSA is able to derive a
good QEP and incurs almost no additional overhead comparing
with the existing strategy that is based on the lexicographical
ordering of the optimization objectives [
The rest of the paper is structured as follows.
Section 2 gives some fundamental information about the Weighted Sum Model, underlying principles and explains the adjustments of this model. Section 3 discusses other related work. Section 4 describes the proposed strategy, the Normalized 2.
This section describes the Pareto Set, which is fundamental for every Multi-Objective Optimization problem, and the Weighted
Model, that will be modified and used in the proposed strategy.
The Pareto set is a set of dominant alternatives, which does not include dominated alternatives. An alternative ‘A’ is dominating an alternative ‘B’ if at least one objective (decision variable) of ‘A’ is better than the objective in ‘B’ and all other objectives in ‘A’ are at least equal to the objectives in ‘B’. Those dominating alternatives are called Pareto optimal as defined by Zitzler and Thile [10]. In the application of query optimization, every objective corresponds to a cost, for example, query execution time, monetary
cost, or energy consumption cost, and an alternative is equivalent to a single QEP.
The strength of finding a Pareto set is that every alternative in this
set is optimal for at least one scoring function. A scoring function
describes the stress on the different objectives in order to set the
importance to them and to compare alternatives in this Pareto set.
[
The Weighted Sum Model (WSM) [
WSM score ( ∗ − ). The different objectives are assumed to be positive: the higher the score, the better the alternative. Assuming objectives to be negative (in case of cost models), the best alternative has equivalently the lowest score. 3.
The lexicographic ordering is probably the simplest but most used
scoring function to solve multi-objective optimization problems
[
once for the lowest parameter. This strategy is equivalent to the example explained in Section 1, which also shows the weaknesses of the lexicographical ordering. Multiple objectives are only considered if the selection process on a single objective is not sufficient. Although this strategy does not have to deal with multiple dimensions or units, it is not sufficient in finding an optimal solution for the proposed optimization problem since it cannot handle multiple objectives and, therefore, is not able to give a sufficient solution.
The set of all optimal solutions under every possible scoring
function is called the Pareto set. Skyline queries [
battery status, an ongoing charging process or factors describing the currently used cloud. The environmental weight adjusts the user weight if, for example, a mobile device is being charged and energy consumption is obsolete, or a query is run overnight and execution time should be assigned a minor importance factor.
can be expressed as in
Figure 3. =
Figure 3 Modified Weighted Sum Model Scoring Function is the value of alternative i (QEPi) for objective j, the userdefined acceptable maximum value for objective j, and the normalized composite
weight of user and environment for objective j defined in Figure 4. seen in this algorithm, each alternative is checked if it violates the user-defined maximum value for each objective (Lines 8-13). The violation itself has to be saved for future use (Line 11) Afterwards, the best alternative (Abest) which is the one with the lowest score is selected (Lines 14-22) and returned as the output of the algorithm. If all possible alternatives violate those restrictions, the algorithm will return the lowest score alternative (AbestRestrictionViolating) as well as the previously saved restriction(s) that it violates (Lines 24-25). The complexity of this algorithm is in linear relation to the count of alternatives, which is also the complexity of the lexicographical ordering strategy as discussed in Section 3.
= is 4.3
This section provides a proof that, independent from possible weights and from
the number of objectives, the proposed algorithm always picks an alternative within the Pareto set.
It is assumed that the chosen algorithm picks an alternative Abest which is not an element of the Pareto set. Compliant with the used formula in the proposed algorithm (Figure 3) it can be determined that − 5.
This section describes an evaluation of the proposed strategy by means of simulation experiments. It also compares the differences of the proposed algorithm
with the lexicographical ordering
strategy [
In the proposed mobile-cloud database environment, each QEP consists of three costs: monetary cost for using the cloud provider, query execution time as time to run a certain query plan, and energy used on the
mobile device. The last cost becomes
important under the condition of using a cache on the mobile
device to have the option of receiving partial or total requested
data from the mobile device itself [
In comparison to the lexicographical ordering strategy the experimental results show two facts: First, the NWSA computes the same results under the same costs as the lexicographical ordering when focusing only on one objective. Second, NWSA produces negligible overhead in computing this selection. As it was already discussed in the previous sections 3 and 4.2, both algorithms are running linear execution time related to the size of QEPs to choose from. That leads to a total algorithm execution time of less than one millisecond per experiment for both algorithms so that the difference is negligible. Concluding this comparison, negligible overhead is incurred and no higher cost alternatives results are selected. Looking at the performance of NWSA, this evaluation shows the possibilities of this strategy.
Impact of Monetary Cost Weight on
MC in $ 60000 50000 40000 30000 20000 10000 0 0 1 1 2 4 5 6 7 8 9 3 , , , , 0 0 0 0 0 0 0 0 0
0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 1
0 0 0 0 0 0 0 0 0
Weight on Monetary Cost To have an option of deciding how to stress the weights on the different objectives can change a lot in terms of total cost as it can be seen in Figure 7-9. The figures show the changes of the total cost of the one million chosen QEPs as the weight on monetary cost increases. The remaining weight is divided equally between execution time and energy consumption.
It can be seen that when the monetary cost weight increases, the monetary costs decreases, while the query execution time and energy consumption increase. It is notable that the minimum and maximum values of an objective span a large gap, so an impact of having weights is easily seen. Already having a small weight on one objective can lead to a big difference in the total cost. While not shown in this paper, the graphs plotting the impacts of increasing weights on the execution time and energy consumption show an equivalent trend as the impact of increasing weights on the monetary cost.
In this paper, a new algorithm, called Normalized Weighted Sum 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 Algorithm (NWSA), was proposed, to select the best query execution plan for query optimization that includes multiple objectives, such as monetary cost, query execution time, and energy consumption, in the decision process. The simulation experiments evaluating NWSA in the context of a mobile-cloud query optimization have been presented. NWSA is able to select the query execution plan that is an element of the Pareto set, while avoiding the expensive cost of computing the Pareto set. NWSA is highly adaptable to any multi-objective decision problem since it is not limited to any number of objectives. The experimental results show that NWSA incurs negligible computational overhead in comparison to the existing lexicographical ordering strategy. Additionally, the use of weights enables a more precise selection of a query execution plan since the minimum and maximum values of an objective span a wide gap.
A future modification is to also consider non-linear functions of
the normalization of objectives as well as of the composition of
user and environmental weights. As far as the usage of this
algorithm is concerned, we intend to incorporate it into the query
optimization process to calculate fast estimations of query costs
for clouds [
ACKNOWLEDGEMENT This work is partially supported by the National Science Foundation Award No. 1349285. [10] E. Zitzler and L. Thiele, "Multiobjective Evolutionary Algorithms:," in IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 3, NO. 4, , NOVEMBER 1999.