Aplicação do algoritmo de Kruskal na otimização de consultas com múltiplas junções relacionais

Abstract

Resumo: A busca por planos ótimos de execução de consultas em SGDBs relacionais é certamente um problema da classe NP. Em virtude disso, a aplicação de algoritmos de programação dinâmica para esta finalidade fica restrita a certo limite de relações. Dessa forma, vários algoritmos foram propostos na tentativa de se encontrar planos aceitáveis em tempo hábil e com baixo consumo de recursos. Dentre estas soluções, podemos citar os algoritmos genéticos que apresentam a solução para o problema de otimização de consultas em tempo polinomial. Porém, por se tratar de um método aleatório, que exibe muitas variações em seus resultados, planos de execução impráticáveis podem ser escolhidos. Neste trabalho apresentaremos o algoritmo de Kruskal em conjunto com algumas regras de geração de sub-planos como alternativa para a geração de planos de execução de consultas. Tal algoritmo apresenta vantagens como código de implementação simples, tempo de execução polinomial e espaço de busca reduzido. Nós implementamos o algoritmo de Kruskal no SGBD PostgreSQL, o que permitiu confrontar seus resultados como algoritmo de programação dinâmica em consultas simples ou algoritmos genéticos em consultas complexas. Para os testes de performance, nossa metodologia de avaliação, tomou por base os benchmarks TPC-H e TPC-E. Os resultados obtidos demonstram que o algoritmo de Kruskal aplicado a otimização de consultas é uma solução viável que exibe bons resultados em consultas que apresentam múltiplas junções.

Abstract: The search for optimal plans in order to execute queries in relational DBMS is certainly an NP-complete problem. In virtue of this, the applicability of dynamic programming algorithms to the search of the optimal plans is restricted to a certain limit of relations. Because of this problem, severals alternative algorithms were proposed in order to find satisfactory plans in an acceptable time and with low consumption of resources. Among these solutions, we can cite the genetic algorithms which that present the solution to the queries optimization problem in polynomial time. However, it is a random method, which displays many variations in their results, and impractical execution plans can be chosen. This document presents the Kruskal’s algorithm together with some rules for generation of sub-plans as an alternative to the query plan generation. This algorithm has advantages as simple code implementation, polynomial run-time and reduced search space. We implemented this algorithm in PostgreSQL DBMS, which allowed comparetheir results with the dynamic programming in simple queries, or the genetic algorithmin complex queries. In performance tests, our evaluation method based on benchmarksTPC-H and TPC-E. The results show that Kruskal’s algorithm applied to the queries optimization is a viable solution that shows good results for queries that have multiplejoins.