Abstract

The near exhaustive search algorithm named ESU-GOO was proposed to optimize small join queries. It optimizes the join query time which consists of both the time to generate join query results and the time to search the join order solution, whereas methods such as exhaustive search and greedy algorithm optimizes only one of them. The ESU-GOO integrates Greedy Operator Ordering (GOO) to Exhaustive Search with join graph Update (ESU). GOO is applied to produce the initial solution in the polynomial time and its solution was used as the starting route for ESU. ESU was applied to generate a good join order solution. In the experiments, the join graphs with 4 to 12 nodes were simulated on the basis of the table relationship of the TPC-H database benchmark. ESU-GOO was compared with ESU optimizing the time to generate join query results and GOO optimizing the time to search the join order solution. The experiment showed that the execution time of ESU-GOO on average is 7 times faster than ESU and the ESU-GOO finds 65% of optimal join order solutions. Of all the experiments, the time that ESU-GOO, ESU and GOO use the least join query time are 60, 14 and 26%, respectively.

Key words: Database, query optimization, join order optimization algorithm, near exhaustive search algorithm.