@article{Chi2013, 
author = {Chihung Chi and Ye Zhou and Xiaojun Ye},
title = {Performance Prediction for Performance-Sensitive Queries Based on Algorithmic Complexity},
year = {2013},
journal = {Tsinghua Science and Technology},
volume = {18},
number = {6},
pages = {618-628},
keywords = {query performance, data size, query complexity, performance-sensitive query},
url = {https://www.sciopen.com/article/10.1109/TST.2013.6678907},
doi = {10.1109/TST.2013.6678907},
abstract = {Performance predictions for database queries allow service providers to determine what resources are needed to ensure their performance. Cost-based or rule-based approaches have been proposed to optimize database query execution plans. However, Virtual Machine (VM)-based database services have little or no sharing of resources or interactions between applications hosted on shared infrastructures. Neither providers nor users have the right combination of visibility/access/expertise to perform proper tuning and provisioning. This paper presents a performance prediction model for query execution time estimates based on the query complexity for various data sizes. The user query execution time is a combination of five basic operator complexities:  O⁢(1),  O⁢(log⁡(n)),  O⁢(n),  O⁢(n⁢log⁡(n)), and  O⁢(n2). Moreover, tests indicate that not all queries are equally important for performance prediction. As such, this paper illustrates a performance-sensitive query locating process on three benchmarks: RUBiS, RUBBoS, and TPC-W. A key observation is that performance-sensitive queries are only a small proportion ( 20%) of the application query set. Evaluation of the performance model on the TPC-W benchmark shows that the query complexity in a real life scenario has an average prediction error rate of less than  10% which demonstrates the effectiveness of this predictive model.}
}