Kruskal´s Algorithm for Query Tree Optimization

This paper describes an implementation of Kruskal´s algorithm in query optimization process for generation of a near optimal execution query tree. The open source Post- greSQL DBMS was used in the experiments since its query optimization is performed by dynamic programming and genetic algorithm, which allows a concrete comparison with our approach. Kruskal´s algorithm presents some advantages like its simplified code, its polynomial-time execution and the reduced search space to generate only one query tree, that will be the optimal tree. In most experiments, Kruskal´s algorithm got the expected results in almost the same time as the results achieved by default Post- greSQL´s optimization algorithms. The results confirm that Kruskal´s algorithm is a feasible method for query optimization.