Shaoyi Yin
Skip Abstract Section
Abstract
The quality of a query execution plan chosen by a Cost-Based Optimizer (CBO) depends greatly on the estimation accuracy of input parameter values. Many research results have been produced on improving the estimation accuracy, but they do not work for every situation. Therefore, "robust query optimization" was introduced, in an effort to minimize the sub-optimality risk by accepting the fact that estimates could be inaccurate. In this survey, we aim to provide an overview of robust query optimization methods by classifying them into different categories, explaining the essential ideas, listing their advantages and limitations, and comparing them with multiple criteria.
- Aboulnaga, A. and Chaudhuri, S. 1999. Self-tuning Histograms: Building Histograms without Looking at Data. In SIGMOD. New York, USA, 181--192. Google Scholar
Digital Library
- Amsaleg, L., al.1996. Scrambling Query Plans to Cope with Unexpected Delays. In PDIS. Miami, USA, 208--219. Google ScholarDigital Library
- Antonshenkov, G. 1993. Dynamic Query Optimization in Rdb/VMS. In ICDE. Vienna, Austria, 538--547. Google ScholarDigital Library
- Arcangeli, J.P., et al. 2004. Mobile Agent Based Self-Adaptive Join for Wide-Area Distributed Query Processing. Journal of Database Management, 15(4): 25--44.Google ScholarCross Ref
- Avnur, R. and Hellerstein, J.M. 2000. Eddies: Continuously Adaptive Query Processing. SIGMOD. Dallas, USA, 261--272. Google ScholarDigital Library
- Babu, S. and Bizarro, P. 2005. Adaptive Query Processing in the Looking Glass. In CIDR. Asilomar, USA, 238--249.Google Scholar
- Babu, S., et al. 2005. Proactive Re-Optimization. In SIGMOD. Baltimore, USA, 107--118. Google ScholarDigital Library
- Babcock, B. and Chaudhuri, S. 2005. Towards a Robust Query Optimizer: A Principled and Practical Approach. In SIGMOD. Baltimore, USA, 119--130. Google ScholarDigital Library
- Bizarro, P., et al. 2005. Content-Based Routing: Different Plans for Different Data. In VLDB. Trondheim, Norway, 757--768. Google ScholarDigital Library
- Bizarro, P., et al. 2009. Progressive Parametric Query Optimization. KDE, 21(4): 582--594. Google ScholarDigital Library
- Bonneau, S. and Hameurlain, A. 1999. Hybrid Simultaneous Scheduling and Mapping in SQL Multi-Query Parallelization. In DEXA. Florence, Italy, 88--98. Google ScholarDigital Library
- Bouganim, L., et al. 2000. Dynamic Query Scheduling in Data Integration Systems. In ICDE. San Diego, USA, 425--434. Google ScholarDigital Library
- Bruno, N., et al. 2001. STHoles: a multidimensional workloadaware histogram. In SIGMOD. Santa Barbara, USA, 211--222. Google ScholarDigital Library
- Bruno, N., et al. 2011. AutoAdmin Project at Microsoft Research: Lessons Learned. IEEE Data Eng. Bull, 34(4): 12--19.Google Scholar
- Bruno, N., et al. 2013. Continuous Cloud-Scale Query Optimization and Processing. PVLDB, 6(11): 961--972. Google ScholarDigital Library
- Cao, L. and Rundensteiner, E.A. 2013. High Performance Stream Query Processing With Correlation-Aware Partitioning. PVLDB, 7(4): 265--276. Google ScholarDigital Library
- Chaudhuri, S., et al. 2008. A Pay-As-You-Go Framework for Query Execution Feedback. PVLDB, 1(1): 1141--1152. Google ScholarDigital Library
- Chaudhuri, S. 2009. Query Optimizers: Time to Rethink the Contract? In SIGMOD. Providence, USA, 961--968. Google ScholarDigital Library
- Chaudhuri, S., et al. 2009. Exact Cardinality Query Optimization for Optimizer Testing. PVLDB, 2(1): 994--1005. Google ScholarDigital Library
- Chen, C.M. and Roussopoulos, N. 1994. Adaptive Selectivity Estimation Using Query Feedback. In SIGMOD. Minneapolis, USA, 161--172. Google ScholarDigital Library
- Chu, F., Halpern, J., Gehrke, J. 2002. Least expected cost query optimization: what can we expect? In PODS. Madison, USA, 293--302. Google ScholarDigital Library
- Cole, R.L. and Graefe, G. 1994. Optimization of Dynamic Query Evaluation Plans. In SIGMOD. Minneapolis, 150--160. Google ScholarDigital Library
- Deshpande, A. 2004. An Initial Study of Overheads of Eddies. SIGMOD Record, 33(1): 44--49. Google ScholarDigital Library
- Deshpande, A., et al. 2007. Adaptive Query Processing. Foundations and Trends in Databases, 1(1): 1--140. Google ScholarDigital Library
- Dutt, A. and Haritsa, J. 2014. Plan bouquets: query processing without selectivity estimation. In SIGMOD. Snowbird, USA, 1039--1050. Google ScholarDigital Library
- Ergenç, B., et al. 2007. Robust Placement of Mobile Relational Operators for Large Scale Distributed Query Optimization. In PDCAT. Adelaide, Australia, 227--235. Google ScholarDigital Library
- Evrendilek, C., et al. 1997. Multidatabase Query Optimization. Distributed and Parallel Databases, 5(1):77--114. Google ScholarDigital Library
- Ghazal, A., et al. 2012. Adaptive Optimizations of Recursive Queries in Teradata. In SIGMOD. Scottsdale, USA, 851--860. Google ScholarDigital Library
- Graefe, G. and Ward, K. 1989. Dynamic query evaluation plans. In SIGMOD. Portland, USA, 358--366. Google ScholarDigital Library
- Graefe, G., et al. 2009. Visualizing the Robustness of Query Execution. In CIDR. Asilomar, USA.Google Scholar
- Graefe, G., et al. 2010. Robust Query Processing. Dagstuhl Workshop Summary 10381, Wadern, Germany.Google Scholar
- Graefe, G. 2011. Robust Query Processing (Research Panel). In ICDE. Hannover, Germany, 1361. Google ScholarDigital Library
- Graefe, G., et al. 2012. Robust Query Processing. Dagstuhl Workshop Summary 12321, Wadern, Germany.Google Scholar
- Gounaris, A., et al. 2002. Adaptive Query Processing: A Survey. In BNCOD. Sheffield, UK, 11--25. Google ScholarDigital Library
- Gounaris, A., et al. 2013. Adaptive Query Processing in Distributed Settings. Advanced Query Processing, Vol. 1: 211--236.Google ScholarCross Ref
- Hameurlain, A. and Morvan, F. 2002. CPU and Incremental Memory Allocation in Dynamic Parallelization of SQL Queries. Journal of Parallel Computing, 28(4): 525--556. Google ScholarDigital Library
- Han, W., et al. 2007. Progressive Optimization in a Shared-Nothing Parallel Database. In SIGMOD. Beijing, 809--820. Google ScholarDigital Library
- Harish, D., et al.. 2007. On the Production of Anorexic Plan Diagrams. In VLDB. Vienna, Austria, 1081--1092. Google ScholarDigital Library
- Harish, D., et al. 2008. Identifying Robust Plans through Plan Diagram Reduction. PVLDB, 1(1): 1124--1140. Google ScholarDigital Library
- Herodotou, H. and Babu, S. Xplus. 2010. A SQL-Tuning-Aware Query Optimizer. PVLDB, 3(1): 1149--1160. Google ScholarDigital Library
- Hong, W. and Stonebraker, M. 1993. Optimization of Parallel Query Execution Plans in XPRS. Distributed and Parallel Databases, 1(1): 9--32. Google ScholarDigital Library
- Ioannidis, Y. and Christodoulakis, S. 1991. On the Propagation of Errors in the Size of Join Results. In SIGMOD. Denver, USA, 168--177. Google ScholarDigital Library
- Ioannidis, Y. 2003. The History of Histograms (abridged). In VLDB. Berlin, Germany, 19--30. Google ScholarDigital Library
- Ives, Z. G., et al. 1999. An Adaptive Query Execution System for Data Integration. In SIGMOD. Philadelphia, USA, 299--310. Google ScholarDigital Library
- Ives, Z.G., et al. 2004. Adapting to Source Properties in Processing Data Integration Queries. In SIGMOD. Paris, France, 395--406. Google ScholarDigital Library
- Kabra, N. and DeWitt, D. 1998. Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans. In SIGMOD. Seattle, USA, 106--117. Google ScholarDigital Library
- Larson, P., et al. 2007. Cardinality Estimation Using Sample Views with Quality Assurance. In SIGMOD. Beijing, 175--186. Google ScholarDigital Library
- Lipton, R.J., et al. 1990. Practical Selectivity Estimation through Adaptive Sampling. In SIGMOD. Atlantic City, 1--11. Google ScholarDigital Library
- Mannino, M., et al. 1988. Statistical profile estimation in database systems. ACM Computing Surveys, 20(3): 191--221. Google ScholarDigital Library
- Markl, V., et al. 2004. Robust Query Processing through Progressive Optimization. SIGMOD. Paris, France, 659--670. Google ScholarDigital Library
- Markl, V., et al. 2007. Consistent Selectivity Estimation via Maximum Entropy. VLDB Journal, 16(1): 55--76. Google ScholarDigital Library
- Morvan, F. and Hameurlain, A. 2009. Dynamic Query Optimization: Towards Decentralized Methods. International Journal of Intelligent Information and Database Systems, 4(3): 461--482. Google ScholarDigital Library
- Neumann, T. and Calindo-Legaria, C. 2013.Taking the Edge off Cardinality Estimation Errors using Incremental Execution. In BTW. Magdeburg, Germany, 73--92.Google Scholar
- Nehme, R.V., et al. 2009. Query Mesh: Multi-Route Query Processing Technology (Demo). PVLDB, 2(2): 1530--1533. Google ScholarDigital Library
- Nehme, R.V., et al. 2013. Multi-Route Query Processing and Optimization. Journal of Computer and System Sciences, 79(3): 312--329. Google ScholarDigital Library
- Olken, F. and Rotem, D. 1986. Simple Random Sampling from Relational Databases. In VLDB. Kyoto, Japan, 160--169. Google ScholarDigital Library
- Picasso Database Query Optimizer Visualizer. http://dsl.serc.iisc.ernet.in/projects/PICASSO/Google Scholar
- Polyzotis, N. 2005. Selectivity-based partitioning: a divideand-union paradigm for effective query optimization. In CIKM. Bremen, Germany, 720--727. Google ScholarDigital Library
- Raman, V., et al. 2003. Using State Modules for Adaptive Query Processing. In ICDE. Bangalore, India, 353--364.Google Scholar
- Reddy, N. and Harista, J. 2005. Analyzing Plan Diagrams of Database Query Optimizers. In VLDB. Trondheim, Norway, 1228--1239. Google ScholarDigital Library
- Selinger, P.G., et al. 1979. Access Path Selection in a Relational DBMS. In SIGMOD. Boston, USA, 23--34. Google ScholarDigital Library
- Srivastava, Uet al. 2006. ISOMER: Consistent Histogram Construction Using Query Feedback. In ICDE. Atlanta, 39. Google ScholarDigital Library
- Stillger, M., et al.2001. LEO-DB2's Learning Optimizer. VLDB. Roma, Italy, 19--28. Google ScholarDigital Library
- Tian, F. and DeWitt, D.J. 2003. Tuple Routing Strategies for Distributed Eddies. In VLDB. Berlin, Germany, 333--344. Google ScholarDigital Library
- Tzoumas, K., et al. 2010. Sharing-Aware Horizontal Partitioning for Exploiting Correlations during Query Processing. PVLDB, 3(1): 542--553. Google ScholarDigital Library
- Tzoumas, K., et al. 2011. Lightweight Graphical Models for Selectivity Estimation without Independence Assumptions. PVLDB, 4(11): 852--863.Google ScholarDigital Library
- Tzoumas, K., et al. 2013. Efficient Adapting Graphical Models for Selectivity Estimation. VLDB Journal, 22(1): 3--27. Google ScholarDigital Library
- Wilschut, A. N. and Apers, P. M. G. 1991. Dataflow Query Execution in a Parallel Main-Memory Environment. In PDIS, Miami Beach, USA, 68--77. Google ScholarDigital Library
- Wiener, J.L., et al. 2009. Benchmarking Query Execution Robustness. In TPC Technology Conference on Performance Evaluation & Benchmarking. Lyon, France, 153--166. Google ScholarDigital Library
- Zhou, Y., et al. 2005. An Adaptable Distributed Query Processing Architecture. Knowledge and Data Engineering. 53(3): 283--309. Google ScholarDigital Library
Index Terms
- Robust Query Optimization Methods With Respect to Estimation Errors: A Survey
Index terms have been assigned to the content through auto-classification.
Recommendations
Robust variance estimation for random effects meta-analysis
In random effects meta-analysis, an overall effect is estimated using a weighted mean, with weights based on estimated marginal variances. The variance of the overall effect is often estimated using the inverse of the sum of the estimated weights, and ...
Robust estimation in partially linear errors-in-variables models
In many applications of regression analysis, there are covariates that are measured with errors. A robust family of estimators of the parametric and nonparametric components of a structural partially linear errors-in-variables model is introduced. The ...
Comments