Análise do genetic query optimizer no postgresql

Análise do Genetic Query Optimizer no PostgreSQL
João Paulo D. Almeida1
1Departamento de Ciência da Computação – Universidade Federal da Bahia (UF BA)
Salvador, BA – Brasil [e-mail] Abstract. This article describes the implementation of the query optimizer GEQO (Genetic Query Optimizer) for PostgreSQL which is used to carry out the planning of large join queries.
Resumo. Este artigo descreve o funcionamento do otimizador de querys GEQO (Genetic Query Optimizer) do PostgreSQl que é utilizado para realizar o planejamento de querys com muitas junções.
1. Introdução
Dentre todos os operadores relacionais o join apresenta o maior custo computacional [PostgreSQL 2012], visto que o número de possíveis planos de consulta cresce exponencialmente com o número de junções (joins) na query. Para que o join seja executado de forma eficiente, podemos utilizar o otimizador de query para avaliar o plano de execução menos custoso. O otimizador de querys comum do PostgreSQL executa uma busca quase exaustiva entre as possíveis estratégias. Este algoritmo do otimizador comum produz soluções próximas da ótima, porém exige uma grande quantidade de tempo e de memória quando está tratando querys com uma grande quantidade de joins, impossibilitando o uso deste otimizador para tais tipos de query. Visando solucionar este problema foi desenvolvido um otimizador que implementa um Algoritmo Genético capaz de solucionar de forma eficiente o problema de ordenação dos joins de uma query.
2. Utilizando Algoritmo Genético para otimizar uma Query
Algoritmos Genéticos (AG) são algoritmos inspirados na teoria da evolução de Darwin onde a solução do problema é obtida através da simulação de uma competição entre indivíduos em uma mesma população, na qual sobreviverá apenas o indivíduo mais apto. A população é iniciada com um determinado número de possíveis soluções (indivíduos) e, com as interações entre esses indivíduos, o indivíduo mais apto irá prevalecer e se perpetuar