Applying Probabilistic Adaptation to Improve the Efficiency of Intra-Query Load Balancing

Applying Probabilistic Adaptation to Improve the Efficiency of Intra-Query Load Balancing

Daniel M. Yellin (IBM Israel Software Lab, Jerusalem, Israel) and Jorge Buenabad-Chávez (Departmento de Computación, Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional, Mexico City, Mexico)
DOI: 10.4018/jaras.2013010102
OnDemand PDF Download:
List Price: $37.50


In the context of adaptive query processing (AQP), several techniques have been proposed for dynamically adapting/redistributing processor load assignments throughout a computation to take account of varying resource capabilities. The effectiveness of these techniques depends heavily on when and to what they adapt processor load assignments, particularly in the presence of varying load imbalance. Most existing approaches to this problem use heuristics based only upon the current machine load levels. The authors provide an algorithm, prAdapt that probabilistically predicts the future load on processors, based upon the recent history. It uses this prediction to evaluate the expected performance of different alternative solutions, taking into account the cost of the adaptation itself. If it finds a better solution than the current load distribution policy, it adapts to that distribution. Using a simulation based evaluation; they compare prAdapt to other approaches for AQP reported in the literature. The authors’ simulation results indicate that prAdapt often outperforms these other approaches.
Article Preview


The goal of an autonomic load balancing system (Ganek & Corbi, 2003; IBM, 2006; Huebscher & McCann, 2008; Sterritt, 2005) is to distribute load across multiple processors in such a way as to optimize system performance. An autonomic load balancing system will continuously monitor the performance of the system across all processors, and decide if a new policy for distributing work is warranted. For instance, one processor may be highly overloaded, and work will need to be redirected from that processor to other processors. It may require that even some of the existing load on that processor be moved to another processor.

In this paper we focus on a specialized domain of computation called Adaptive Query Processing (AQP), which uses a form of partitioned parallel processing to provide scalable query processing. Since this technique performs at the speed of the slowest participant, it has prompted several proposals for adaptivity specifically aimed at load balance (Gounaris et al., 2005; Raman, Han, & Narang, 2005; Shah et al., 2003). These proposals differ from most work on dynamic load balancing for parallel databases (DeWitt et al., 1992; Rahm & Marek, 1993) in changing load balance within, rather than between, queries. An evaluation and comparison of these approaches can be found in Paton et al. (2006, 2009).

Most AQP approaches for deciding when to adapt use only current machine load levels to make their decision. In this paper we explore a probabilistic approach that uses past performance (machine load levels) over a period of time to predict future performance. This prediction is then used to decide when to adapt. We provide empirical evidence for the effectiveness of our approach by comparing it to other algorithms in the literature. An initial version of this algorithm was presented in Yellin, Buenabad-Chávez, and Paton (2008). This paper expands upon that work providing new theoretical results, new variations on the algorithm, and more focused experiments to validate the efficacy of the approach. The experimental approach used to evaluate our approach is based upon the approach in Paton et al. (2009). We chose to keep the same experimental setting in order to better evaluate our approach directly against previous benchmarks. Part of the contribution of this paper is to show that using some fairly straightforward adaptive techniques to decide when to adapt, performance can be significantly improved.

The rest of this paper is organized as follows. In the next section we present the AQP problem and prior work on this problem. We focus on two existing algorithms, Flux (Shah et al., 2003) and RevisedDelta (Paton et al., 2009). The former is the seminal work in AQP upon which almost all other research is based, while the latter is the work that inspired the prAdapt algorithm in this paper. We also provide a theoretical framework to analyze the effectiveness of different approaches. In Appendix A and Appendix B we show that under the assumption that the immediate future will imitate the recent past, and under some additional assumptions, RevisedDelta (or a slight variant) is the optimal algorithm. However, the assumption that the future will imitate the past is not always valid, and for that reason in the section following the next one we describe the prAdapt algorithm, which attempts to probabilistically predict the future given the past. In the Experimental Methodology section we describe our methodology and in the Results Section we state the results of our experiments comparing prAdapt to Flux and to RevisedDelta. prAdapt has several parameters, and we also provide experimental evidence as to the effect of these parameters on the performance of the algorithm. The last section presents our conclusion, additional related work, and directions for future research.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 7: 2 Issues (2016): 1 Released, 1 Forthcoming
Volume 6: 2 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing