Robust heuristic algorithms for exploiting the common tasks of relational cloud database queries

Date

2015-05-01

Author

Dokeroglu, Tansel
Bayir, Murat Ali
Coşar, Ahmet

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Cloud computing enables a conventional relational database system's hardware to be adjusted dynamically according to query workload, performance and deadline constraints. One can rent a large amount of resources for a short duration in order to run complex queries efficiently on large-scale data with virtual machine clusters. Complex queries usually contain common subexpressions, either in a single query or among multiple queries that are submitted as a batch. The common subexpressions scan the same relations, compute the same tasks (join, sort, etc.), and/or ship the same data among virtual computers. The total time spent for the queries can be reduced by executing these common tasks only once. In this study, we build and use efficient sets of query execution plans to reduce the total execution time. This is an NP-Hard problem therefore, a set of robust heuristic algorithms, Branch-and-Bound, Genetic, Hill Climbing, and Hybrid Genetic-Hill Climbing, are proposed to find (near-) optimal query execution plans and maximize the benefits. The optimization time of each algorithm for identifying the query execution plans and the quality of these plans are analyzed by extensive experiments. (C) 2015 Elsevier B.V. All rights reserved.

Subject Keywords

Relational cloud database, Multiple query optimization, Evolutionary computing, Branch-and-bound, Hill climbing

URI

https://hdl.handle.net/11511/31553

Collections

Graduate School of Natural and Applied Sciences, Article