Scientific Research and Essays

  • Abbreviation: Sci. Res. Essays
  • Language: English
  • ISSN: 1992-2248
  • DOI: 10.5897/SRE
  • Start Year: 2006
  • Published Articles: 2767

ESU-GOO: The join order algorithm for optimizing small join queries

  Areerat Trongratsameethong* and Jarernsri L. Mitrpanont    
Faculty of Information and Communication Technology, Mahidol University, Bangkok, Thailand.
Email: [email protected]

  •  Accepted: 30 January 2012
  •  Published: 09 February 2012



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.