NON-EXHAUSTIVE JOIN ORDERING SEARCH ALGORITHMS FOR LJQO

摘要：

In relational database systems the optimization of select-project-join queries is a combinatorial problem. The use of exhaustive search methods is prohibitive because of the exponential increase of the search space. Randomized searches are used to find near optimal plans in polynomial time. In this paper, we investigate the large join query optimization (LJQO) problem by extending randomized algorithms and implementing a 2PO algorithm as a query optimizer in a popular open-source DBMS. We compare our solution with an implementation of a genetic algorithm. Through a multidimensional test schema, we discuss pros and cons about the behavior of these algorithms. Our results show that 2PO algorithm is fast to run and the costs of generated plans are better in most cases when compared to those of the genetic algorithms.

关键词： Query optimization Join ordering Randomized algorithms Genetic algorithms

作者: Tarcizio Alexandre Bini Adriano Lange Marcos Sfair Sunye

作者单位: Informatics Department, Federal University of Paran á, Centro Politècnico, Jardim das Amèricas, Curitiba PR, Brazil

会议类型: 国际会议

会议名称: 13th International Conference on Enterprise Information System(第13届企业信息系统国际会议 ICEIS 2011)

会议地点: 北京

会议语种:英文

页码: 2037-2042

在线出版日期: 2011-06-08（万方平台首次上网日期，不代表论文的发表时间）