An inside analysis of a genetic-programming based optimizer

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Muntes-Mulero, V., Aguilar-Saborit, J., Larriba-Pey, J.-L., Zuzarte, C., Markl, V.
Format: Conference Proceeding
Language:English
Subjects:
Algorismes genètics
Arquitectura de computadors
Bases de dades
Bases de dades relacionals
Computer Architecture
Cost function
Dynamic programming
Evolutionary algorithms
Evolutionary computation
Explosions
Genetic algorithms
Genetic mutations
Genetic optimizer
Genetic programming
Genetic-programming based optimizer
Informàtica
Inside analysis
Interrogació
Join order problem
Performance analysis
Programació dinàmica
Query execution plans
Query formulation
Query optimization
Query processing
Querying (Computer science)
Random search strategy
Relational databases
Sistemes d'informació
Testing
Àrees temàtiques de la UPC
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:1098-8068
DOI:10.1109/IDEAS.2006.10