Chenxiao Wang
email: chenxiao@ou.edu

Le Gruenwald
email: ggruenwald@ou.edu

Laurent D'orazio
email: laurent.dorazio@univ-rennes1.fr

SLA-Aware Cloud Query Processing with Reinforcement Learning-based Multi-Objective Re-Optimization

Keywords: Query Optimization, Cloud Databases, Reinforcement Learning, Query Re-Optimization

Query processing on cloud database systems is a challenging problem due to the dynamic cloud environment. In cloud database systems, besides query execution time, users also consider the monetary cost to be paid to the cloud provider for executing queries. Moreover, a Service Level Agreement (SLA) is signed between users and cloud providers before any service is provided. Thus, from the profit-oriented perspective for the cloud providers, query re-optimization is multi-objective optimization that minimizes not only query execution time and monetary cost but also SLA violations. In this paper, we introduce ReOptRL and SLAReOptRL, two novel query re-optimization algorithms based on deep reinforcement learning. Experiments show that both algorithms improve query execution time and query execution monetary cost by 50% over existing algorithms, and SLAReOptRL has the lowest SLA violation rate among all the algorithms.

Introduction

In a traditional database management system (DBMS), finding the query execution plan (QEP) with the best query execution time among those QEPs generated by a query optimizer is the key to the performance of a query. However, in a cloud database system, minimizing query response time is not the only goal of query optimization. As hardware usage is charged on-demand and scalability is available to users, query execution monetary cost also needs to be considered as one of the objectives for optimizing QEPs. Meanwhile, the cloud providers need to minimize SLA violation rate in addition to fulfilling the users' requirements of query execution time and monetary cost for query execution. Traditionally, the query optimizer evaluates the time and monetary costs of different QEPs to derive the best QEP for a query before execution. These time and monetary costs are estimated based on the data statistics available to the query optimizer at the moment when the query optimization is performed. These statistics are often approximate, which may result in inaccurate estimates for the time and monetary costs needed to execute the query. Thus, the QEP generated before query execution may not be the best one.

To deal with this issue, there exist methods proposed to re-optimize queries during their execution [START_REF] Ortiz | Changing the Face of Database Cloud Services with Personalized Service Level Agreements[END_REF][START_REF] Marcus | Deep Reinforcement Learning for Join Order Enumeration[END_REF][START_REF] Kandi | An integer linear-programming based resource allocation method for SQL-like queries in the cloud[END_REF]. Ortiz and et al. [START_REF] Ortiz | Changing the Face of Database Cloud Services with Personalized Service Level Agreements[END_REF] apply deep reinforcement learning (RL) to learn a representation of queries, which can then be used in downstream query optimization tasks. Marcus and et.al present work of a deep RL-based join optimizer, ReJOIN [START_REF] Marcus | Deep Reinforcement Learning for Join Order Enumeration[END_REF], which orders a preliminary view of the potential for deep RL in this context. In these techniques, QEPs are re-optimized multiple times by a deep RL model. Kipf [START_REF] Kandi | An integer linear-programming based resource allocation method for SQL-like queries in the cloud[END_REF] uses Deep Neural Network (DNN) to learn cardinality estimates. Wu and et.al [START_REF] Wu | Sampling-Based Query Re-Optimization[END_REF] have proposed Sample, a query re-optimization algorithm that updates data statistics estimated from a sample of tuples collected during runtime. However, none of them addresses monetary costs and SLA requirements for cloud databases at the same time. In this paper, we present two algorithms, ReOptRL and SLAReOptRL, that use reinforcement learning to perform multi-objective query re-optimization for query processing in an end-to-end cloud database system. The algorithms employ a reward function designed specifically for query re-optimization considering query execution time, money cost and SLA requirements.

The Reinforcement Learning-based Multi-Objective Query Re-Optimization Algorithm (ReOptRL)

We choose RL instead of supervised learning methods because RL does not require training data, which is a labeled dataset of past actions, to be available in advance to train the learning model before the model can be used to predict future actions. There are various kinds of RL algorithms that have been proposed. Q-Learning is one of the popular value-based RL algorithms and using the Bellman equation [START_REF] Wiering | Reinforcement Learning: State-of-the-Art[END_REF].

