Immanuel Trummer
Abstract
Classical query optimization compares query plans according to one cost metric and associates each plan with a constant cost value. In this paper, we introduce the Multi-Objective Parametric Query Optimization (MPQ) problem where query plans are compared according to multiple cost metrics and the cost of a given plan according to a given metric is modeled as a function that depends on multiple parameters. The cost metrics may for instance include execution time or monetary fees; a parameter may represent the selectivity of a query predicate that is unspecified at optimization time.
MPQ generalizes parametric query optimization (which allows multiple parameters but only one cost metric) and multi-objective query optimization (which allows multiple cost metrics but no parameters). We formally analyze the novel MPQ problem and show why existing algorithms are inapplicable. We present a generic algorithm for MPQ and a specialized version for MPQ with piecewise-linear plan cost functions. We prove that both algorithms find all relevant query plans and experimentally evaluate the performance of our second algorithm in a Cloud computing scenario.
- M. Abhirama, S. Bhaumik, and A. Dey. On the stability of plan costs and the costs of plan stability. PVLDB, 2010. Google Scholar
Digital Library
- Z. Abul-Basher, Y. Feng, and P. Godfrey. Alternative Query Optimization for Workload Management. In Database and Expert Systems Applications, 2012.Google ScholarCross Ref
- S. Agarwal, A. Iyer, and A. Panda. Blink and It's Done: Interactive Queries on Very Large Data. PVLDB, 2012. Google ScholarDigital Library
- B. Babcock and S. Chaudhuri. Towards a Robust Query Optimizer: a Principled and Practical Approach. SIGMOD Conf., 2005. Google ScholarDigital Library
- S. Babu, P. Bizarro, and D. DeWitt. Proactive Re-Optimization. SIGMOD Conf., 2005. Google ScholarDigital Library
- A. Bemporad, K. Fukuda, and F. Torrisi. Convexity Recognition of the Union of Polyhedra. Computational Geometry, 2001. Google ScholarDigital Library
- P. Bizarro, N. Bruno, and D. DeWitt. Progressive Parametric Query Optimization. Trans. on KDE, Apr. 2009. Google ScholarDigital Library
- N. Bruno. Polynomial heuristics for query optimization. In ICDE, pages 589--600, 2010.Google ScholarCross Ref
- N. Bruno and R. V. Nehme. Configuration-Parametric Query Optimization for Physical Design Tuning. SIGMOD Conf., 2008. Google ScholarDigital Library
- F. Chu, J. Halpern, and J. Gehrke. Least Expected Cost Query Optimization: What can we Expect? SIGMOD Conf., 2002. Google ScholarDigital Library
- R. Cole and G. Graefe. Optimization of dynamic query evaluation plans. 1994.Google Scholar
- A. Dey, S. Bhaumik, and J. Haritsa. Efficiently Approximating Query Optimizer Plan Diagrams. PVLDB, 2008. Google ScholarDigital Library
- S. Ganguly. Design and Analysis of Parametric Query Optimization Algorithms. PVLDB, 1998. Google ScholarDigital Library
- S. Ganguly, W. Hasan, and R. Krishnamurthy. Query Optimization for Parallel Execution. In SIGMOD Conf., 1992. Google ScholarDigital Library
- M. Garofalakis and Y. Ioannidis. Multi-Dimensional Resource Scheduling for Parallel Queries. In SIGMOD Conf., 1996. Google ScholarDigital Library
- G. Graefe and K. Ward. Dynamic Query Evaluation Plans. SIGMOD Conf., 1989. Google ScholarDigital Library
- A. Hulgeri and S. Sudarshan. Parametric Query Optimization for Linear and Piecewise Linear Cost Functions. PVLDB, 2002. Google ScholarDigital Library
- A. Hulgeri and S. Sudarshan. AniPQO: Almost Non-Intrusive Parametric Query Optimization for Nonlinear Cost Functions. PVLDB, 2003. Google ScholarDigital Library
- Y. E. Ioannidis, R. T. Ng, K. Shim, and T. K. Sellis. Parametric Query Optimization. PVLDB, May 1997. Google ScholarDigital Library
- V. Kaibel and M. Pfetsch. Some algorithmic problems in polytope theory. Algebra, Geometry and Software Systems, 1, 2003.Google Scholar
- S. Kambhampati, U. Nambiar, Z. Nie, and S. Vaddi. Havasu: A Multi-Objective, Adaptive Query Processing Framework for Web Data Integration. ASU CSE, 2002.Google Scholar
- H. Kllapi, E. Sitaridi, M. M. Tsangaris, and Y. E. Ioannidis. Schedule Optimization for Data Processing Flows on the Cloud. In SIGMOD Conf., 2011. Google ScholarDigital Library
- K. Ono and G. Lohman. Measuring the complexity of join enumeration in query optimization. PVLDB, pages 314--325, 1990. Google ScholarDigital Library
- C. Papadimitriou and M. Yannakakis. Multiobjective Query Optimization. PODS, 2001. Google ScholarDigital Library
- N. Reddy and JR. Haritsa. Analyzing plan diagrams of database query optimizers. PVLDB, 2005. Google ScholarDigital Library
- P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access Path Selection in a Relational Database Management System. In SIGMOD Conf., pages 23--34, 1979. Google ScholarDigital Library
- A. Simitsis, P. Vassiliadis, and T. Sellis. State-Space Optimization of ETL Workflows. Trans. on KDE, Oct. 2005. Google ScholarDigital Library
- A. Simitsis, K. Wilkinson, M. Castellanos, and U. Dayal. Optimizing Analytic Data Flows for Multiple Execution Engines. SIGMOD Conf., 2012. Google ScholarDigital Library
- M. Steinbrunn, G. Moerkotte, and A. Kemper. Heuristic and randomized optimization for the join ordering problem. VLDB J., 6(3): 191--208, 1997. Google ScholarDigital Library
- TPC. TPC-H Benchmark, 2013.Google Scholar
- I. Trummer and C. Koch. Approximation Schemes for Many-Objective Query Optimization. SIGMOD Conf., 2014. Google ScholarDigital Library
- Z. Xu, Y. C. Tu, and X. Wang. PET: Reducing Database Energy Cost via Query Optimization. PVLDB, 2012. Google ScholarDigital Library
Recommendations
Multi-objective parametric query optimization
We propose a generalization of the classical database query optimization problem: multi-objective parametric query (MPQ) optimization. MPQ compares alternative processing plans according to multiple execution cost metrics. It also models missing pieces ...
Multi-objective parametric query optimization
Classical query optimization compares query plans according to one cost metric and associates each plan with a constant cost value. In this paper, we introduce the multi-objective parametric query optimization (MPQO) problem where query plans are ...
Multi-Objective Parametric Query Optimization
We propose a generalization of the classical database query optimization problem: multi-objective parametric query optimization (MPQ). MPQ compares alternative processing plans according to multiple execution cost metrics. It also models missing pieces ...
Comments