In cloud database systems, hardware configurations, data usage, and workload allocations are continuously changing. These changes make it difficult for the query optimizer to obtain an optimal query execution plan (QEP) for a query based on the data statistics collected before the query execution. In order to optimize a query with a more accurate cost estimation to achieve such a QEP, performing query re-optimizations during the query execution has been proposed in the literature. However, some of the re-optimizations may not provide any gain in terms of query response time or monetary cost and may also have negative impacts on the query performance due to their overheads. This raises the question of how to determine when a re-optimization is beneficial. In addition, a Service Level Agreement (SLA) is signed between users and the cloud. Thus, query re-optimization is multi-objective optimization that minimizes not only query execution time and monetary cost but also SLA violation. However, none of the existing query re-optimization algorithms considers all these three objectives together and none of them can predict when a re-optimization is beneficial.

To fill the gap, in this dissertation, four novel query re-optimization algorithms, ReOpt, ReOptML, ReOptRL and SLAReOptRL are proposed. Extensive theoretical and experimental evaluations performed on our proposed techniques showed that each of them has better performance in terms of time, monetary cost, and SLA violation rate than state-of-the-art techniques when applied to the TPC-H database benchmark.