𝑄(𝑆 ! , 𝑎 ! ) ← 𝑄(𝑆 ! , 𝑎 ! ) + 𝛼*𝑅 ! + ϒ 𝑄(𝑆 !"# , 𝑎 !"# ) -𝑄(𝑆 ! , 𝑎 ! ). (1)
In Q-Learning, a table (called Q-table) is used to store all the potential state-action pairs (Sn, an) and an evaluated Q-value associated with this pair. In Equation (1), Q (St, at) is an evaluated value (called Q-value) for executing Action at at State St. This value is used to select the best Action to perform under the current state. In our scenario, there are many available containers on which a single query operator can be executed. Thus, many state-action pairs are in the Q-table potentially. Iterating a large Q-table incurs extra time overhead which delays the query execution. To solve this issue, we apply Deep Q Network (DQN) [START_REF] Wiering | Reinforcement Learning: State-of-the-Art[END_REF] as our reinforcement learning for query re-optimization. DQN works similarly to Q-Learning. The major difference is that, given a state, instead of using the Q-table, it uses a neural network to estimate the Q-values for all the potential actions. The input of the neural network is the current state. For the current QEP to represent the current state, we use a one-hot vector adapted from the recent work [START_REF] Marcus | Deep Reinforcement Learning for Join Order Enumeration[END_REF] to represent a QEP. The ReOptRL algorithm is given in Fig. 1. First, a query is submitted to a query optimizer which generates the QEP (logical plan) for the query (Line 4). Then the QEP is converted into a one-hot vector representation (Line 7). This vector is sent to the RL model, which is a neural network. The RL model will evaluate the Qvalues for all the potential actions to execute the next available query operator (Line 8). Each of these actions consists of two parts, a physical operator and a container (machine) to execute the physical operator. Then the action with the best Q-value will be selected and performed by the DBMS (Line 9). After that, the executed query operator is discarded from the QEP (Line 10). The reward is updated with the time and monetary cost needed to execute the operator and then the expected Q-value is updated by the Bellman Equation ( 1) with the updated reward (Lines 11-13). The weights of the neural network are updated accordingly by the back-propagation method (Line 14). This process repeats for each operator in the QEP and terminates when all the operators in the QEP are executed. The query results are then sent to the user (Line 17).

Fig. 1. The ReOptRL Algorithm

In ReOptRL, after an action is performed, the reward function is used to evaluate the action. This gives feedback on how the selected action performs to the learning model. The performed action with a high reward will be more likely to be selected again under the same state. The reward function plays a key role in the entire algorithm. According to the Bellman equation, if the reward of performing a previous action At-1 is high on state St-1, the Q-value will also be high. This means that, given the same state, the action with the good previous performance will have a higher chance to be selected. In our algorithm, we would like the actions with low query execution time and monetary cost to be the ones that will be more likely to be chosen. To reflect this feature, we define the reward function as follows: where 𝑊 ! and 𝑊 * are the time and monetary weights provided by the user, and T +, -and M +, -are the time and monetary costs for executing the current operator op in query q.

𝑅𝑒𝑤𝑎𝑟𝑑 𝑅 = # #"(% ! * ' "# $ )"(% % * ) "# $ ) (1
According to this reward function, the query is executed based on the user's preference which is either the user wanting to spend more money for a better query execution time or vice versa. We call these two preferences Weights. These two weights defined by the user are called Weight Profile (wp), which is a two-dimensional vector, and each dimension is a number between 0.0 to 1.0. Notice that the user only needs to specify one dimension of the weight profile, the other dimension is computed as 1-Weight automatically. The detail can be found in our previous work [START_REF] Wang | Adaptive Time-Monetary Cost Aware Query Optimization on Cloud DataBase[END_REF].

3 The SLA-Aware Reinforcement Learning-Based Multi-Objective Query Re-Optimization Algorithm (SLAReOptRL)

An SLA is a contract between cloud service providers and consumers, mandating specific numerical target values which the service needs to achieve. Considering an SLA in query processing is important for cloud databases. If an SLA violation happens, the cloud service providers need to pay a penalty to their users in a form such as money or CPU credits. From a profit-oriented perspective, cloud service providers would want to keep the number of SLA violations as low as possible. Different cloud service providers implement different SLAs with their users. Using time and monetary costs to execute a query as the SLA requirements has been studied in [START_REF] Ortiz | Changing the Face of Database Cloud Services with Personalized Service Level Agreements[END_REF]. We find them practical and more specific to users and thus adopt the same SLA requirements in our work.

In particular, the reward function shown in Equation ( 4) is extended from Equation (2) to make it possible to select the best action according to the SLA requirements:

𝑅𝑒𝑤𝑎𝑟𝑑 𝑅 = ! !"($ ! * &' "# $ "( ! ))"($ % * (+ "# $ "( % )) (2)
where 𝑇 ./ 0 and 𝑀 ./ 0 are the time and monetary costs for executing the current operator op in query q

𝑃 , = 𝛼 -. * 𝑑𝑒𝑙𝑎𝑦_𝑡𝑖𝑚𝑒, 𝑃 / = 𝛼 -. * 𝑒𝑥𝑐𝑒𝑒𝑑𝑒𝑑_𝑚𝑜𝑛𝑒𝑦
where 𝛼 ./ is the operator impact rate of the operator type op

𝑑𝑒𝑙𝑎𝑦_𝑡𝑖𝑚𝑒 = 7 0 𝑇 -. 0 -𝑆𝐿𝐴. 𝑇 -. 0 𝑖𝑓 𝑇 -. 0 > 𝑆𝐿𝐴. 𝑇 -. 0 (3)
𝑒𝑥𝑐𝑒𝑒𝑑𝑒𝑑_𝑚𝑜𝑛𝑒𝑦 = 7 0 𝑀 -. 0 -𝑆𝐿𝐴. 𝑀 -. 0 𝑖𝑓 𝑀 -. 0 > 𝑆𝐿𝐴. 𝑀 -. 0 (4)
In this reward function (Equation ( 4)), 𝑃 ! and 𝑃 * reflect the extra costs for executing a query operator if the SLA is violated. If the SLA is not violated for executing every operator, then this equation is the same as the reward function used in ReOptRL (Equation ( 2)). In Equations ( 5) and ( 6), 𝑑𝑒𝑙𝑎𝑦_𝑡𝑖𝑚𝑒 is the amount of difference between the actual time to execute a query operator and the maximum time allowed to execute this query operator as specified in the SLA. The same idea applies to 𝑒𝑥𝑐𝑒𝑒𝑑𝑒𝑑_𝑚𝑜𝑛𝑒𝑦 for monetary costs. We use these two values to quantify the SLA violation on query execution time and monetary cost. In Equation ( 4), these two values are used to compute 𝑃 ! and 𝑃 * . It shows that the larger the number of SLA violations, the smaller the reward becomes. We build the reward function this way so that the reward is related to SLA violations. Also, we use the query operator impact rate 𝛼 ./ to scale up the impact of SLA violations on different types of operators.

Performance Evaluation

There are two sets of machines used in our experiments. A single local machine used to train the machine learning model and to perform the query optimization. This local machine has an Intel i5 2500K Dual-Core processor running at 3 GHz with 16GB DRAM. The second set consists of 10 dedicated Virtual Private Servers (VPSs) that are used for the deployment of the query execution engine. The query optimizer and the query engine used in the experiments are modified from the open-source database management system, PostgreSQL 8.4. The data are distributed among these VPSs. The queries and database tables are generated using the TPC-H database benchmark. The database tables are populated with 1,000 GB data using the default data generator. We run 50,000 queries and these queries are generated by the query templates randomly selected from the 22 query templates from the benchmark.

We compare the performance results obtained when the following query re-optimization algorithms are incorporated into query processing: 1) our two proposed algorithms, ReOptRL and SLAReOptRL; 2) the algorithm where a query re-optimization is conducted automatically after the execution of each operator in the query is completed (denoted as ReOpt), which we developed based on the work presented in [START_REF] Wang | Adaptive Time-Monetary Cost Aware Query Optimization on Cloud DataBase[END_REF]; 3) the algorithm where a query re-optimization is conducted by a supervised machine learning model decision (denoted as ReOptML). 4) the algorithm proposed in [START_REF] Wu | Sampling-Based Query Re-Optimization[END_REF] where query optimization uses sampling-based query estimation (denoted as Sample), and 5) the algorithm that uses no re-optimization (denoted as NoReOpt). From Fig. 2 (a) and (b), we can see that, for both the query execution time and monetary costs, on average SLAReOptRL performs the best and ReOptRL performs the second best among all the algorithms. Specifically, comparing with the baseline NoRe-Opt where no re-optimization is conducted, the query execution time improvement using SLAReOptRL is 45%, ReOptRL 39%, ReOptML 27%, ReOpt 13%, and Sample 10%, while the monetary cost improvement using SLAReOptRL is 62%, ReOptRL 52%, ReOptML 27%, ReOpt 17%, and Sample 5%. Especially, the monetary cost has a significant improvement (SLAReOptRL and ReOptRl are 62% and 52% better than NoReOpt, repsectively). Moreover, from Fig. 3, we can also find that by using SLAR-eOptRL, the SLA violation rate is the lowest one among the SLA violation rates caused by all the algorithms. This shows the positive effect of considering SLA requirements in re-optimization.

Conclusion

This paper presents two query re-optimization algorithms called ReOptRL and SLAR-eOptRL. Both use a reinforcement learning-based model to decide the physical query operator and machines to execute an operator from a query execution plan (QEP) for a query in a cloud database system. The experiments conducted using the TPC-H database benchmark show that both SLAReOptRL and ReOptRL improve query response time (from 12% to 45%) and monetary cost (from 17% to 62%) over the existing algorithms In addition, we also find that when there are SLA requirements, SLAReOptRL performs 20% better than ReOptRL on SLA violation rate.

Fig. 2 .

 2 Fig. 2. Time (a) and monetary cost (b) performance for executing queries using different algorithms (a) (b)

