Volume 6 Number 9 (Sep. 2011)
Home > Archive > 2011 > Volume 6 Number 9 (Sep. 2011) >
JSW 2011 Vol.6(9): 1655-1663 ISSN: 1796-217X
doi: 10.4304/jsw.6.9.1655-1663

Optimizing Large Query by Simulated Annealing Algorithm Based On Graph-Based Approach

Yongheng Chen1, Wanli Zuo1, 2, Fenglin He1, Kerui Chen1
1College of Computer Science and Technology, Jilin University, Changchun, China
2Key Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education


Abstract—In the relational database setting today, large queries containing many joins are becoming increasingly common. In general the ordering of join-operations is quite sensitive and has a devastatingly negative effect on the efficiency of the DBMS. Scheufele and Moerkotte proved that join-ordering is NP-complete in the general case [1]. The dynamic programming algorithm has a worst case running time, thus for queries with more than 10 joins, it becomes infeasible. To resolve this problem, random strategies are used. Simulated annealing is an intelligent algorithm of developing very fast. In this paper, we introduce the traditional simulated annealing algorithm through discussing its theory and process, analyzes its shortcoming in detail, simple describe influence of key parameters to simulated annealing algorithm and provided feasible improvement. Especially, in order to avoid the deficiency resulted by the neighbors of state, and make the query optimization support complex non-inner join, the improved algorithm gives a semantics expression of query and a method of constructing the connected join pairs. Experimental results show that the improved algorithm outperforms the original algorithm in terms of both output quality and running time.

Index Terms—simulated annealing, Query optimization, Join-Order, Randomized Algorithms

[PDF]

Cite: Yongheng Chen, Wanli Zuo, Fenglin He, Kerui Chen, "Optimizing Large Query by Simulated Annealing Algorithm Based On Graph-Based Approach," Journal of Software vol. 6, no. 9, pp. 1655-1663, 2011.

General Information

ISSN: 1796-217X (Online)
Frequency: Monthly (2006-2019); Bimonthly (Since 2020)
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, Google Scholar, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Dec 06, 2019 News!

    Vol 14, No 1- Vol 14, No 4 has been indexed by EI (Inspec)   [Click]

  • Jun 22, 2020 News!

    Papers published in JSW Vol 14, No 1- Vol 15 No 4 have been indexed by DBLP     [Click]

  • Jun 22, 2020 News!

    The papers published in Vol 15, No 5 have all received dois from Crossref    [Click]

  • Aug 01, 2018 News!

    [CFP] 2020 the annual meeting of JSW Editorial Board, ICCSM 2020, will be held in Rome, Italy, July 17-19, 2020   [Click]

  • Jun 22, 2020 News!

    Vol 15, No 5 has been published with online version     [Click]