1. An inside analysis of a genetic-programming based optimizer
- Author
-
Muntés Mulero, Víctor, Aguilar Saborit, Josep, Larriba Pey, Josep, Zuzarte, Calisto, Markl, Volker, Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors, and Universitat Politècnica de Catalunya. DAMA-UPC - Data Management Group
- Subjects
Query processing ,Inside analysis ,Querying (Computer science) ,Query execution plans ,Informàtica::Sistemes d'informació::Bases de dades [Àrees temàtiques de la UPC] ,Join order problem ,Genetic algorithms ,Query formulation ,Dynamic programming ,Evolutionary algorithms ,Genetic-programming based optimizer ,Computer Architecture ,Arquitectura de computadors ,Bases de dades relacionals ,Programació dinàmica ,Algorismes genètics ,Random search strategy ,Genetic optimizer ,Query optimization ,Relational databases ,Informàtica::Arquitectura de computadors [Àrees temàtiques de la UPC] ,Bases de dades -- Interrogació - Abstract
The use of evolutionary algorithms has been proposed as a powerful random search strategy to solve the join order problem. Specifically, genetic programming used in query optimization has been proposed as an alternative to the limitations of dynamic programming with large join queries. However, very little is known about the impact and behavior of the genetic operations used in this type of algorithms. In this paper, we present an analysis that helps us to understand the effect of these operations during the optimization execution. Specifically, we study five different aspects: the age of the members in the population in terms of generations, the number of query execution plans (QEP) discarded without producing new offsprings, the average QEP life time in generations, the efficiency of the genetic operations and the evolution of the best cost. All in all, our analysis allows us to understand the impact of crossovers compared to mutation operations and the dynamically changing effects of these operations.
- Published
- 2006