Fig. 3 .

 3 Fig.3. Average SLA violation rates when executing queries using different algorithms

  )

		Algorithm: Reinforcement Learning Based Multi-Objective Query
	Re-Optimization (ReOptRL)
		INPUT: SQL query, Weight Profile wp, Reward Function R (),
		Learning rate α, Discount rate ϒ
		OUTPUT: The query result set of the input query
	1.	t=0
	2.	Result = Φ
	3.	Qt= 0
	4.	QEP = QueryOptimizer(query)
	5.	while QEP≠ Φ
	6.	Op=next available operator in QEP
	7.	State St= convert QEP to a state vector
	8.	Actiont=RunLearningModel (St, wp)
	9.	Result=Result ∪ execute (Op, Actiont)
	10.	QEP=QEP-Op
	11.	Update RN=R (wp, Actiont.time, Actiont.money))
	12.	Obtain Q-value of next state Qt+1 from the neural network
	13.	Update Q-value of current state Qt = Bellman (Qt, Qt+1, Rt, 𝛼, ϒ)
	14.	Update Weights in the neural network
	15.	t=t+1
	16. end while
	17. return Result


Michail Georgoulakis
email: michailgeorgoulakis@dblab.ece.ntua.gr

Verena Kantere
email: verena@dblab.ece.ntua.gr

Michail Georgoulakis Misegiannis

Laurent D'orazio
email: laurent.dorazio@univ-rennes1.fr

Multi-objective query optimization in Spark SQL

Keywords: Information Systems → Query optimization;, Parallel data processing → Apache Spark query optimization, cost model, cloud computing, multi-objective optimization, Apache Spark, Catalyst optimizer

published or not. The documents may come

INTRODUCTION

Query optimization is the most challenging step of query processing. A query optimizer can either be rule-based, using heuristics to convert the logical query plan to a physical one, or cost-based, using cost functions to compare alternative query plans and return the optimal according to its estimations. The architecture of a costbased query optimizer consists of 3 key stages that determine the quality of its predictions [START_REF] Leis | How Good Are Query Optimizers[END_REF] : cardinality estimation, cost modeling and plan enumeration.

The majority of works on query optimization aim to minimize query execution time on a fixed hardware configuration, which is a valid assumption in the on-premise world. Query processing in the Cloud, however, presents an extra challenge as a number of alternative hardware instances are available. Depending on the resource configuration that is used, the execution might be completely different. Decision making involves deciding on the type of the cluster (homogeneous or heterogeneous), the number of instances that will be used, their type, and their characteristics (e.g. RAM size). In such a scenario, a query optimizer should be able to pick both an optimal physical query execution plan, as well as a resource configuration among available hardware instances, thus bridging the gap between query and resource optimization [START_REF] Viswanathan | Query and Resource Optimization: Bridging the Gap[END_REF].

In order to achieve this, optimizer cost models should be hardwareagnostic, being able to model the behaviour of a query plan in different clusters and systems. A hardware-agnostic cost model could lead to lower costs as well as better resource efficiency [START_REF] Siddiqui | Cost Models for Big Data Query Processing: Learning, Retrofitting, and Our Findings[END_REF].

Query optimization is usually associated with minimizing query execution time. The performance of a query, however, can be evaluated in terms of more objectives. Features of the cloud, like resource elasticity and pricing increase the objectives that can be simultaneously optimized in a cloud setting. Adding instances to achieve maximum parallelization during query execution will in general lead to lower execution times, but may also lead to much higher monetary costs, as well as increased energy consumption. Monetary cost is one of the most prevalent query optimization objectives in the cloud [START_REF] Trung | Dynamic Estimation and Grid Partitioning Approach for Multi-objective Optimization Problems in Medical Cloud Federations[END_REF][START_REF] Leis | Towards Cost-Optimal Query Processing in the Cloud[END_REF][START_REF] Song | Spark-based Cloud Data Analytics using Multi-Objective Optimization[END_REF]. Energy consumption has also been considered lately [START_REF] Sathya Sofia | Multi-objective Task Scheduling to Minimize Energy Consumption and Makespan of Cloud Computing Using NSGA-II[END_REF], as cloud providers yearn for reducing energy cost. Other objectives that can be considered in multi-objective query optimization are result precision [START_REF] Trummer | Multi-objective parametric query optimization[END_REF], or data security.

Query optimization in big data systems, which are usually hosted in the cloud, is particularly challenging. As a result, it is necessary that the estimation components of query optimizers (cardinality estimator, cost model) are accurate. One of the most popular big data processing frameworks is Apache Spark, which is widely used in research and industry. However, the query optimizer of Spark's SQL-based component, Spark SQL, has a limited cost model.

In this work, we propose a multi-objective cost model for Spark SQL. In order to achieve this, we re-implement an existing proposed cost model [START_REF] Baldacci | A Cost Model for SPARK SQL[END_REF] for Spark SQL which shows promising accuracy in estimating query execution time. We validate its accuracy and extend it to provide estimations for the monetary cost of a given query plan.

The cost model receives a query and a set of Spark application configurations as an input, and returns the optimal query plans for each configuration, resulting in a Pareto front. The returned plans present different tradeoffs for the two objectives, and the user can either pick one or assign preference weights to the two objectives, and be provided with a single query plan that best meets them.

We also conduct an experimental study to validate the cost model estimation and prediction accuracy for a Spark-Yarn-HDFS architecture. We conducted our experiments on a real private cloud environment, using data and queries from the TPC-H benchmark.

Overall, the contributions of this work are the following:

• proposal of a multi-objective cost model for Spark SQL • a user-interactive method for exploring the space of alternative query plans and choosing an optimal one • reimplementation and extension of a state of the art cost model • a detailed experimental study on a real private cloud environment The rest of this paper is organized as follows. Related work is discussed in Section 2. Section 3 describes the cost model that we implemented. The experimental evaluation and its results follow in Section 4, while Section 5 concludes the paper.

RELATED WORK

Optimization in Spark The Spark SQL query optimizer, Catalyst [START_REF] Armbrust | Spark SQL: Relational Data Processing in Spark[END_REF], is an extensible optimizer which can be extended with new rules. However, it is not ideal for cost-based query optimization. It only uses a limited cost model, being unable to provide analytical estimations for the execution time of a query plan. A number of research works have focused on improving specific limitations of the Catalyst optimizer [START_REF] Chawla | Optimization in the catalyst optimizer of Spark SQL[END_REF][START_REF] Uta | Demo] Lowlatency spark queries on updatable data[END_REF].

In 2018, Baldacci and Golfarelli proposed a cost model for Spark SQL [START_REF] Baldacci | A Cost Model for SPARK SQL[END_REF], which showed promising results for the set of GPSJ queries, as it estimates their execution time with less than 20% error. It is a proposed improvement to the Catalyst optimizer which, as its authors state, is a first step into turning the Catalyst into a fully cost based optimizer. The cost model was not integrated into the Catalyst itself, but was evaluated manually. It includes a cardinality estimation technique, and it is also hardware and cluster-agnostic.

