Paper Info
Title
Optimizing Large Query by Simulated Annealing Algorithm Based On Graph-Based Approach.
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. © 2011 ACADEMY PUBLISHER.
Year
DOI
Venue
2011
10.4304/jsw.6.9.1655-1663
JSW
Keywords
Field
DocType
join-order,query optimization,randomized algorithms,simulated annealing
Joins,Computer science,Artificial intelligence,Query optimization,Simulated annealing,Dynamic programming,Randomized algorithm,Graph,Mathematical optimization,Algorithm,Adaptive simulated annealing,Semantics,Machine learning
Journal
Volume
Issue
Citations 
6
9
1
PageRank 
References 
Authors
0.40
2
4
Name
Order
Citations
PageRank
Yongheng Chen1184.50
Wanli Zuo234242.73
Fengling He3687.88
Kerui Chen4162.78