A SQL-on-Hadoop query consists of a work ow of MapReduce jobs with a single point of con guration. This means that the developer tunes hundreds of tuning parameters directly in the query source code (or via terminal interface), but the system assumes the same conguration to every running job. The lurking problem is that the system allocates computing resources uniformly to every running job, even if they present di erent consumption needs (after all the tuning setup is the same). In this paper, we demonstrate that such uniform allocation of resources drives the query to ine cient performance. We claim that applying a non-uniform allocation method to de ne a customized tuning setup for each job can outperform the uniform allocation. Ultimately, we demonstrate that searching for speci c tuning setup is an optimization problem with polynomial cost.
Ever since the proliferation of SQL-on-Hadoop engines [
However, tuning SQL-on-Hadoop queries is more complex than tuning MapReduce jobs, because queries span a work ow of jobs with a single point of con guration (i.e., the tuning setup is set in the query source code or via command line). In practice, developers tune the physical resources to be allocated by the query and the query processing engine propagates such set of physical resources to all jobs in the query plan with potential ine cient performance (see Section 4).
In traditional SQL processing, a query plan indicates the execution ow for the query operators. SQL-on-Hadoop processing is no di erent, but in the dis
trsee 680000 am 400 r 200 a p 0 #
0 10 20 30
tributed environment of MapReduce systems every job of a query plan
implements a di erent set of query operators with di erent resource consumption
needs [
Contribution. In order to avoid such propagation of tuning setup, we propose a novel resource allocation method that assigns a speci c tuning setup for each job in the query plan. We formulate the searching for speci c tuning setup as a combinatorial optimization problem, highlight its special structure, and show that some special properties preserve the computational e ciency for a particular input of this problem. We also present the shortcoming of tuning SQL-on-Hadoop queries with the current MapReduce tuning advisers and how these queries can achieve better performance when employing our method.
Structure. Section 2 presents the notations and de nitions required for presenting the problem. Section 3 presents the problem of tuning SQL-on-Hadoop queries. Section 4 presents the current tuning allocation method and its impact on SQL-on-Hadoop queries. Section 5 presents our method. Section 6 concludes. 2
Let us de ne a query plan as a directed acyclic graph G = (V; E), where the set of vertices V represents the MapReduce jobs, and the set of edges E denotes the precedence between two jobs. More precisely, a vertex (job) j 2 V is a tuple of the form j = (Oj ; Tj ; Cj ) in which Oj is the set of physical query operators it executes, Tj is the set of associated input tables that are read and processed by j, and Cj is the set of con gurations used to allocate resources. In this set each c 2 C represents a con guration exposed by the SQL-on-Hadoop system that allocates resources to jobs. Each directed edge is an ordered pair of vertices e = (i; j) 2 E that connects the jobs i to j, when the execution of i directly precedes j.
Figure 2 illustrates the query plans compiled for TPC-H query 7, in version
0.13.1 and 3.1.0 of Apache Hive to reinforce the growing complexity of
SQL-on(a) Query plan compiled by Hive 0.13.1.
v3
v2
v5
v4
v1
v6
v7
v11
v10
v9
Hadoop queries. Note that the number of MapReduce jobs in each query plan
di ers considerably across software releases due to the development of di erent
optimization techniques and the addition of new query operators. Although our
example sticks to the Apache Hive terminology other SQL-on-Hadoop systems
like Spark [
In SQL-on-Hadoop systems, the task of allocating physical resources through tuning setups mainly comprises two steps: (1) searching for the most e cient tuning setup for a job j 2 V , and (2) allocating the found tuning setup to the same job j. We de ne the most e cient tuning setup as the con guration that drives the query to decrease response time or minimize resource usage.
Searching for the most e cient tuning setup is a task performed by Tuning
Advisers. The common approach is to pro le the query execution and, then,
to employ heuristics such as Genetic Algorithm [
However, allocating the found tuning setup remains a problem due to the single point of con guration of SQL-on-Hadoop queries. We propose to replace the single point of con guration of queries, exposed to developers, by an automated tuning system able to allocate speci c tuning setup per job. Thus, we de ne the task of allocating tuning setups Cj for each job j 2 V in a query plan G as the problem of assigning the most e cient tuning setup found by the adviser function f (j).
In De nition 2, we formulate the tuning allocation as a combinatorial optimization problem, and use this perspective to develop the reasoning about how to improve the current allocation of con gurations to jobs for a query plan. For the problem de nition, suppose that we have a computable function : C V ! R, where (Ci; j) determines the computational cost of execute a job j with a tuning setup Ci. We de ne the problem of assigning the most e cient tuning setup, as follows: De nition 2 (Tuning Allocation Problem). Given a directed acyclic graph G = (V; E) representing a query plan, a set C of possible con gurations, and a cost function : C V ! R. Find an assignment of tuning setups such that the total cost to process all jobs is minimum, that is, the summation X X j2V Ci2C (Ci; j) is minimum.
Next, we present the current approach employed by SQL-on-Hadoop systems to assign tuning setups to jobs. In Section 5, we present our approach to assign tuning setups to jobs. 4
The methodology employed by the current SQL-on-Hadoop engines allocates the same physical resources to all jobs of a query plan. We name this methodology as the Uniform Tuning method, and we treat it as a shortcoming for the query plan. We de ne the Uniform Tuning method as follows: De nition 3 (Uniform Tuning). The Uniform Tuning is the assignment of con gurations to jobs such that Cu = Cv for any u; v 2 V and Cu; Cv 2 C.
Despite the adviser function f (j) always nd the most e cient tuning setup Cj for every job j 2 V , in the case where only one tuning setup Cj is replicate to all jobs in V (according to De nition 3), Cj may negatively a ect the query's performance, as we observe in Figure 3. The uniform tuning problem becomes more severe because SQL-on-Hadoop systems delegate to developers the responsibility to chose one of the available tuning setups Cj to be replicated.
The Fig. 3 illustrates that the Uniform Tuning drives the query processing
to ine cient performance in practice through experiments in the Amazon
Elastic MapReduce (EMR) cloud environment. We used Star sh [
20 ) % ( p d0 u e e p S 20 20 ) % ( p d0 u e e p S 20 -1 -2 -3 -4 -5 -6 g g g g g g inn inn inn inn inn inn uT uT uT uT uT uT (a) Query 2. :2786 :2791 :1003 :1378 :1266 7 2 : 1 -1 -2 -3 -4 -5 -6 g g g g g g inn inn inn inn inn inn uT uT uT uT uT uT (e) Query 7.
0 20 100
0 100 200 The experiments ran with 6 machines (type c5.2xlarge: 8 of CPU and 16GB of RAM, 100GB of SSD disks). Each runtime is an average of 3 executions.
The x-axis represent the available tuning setups, where tuning-j represents the given Cj generated for a job j. Each Cj was applied uniformly to the query plan, following De nition 3. The y-axis represents the speedups when the execution of the query under the tuning-j is compared to the execution of the default con guration. The default con guration is the con guration bundled with the SQL-on-Hadoop system and is our baseline. According to De nition 3, each tuning setup allocates a di erent set of resources uniformly to the query, consequently, producing a di erent outcome. Note that in all queries the performance degrades due to the presence of the uniform allocation of resources, as expected.
We claim that applying a non-uniform allocation method to de ne a customized tuning setup for each job can outperform the current alternative (uniform tuning), which consists of choosing arbitrarily a tuning setup C0 and replicate it to all jobs. Therefore, our contribution is a non-uniform allocation method that allows SQL-on-Hadoop systems to apply speci c tuning setup per job.
For a query plan G = (V; E), every job implements a di erent set of SQL
operators, i.e., for every job u; v 2 V we have Ou 6= Ov. Consequently, we assume that
each job presents di erent resource consumption needs [
The following integer linear programming model describes the optimal solution for the Tuning Allocation Problem. We de ne the binary decision variable xij 2 f0; 1g to indicate whether a tuning setup Ci 2 C is assigned to a job j 2 V . Let the coe cient cij = (Ci; j) be the computational cost for executing a job j with the tuning setup Ci.
X X The objective function (1) minimizes the computational cost in processing all the jobs for a given query plan. Constraints in (2) ensure that exactly one tuning setup is assigned to a vertex. Reciprocally, the equality in (3) says that only one vertex j 2 V can choose a tuning setup Ci 2 C. Finally, the constraints in (4) preserve the decision variable's integrality.
Claim 1. The Non-Uniform Tuning method can nd the optimal solution for the Tuning Allocation Problem in polynomial time.
The program in (1)-(4) describes precisely the model of an well known combinatorial optimization problem called Assignment Problem. For clarity of exposition, we present a procedure to transform an instance hG = (V; E); Ci of the Tuning Allocation Problem into an instance hG0 = (V 0; E0)i of the original Assignment Problem as follows. Let G0 be a undirected graph such that we create a new vertex i associated to each set Ci 2 C. Also add a copy of each j 2 V and de ne U as the set of all i added to G0 in this way we have V 0 = U [ V with U and V disjoint. Now, we add an edge fi; jg between every vertex i 2 U and j 2 V . The cost of assigning a tuning setup Ci to job j is cij and can be interpreted as an weight on the edge fi; jg 2 E0. Notice that all edges (1) (2) (3) (4) in E0 go between U and V . This implies that G0 (the input of the Assignment Problem) is a complete bipartite graph.
Even though the Assignment Problem problem is known to be NP-hard,
an optimal solution can be obtained e ciently (within execution time bounded
by a polynomial function) when the input graph is bipartite [
An important observation about the Tuning Allocation Problem is that if we drop the constraints (3) of the linear model, the solution remains feasible for the problem. It means that we can attribute a con guration Ci to more than one job (otherwise, the uniform tuning method would not be feasible). Therefore, the natural formulation for this problem is a relaxation for the Assignment Problem. Actually, the resulting integer linear program can be rewritten as follows:
Fortunately, the coe cient matrix does not change, and we still have an incidence matrix of a bipartite graph. In this way, the matrix of coe cients of the problem maintains the total unimodularity. Consequently, the Tuning Allocation Problem also can be solved in polynomial time.
Claim 2. For a query plan G = (V; E), in worst case, the non-uniform method is equal to the uniform method, otherwise the non-uniform method performs better.
Let the tuning setup C0 be the one assigned to all jobs j 2 V of the query plan G using the uniform tuning. Now, consider the case with non-uniform tuning in which for the same query plan G, the most e cient tuning for every job j can be obtained by calling interactively the function f (j) (see De nition 1). Directly from de nition of the adviser function f (j), we have the following inequality (f (j); j) (C0; j) (5) for every job j 2 V . The inequality says that, in the best case for the uniform tuning, the arbitrary tuning setup C0 can be the most e cient for j, but there are no guarantees that it will happen. While attributing a tuning setup Ci chosen by the function f (j), we know that it is always the most suitable tuning setup for j. Consequently, the total cost required to execute all jobs j 2 V of the query plan G using the non-uniform method, can be written, as the following summation:
X (f (j); j):
So, from the inequality (5) we can compare the total costs of the two methods, as follows:
X (f (j); j) i.e., the computational cost for executing the query plan G using the non-uniform assignment method is at most equals to the cost for the uniform method.
The advantage of using the uniform tuning method is that it is simple and straightforward, i.e., the SQL-on-Hadoop engine just replicates the chosen tuning setup. On the other hand, there are no guarantees that the chosen tuning setup will perform well during the query's execution. In this sense, our proposal of non-uniform tuning personalizes the tuning setup for each job and the optimal assignment of tuning setups is guaranteed. In other words, the Tuning allocation Problem can be solved optimally with the non-uniform tuning method and Claim 1 shows that it can be done in polynomial time. Furthermore, a direct consequence of the non-uniform tuning method is the improvement in the performance of the query plan, as stated in Claim 2. 6
In this paper we presented the shortcoming of MapReduce tuning advisers when applied to SQL-on-Hadoop systems due to the uniform allocation of physical resources and its consequences on query's performance. After, we modeled the Tuning Allocation Problem in order to solve the uniform allocation of physical resources. We presented our Non-Uniform Tuning method and proved that it allows assigning optimal tuning setups to SQL-on-Hadoop queries. We also proved that the optimal set of tuning setups required by a query can be found in polynomial time. For future work, an interesting direction consists of combining multiple tuning advisers to optimize one single query, once di erent tuning advisers focus on di erent query operators with di erent resource usage. Acknowledgement: This study was nanced in part by the Coordenac~ao de Aperfeicoamento de Pessoal de N vel Superior - Brasil (CAPES) - Finance Code 001.