Distributed query optimisation using two stage simulated annealing

It is widely accepted that query optimisation is a significant problem in centralised and distributed database systems. It has long been known that several of the heuristic algorithms proposed in the literature for centralised and distributed query optimisation problems only achieve suboptimal solutions. Although an exhaustive search gives an optimal solution, it is not practical in either centralised or distributed database systems when queries are not of a trivial size and the number of processing sites tends to be large. In the distributed query optimisation process, a query execution plan not only determines the order in which to perform the joins, but also determines the order in which to choose the join method to be used and their respective processing sites. The main aim of this work is to improve the search time of distributed database systems, such as R*, in finding the best query execution plan by using the Two Stage Simulated Annealing (TSSA) algorithm. The TSSA algorithm is a combination of an heuristic method with the well-known search technique, Simulated Annealing (SA). The proposed method will give a near optimal solution with respect to the search time and produce a reasonable query execution plan. The first stage of TSSA uses an heuristic algorithm to produce a good initial solution for the second stage and then at the second stage of TSSA, SA is applied to achieve the optimal solution. Clearly, the first stage gives us two benefits. The first benefit is to cut down drastically the search time and the second is that the solution from an heuristic algorithm normally is promising, though suboptimal. With the mechanism of uphill and downhill moves of SA, the solution will converge to the optimal solution. The proposed query optimisation approach has been evaluated by experiments using generated databases and database queries