Although Spark is highly configurable, its manual tuning is time consuming and complex, due to the high-dimensional configuration space. A lot of works provide frameworks for tuning Spark applications [START_REF] Nikitopoulou | Performance Analysis and Auto-tuning for SPARK in-memory analytics[END_REF][START_REF] Song | Spark-based Cloud Data Analytics using Multi-Objective Optimization[END_REF][START_REF] Yu | Datasize-Aware High Dimensional Configurations Auto-Tuning of In-Memory Cluster Computing[END_REF], in most cases with learned methods. The proposed cost model can be useful in this perspective too, as apart from producing optimal query plans, it can also be used for tuning and comparing different application configurations.

Multi-objective query optimization Karampaglis et al. [START_REF] Karampaglis | A Biobjective cost model for database queries in a multi-cloud environment[END_REF] proposed a bi-objective query cost model suitable for query optimization over a multi-cloud environment. It successfully provides estimates of both the expected execution time and monetary cost.

A number of works have considered multi-objective query optimization in the cloud. Kllapi et al. [START_REF] Kllapi | Schedule optimization for data processing flows on the cloud[END_REF] proposed a technique to optimize dataflow scheduling on a set of containers and form one schedule best meeting user constraints. Their work can also be used for query optimization, when the execution of a query can happen over multiple containers. Multi-objective parametric query optimization [START_REF] Trummer | Multi-objective parametric query optimization[END_REF] takes a different approach to query optimization, which happens before runtime with the use of an exhaustive DP algorithm, and models queries as functions of parameters.

COST MODEL AND IMPLEMENTATION

In this work, we propose a cost model for cost-based multi-objective query optimization in Apache Spark. The cost model is based on a proposed cost model for Spark SQL [START_REF] Baldacci | A Cost Model for SPARK SQL[END_REF], which is reimplemented, experimentally evaluated, and extended to include a formula for the estimation of the monetary cost of query plans. By using the extended cost model, the query optimization problem is tackled as a multi-objective optimization (MOO) problem aiming to minimize monetary cost together with query execution time, and using different methods to explore the space of Pareto-optimal query plans.

System Architecture

Figure 1 shows the system upon which the cost model operates.

The storage layer includes a number of datanodes inside an HDFS filesystem. Data is processed in Spark, and Yarn is the resource negotiator between HDFS and Spark. For data management, data is stored in Apache Hive tables and accessed through Spark SQL queries. As for the optimizer, we envision an extended version of the Catalyst, operating cost-based by using the proposed cost model. We implemented the cost model outside Spark and used it manually.

Cost Model Preliminaries

The proposed Spark SQL cost model [START_REF] Baldacci | A Cost Model for SPARK SQL[END_REF] can provide more than Catalyst when it comes to estimating the execution time for a query execution plan, as highlighted by Table 1. It is based on disk access time and network speed, as disk and network performance is critical in one-pass workloads, like Spark SQL queries. This means that it is a reconfigurable model, that can be tuned for any cluster (as long as it is homogeneous) and system. It also performs traditional SQL optimizations by collecting table and columns statistics from the database. It is also aware of the cluster topology, and takes into account Spark application parameters that influence query execution time. The Spark application parameters considered are the number of Spark executors, and the number of cores inside each executor.

One of its limitations is that it only covers the class of Generalized Projection, Selection, and Join (GPSJ) queries, which are a subset of SQL queries. This means that the use of specific SQL operators like UNION ALL or OUTER JOIN are not supported by the cost model. In addition to that, it is also limited to homogeneous clusters, not being able to make estimations for clusters involving different computing instances.

The cost model is capable of analytically estimating the execution time of the five essential RDD transformations that occur in Spark SQL GPSJ queries: (1) Full table scan (2) Full table scan and broadcast (3) Shuffle hash join (4) Broadcast hash join (5) Group by. Each of the transformations is modeled as a function, in the cost model code. Precisely modeling these operations is challenging, so the cost model focuses on a set of basic bricks that determine transformations and actions cost, for which it provides cost estimates (Read, Write, Shuffle Read, Broadcast). Each one of these functions receives a data table set as an input (or two, in case of a join operator), as well as the table's cardinality, size, partitions and any filtering predicates. It returns the estimated time needed to execute the transformation, the columns returned, the cardinality and the adjusted size of the table set, as well as the number of partitions of the output. The estimated execution time for a query is obtained by summing up the time needed to execute each RDD transformation forming the query physical plan.

Bi-objective cost model

In the Spark-Yarn-HDFS architecture, query execution involves two parts. A user submits a query, and then specifies some parameters to configure the Spark application. Spark application tuning usually occurs manually and empirically and is a complex decision to make, as Spark has a considerable number of parameters that can be configured. One of the most critical parameters is the number of executors that will be allocated for an application. Each Spark executor runs within a Yarn container. Yarn containers are provided by Yarn on demand at the start of each Spark Application. Each one hosts a Spark executor as well as a number of cores that are assigned to it. They are deallocated when the Spark application completes.

If the Spark application were to be deployed on a public cloud, assigning each executor on a different computing instance would allow us to benefit from maximum parallelization. It would require renting a number of homogeneous computing instances from a public cloud provider, using them during the runtime of a query and leasing them when execution is completed. The monetary cost of running a Spark application with 4 executors and 4 cores on each executor in a 4-node cluster in a public cloud is equivalent with the cost of renting 4 homogeneous computing instances with 4 vCPUs each, for the time needed for the query to execute.

As a result, we model the monetary cost of a query plan with the following formula:

𝑐𝑜𝑠𝑡 = #𝑒𝑥𝑒𝑐𝑢𝑡𝑜𝑟𝑠 * 𝑟𝑢𝑛𝑡𝑖𝑚𝑒 * 𝑒𝑐2𝑐𝑜𝑠𝑡 ($/ℎ𝑜𝑢𝑟 )/3600 (1)
with ec2cost being the hourly cost of using a given instance on Amazon EC2, which we divide by 3600 to scalarize it to seconds. If we use two a1.xlarge instances, for example, we can simulate the execution of a Spark query with 2 executors and 4 cores (a1.xlarge includes 4 vCPUs). The formula assumes per-second billing.

Query plan enumeration

For a given query, the cost model is able to compare all valid query plans. In our case, two alternative join operators were available and we considered all their combinations, as well as all possible join orderings. We based our monetary cost estimations on the price of renting an a1.medium instance from Amazon EC2, considering cases of renting a different number of a1.medium instances, ranging from 1 to 8. The cost model is easily extensible therefore prices for more computing instance types can be included and different cluster and application scenarios can be compared, as long as the cluster is homogeneous. As a result, our search space for a query involving 3 join operators involved 2 3 join operator combinations, 3! join orderings, and 8 available application configurations, involving a different number of computing instances each time. We assumed that one Spark executor is allocated for each computing instance, resulting in a search space of 8*6*8=384 query plans. Understandably, the search space can become extremely large for more comlpex queries. The search space can be reduced significantly if we assume that join ordering happens optimally, as the most recent Catalyst version can make cost-based join ordering decisions. A further reduction can be achieved by not considering query plans involving broadcast hash joins for joins involving table sets whose size exceeds a specific threshold, as well as the opposite, considering only broadcast hash joins for trivial cases, where a table set joined is considerably small. Applying these 2 steps can lead to a significant reduction of the search space.

