File(s) under permanent embargo
Distributed query optimisation using two stage simulated annealing
thesisposted on 2023-05-27, 18:14 authored by Pongpinigpinyo, Sunee
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.
Rights statementCopyright 1996 the author - The University is continuing to endeavour to trace the copyright owner(s) and in the meantime this item has been reproduced here in good faith. We would be pleased to hear from the copyright owner(s). Aims to improve the search time of distributed data systems, such as R*, in finding the best query execution plan by using the Two Stage Simulated Annealing (TSSA) algorithm. Thesis (M.Sc.)--University of Tasmania, 1997. Includes bibliographical references. Aims to improve the search time of distributed data systems, such as R*, in finding the best query execution plan by using the Two Stage Simulated Annealing (TSSA) algorithm