Otimização de consultas no PostgreSQL utilizando o algoritmo de Kruskal

Abstract

Resumo: O papel da otimização de consultas é promover a recuperação dos dados desejados no menor tempo possível. Diversos algoritmos são utilizados nos atuais Sistemas Gerenciadores de Bancos de Dados (SGBD) para realizar a otimização de consultas e determinar a melhor ordem de execução das junções. Os algoritmos de programação dinâmica possuem um custo computacional elevado para determinar a solução ótima, enquanto os algoritmos heurísticos e aleatórios possuem custo computacional menor mas podem alcançar como resultado soluções que estão longe de serem ótimas. Encontrar um algoritmo que seja executado em um tempo razoável e que indique como resultado ao menos uma solução próxima da ótima significa obter um otimizador de consultas extremamente eficiente. Este trabalho apresenta a implementação do algoritmo de Kruskal no processo de otimização de consultas do PostgreSQL. Esse é um algoritmo guloso bottom-up que sempre executa primeiro a junção com maior ganho para formar a árvore geradora mínima do grafo. Dentre os algoritmos existentes foi escolhido o algoritmo de Kruskal por sua simplicidade de implementação e possibilidade de adequação da sua definição ao processo de otimização de consultas. O SGBD escolhido para a realização dos experimentos foi o PostgreSQL por possuir um conjunto complexo de recursos e por ser um software de código aberto. Na maioria dos experimentos realizados o algoritmo de Kruskal retornou os resultados esperados em tempos bastante próximos dos obtidos com os algoritmos implementados no PostgreSQL, com a vantagem da simplicidade de implementação do algoritmo de Kruskal e do seu espaço de busca reduzido enquanto apenas uma árvore de execução é gerada como solução ótima. Os resultados demonstram que o algoritmo de Kruskal é um algoritmo viável para a técnica de otimização de consultas, faltando no futuro definir quais conjuntos de consultas são beneficiados por este algoritmo.

Abstract: The query optimization purpose is to retrieve the information as quickly as possible. Many different algorithms are implemented on the modern Database Management Systems (DBMS) aiming the query optimization and in order to define the optimizing join order. The optimization by Dynamic programming finds optimal solutions but has high costs of execution. On the other hand, heuristcs and randomized algorithms have lower execution costs, however there is no guarantee a good solution will be found using this methods. Therefore, developing an algorithm able to find a sub-optimal solution in are asonable time means to have an extremely efficient query optimizer. This work presents Kruskal’s algorithm in query optimization process, which is a bottom-up greedy algorithm that always performs most profitable joins first to reduce query graph to its minimal spanning tree. Kruskal’s algorithm has been chosen because of its easy implementation and because it is possible to apply its defition on query optimization process. PostgreSQL DBMS has been chosen to perform the experiments because it offers full support for many sophisticated features, is an open source relational database systemand performs its query optimization by using Dynamic programming and heuristics algorithms. These features allow a concrete comparison between our approach and the existing ones. On most of tests, Kruskal’s algorithm got the expected results in almost the same time as the results reached by default PostgreSQL’s optimization algorithms, with the advantage on the simplicity of Kruskal’s algorithm implementation and its reduced search space necessary in order to generate only one optimal execution query tree. The results confirm us that Kruskal’s algorithm is a viable method for query optimization while a future work is to perform a broad test to determine, more precisely, witch set of queries would be benefited by this algorithm.