Abstract
Genetic programming has been proposed as a possible although still intriguing approach for query optimization. There exist two main aspects which are still unclear and need further investigation, namely, the quality of the results and the speed to converge to an optimum solution. In this paper we tackle the first aspect and present and validate a statistical model that, for the first time in the literature, lets us state that the average cost of the best query execution plan (QEP) obtained by a genetic optimizer is predictable. Also, it allows us to analyze the parameters that are most important in order to obtain the best possible costed QEP. As a consequence of this analysis, we demonstrate that it is possible to extract general rules in order to parameterize a genetic optimizer independently from the random effects of the initial population.
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
Bennett, K., Ferris, M.C., Ioannidis, Y.E.: A genetic algorithm for database query optimization. In: Belew, R., Booker, L. (eds.) Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 400–407. Morgan Kaufmann, San Mateo (1991)
Everitt, B.S.: The Cambridge Dictionary of Statistics. Cambridge Univ. Press, Cambridge (1998)
Ioannidis, Y.E., Wong, E.: Query optimization by simulated annealing. In: SIGMOD 1987: Proceedings of the 1987 ACM SIGMOD international conference on Management of data, pp. 9–22. ACM Press, New York (1987)
Krishnamurthy, R., Boral, H., Zaniolo, C.: Optimization of nonrecursive queries. In: VLDB, pp. 128–137 (1986)
Montgomery, D.: Design and Analysis of Experiments. John Wiley & Sons, New York (1991)
Muntes, V., Aguilar, J., Zuzarte, C., Larriba, J.L.: An io-based cost model for the carquinyoli genetic optimizer. Technical Report UPC-DAC-RR-2005-69, Dept. d’Arqu. de Comp. UPC (2005), http://www.dama.upc.edu
Muntés-Mulero, V., Aguilar-Saborit, J., Zuzarte, C., Larriba-Pey, J.-L.: Cgo: a sound genetic optimizer for cyclic query graphs. In: Proc. of ICCS 2006, Reading, UK, pp. 156–163. Springer, Heidelberg (2006)
Scheffé, H.: The Analysis of Variance. John Wiley & Sons, Inc., New York (1959)
Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A., Price, T.G.: Access path selection in a relational database management system. In: Proceedings of the 1979 ACM SIGMOD international conference on Management of data, pp. 23–34. ACM Press, New York (1979)
Steinbrunn, M., Moerkotte, G., Kemper, A.: Heuristic and randomized optimization for the join ordering problem. VLDB Journal: Very Large Data Bases 6(3), 191–208 (1997)
Stillger, M., Spiliopoulou, M.: Genetic programming in database query optimization. In: Koza, J.R., Goldberg, D.E., Fogel, D.B., Riolo, R.L. (eds.) Genetic Programming 1996: Proceedings of the First Annual Conference, Stanford University, CA, USA, July 28-31, 1996, pp. 388–393. MIT Press, Cambridge (1996)
Swami, A.: Optimization of large join queries: combining heuristics and combinatorial techniques. In: SIGMOD 1989: Proceedings of the 1989 ACM SIGMOD international conference on Management of data, pp. 367–376. ACM Press, New York (1989)
Tao, Y., Zhu, Q., Zuzarte, C., Lau, W.: Optimizing large star-schema queries with snowflakes via heuristic-based query rewriting. In: CASCON 2003: Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research, pp. 279–293. IBM Press (2003)
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
Muntés-Mulero, V., Pérez-Casany, M., Aguilar-Saborit, J., Zuzarte, C., Larriba-Pey, JL. (2006). Parameterizing a Genetic Optimizer. In: Bressan, S., Küng, J., Wagner, R. (eds) Database and Expert Systems Applications. DEXA 2006. Lecture Notes in Computer Science, vol 4080. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11827405_69
Download citation
DOI: https://doi.org/10.1007/11827405_69
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37871-6
Online ISBN: 978-3-540-37872-3
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.