In the experimental part, we also had to overcome the limitation of Catalyst returning a single query plan and not providing alternatives, which we did by reconfiguring certain configuration parameters (disabling broadcast joins, changing broadcast joins thresholds). This allowed us to produce and compare many query plans.

Multi-objective optimization

We follow a two-step process to achieve multi-objective optimization. In the first step, we apply single-objective optimization, to find the optimal query plan in terms of execution time for every one of the available system configurations. A single query plan is returned for each available Spark configuration. The point of this step is that as the monetary cost of the query is dependent on query execution time, the fastest plan will also be the cheapest, for a fixed computing instance and a fixed number of Spark executors. Thus, the different tradeoffs are offered by the alternative configurations, and not by alternative query plans inside a certain application setting.

The second step is the multi-objective optimization one, as all the query plans from the first step are compared in terms of both objectives. Dominated plans are discarded, and the remaining, Paretooptimal plans are the output of the cost model, forming a Pareto front. The query plan that will be selected will determine both the physical query plan that will be used for query execution, as well as the application configuration in Spark.

After the Pareto front is formed, the final step is the decision process, which will happen by the user. As the number of alternative query plans can be quite large, the process of visualizing the alternatives to the user, and assisting him/her to make a decision is another challenge.

The user can pick a query plan that best meets his/her needs. In order to reduce the number of alternatives, he/she can set maximum price and latency filters to adjust to his/her budget and needs. The cost model can also be used in the user-interactive mode. In this mode, the user submits preference weights to the objectives and the cost model returns a single plan best meeting them, having scalarized the problem back to a single-objective one, using a simple equation.

𝐹 (𝑥) = 𝑤 1 * 𝑓 1 (𝑥) + 𝑤 2 * 𝑐 * 𝑓 2 (𝑥) (2)
where c is a constant that we set to an empirical value of 25000, used to normalize the values of time and money to the same order of magnitude. In that case, 25 seconds of query execution are equivalent with a monetary cost of 0.001 US dollars. In our experiments, execution time varied between 50-400 seconds depending on the query and configuration, and monetary cost between 0.001 -0.01 US dollars per query, so in case no objective is weighted, a query plan near the middle of the Pareto curve is selected. The query plan that has the minimum value for F, is the one selected for execution. Before the user submits the preferred weights, he/she can also be provided with a value showing the time-money relationship for the weights he/she has selected.

EXPERIMENTAL EVALUATION

Methodology The cost model makes the following assumptions, which our work inherited too:

• It covers the class of GPSJ queries • It assumes uniform distribution of data in table sets

• It performs single query optimization, assuming a cold start • It assumes operating on a homogeneous cluster We evaluated the cost model for a main-memory scenario, assuming that all data fits in memory, as well as intermediate results. We also assumed exclusion of exogenous factors potentially affecting cluster performance, and we calculated a Spark-Yarn initialization overhead in each query, which we did not take into account.

For the evaluation of the cost model, we follow a two step methodology. First, we examine the estimation accuracy of the cost model. Second, we evaluate the optimality of the cost model, aiming to see if it can point to an optimal query plan among alternatives.

The cost model can be used to produce a Pareto front, including plans that offer different time-money tradeoffs. The decision maker Setup We conducted our experiments in Grid '5000 [], a largescale and flexible platform for experiment-driven research in computer science, with a focus on parallel and distributed computing.

In our experiments Grid '5000 was used as a private cloud, where we deployed up to 8 homogeneous computing nodes, each one containing 2 CPUs Intel Xeon E5-2630 v3, 8 cores/CPU, 128GB RAM, 5x558GB HDD, 186GB SSD, and 2 x 10Gb Ethernet. Inside our cluster, we set up an HDFS filesystem where each node worked as a datanode, and our dataset was stored in the SSDs.

Experimental Evaluation The cost model was reimplemented using the formulas described in the original paper to model each one of the five RDD transformations. For our experiments and estimations we used the TPC-H benchmark dataset and queries. The performance of the cost model was validated, when it comes to taking into account the impact of different factors. This allowed us to fine-tune the cost model for our system configuration, and also re-evaluate it and observe its strengths and inaccuracies. Figure 2 shows its performance for a number of TPC-H queries (7.7% error) in a scenario with 4 Spark executors and 4 executor cores. The estimations are quite accurate with the exception of Query 10, where there is a 20% overestimation error. After breaking down the query, which involves 5 tables and 4 join operations, we realize that the key overestimation occurs in the final broadcast join, which runs quicker than expected. Figure 3 shows that the cost model is also able to capture the impact adding Spark executors has for query execution, with an error rate of 12.1%. The query execution time values are an average of a set of TPC-H queries' execution time. A more detailed evaluation of the cost model estimation accuracy can be found in the diploma thesis, upon which this paper is based [].

Inaccuracies mainly have to do with the fact that the cost model does not precisely model Spark data actions and transformations, but only provides estimates on key operations. Furthermore, in some cases it assumes linear relations between different factors not considering heuristics or overkills that occur in Spark. Finally, stochastic processes happening in the cluster might be influencing system characteristics like the read/write throughput or the network speed, causing minor inaccuracies. Tuning the cost model for a given cluster was a challenging task.

In terms of optimality (prediction accuracy), the cost model is able to make correct choices for trivial cases. For complex queries, when it did not point to the optimal plan, it was able to at least spot the trends and propose a near-optimal query plan, having small 4 shows the performance of the cost model when it comes to comparing 3 good enough query plans for TPC-H Query 2, for a configuration involving 4 Spark executors and 4 executor cores. As the table sets considered in Query 2 are quite small, the query plan involving only broadcast joins performs slightly better than the alternatives. Shuffle joining in every case results in a slightly worse execution time, whereas operating the first join with a shuffle join operator and the other two with a broadcast one has similar execution time with the optimal case. The cost model gives equally good estimates for the two best execution plans.

In comparison with the Catalyst, it is able to make better choices than the Spark SQL optimizer in many cases. For example, for a very simple query involving just a join operation (Fig. 5), we can see that a broadcast hash join is a better choice, as it results in an 8 seconds faster query execution than using a shuffle hash join. However, the Catalyst will by default choose to shuffle join these tables. The cost model is able to point to the broadcast hash join as the better option. In the experimental study, the cost model proved that it can be a "relevant first step for turning Catalyst into a fully cost based optimizer", showing significant estimation accuracy while The cost model returns the fastest query plan for each application configuration, and then the plans are compared in terms of both objectives. In that case, all three query plans are Pareto optimal and form a Pareto front, as they present different time-money tradeoffs. Thus, the problem is formulated to a multi-objective optimization one. The user can either decide himself/herself which query plan best fits his/her application, or can assign weights of preferences to the objectives in the user-interactive mode of the cost model. For the case of 𝑤 1 = 𝑤 2 , the plan with the 4 executors is picked. In case of 𝑤 1 = 2 * 𝑤 2 , the plan with the 8 executors is picked, and in case of 𝑤 2 = 2 * 𝑤 1 the selected plan is the one with 2 executors, as the time-money relationship changes each time.

FUTURE WORK -CONCLUSION

