# Efficient ELM-Based Two Stages Query Processing Optimization for Big Data

Authors: Linlin Ding; Yu Liu; Baoyan Song; Junchang Xin
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

MapReduce and its variants have emerged as viable competitors
for big data analysis with a commodity cluster of machines. As an
extension of MapReduce, ComMapReduce realizes the lightweight communication
mechanisms to enhance the performance of query processing
applications for big data. However, different communication strategies of
ComMapReduce can substantially affect the executions of query processing
applications. Although there is already the research work that can identify
the communication strategies of ComMapReduce according to the
characteristics of the query processing applications, some drawbacks still
exist, such as relative simple model, too much user participation, and relative
simple query processing execution. Therefore, an efficient ELM-based
two stages query processing optimization model is proposed in this paper,
named ELM to ELM (E2E) model. Then, we develop an efficient sample
training strategy to train our E2E model. Furthermore, two query processing
executions based on the E2E model, respectively, Just-in-Time execution
and Queue execution, are presented. Finally, extensive experiments are
conducted to verify the effectiveness and efficiency of the E2E model.


---

## Body

## 1. Introduction

Nowadays, MapReduce [1] has become a widespread programming framework for big data analysis. Hadoop (http://hadoop.apache.org/) is a popular open-source implementation of MapReduce that many academies and industrial organizations adopt it in research and production deployments. The success of MapReduce stems from hiding the details of parallelization, fault-tolerance, and load balancing in a simple programming framework. MapReduce and its variants are used to process the big data applications, such as Web indexing, data mining, machine learning, financial analysis, scientific simulation, and bioinformatics research [2–10].As one of the successful extensions of MapReduce, ComMapRedcue [3, 4] adds simple lightweight communication mechanisms to generate the certainshared information and implements the query processing applications for big data. In ComMapReduce framework, three basic and two optimization communication strategies are presented to solve the problem of how to communicate and obtain theshared information of different applications. After further analyzing the ComMapReduce execution course and the abundant experiments, we find out that different communication strategies of ComMapReduce can substantially impact the performance of query processing applications.To identify the communication strategy, the existing research work [11] proposes a query optimization model, namedELM_CMR, based on ELM [12] which has the classification performance at an excellent standard. According to the characteristics of query processing programs,ELM_CMR can identify the communication strategy of ComMapReduce. However,ELM_CMR still has the following drawbacks. First, regardless of the MapReduce or ComMapReduce framework, a program only consists of black_box Map and Reduce functions, without knowing the distributed details about the framework. But the configuration parameters of the framework can fully influence the performance of query processing. Finding the most suitable configuration parameters setting itself is difficult. The burden falls on the user who submits the MapReduce or ComMapReduce job to specify settings for all configuration parameters, which highlights the challenges the user faces. How to identify the proper configuration parameters according to the user program is a difficult problem. Second, the implementation algorithm of multiple queries inELM_CMR only processes the queries based on the classification results and predicted execution time, but there is no consideration of the characteristics among different queries. Different queries can share computation and data so as to enhance the performance further. Third,ELM_CMR only adopts simple training method to gain the classification model. If more efficient training method is adopted to obtain the training data, the accuracy of the classification model can be improved.Therefore, in this paper, for resolving the above problems and drawbacks, we propose an efficient ELM-based two stages query processing optimization model, named ELM to ELM (E2E) model. According to the characteristics of the users programs, the first stage can gain thefeature parameters using ELM algorithm. After that, according to the results of the first stage, the second stage can identify the final classification result by ELM algorithm too. Furthermore, an efficient sample training strategy is presented to train theE2E model. We also develop two query processing executions based on theE2E model, Just-in-Time execution and Queue execution. The contributions of this paper can be summarized as follows.(i)
We propose an efficient ELM-based two stages query processing optimization model, namedE2E model, which can realize the most optimal executions of query processing applications in MapReduce or ComMapReduce framework.(ii)
We develop a sample training strategy to train ourE2E model and two query executions based onE2E model, Just-in-Time execution, and Queue execution.(iii)
The experimental studies using synthetic data show the effectiveness and efficiency of theE2E model.The remainder of this paper is organized as follows. Section2 briefly introduces the background, containing the ELM andELM_CMR. OurE2E model is proposed in Section 3. The two executions for query processing applications based onE2E are presented in Section 4. The experimental results to show the performance ofE2E model are reported in Section 5. Finally, we conclude this paper in Section 6.


## 2. Background

In this section, we describe the background of our work, which includes a brief overview of the traditional ELM and the detailed descriptions of theELM_CMR.


### 2.1. Review of ELM

Nowadays, extreme learning machine (ELM) [12] and its variants [13–28] have the characteristics of excellent generalization performance, rapid training speed, and little human intervene, which have attracted extensive attention from more and more researchers. ELM is originally designed for the single hidden-layer feedforward neural networks (SLFNs [29]) and is then extended to the “generalized” SLFNs. ELM algorithm first randomly allocates the input weights and hidden layer biases and then analytically computes the output weights of SLFNs. Contrary to the other conventional learning algorithms, ELM reaches the optimal generalization performance at a very fast learning speed. ELM is less sensitive to the user defined parameters, so it can be deployed fast and convenient. That is the reason we choose ELM as our basic method to construct the query processing optimization model.ForN arbitrary distinct samples (xj,tj), where xj=[xj1,xj2,…,xjn]T∈Rn and tj=[tj1,tj2,…,tjm]T∈Rm, standard SLFNs with hidden nodes L and activation function g(x) are mathematically modeled as(1)∑i=1L‍βigixj=∑i=1L‍βigwi·xj+bi=ojj=1,2,…,N,where L is the number of hidden layer nodes, wi=[wi1,wi2,…,win]T is the weight vector between the ith hidden node and the input nodes, βi=[βi1,βi2,…,βim]T is the weight vector connecting the ith hidden node and the output nodes, bi is the threshold of the ith hidden node, and oj=[oj1,oj2,…,ojm]T is the jth output vector of the SLFNs.The standard SLFNs can approximate theseN samples with zero error. The error of ELM is ∑j=1L‍∥oj-tj∥=0 and there exist βi, wi, and bi such that(2)∑i=1L‍βigwi·xj+bi=tjj=1,2,…,N.Equation (2) can be expressed compactly as follows:(3)Hβ=T,where(4)Hw1,w2,…,wL,b1,b2,…,bL,x1,x2,…,xL=hx1hx2⋮hxN=gw1·x1+b1gw2·x1+b2…gwL·x1+bLgw1·x2+b1gw2·x2+b2…gwL·x2+bL⋮⋮⋮⋮gw1·xN+b1gw2·xN+b2…gwL·xN+bLN×L,(5)β=β1Tβ2T⋮βLTL×m,T=t1Tt2T⋮tNTN×m.H is set as the hidden layer output matrix of the neural network. The ith column of H is called the ith hidden node output with respect to inputs x1,x2,…,xN. The smallest norm least-squares solution of the above multiple regression system is shown as follows:(6)β^=H†T,where H† is the Moore-Penrose generalized inverse of matrix H. Then the output function of ELM can be modeled as follows:(7)fx=hxβ=hxH†T.The computational course for ELM is shown in Algorithm1. Only after properly setting the related parameters, ELM can start the training process. The first step is to generate L pairs of hidden node parameters (wi,bi) (Lines 1–3). The second step actually calculates the hidden layer output matrix H by using (4) (Line 4). The third step mainly computes the corresponding output weight vector β (Line 5). After completing the above training process, the output of the new dataset can be predicted by ELM according to (7).Algorithm 1:ELM.
(1)for  i=1 to L  do
(2)  Randomly generate the hidden node parameters (wi, bi);
(3)end for
(4) Calculate the hidden layer output matrixH;
(5) Calculate the output weight vectorβ=H†T;


### 2.2.ELM_CMR Model

ComMapReduce [3, 4] is an improved MapReduce framework with lightweight communication mechanisms. A new node, named the Coordinator node, is added to store and generate the certainshared information of different applications. In ComMapReduce, three basic communication strategies, LCS, ECS, and HCS, and two optimization communication strategies, PreOS and PostOS, are proposed to identify how to receive and generate theshared information. In short, without affecting the existing characteristics of the original MapReduce framework, ComMapReduce is a successful parallel programming framework with globalshared information to filter the unpromising data of query processing programs.The existingELM_CMR [11] is an efficient query processing optimization model based on ELM. It can identify the communication strategies of query processing applications in ComMapReduce according to the features of queries. Figure 1 shows the architecture ofELM_CMR model. The four components ofELM_CMR are, respectively, theFeature Selector, theELM Classifier, theQuery Optimizer, and theExecution Fabric.Figure 1
Architecture ofELM_CMR model.TheFeature Selector mainly examines the training query processing programs and selects the configuration parameters that can wholly affect the query performance by the job profiles. Naturally, the parameters of program p can be divided into three types, parameters that predominantly affect Map task execution; parameters that predominantly affect Reduce task execution; and the cluster parameters. Then, in each cluster, we adopt the minimum-redundancy-maximum-relevance (mRMR) [30] feature selection to find the optimal parameters sharply affecting the performance. And then, we generate the globally optimal configuration parameter settings by combining the results of each subspace. Therefore, the near-optimal configuration parameter setting can be generated.After selecting the features of training data, theFeature Selector sends the extracted training data to theELM Classifier. It uses the training data to construct the ELM model by the traditional ELM algorithm. After that, when there are one or multiple queries to be processed, theELM Classifier can rapidly obtain the classification results of the queries and then sends them to theQuery Optimizer.TheQuery Optimizer applies the classification results of theELM Classifier and combines the implementation patterns to choose an optimizedexecution order. After gaining theexecution order, the query is sent to theExecution Fabric.TheExecution Fabric implements the program in ComMapReduce framework. When there is one query to be processed, theExecution Fabric implements the query according to the classification result of theQuery Optimizer inELM_CMR. When there are multiple queries to be processed, the multiple queries can be classified byELM Classifier and gain the best communication strategy of each program. Then, a Task Scheduler Simulator is used to simulate the execution time of queries. According to the execution time and the classification results of the queries, theQuery Optimizer designs anexecution order following the common principle of Shortest Job First (SJF) to implement multiple queries.


## 2.1. Review of ELM

Nowadays, extreme learning machine (ELM) [12] and its variants [13–28] have the characteristics of excellent generalization performance, rapid training speed, and little human intervene, which have attracted extensive attention from more and more researchers. ELM is originally designed for the single hidden-layer feedforward neural networks (SLFNs [29]) and is then extended to the “generalized” SLFNs. ELM algorithm first randomly allocates the input weights and hidden layer biases and then analytically computes the output weights of SLFNs. Contrary to the other conventional learning algorithms, ELM reaches the optimal generalization performance at a very fast learning speed. ELM is less sensitive to the user defined parameters, so it can be deployed fast and convenient. That is the reason we choose ELM as our basic method to construct the query processing optimization model.ForN arbitrary distinct samples (xj,tj), where xj=[xj1,xj2,…,xjn]T∈Rn and tj=[tj1,tj2,…,tjm]T∈Rm, standard SLFNs with hidden nodes L and activation function g(x) are mathematically modeled as(1)∑i=1L‍βigixj=∑i=1L‍βigwi·xj+bi=ojj=1,2,…,N,where L is the number of hidden layer nodes, wi=[wi1,wi2,…,win]T is the weight vector between the ith hidden node and the input nodes, βi=[βi1,βi2,…,βim]T is the weight vector connecting the ith hidden node and the output nodes, bi is the threshold of the ith hidden node, and oj=[oj1,oj2,…,ojm]T is the jth output vector of the SLFNs.The standard SLFNs can approximate theseN samples with zero error. The error of ELM is ∑j=1L‍∥oj-tj∥=0 and there exist βi, wi, and bi such that(2)∑i=1L‍βigwi·xj+bi=tjj=1,2,…,N.Equation (2) can be expressed compactly as follows:(3)Hβ=T,where(4)Hw1,w2,…,wL,b1,b2,…,bL,x1,x2,…,xL=hx1hx2⋮hxN=gw1·x1+b1gw2·x1+b2…gwL·x1+bLgw1·x2+b1gw2·x2+b2…gwL·x2+bL⋮⋮⋮⋮gw1·xN+b1gw2·xN+b2…gwL·xN+bLN×L,(5)β=β1Tβ2T⋮βLTL×m,T=t1Tt2T⋮tNTN×m.H is set as the hidden layer output matrix of the neural network. The ith column of H is called the ith hidden node output with respect to inputs x1,x2,…,xN. The smallest norm least-squares solution of the above multiple regression system is shown as follows:(6)β^=H†T,where H† is the Moore-Penrose generalized inverse of matrix H. Then the output function of ELM can be modeled as follows:(7)fx=hxβ=hxH†T.The computational course for ELM is shown in Algorithm1. Only after properly setting the related parameters, ELM can start the training process. The first step is to generate L pairs of hidden node parameters (wi,bi) (Lines 1–3). The second step actually calculates the hidden layer output matrix H by using (4) (Line 4). The third step mainly computes the corresponding output weight vector β (Line 5). After completing the above training process, the output of the new dataset can be predicted by ELM according to (7).Algorithm 1:ELM.
(1)for  i=1 to L  do
(2)  Randomly generate the hidden node parameters (wi, bi);
(3)end for
(4) Calculate the hidden layer output matrixH;
(5) Calculate the output weight vectorβ=H†T;


## 2.2.ELM_CMR Model

ComMapReduce [3, 4] is an improved MapReduce framework with lightweight communication mechanisms. A new node, named the Coordinator node, is added to store and generate the certainshared information of different applications. In ComMapReduce, three basic communication strategies, LCS, ECS, and HCS, and two optimization communication strategies, PreOS and PostOS, are proposed to identify how to receive and generate theshared information. In short, without affecting the existing characteristics of the original MapReduce framework, ComMapReduce is a successful parallel programming framework with globalshared information to filter the unpromising data of query processing programs.The existingELM_CMR [11] is an efficient query processing optimization model based on ELM. It can identify the communication strategies of query processing applications in ComMapReduce according to the features of queries. Figure 1 shows the architecture ofELM_CMR model. The four components ofELM_CMR are, respectively, theFeature Selector, theELM Classifier, theQuery Optimizer, and theExecution Fabric.Figure 1
Architecture ofELM_CMR model.TheFeature Selector mainly examines the training query processing programs and selects the configuration parameters that can wholly affect the query performance by the job profiles. Naturally, the parameters of program p can be divided into three types, parameters that predominantly affect Map task execution; parameters that predominantly affect Reduce task execution; and the cluster parameters. Then, in each cluster, we adopt the minimum-redundancy-maximum-relevance (mRMR) [30] feature selection to find the optimal parameters sharply affecting the performance. And then, we generate the globally optimal configuration parameter settings by combining the results of each subspace. Therefore, the near-optimal configuration parameter setting can be generated.After selecting the features of training data, theFeature Selector sends the extracted training data to theELM Classifier. It uses the training data to construct the ELM model by the traditional ELM algorithm. After that, when there are one or multiple queries to be processed, theELM Classifier can rapidly obtain the classification results of the queries and then sends them to theQuery Optimizer.TheQuery Optimizer applies the classification results of theELM Classifier and combines the implementation patterns to choose an optimizedexecution order. After gaining theexecution order, the query is sent to theExecution Fabric.TheExecution Fabric implements the program in ComMapReduce framework. When there is one query to be processed, theExecution Fabric implements the query according to the classification result of theQuery Optimizer inELM_CMR. When there are multiple queries to be processed, the multiple queries can be classified byELM Classifier and gain the best communication strategy of each program. Then, a Task Scheduler Simulator is used to simulate the execution time of queries. According to the execution time and the classification results of the queries, theQuery Optimizer designs anexecution order following the common principle of Shortest Job First (SJF) to implement multiple queries.


## 3.E2E Model

In this section, the overview of ourE2E model is introduced first in Section 3.1. Then, training theE2E model is shown in Section 3.2. Finally, predicting theE2E model is proposed in Section 3.3.


### 3.1. Overview ofE2E Model

OurE2E model can identify the optimal communication strategies of query processing programs in MapReduce or ComMapReduce, which contains three main phases, respectively, thetraining phase, theprediction phase, and theexecution phase. Figure 2 shows the whole workflow of query processing in theE2E model. The main workflow is as follows.Figure 2
Workflow ofE2E model.First, thetraining phase is responsible for extracting the training query processing programs that have a large effect on theE2E model. In thetraining phase, we use sample-based training strategies to run our workload, in isolation, pairwise, and at several higher multiprogramming levels. After gaining the training samples, they can be used to generate theE2E model in theprediction phase. The details of training phase will be introduced in Section 3.2.Second, in theprediction phase, by using the training samples from thetraining phase, the two stagesE2E model can be generated based on the traditional ELM algorithm. According to the user’s programs, the first stage can obtain the most optimalfeature parameters of the programs by ELM. And then, using thefeature parameters of the first stage, the second stage can identify the classification results of the query processing programs by ELM. The details of theprediction phase will be shown in Section 3.3.Third, after gaining theE2E model, for the query processing programs submitted to MapReduce or ComMapReduce, we can predict their optimal communication strategies in theexecution phase. We propose two query executions based onE2E model, the Just-in-Time execution which tackles one query processing program, and the Queue execution which tackles multiple concurrent queries. The details of the execution phase will be illustrated in Section 4.


### 3.2. TrainingE2E Model

To obtain the prediction model more accurately, we need to train theE2E model. Different from the simple training course ofELM_CMR model, thetraining phase of ourE2E model consists of running the queries in isolation, pairwise as well as at several higher multiprogramming levels. In addition, in order to gain the measurements that capture the interactions, we omit the first few samples in our experiments. This approach makes us ignore the overhead of the initial query setup and caching the initial supporting structures.TheE2E model realizes thetraining phase by sampling approach, containing isolation, pairwise, and higher degree of concurrency, which allows us to approximate the running of queries in MapReduce or ComMapReduce. The course of thetraining phase is displayed in Figure 2. First, we sample the workload in isolation to gain how each query behaves, which can be seen as the baseline of training. Second, according to the query types in our experiments, we build a matrix of interaction by running all unique pairwise combinations. Pairwise sample can help us to simply estimate the degree of concurrency. Here, Latin hypercube sampling approach (LHS) can uniformly distribute our samples throughout our prediction space, which can be realized by creating a hypercube with the same dimension as the multiprogramming level. We adopt LHS to sample at pairwise or several higher multiprogramming levels. We then select the samples that every value on every plane gets inter selected exactly one. A simple example of two-dimensional LHS is shown in Table 1. In Table 1, Query-A, Query-B, Query-C, and Query-D stand for four queries to be processed by pairwise combinations. After combining using LHS, the four queries can obtain the optimal combinations.Table 1
An example of LHS.
Query
Query-A
Query-B
Query-C
Query-D
Query-A
▲
Query-B
▲
Query-C
▲
Query-D
▲Furthermore, the above strategy shows how to run the samples, in isolation, pairwise, and at several higher multiprogramming levels using LHS. As we know, the number of queries to be processed is large, and in order to enhance the training accuracy, we need to choose the queries that is the representative queries in each query type and then construct the samples to be trained. The corresponding cluster algorithms based on DBSCAN [31] can be also adopted to gain the most representative query in each query type. In practice, although the training time ofE2E may be long, it is worth mentioning thattraining phase allows our model to be extremely lightweight once it reaches theprediction phase and enhance the accuracy.


### 3.3. PredictingE2E Model

Then, we introduce the details of theprediction phase. A MapReduce job j can be expressed by a MapReduce program p running on input data d and cluster r, which can be expressed as j=p,d,r,c in short. We call the d, r, and c thefeature parameters ofp. The users only submit their jobs to MapReduce or ComMapReduce without knowing the internal configuration details of the system.However, a number of choices can be made in order to fully specify how the job should be executed. These choices, represented byc in q,d,r,c, stand for a high dimensional space of configuration parameter settings, such as the number of Map and Reduce task, the block size, and the amount of memory. The performance changes a lot in different configuration parameters. For any parameter, its value is not specified explicitly during job submission, the default values either shipped with the system or specified by the system administrator. However, the normal users do not understand the running details of MapReduce. That is to say, finding good configuration settings for MapReduce job is time consuming and requires extensive knowledge of system internals. Because the users have little information of the parallelization details of MapReduce, it is necessary to gain the suitable configuration parameters. The first stage of ourE2E model is to generate the model for identifying the suitable configuration parameters of query processing programs by ELM. The main goal of the first stage is to construct a black_boxfeature parameters of queries, containing d,r,c. The configuration parameters wholly affecting the performance adopted byE2E are the same as ourELM_CMR approach as shown in Table 2. The corresponding information of the job can be obtained from sampling a few tasks of the job. After the first stage, thefeature parameters setting can be obtained by ELM algorithm. After gaining the configuration parameters, the second stage is to use them to predict the communication strategy of ComMapReduce or MapReduce by ELM algorithm too and then generates the classification results. This stage is similar to the prediction ofELM_CMR, so we do not illustrate in detail in this section.Table 2
Feature parameters in the experiments.
Property name
Type
Default value
io.sort.mb
int
100
io.sort.factor
int
10
min.num.spills.for.combine
int
3
mapred.compress.map.output
boolean
false
mapred.reduce.parallel.copies
int
5
mapred.reduce.copy.backoff
int
300
dfs.heartbeat.interval
int
3
dfs.block.size (M)
int
64
mapred.map.task
int
4
mapred.reduce.task
int
4
mapred.tasktracker.map.task.maximum
int
4
mapred.tasktracker.reduce.task.maximum
int
4
Data size (G)
int
10
Data distribution
boolean
uniform
Number of slave nods
int
8


## 3.1. Overview ofE2E Model

OurE2E model can identify the optimal communication strategies of query processing programs in MapReduce or ComMapReduce, which contains three main phases, respectively, thetraining phase, theprediction phase, and theexecution phase. Figure 2 shows the whole workflow of query processing in theE2E model. The main workflow is as follows.Figure 2
Workflow ofE2E model.First, thetraining phase is responsible for extracting the training query processing programs that have a large effect on theE2E model. In thetraining phase, we use sample-based training strategies to run our workload, in isolation, pairwise, and at several higher multiprogramming levels. After gaining the training samples, they can be used to generate theE2E model in theprediction phase. The details of training phase will be introduced in Section 3.2.Second, in theprediction phase, by using the training samples from thetraining phase, the two stagesE2E model can be generated based on the traditional ELM algorithm. According to the user’s programs, the first stage can obtain the most optimalfeature parameters of the programs by ELM. And then, using thefeature parameters of the first stage, the second stage can identify the classification results of the query processing programs by ELM. The details of theprediction phase will be shown in Section 3.3.Third, after gaining theE2E model, for the query processing programs submitted to MapReduce or ComMapReduce, we can predict their optimal communication strategies in theexecution phase. We propose two query executions based onE2E model, the Just-in-Time execution which tackles one query processing program, and the Queue execution which tackles multiple concurrent queries. The details of the execution phase will be illustrated in Section 4.


## 3.2. TrainingE2E Model

To obtain the prediction model more accurately, we need to train theE2E model. Different from the simple training course ofELM_CMR model, thetraining phase of ourE2E model consists of running the queries in isolation, pairwise as well as at several higher multiprogramming levels. In addition, in order to gain the measurements that capture the interactions, we omit the first few samples in our experiments. This approach makes us ignore the overhead of the initial query setup and caching the initial supporting structures.TheE2E model realizes thetraining phase by sampling approach, containing isolation, pairwise, and higher degree of concurrency, which allows us to approximate the running of queries in MapReduce or ComMapReduce. The course of thetraining phase is displayed in Figure 2. First, we sample the workload in isolation to gain how each query behaves, which can be seen as the baseline of training. Second, according to the query types in our experiments, we build a matrix of interaction by running all unique pairwise combinations. Pairwise sample can help us to simply estimate the degree of concurrency. Here, Latin hypercube sampling approach (LHS) can uniformly distribute our samples throughout our prediction space, which can be realized by creating a hypercube with the same dimension as the multiprogramming level. We adopt LHS to sample at pairwise or several higher multiprogramming levels. We then select the samples that every value on every plane gets inter selected exactly one. A simple example of two-dimensional LHS is shown in Table 1. In Table 1, Query-A, Query-B, Query-C, and Query-D stand for four queries to be processed by pairwise combinations. After combining using LHS, the four queries can obtain the optimal combinations.Table 1
An example of LHS.
Query
Query-A
Query-B
Query-C
Query-D
Query-A
▲
Query-B
▲
Query-C
▲
Query-D
▲Furthermore, the above strategy shows how to run the samples, in isolation, pairwise, and at several higher multiprogramming levels using LHS. As we know, the number of queries to be processed is large, and in order to enhance the training accuracy, we need to choose the queries that is the representative queries in each query type and then construct the samples to be trained. The corresponding cluster algorithms based on DBSCAN [31] can be also adopted to gain the most representative query in each query type. In practice, although the training time ofE2E may be long, it is worth mentioning thattraining phase allows our model to be extremely lightweight once it reaches theprediction phase and enhance the accuracy.


## 3.3. PredictingE2E Model

Then, we introduce the details of theprediction phase. A MapReduce job j can be expressed by a MapReduce program p running on input data d and cluster r, which can be expressed as j=p,d,r,c in short. We call the d, r, and c thefeature parameters ofp. The users only submit their jobs to MapReduce or ComMapReduce without knowing the internal configuration details of the system.However, a number of choices can be made in order to fully specify how the job should be executed. These choices, represented byc in q,d,r,c, stand for a high dimensional space of configuration parameter settings, such as the number of Map and Reduce task, the block size, and the amount of memory. The performance changes a lot in different configuration parameters. For any parameter, its value is not specified explicitly during job submission, the default values either shipped with the system or specified by the system administrator. However, the normal users do not understand the running details of MapReduce. That is to say, finding good configuration settings for MapReduce job is time consuming and requires extensive knowledge of system internals. Because the users have little information of the parallelization details of MapReduce, it is necessary to gain the suitable configuration parameters. The first stage of ourE2E model is to generate the model for identifying the suitable configuration parameters of query processing programs by ELM. The main goal of the first stage is to construct a black_boxfeature parameters of queries, containing d,r,c. The configuration parameters wholly affecting the performance adopted byE2E are the same as ourELM_CMR approach as shown in Table 2. The corresponding information of the job can be obtained from sampling a few tasks of the job. After the first stage, thefeature parameters setting can be obtained by ELM algorithm. After gaining the configuration parameters, the second stage is to use them to predict the communication strategy of ComMapReduce or MapReduce by ELM algorithm too and then generates the classification results. This stage is similar to the prediction ofELM_CMR, so we do not illustrate in detail in this section.Table 2
Feature parameters in the experiments.
Property name
Type
Default value
io.sort.mb
int
100
io.sort.factor
int
10
min.num.spills.for.combine
int
3
mapred.compress.map.output
boolean
false
mapred.reduce.parallel.copies
int
5
mapred.reduce.copy.backoff
int
300
dfs.heartbeat.interval
int
3
dfs.block.size (M)
int
64
mapred.map.task
int
4
mapred.reduce.task
int
4
mapred.tasktracker.map.task.maximum
int
4
mapred.tasktracker.reduce.task.maximum
int
4
Data size (G)
int
10
Data distribution
boolean
uniform
Number of slave nods
int
8


## 4. Executions ofE2E Model

After generating theE2E model, the pending queries can be implemented under ourE2E model. In this section, two scenarios are proposed for executing query processing programs using theE2E model. In the first scenario, one new query is being submitted for immediate execution, named as Just-in-Time execution. In the second scenario, a Queue-based multiple concurrent queries execution is proposed, where an ordered list of queries to run is gained.


### 4.1. Just-in-Time Execution

When there is one new query being submitted, theE2E model generates its classification result as soon as possible. According to the characteristics of the coming query, the first stage ofE2E model can generate thefeature parameters of this query based on ELM. After that, the user can make a decision that whether adopting ComMapReduce or which communication strategy can be adopted by the second stage ofE2E model, and then implements the query processing application.The course of Just-in-Time execution is shown in Algorithm2. First, the most optimalfeature parameters of query processing job j are extracted in the first stage ofE2E model (Line 1). Second, after obtaining thefeature parameters of job j, theE2E generates the classification result of j (Line 2). Third, according to the classification of j, theE2E ensures how to implement the query and sends it to MapReduce or ComMapReduce framework. The framework uses the optimization result to execute the query program (Line 3).Algorithm 2:Just-in-Time execution.
(1) Generate thefeature parameters of j by the first stage of E2E model;
(2) Generate the execution plan ofj by the second stage of E2E model;
(3) Executej with its communication strategy;For example, for a submitted skyline query, the first stage ofE2E can obtain the most optimalfeature parameters of this skyline query. After abstracting itsfeature parameters, theE2E can generate its classification and then identifies the communication strategy of this skyline query, such as PostOS. After that, the skyline query will be implemented in ComMapReduce with PostOS.


### 4.2. Queue Execution

When there are multiple concurrent queries to be processed, we design an efficientexecution order of queries based onE2E model. Under theexecution order, the performance of multiple concurrent queries can reach a nice status. Of course, we can execute these queries one by one with their classification results ofE2E, but a lot of calculations and execution time would be wasted. Therefore, theexecution order is important to enhance the performance of multiple concurrent queries.As we know, different queries usually contain the overlap parts, such as the same query type and the same processing data. Therefore, when processing multiple concurrent queries, if we can identify the correlations of query type and processing data of the multiple queries, then the sharing computation and data can be used to prevent the repeated processing and scanning.The main processing course of Queue execution is shown in Figure3. There are three main components in the Queue execution, respectively, theAnalyzer, theOptimizer, and theExecutor.Figure 3
Workflow of Queue execution.First, for the multiple concurrent queries to be executed, after obtaining the classification results byE2E model, theAnalyzer analyzes the queries and divides the queries into some subsets by considering the share of computation. This dividing approach can divide the queries with the same query type into the same subset, then the queries in a subset can be computed together.Second, in each subset, theOptimizer can design the local execution order according to the characteristics of the sharing computation and data. It can analyze the data being processed of the multiple concurrent queries in the same subset, and then the queries with sharing data can share the computation results of the sharing data. TheOptimizer also can cache the corresponding intermediate results into memory or buffer by the characteristics of the queries so as to reduce the repeated implementations of the same operations and I/O cost. Then, similar to our formerELM_CMR, theOptimizer also uses a Task Scheduler Simulator to simulate the scheduling and executions of Map and Reduce tasks of each query. The execution time of a job j can be estimated by the Task Schedular Simulator. So, according to the common principle of Shortest Job First (SJF) too, theexecution order of each subset is gained.Finally, after obtaining theexecution order of each subset, theExecutor also uses theSJF principle of the subsets by simple merging their execution time of each subset, so the global execution order (O_s) of the multiple queries is the ascending order of the simulated execution time of each subset. Then, the multiple queries can be implemented under the globalexecution order.Algorithm3 illustrates the whole execution course of the multiple concurrent queries. First, we can obtain the classification of each query by theE2E model (Lines 1–3). Then, theAnalyzer divides the queries sharing computation into some subsets (Line 4). Then, in each subset, theOptimizer can analyze and divide the sharing data, and then computes the sharing data. After gaining the simulated time of each query in each subset, the localexecution order is obtained by considering the sharing and features of the queries in each subset bySJF (Lines 5–10). Finally, the globalexecution order of the queries is generated bySJF too (Line 11).Algorithm 3:Multiple queries.
(1)for each query qi  do
(2)  Generate the classification ofqi by E2E;
(3)end for
(4)  Divide the queries into some subsets by query type;
(5)for each subset do
(6)  Analyze and divide the sharing data;
(7)  Compute and query of the sharing data;
(8)  Calculate the simulate execution time;
(9)  Generate the localexecution order of each subset by SJF;
(10)end for
(11)  Generate the globalexecution order by SJF;Figure4 shows an example of the implementation of the multiple concurrent queries. Suppose that there are eight queries to be processed. First, these queries can obtain their classification results byE2E. After that, theAnalyzer divides these queries into four subsets by the sharing of computation, the same query type, respectively, top-k,kNN, skyline, and join.Figure 4
Implementation of multiple queries.In each subset, theOptimizer can make a localexecution order by the features of the queries. For example, the subset of skyline query contains three skyline queries, q2, q5, and q8, with their processing data sets s2={p1,p2,p3,p4,p5,p6}, s5={p1,p2,p3,p7,p8,p9}, and s8={p4,p5,p6,p7,p8,p9}. For these skyline queries, theOptimizer divides the sharing data and gains the following sharing subdatasets, sa={p1,p2,p3}, sb={p4,p5,p6}, and sc={p7,p8,p9}. Then, theOptimizer can transfer the above skyline queries into some simple skyline queries, s2=sa∪sb, s5=sa∪sc, and s8=sb∪sc. So, theOptimizer can make a solution that the skyline queries first compute the results of sa, sb, and sc, and then gain a localexecution order bySJF, q5, q8, and q2. The similar processing course is fit for the top-k andkNN queries. For our join query of small-big tables, theOptimizer can cache the corresponding small table into memory of Map tasks so as to reduce the repeated scan of the small table. Finally, the globalexecution orderOs, q7, q1, q5, q8, q2, q3, q4, and q6 can be gained by simple merge ofSJF of the four subsets.


## 4.1. Just-in-Time Execution

When there is one new query being submitted, theE2E model generates its classification result as soon as possible. According to the characteristics of the coming query, the first stage ofE2E model can generate thefeature parameters of this query based on ELM. After that, the user can make a decision that whether adopting ComMapReduce or which communication strategy can be adopted by the second stage ofE2E model, and then implements the query processing application.The course of Just-in-Time execution is shown in Algorithm2. First, the most optimalfeature parameters of query processing job j are extracted in the first stage ofE2E model (Line 1). Second, after obtaining thefeature parameters of job j, theE2E generates the classification result of j (Line 2). Third, according to the classification of j, theE2E ensures how to implement the query and sends it to MapReduce or ComMapReduce framework. The framework uses the optimization result to execute the query program (Line 3).Algorithm 2:Just-in-Time execution.
(1) Generate thefeature parameters of j by the first stage of E2E model;
(2) Generate the execution plan ofj by the second stage of E2E model;
(3) Executej with its communication strategy;For example, for a submitted skyline query, the first stage ofE2E can obtain the most optimalfeature parameters of this skyline query. After abstracting itsfeature parameters, theE2E can generate its classification and then identifies the communication strategy of this skyline query, such as PostOS. After that, the skyline query will be implemented in ComMapReduce with PostOS.


## 4.2. Queue Execution

When there are multiple concurrent queries to be processed, we design an efficientexecution order of queries based onE2E model. Under theexecution order, the performance of multiple concurrent queries can reach a nice status. Of course, we can execute these queries one by one with their classification results ofE2E, but a lot of calculations and execution time would be wasted. Therefore, theexecution order is important to enhance the performance of multiple concurrent queries.As we know, different queries usually contain the overlap parts, such as the same query type and the same processing data. Therefore, when processing multiple concurrent queries, if we can identify the correlations of query type and processing data of the multiple queries, then the sharing computation and data can be used to prevent the repeated processing and scanning.The main processing course of Queue execution is shown in Figure3. There are three main components in the Queue execution, respectively, theAnalyzer, theOptimizer, and theExecutor.Figure 3
Workflow of Queue execution.First, for the multiple concurrent queries to be executed, after obtaining the classification results byE2E model, theAnalyzer analyzes the queries and divides the queries into some subsets by considering the share of computation. This dividing approach can divide the queries with the same query type into the same subset, then the queries in a subset can be computed together.Second, in each subset, theOptimizer can design the local execution order according to the characteristics of the sharing computation and data. It can analyze the data being processed of the multiple concurrent queries in the same subset, and then the queries with sharing data can share the computation results of the sharing data. TheOptimizer also can cache the corresponding intermediate results into memory or buffer by the characteristics of the queries so as to reduce the repeated implementations of the same operations and I/O cost. Then, similar to our formerELM_CMR, theOptimizer also uses a Task Scheduler Simulator to simulate the scheduling and executions of Map and Reduce tasks of each query. The execution time of a job j can be estimated by the Task Schedular Simulator. So, according to the common principle of Shortest Job First (SJF) too, theexecution order of each subset is gained.Finally, after obtaining theexecution order of each subset, theExecutor also uses theSJF principle of the subsets by simple merging their execution time of each subset, so the global execution order (O_s) of the multiple queries is the ascending order of the simulated execution time of each subset. Then, the multiple queries can be implemented under the globalexecution order.Algorithm3 illustrates the whole execution course of the multiple concurrent queries. First, we can obtain the classification of each query by theE2E model (Lines 1–3). Then, theAnalyzer divides the queries sharing computation into some subsets (Line 4). Then, in each subset, theOptimizer can analyze and divide the sharing data, and then computes the sharing data. After gaining the simulated time of each query in each subset, the localexecution order is obtained by considering the sharing and features of the queries in each subset bySJF (Lines 5–10). Finally, the globalexecution order of the queries is generated bySJF too (Line 11).Algorithm 3:Multiple queries.
(1)for each query qi  do
(2)  Generate the classification ofqi by E2E;
(3)end for
(4)  Divide the queries into some subsets by query type;
(5)for each subset do
(6)  Analyze and divide the sharing data;
(7)  Compute and query of the sharing data;
(8)  Calculate the simulate execution time;
(9)  Generate the localexecution order of each subset by SJF;
(10)end for
(11)  Generate the globalexecution order by SJF;Figure4 shows an example of the implementation of the multiple concurrent queries. Suppose that there are eight queries to be processed. First, these queries can obtain their classification results byE2E. After that, theAnalyzer divides these queries into four subsets by the sharing of computation, the same query type, respectively, top-k,kNN, skyline, and join.Figure 4
Implementation of multiple queries.In each subset, theOptimizer can make a localexecution order by the features of the queries. For example, the subset of skyline query contains three skyline queries, q2, q5, and q8, with their processing data sets s2={p1,p2,p3,p4,p5,p6}, s5={p1,p2,p3,p7,p8,p9}, and s8={p4,p5,p6,p7,p8,p9}. For these skyline queries, theOptimizer divides the sharing data and gains the following sharing subdatasets, sa={p1,p2,p3}, sb={p4,p5,p6}, and sc={p7,p8,p9}. Then, theOptimizer can transfer the above skyline queries into some simple skyline queries, s2=sa∪sb, s5=sa∪sc, and s8=sb∪sc. So, theOptimizer can make a solution that the skyline queries first compute the results of sa, sb, and sc, and then gain a localexecution order bySJF, q5, q8, and q2. The similar processing course is fit for the top-k andkNN queries. For our join query of small-big tables, theOptimizer can cache the corresponding small table into memory of Map tasks so as to reduce the repeated scan of the small table. Finally, the globalexecution orderOs, q7, q1, q5, q8, q2, q3, q4, and q6 can be gained by simple merge ofSJF of the four subsets.


## 5. Performance Evaluation

In this section, the performance of ourE2E model is evaluated in detail with various experimental settings. We first describe the setup used in our experiments in Section 5.1. Then we present and discuss the experimental results in Section 5.2.


### 5.1. Experimental Setup

The experimental setup is the same asELM_CMR model as follows. The experimental setup is a Hadoop cluster running on 9 nodes in a high speed Gigabit network, with one node as the Master node and the Coordinator node and the others as the Slave nodes. Each node has an Intel Quad Core 2.66 GHz CPU, 4 GB memory, and CentOS Linux 5.6. We use Hadoop 0.20.2 and compile the source codes under JDK 1.6. The ELM algorithm is implemented in MATLABR2009a.ELM_CMR is an efficient query processing optimization model based on ELM. It can identify the communication strategies of query processing applications in ComMapReduce according to the features of queries. So far, except theELM_CMR model, there is no any other method to study how to choose the optimal strategies of ComMapReduce for query processing applications. So, we evaluate the performance ofE2E model in different implementations for Just-in-Time execution and Queue execution by comparing withELM_CMR.In order to fully evaluate the performance ofE2E model, four typical query processing applications are adopted to evaluate the implementations of Just-in-Time execution and Queue execution, respectively, top-k,kNN, skyline, and join. In Just-in-Time execution evaluating, we, respectively, test the performance of top-k,kNN, skyline, and join under different data sizes inE2E andELM_CMR. In Queue execution evaluating, we design two kinds of experiments. One is that the multiple queries are the same kind of query under different data sizes, taking skyline query as an example. The other one is that the multiple queries are the different kinds of queries under different data sizes, taking top-k (2 G), top-k (8 G),kNN (2 G), andkNN (8 G) as examples.We use the synthetic data to test the performance. The synthetic datasets include different data sizes and different distributions, such as uniform distribution in top-k andkNN, anticorrelated distribution in skyline, and small-big tables in join. They can reflect the performance under different situations. The classification results ofE2E model contain 7 types, respectively, ECS, HCS-0.5, HCS-1, HCS-2, PreOS, PostOS, and MapReduce (MR). HCS-0.5 means the preassigned time interval of HCS is 0.5 s. Table 2 summarizes the parameters used in the experiments including the default values.


### 5.2. Experimental Results

First, we give the classification results ofE2E model andELM_CMR model by processing the above four query processing applications in different data size shown in Table 3. We can see that for the same query type and data size, the classification results of the queries are different, so the performance of the two models is different too. In the following, we evaluate the performance of the queries according to the classification results of Table 3.Table 3
Classifications ofE2Eand ELM_CMR.
Query
top-k
kNN
skyline
join
Data (G)
2
4
8
16
2
4
8
16
0.2
0.4
0.8
1.6
5
10
15
20
E2E
HCS-0.5
HCS-0.5
PreOS
PreOS
ECS
HCS-0.5
PreOS
PreOS
HCS-0.5
HCS-0.5
PostOS
PostOS
ECS
ECS
ECS
PreOS
ELM_CMR
ECS
ECS
HCS-1
HCS-0.5
HCS-0.5
HCS-1
HCS-2
HCS-2
ECS
HCS-1
HCS-2
HCS-2
MR
HCS-1
HCS-2
HCS-2Second, the performance of Just-in-Time execution is shown in the following figures. Figure5 shows the performance of top-k queries (k=1000), with the data size is 2 G, 4 G, 8 G, and 16 G in uniform distribution. We can see that the performance of top-k queries in the classification results ofE2E model is better thanELM_CMR. The reason is thatE2E model can effectively evaluate the optimal configuration parameters of the queries thanELM_CMR model. When k is much smaller than the original data, the globalshared information of ComMapReduce can reach the most optimal one quickly, so the Mappers can retrieve theshared information in the initial phase to filter the unpromising data.Figure 5
Performance of top-k query.Figure6 shows the performance ofkNN queries with different data size of uniform distribution. The performance ofE2E is also optimal toELM_CMR model, where the reason is thatE2E model can gain the suitable classification results.Figure 6
Performance ofkNN query.Figure7 shows the performance of skyline queries in anticorrelated distribution with different data size. We can see that the performance of different execution plans is not obviously different, but PostOS is a little better. The reason is that the original data are skewed to the final results in anticorrelated distribution. The percentage of filtering is low, so the performance difference is not obvious. In this situation, althoughE2E andELM_CMR can obtain the classification, it can also choose the other communication strategies.Figure 7
Performance of skyline query.Figure8 shows the performance of join queries in different data size of small-big tables, with the same data size of the small table 2 G, and the different data sizes of big table are shown in Table 3. The performance ofE2E is much better thanELM_CMR. In ComMapReduce, the join attributes of the small table can be set as theshared information to filter the unpromising intermediate results.Figure 8
Performance of join query.Third, we evaluate the performance of the same kind of multiple queries implemented in differentexecution orders. Figure 9 illustrates the performance of twoexecution orders of four skyline queries in different data sizes, 0.2 G, 0.4 G, 0.8 G, and 1.6 G in anticorrelated distribution. The running time of our optimizedexecution order is shorter than the running time of the original order. OurE2E can identify the proper classifications andexecution order of the queries to enhance the performance. In the original order in random, the queries do not have the optimal classifications and implementations withELM_CMR model.Figure 9
The same query type.Figure10 shows the performance of the multiple queries about different types under differentexecution orders, respectively, top-k (2 G), top-k (8 G),kNN (2 G), andkNN (8 G) in uniform distribution. We can see that the performance under ourE2E model is much optimal than theELM_CMR model. The optimizedexecution order ofE2E model does not only consider the classification results ofE2E model, but also consider the characteristics of the queries deeply.Figure 10
The different query types.


## 5.1. Experimental Setup

The experimental setup is the same asELM_CMR model as follows. The experimental setup is a Hadoop cluster running on 9 nodes in a high speed Gigabit network, with one node as the Master node and the Coordinator node and the others as the Slave nodes. Each node has an Intel Quad Core 2.66 GHz CPU, 4 GB memory, and CentOS Linux 5.6. We use Hadoop 0.20.2 and compile the source codes under JDK 1.6. The ELM algorithm is implemented in MATLABR2009a.ELM_CMR is an efficient query processing optimization model based on ELM. It can identify the communication strategies of query processing applications in ComMapReduce according to the features of queries. So far, except theELM_CMR model, there is no any other method to study how to choose the optimal strategies of ComMapReduce for query processing applications. So, we evaluate the performance ofE2E model in different implementations for Just-in-Time execution and Queue execution by comparing withELM_CMR.In order to fully evaluate the performance ofE2E model, four typical query processing applications are adopted to evaluate the implementations of Just-in-Time execution and Queue execution, respectively, top-k,kNN, skyline, and join. In Just-in-Time execution evaluating, we, respectively, test the performance of top-k,kNN, skyline, and join under different data sizes inE2E andELM_CMR. In Queue execution evaluating, we design two kinds of experiments. One is that the multiple queries are the same kind of query under different data sizes, taking skyline query as an example. The other one is that the multiple queries are the different kinds of queries under different data sizes, taking top-k (2 G), top-k (8 G),kNN (2 G), andkNN (8 G) as examples.We use the synthetic data to test the performance. The synthetic datasets include different data sizes and different distributions, such as uniform distribution in top-k andkNN, anticorrelated distribution in skyline, and small-big tables in join. They can reflect the performance under different situations. The classification results ofE2E model contain 7 types, respectively, ECS, HCS-0.5, HCS-1, HCS-2, PreOS, PostOS, and MapReduce (MR). HCS-0.5 means the preassigned time interval of HCS is 0.5 s. Table 2 summarizes the parameters used in the experiments including the default values.


## 5.2. Experimental Results

First, we give the classification results ofE2E model andELM_CMR model by processing the above four query processing applications in different data size shown in Table 3. We can see that for the same query type and data size, the classification results of the queries are different, so the performance of the two models is different too. In the following, we evaluate the performance of the queries according to the classification results of Table 3.Table 3
Classifications ofE2Eand ELM_CMR.
Query
top-k
kNN
skyline
join
Data (G)
2
4
8
16
2
4
8
16
0.2
0.4
0.8
1.6
5
10
15
20
E2E
HCS-0.5
HCS-0.5
PreOS
PreOS
ECS
HCS-0.5
PreOS
PreOS
HCS-0.5
HCS-0.5
PostOS
PostOS
ECS
ECS
ECS
PreOS
ELM_CMR
ECS
ECS
HCS-1
HCS-0.5
HCS-0.5
HCS-1
HCS-2
HCS-2
ECS
HCS-1
HCS-2
HCS-2
MR
HCS-1
HCS-2
HCS-2Second, the performance of Just-in-Time execution is shown in the following figures. Figure5 shows the performance of top-k queries (k=1000), with the data size is 2 G, 4 G, 8 G, and 16 G in uniform distribution. We can see that the performance of top-k queries in the classification results ofE2E model is better thanELM_CMR. The reason is thatE2E model can effectively evaluate the optimal configuration parameters of the queries thanELM_CMR model. When k is much smaller than the original data, the globalshared information of ComMapReduce can reach the most optimal one quickly, so the Mappers can retrieve theshared information in the initial phase to filter the unpromising data.Figure 5
Performance of top-k query.Figure6 shows the performance ofkNN queries with different data size of uniform distribution. The performance ofE2E is also optimal toELM_CMR model, where the reason is thatE2E model can gain the suitable classification results.Figure 6
Performance ofkNN query.Figure7 shows the performance of skyline queries in anticorrelated distribution with different data size. We can see that the performance of different execution plans is not obviously different, but PostOS is a little better. The reason is that the original data are skewed to the final results in anticorrelated distribution. The percentage of filtering is low, so the performance difference is not obvious. In this situation, althoughE2E andELM_CMR can obtain the classification, it can also choose the other communication strategies.Figure 7
Performance of skyline query.Figure8 shows the performance of join queries in different data size of small-big tables, with the same data size of the small table 2 G, and the different data sizes of big table are shown in Table 3. The performance ofE2E is much better thanELM_CMR. In ComMapReduce, the join attributes of the small table can be set as theshared information to filter the unpromising intermediate results.Figure 8
Performance of join query.Third, we evaluate the performance of the same kind of multiple queries implemented in differentexecution orders. Figure 9 illustrates the performance of twoexecution orders of four skyline queries in different data sizes, 0.2 G, 0.4 G, 0.8 G, and 1.6 G in anticorrelated distribution. The running time of our optimizedexecution order is shorter than the running time of the original order. OurE2E can identify the proper classifications andexecution order of the queries to enhance the performance. In the original order in random, the queries do not have the optimal classifications and implementations withELM_CMR model.Figure 9
The same query type.Figure10 shows the performance of the multiple queries about different types under differentexecution orders, respectively, top-k (2 G), top-k (8 G),kNN (2 G), andkNN (8 G) in uniform distribution. We can see that the performance under ourE2E model is much optimal than theELM_CMR model. The optimizedexecution order ofE2E model does not only consider the classification results ofE2E model, but also consider the characteristics of the queries deeply.Figure 10
The different query types.


## 6. Conclusions

In this paper, we propose an efficient query processing optimization model based on ELM,E2E model. OurE2E can effectively analyze the query processing applications and then generates the most optimized executions of query processing applications. After analyzing the problems of the formerELM_CMR model, we use two stages model to classify the query processing applications in ComMapReduce framework. Then, we propose an efficient training approach to train our model. We also give the query executions based onE2E model in two situations, Just-in-Time execution and Queue execution. The experiments demonstrate that theE2E model is efficient and the query processing applications can reach an optimal performance.



---

*Source: 236084-2015-05-27.xml*