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

Dokeroglu T., Bayir M. A., COŞAR A.

APPLIED SOFT COMPUTING, cilt.30, ss.72-82, 2015 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 30
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1016/j.asoc.2015.01.026
  • Dergi Adı: APPLIED SOFT COMPUTING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.72-82
  • Anahtar Kelimeler: Relational cloud database, Multiple query optimization, Evolutionary computing, Branch-and-Bound, Hill Climbing, GENETIC ALGORITHM, OPTIMIZATION, PARALLEL
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.