In the future, we aim to extend the cost model to consider heterogeneous resources. This will require modeling the execution costs on different hardware, like GPUs. We also aim to explore more optimization goals, like energy consumption, which is a critical objective in green and sustainable data centers. Finally, a long term goal is to try to integrate the cost model into the Catalyst.

In this paper we proposed a multi-objective cost model for query optimization in Spark SQL. We built on a proposed cost model that showed promising results, which we extended by introducing a formula for estimating the monetary cost of query plans in Spark. The cost model is able to produce and compare query plans providing different time-money tradeoffs, and we also introduce a method for assisting the user into picking a single one. The cost model was implemented and tested, as a detailed experimental study was conducted in a private cloud environment.

Figure 1 :

 1 Figure 1: System architecture

Figure 2 :

 2 Figure 2: Execution time for different TPC-H queries

Figure 3 :Figure 4 :Figure 5 :

 345 Figure 3: Query Execution times for different number of Spark executors

  Figure

Figure 6 :

 6 Figure 6: Pareto Front of the optimal query plans

Table 1 :

 1 Comparison of Catalyst and proposed cost model


Michail Georgoulakis Misegiannis

Laurent D'orazio
email: laurent.dorazio@univ-rennes1.fr

Verena Kantere
email: verena@dblab.ece.ntua.gr

From Cloud to Serverless: MOO in the new Cloud epoch

During the last 10 years, the volume of global data has risen more than tenfold. The commercial rise of cloud computing eased the process of storing, processing and managing big data. Recently, the cloud evolved with the emergence of serverless computing platforms that offer an even more abstracted service model. The elasticity of cloud computing creates significant optimization problems, which can be tackled either with a single objective, or as multi-objective opimization problems (MOO). When it comes to data management, the two main MOO problems in a cloud computing environment are query optimization and task scheduling. Some of the techniques used for solving MOO problems in the cloud are the weighted sum model, mathematical-programming based algorithms and genetic algorithms.

We propose the presentation of a tutorial that will underline the main MOO problems of a cloud computing environment in regards to data management, and evaluate the use of serverless computing for such problems. The tutorial will offer the audience a better understanding of current MOO challenges and applications in the cloud, while also giving them an overview of different solutions to such problems and the techniques that can be used for solving them. * The supervisors' names are included in alphabetical order, both contributed equally.

DURATION

The tutorial will be presented in one and a half hour. It will consist of three parts, lasting half an hour each. The topics to be discussed in each part will be presented in the following sections.

2 TUTORIAL DESCRIPTION 2.1 From Cloud Computing... Cloud computing refers to the on demand delivery of computing services to different clients. These services are provided by cloud vendors on three levels of abstraction, each one represented by a service model:

Infrastructure as a service (IaaS) In IaaS platforms, users can rent and manage data center infrastructure like compute and storage services in the form of virtual machines.

Platform as a service (PaaS) PaaS provides hardware and software tools for the user to build and manage a customized application.

Software as a service (SaaS) SaaS delivers web applications to its users, which are fully managed by the SaaS vendor.

Cloud computing comes with significant advantages, enabling users to make savings in cost through a pay for use pricing scheme, and providing elasticity in terms of resource management. The significance of these benefits led to the emergence of a new cloud service model:

Function as a service (FaaS) Serverless computing consists of two service models, FaaS and BaaS (backend as a service). Serverless however most often refers to FaaS platforms, which are code execution environments where developers can write applications in the form of independent functions and execute them using cloud resources. FaaS has similarities with IaaS and PaaS. It differs from PaaS in terms of scaling, which is done automatically in FaaS, and its difference from IaaS is that apart from scaling, resource allocation and management are also automatic in FaaS. FaaS also has a pay for use charging policy, meaning that a FaaS user will never sustain and pay for idle resources.

Despite the advantages, the increased abstraction of FaaS comes with some significant limitations, not allowing it to reach its full potential [START_REF] Hellerstein | Serverless Computing: One Step Forward, Two Steps Back[END_REF][START_REF] Khandelwal | Le Taureau: Deconstructing the Serverless Landscape A Look Forward[END_REF][START_REF] Wawrzoniak | Boxer: Data Analytics on Network-enabled Serverless Platforms[END_REF]. Some of them are the following: (1) the functions short lifespan; (2) the lack of direct communication between functions; (3) the startup delay when invoking multiple functions (cold start); (4) the lack of resource heterogeneity in today's FaaS offerings; (5) security vulnerabilities.

Pricing and elasticity make the cloud a suitable environment to run data-intensive applications. As a result, large volumes of data are stored and processed in the cloud, and data management in such applications is critical. An important part of data management is query processing, which, combined with cloud resources' management are two procedures containing significant optimization problems. The focus of this tutorial are IaaS platforms, where the different resource allocation options mean that one combination of resources will be better than another, depending on user objectives, which leaves room for optimization problems.

Query processing consists of four stages: parsing, translation, optimization and evaluation, with query optimization being the most challenging one. During this phase, a logical plan is received by a query optimizer and an optimal physical query plan is returned, including the physical operators that will be used for query execution. The space of alternative query plans can be very big for complex queries, complicating query optimization.

When it comes to resource management, IaaS platforms include a pool of available resources which can be rented by their users to execute their tasks. The resource configuration a user chooses for an application will determine how efficiently the application will be executed. Furthermore, the task of scheduling tasks to available resources is a difficult optimization problem, due to the infinite space of alternative schedules. These two are the two main resource optimization problems in an IaaS environment.

Optimization problems such as query optimization and task scheduling can be tackled as multi-objective optimization problems (MOO). In MOO, the goal is to find a set of Pareto-optimal solutions, which are solutions that cannot be improved in any of the objectives without degrading at least one of the other objectives. The different optimization goals considered for the aforementioned data and resource management problems can be the following: (1) execution time, the primal optimization objective in related MOO works (2) monetary cost, another important factor in cloud computing [START_REF] Helff | Interactive Multi-Objective Query Optimization in Mobile-Cloud Database Environments based on a Weighted Sum Model[END_REF][START_REF] Karampaglis | A Bi-objective cost model for database queries in a multi-cloud environment[END_REF][START_REF] Trung | Dynamic Estimation and Grid Partitioning Approach for Multi-objective Optimization Problems in Medical Cloud Federations[END_REF][START_REF] Song | Spark-based Cloud Data Analytics using Multi-Objective Optimization[END_REF] (3) energy consumption, closely related to monetary cost [START_REF] Sathya Sofia | Multi-objective Task Scheduling to Minimize Energy Consumption and Makespan of Cloud Computing Using NSGA-II[END_REF][START_REF] Trummer | An incremental anytime algorithm for multi-objective query optimization[END_REF] (4) result precision,which can be critical in cases where decision making has to happen quickly [START_REF] Agarwal | Blink and it's done: Interactive queries on very large data[END_REF][START_REF] Trummer | Multi-objective parametric query optimization[END_REF]. Multi-objective query (MOQO) and resource optimization have been the basis of numerous research works, which will be analysed in the following sections. Most of of these works are based on IaaS platforms where decision making on resources complicates optimization problems.

...To Serverless Computing

