Abstract
Adaptive query processors make decisions as to the most effective evaluation strategy for a query based on feedback received while the query is being evaluated. In essence, any of the decisions made by the optimizer (e.g., on operator order or on which operators to use) may be revisited in an adaptive query processor. This paper focuses on changes to physical operators (e.g., the specific join operators used, such as hash-join or merge-join) in pipelined query evaluators. In so doing, the paper characterizes the runtime properties of pipelined operators in a way that makes explicit when specific operators may be replaced, and that allows the validity of operator replacements to be proved. This is illustrated with reference to the substitution of join operators during their evaluation.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Avnur, R., Hellerstein, J.M.: Eddies: Continuously Adaptive Query Processing. In: ACM SIGMOD, pp. 261–272 (2000)
Babu, S., Bizarro, P.: Adaptive Query Processing in the Looking Glass. In: CIDR, pp. 238–249 (2005)
Babu, S., Bizarro, P., DeWitt, D.: Proactive Re-Optimization. In: Proc. ACM SIGMOD, pp. 107–118 (2005)
Garcia-Molina, H., Widom, J., Ullman, J.D.: Database System Implementation. Prentice-Hall, Inc., Englewood Cliffs (1999)
Gounaris, A., Smith, J., Paton, N.W., Sakellariou, R., Fernandes, A.A.A.: Adapting to Changing Resources in Grid Query Processing. In: Pierson, J.-M. (ed.) VLDB DMG 2005. LNCS, vol. 3836, pp. 30–44. Springer, Heidelberg (2006)
Graefe, G.: Encapsulation of Parallelism in the Volcano Query Processing System. In: Proc. SIGMOD, pp. 102–111 (1990)
Graefe, G.: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2), 73–170 (1993)
Ives, Z.G., Florescu, D., Friedman, M., Levy, A.Y., Weld, D.S.: An Adaptive Query Execution System for Data Integration. In: SIGMOD Conference, pp. 299–310 (1999)
Kabra, N., DeWitt, D.J.: Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans. In: SIGMOD Conference, pp. 106–117 (1998)
Markl, V., Raman, V., Simmen, D.E., Lohman, G.M., Pirahesh, H.: Robust Query Processing through Progressive Optimization. In: SIGMOD Conference, pp. 659–670 (2004)
Mishra, P., Eich, M.H.: Join Processing in Relational Databases.. ACM Comput. Surv. 24(1), 63–113 (1992)
Ng, K.W., Wang, Z., Muntz, R.R.: Dynamic Reconfiguration of Sub-Optimal Parallel Query Execution Plans. Technical Report CSD-980033, UCLA (1998)
Raman, V., Deshpande, A., Hellerstein, J.M.: Using State Modules for Adaptive Query Processing. Technical Report UCB/CSD-03-1231, University of California Berkeley (2003)
Shah, M.A., Hellerstein, J.M., Chandrasekaran, S., Franklin, M.J.: Flux: An Adaptive Partitioning Operator for Continuous Query Systems. In: ICDE, pp. 25–36 (2003)
Urhan, T., Franklin, M.J., Amsaleg, L.: Cost Based Query Scrambling for Initial Delays. In: SIGMOD Conference, pp. 130–141 (1998)
Wilschut, A.N., Apers, P.M.G.: Dataflow Query Execution in a Parallel Main-memory Environment. Distributed and Parallel Databases 1(1), 103–128 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Eurviriyanukul, K., Fernandes, A.A.A., Paton, N.W. (2006). A Foundation for the Replacement of Pipelined Physical Join Operators in Adaptive Query Processing. In: Grust, T., et al. Current Trends in Database Technology – EDBT 2006. EDBT 2006. Lecture Notes in Computer Science, vol 4254. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11896548_44
Download citation
DOI: https://doi.org/10.1007/11896548_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-46788-5
Online ISBN: 978-3-540-46790-8
eBook Packages: Computer ScienceComputer Science (R0)