As FaaS built on some of the cloud's existing advantages, the same optimization problems occur there, offering new opportunities to benefit from when solving them:

Even more cost, energy savings By using a FaaS platform to solve MOO problems, users will pay less in many cases, due to its event-driven charging policy. In the same manner, cloud providers will save energy by not sustaining idle resources and will also have economic benefits.

Handling of massively parallel tasks Massively parallel applications are a good fit for serverless platforms [START_REF] Hellerstein | Serverless Computing: One Step Forward, Two Steps Back[END_REF], as they exploit their autoscaling feature, and requests need not communicate with each other. When considering data management and querying in the cloud, data-intensive database queries requiring processing over a distributed data set can be a good serverless fit, as their tasks can be parellelized and almost no data shipping between serverless functions will be required.

Response to interactive analytics Serverless has also proven to be a good fit for other data-intensive applications like interactive analytics, and subsequently is suitable for optimizing interactive queries [START_REF] Müller | Lambada: Interactive data analytics on cold data using serverless cloud infrastructure[END_REF].

However, the aforementioned limitations of serverless mean that the serverless paradigm also comes with significant obstacles concerning MOO in data management scenarios:

Data Shuffling Data shuffling is the most commonly used communication pattern in distributed query processing to transfer data across stages. In serverless computing, functions are stateless and do not communicate. Consequently, intermediate data between stages needs to be stored in persistent storage systems like Amazon S3 [START_REF] Müller | Lambada: Interactive data analytics on cold data using serverless cloud infrastructure[END_REF][START_REF] Perron | Starling: A scalable query engine on cloud function services[END_REF], and accessing it each time comes with significant overhead. Slow data shuffling is a big obstacle for distributed query processing, having a negative impact on query execution time.

Lack of control over resources From a user perspective, the fact that there is zero control over computing resources and task scheduling means that the optimization challenges they offer are also abstracted by the users and rely on FaaS vendors' methods, which makes the need for quality solutions critical.

Short term tasks only Serverless functions have a short lifespan. In AWS Lambda, this limit is 15 minutes [START_REF] Lambda | Amazon Lambda[END_REF]. As a result, they cannot be used for long-running tasks like complex analytical queries, limiting even more the queries that can leverage the serverless paradigm.

Security Issues Security is also an open issue in serverless. Existing platforms present some vulnerabilities due to increased co-residency, as well as higher leak probability because of increased network communication.

Serverless might be gaining ground, however at the moment the areas where FaaS performs better and overcomes traditional, VM-based IaaS are still limited [START_REF] Istemi Ekin Akkus | SAND: Towards highperformance serverless computing[END_REF]. MOQO and resource optimization problems in IaaS have been a hot research topic with numerous contributions.

Techniques and Motivations

Solving MOO problems comes with a set of challenges most of which concern the generation of Pareto optimal solutions. An MOO problem can be efficiently tackled by producing a good number of Pareto optimal solutions which are diverse enough to provide a good coverage of the Pareto front

In order to respond to this challenge, a lot of MOO techniques have been used. Multi-objective optimization methods can be divided into four classes depending on the decision making involved.

No preference methods The goal is to find a relevant set of Pareto optimal solutions providing different trade-offs, and no decision making is involved.

A priori methods The decision maker has provided his/her weighted objectives and then a single solution best satisfying these preferences is returned.

A posteriori methods The two aforementioned techniques are combined, as a representative set of Pareto optimal solutions is first found, and then it is up to the decision maker to select the most suitable for him.

Interactive methods The decision maker iteratively searches for his/her preferred solutions, each time providing the system with information to specify and improve the quality of proposed trade-offs and solutions. It is up to the decision maker to stop the search and pick a solution.

When optimization happens a priori, MOO is usually tackled with a scalarized method, which translates the MOO problem to a SOO problem with Pareto optimal solutions. When decision making happens in the end, an MOO problem is tackled either with a mathematical-programming based method, or with an evolutionary method that involves a genetic algorithm.

Scalarized Methods The most typical scalarized method is linear scalarization, also known as the weighted sum model. With the use of a weighted sum model (WS), a MOO problem is transformed into a single objective one, by distributing a number of preference weights into the objectives [START_REF] Helff | Weighted sum model for multi-objective query optimization for mobile-cloud database environments[END_REF][START_REF] Helff | Interactive Multi-Objective Query Optimization in Mobile-Cloud Database Environments based on a Weighted Sum Model[END_REF][START_REF] Trummer | Approximation schemes for many-objective query optimization[END_REF]. It calculates the optimal plan for a number of weight distributions, and returns a Pareto plan set (PPS). WS can find every point on the Pareto-optimal front for a convex problem, however this is not the case for non-convex problems, where the WS approach can miss some Pareto-optimal points. A slight fixup method to this is the e-constraint method which is similar to the weighted sum, but it repeatedly adds constraints to all but one objective, forcing this way the generation of more diverse solutions [START_REF] Das | A Closer Look at Drawbacks of Minimizing Weighted Sums of Objectives for Pareto Set Generation in Multicriteria Optimization Problems[END_REF].

Mathematical-programming based Methods A common class of a posteriori MOO methods are mathematical programming based ones where an algorithm is implemented and run repeatedly. After each loop, a Pareto optimal solution is produced. This algorithm can be exhaustive [START_REF] Kllapi | Schedule optimization for data processing flows on the cloud[END_REF][START_REF] Trummer | Multi-objective parametric query optimization[END_REF], linear programmingbased [START_REF] Kllapi | Automated management of indexes for dataflow processing engines in IaaS clouds[END_REF], probabilistic [START_REF] Kllapi | Schedule optimization for data processing flows on the cloud[END_REF], greedy [START_REF] Kllapi | Schedule optimization for data processing flows on the cloud[END_REF], or incremental [START_REF] Trummer | An incremental anytime algorithm for multi-objective query optimization[END_REF]. Those algorithms usually solve the multi-objective optimization problem by constructing several scalarizations.

Evolutionary Methods

The other class of a posteriori MOO methods are evolutionary ones, where one run of a genetic algorithm produces a set of Pareto optimal solutions. Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is probably the most popular choice [START_REF] Christoforou | An effective resource management approach in a FaaS environment[END_REF][START_REF] Sathya Sofia | Multi-objective Task Scheduling to Minimize Energy Consumption and Makespan of Cloud Computing Using NSGA-II[END_REF] or basis for new algorithms [START_REF] Trung | Dynamic Estimation and Grid Partitioning Approach for Multi-objective Optimization Problems in Medical Cloud Federations[END_REF][START_REF] Peng | Multi-objective optimization research and applied in cloud computing[END_REF], with interesting alternatives having considered SPEA2 [START_REF] Christoforou | An effective resource management approach in a FaaS environment[END_REF], particle swarm optimization [START_REF] Azimzadeh | Multi-objective job scheduling algorithm in cloud computing based on reliability and time[END_REF], techniques based on simulated annealing [START_REF] Gan Guo-Ning | Genetic simulated annealing algorithm for task scheduling based on cloud computing environment[END_REF], and ant colony optimization [START_REF] Priyanto | Implementation of ant colony optimization algorithm on the project resource scheduling problem[END_REF]. Genetic algorithms are a good fit for tackling MOO problems, as they generate sets of solutions with a parallel search, they can apply techniques like niching in order to ensure the divergence of solutions, and finally the parallelism achieved through evolutionary algorithms' operators can provide a better search speed. However, in some cases the convergence of the algorithm (and consequently the Pareto optimality of the solution set) cannot be guaranteed and measured, and might depend on the initial solutions provided. [START_REF] Michael | A tutorial on multiobjective optimization: fundamentals and evolutionary methods[END_REF].

Most of the works mentioned aim to optimize query execution time alongside monetary cost, however other MOO works aim to reduce energy consumption alongside latency [START_REF] Sathya Sofia | Multi-objective Task Scheduling to Minimize Energy Consumption and Makespan of Cloud Computing Using NSGA-II[END_REF][START_REF] Trummer | An incremental anytime algorithm for multi-objective query optimization[END_REF], and others including result precision in their use case scenarios [START_REF] Trummer | Multi-objective parametric query optimization[END_REF], or having error percentage constraints alongside time constraints [START_REF] Agarwal | Blink and it's done: Interactive queries on very large data[END_REF]. Most works involved two or three objectives, with the exception of some more generic solutions having used up to 9 optimization metrics

The target environment of most research works is IaaS platforms. However, there have also emerged works studying scheduling in FaaS environments [START_REF] Christoforou | An effective resource management approach in a FaaS environment[END_REF][START_REF] Hoseinyfarahabady | A Dynamic Resource Controller for a Lambda Architecture[END_REF], and more are expected to appear in the future, as serverless steadily gains ground in the cloud landscape [START_REF] Trummer | Approximation schemes for many-objective query optimization[END_REF].

Usecases and Applications

In this section, we present some exemplary systems using the presented techniques as well as the use cases that they support:

Weighted Sum Model Normalized Weighted Sum Model (NWSM) [START_REF] Helff | Weighted Sum Model for Multi-Objective Query Optimization for Mobile-Cloud Database Environments[END_REF][START_REF] Helff | Interactive Multi-Objective Query Optimization in Mobile-Cloud Database Environments based on a Weighted Sum Model[END_REF] is a user-interactive MOQO strategy based on a modified weighted sum model and is used to achieve MOO in a mobile-cloud database environment, able to take into account 3 cost objectives: query latency, monetary cost, and mobile device energy consumption. By using NWSA, the user assigns weights of importance to each of the 3 objectives, which are multiplied with the different metric costs to produce the final cost estimation of a QEP. In the end, the QEP with the lowest score is selected and executed. More recently, Kllapi et al. [START_REF] Kllapi | Automated management of indexes for dataflow processing engines in IaaS clouds[END_REF] tackled dataflow optimization with index interleaving algorithms aiming to utilise idle slots in the dataflow execution schedule and build indexes in parallel, without extra delay or cost. In order to include both of the objectives in the optimization process, the weighted sum method is used.

MOO Algorithms Multi-objective parametric query optimization [START_REF] Trummer | Multi-objective parametric query optimization[END_REF] takes a different approach to query optimization, which happens with the use of an exhaustive DP algorithm executing before query runtime, and models queries as functions of parameters. When a query is submitted its parameters are specified, and optimization is completed a posteriori. Real life applications of such technique involve querying cloud databases with a timemoney trade-off. In another work concerning dataflow schedule optimization in the cloud [START_REF] Kllapi | Schedule optimization for data processing flows on the cloud[END_REF], several greedy, probabilistic, and exhaustive optimization algorithms are used to explore the space of alternative schedules, before choosing an optimal one based on a time-money trade-off.

Evolutionary Algorithms Christoforou et al. [START_REF] Christoforou | An effective resource management approach in a FaaS environment[END_REF] proposed a new resource management approach in a FaaS platform, based on intelligent techniques and genetic algorithms. Three different algorithms were used to find a set of near-optimal solutions to the MOO problem, and their performance is compared. In another MOO work aiming to reduce energy consumption and makespan [START_REF] Sathya Sofia | Multi-objective Task Scheduling to Minimize Energy Consumption and Makespan of Cloud Computing Using NSGA-II[END_REF], the DVFS technique is used to reduce energy consumption, which enables VMs to run at different blends of frequencies and voltages. The MOO is solved with the help of NSGA-II for energy consumption and latency. Finally, Artificial Neural Networks were also used in the genetic algorithms optimization procedure to predict the available resources based on task characteristics.

Other An additional contribution, concerning MOQO came from Karampaglis et al. [START_REF] Karampaglis | A Bi-objective cost model for database queries in a multi-cloud environment[END_REF], who introduced the first proposal for a bi-objective query cost model suitable for optimization of queries executed over a multi-cloud environment. It successfully provides estimates of both the expected running time and the monetary cost associated with a query.

OUTLINE

The tutorial will start with a brief introduction covering and comparing cloud and serverless computing platforms, and evaluating optimization problems in such environmental settings. Then, the focus will be shifted to different techniques applied for solving MOO problems in cloud computing, and then use cases and applications using each technique will be presented and discussed, allowing a comparison study to be made with regards to different techniques. Finally, the tutorial will lead to a discussion on MOO problems in a serverless environment, evaluating the opportunities and limitations the serverless paradigm gives for solving them.

GOALS AND OBJECTIVES

The tutorial aims to familiarize the audience with the main MOO challenges the cloud offers, as well as possible techniques to tackle them. The audience will be presented with some successful works on this domain, and their advantages and disadvantages will be evaluated. Finally, the tutorial will encourage a discussion on the future of the cloud with regards to serverless computing.

INTENDED AUDIENCE

The tutorial targets a wide audience. People with only basic knowledge regarding the optimization challenges in a cloud landscape will receive all the necessary feedback to understand the current situation with its challenges and opportunities. More familiar members of the audience will also have the chance to participate as common techniques for solving MOO problems will be discussed. A further discussion about their advantages and disadvantages, alongside ideas about the future of the cloud and serverless will enable even experienced users and researchers to gain a good insight on the topic.

SHORT BIOGRAPHIES

Michail Georgoulakis Misegiannis is a graduate of the School of Electrical and Computer Engineering in the National Technical University of Athens (NTUA). His research interests include query processing, query optimization and cost modeling which were the basis of his diploma thesis. He is also interested in trends and open problems in cloud computing, as well as data management systems for modern hardware.

Verena Kantere is an Assistant Professor at the School of ECE of the NTUA. Before she was a Maître d'Enseignement et de Recherche at the Centre Universitaire d' Informatique of the University of Geneva. Previously, she was a tenure-track junior assistant professor at the Department of Electrical Engineering and Information Technology at the Cyprus University of Technology. She has received a Diploma and a Ph.D. from the NTUA and a M.Sc. from the Department of Computer Science at the University of Toronto. Laurent d'Orazio has been a Professor at Univ Rennes, CNRS, IRISA since 2016. He received his PhD degree in computer science from Grenoble National Polytechnic Institute in 2007. He was an Associate Professor at Blaise Pascal University and LIMOS CNRS, Clermont-Ferrand from 2008 to 2016. His research interests include (big) data algorithms and architectures, distributed and parallel databases.