Predicting the execution time of queries is an important problem with applications in scheduling, service level agreements and error detection. During query planning, a cost is associated with the chosen execution plan and used to rank competing plans. It would be convenient to use that cost to predict execution time, but it has been claimed in the literature that this is not possible. In this paper, we thoroughly investigate this claim considering both linear and non-linear models. We find that the accuracy using more complex models with only the optimizer cost is comparable to the reported accuracy in the literature. The most accurate method in the literature is nearest-neighbour regression which does not produce a model. The published results used a large feature set to identify nearest neighbours. We show that it is possible to achieve the same level of accuracy using only the cost to identify nearest neighbours. Using a smaller feature set brings the advantages of reduced overhead in terms of both storage space for the training data and the time to produce a prediction.
Following that work, Ganapathi proposed using nearest-neighbour regression to provide predictions of resource usage, not just execution time @cite_17 . Nearest-neighbour regression is a powerful, non-parametric method that requires no training and performs all its work when a prediction is required @cite_7 . Instead of proposing a model and tuning its parameters, nearest-neighbour regression works by identifying the @math most similar data points in the training data and assuming that the target values associated with them will be similar to the value associated with the new data point.
@cite_7 @cite_17
1985258161 2100773341
Abstract Nonparametric regression is a set of techniques for estimating a regression curve without making strong assumptions about the shape of the true regression function. These techniques are therefore useful for building and checking parametric models, as well as for data description. Kernel and nearest-neighbor regression estimators are local versions of univariate location estimators, and so they can readily be introduced to beginning students and consulting clients who are familiar with such summaries as the sample mean and median. One of the most challenging aspects of managing a very large data warehouse is identifying how queries will behave before they start executing. Yet knowing their performance characteristics --- their runtimes and resource usage --- can solve two important problems. First, every database vendor struggles with managing unexpectedly long-running queries. When these long-running queries can be identified before they start, they can be rejected or scheduled when they will not cause extreme resource contention for the other queries in the system. Second, deciding whether a system can complete a given workload in a given time period (or a bigger system is necessary) depends on knowing the resource requirements of the queries in that workload. We have developed a system that uses machine learning to accurately predict the performance metrics of database queries whose execution times range from milliseconds to hours. For training and testing our system, we used both real customer queries and queries generated from an extended set of TPC-DS templates. The extensions mimic queries that caused customer problems. We used these queries to compare how accurately different techniques predict metrics such as elapsed time, records used, disk I Os, and message bytes. The most promising technique was not only the most accurate, but also predicted these metrics simultaneously and using only information available prior to query execution. We validated the accuracy of this machine learning technique on a number of HP Neoview configurations. We were able to predict individual query elapsed time within 20 of its actual time for 85 of the test queries. Most importantly, we were able to correctly identify both the short and long-running (up to two hour) queries to inform workload management and capacity planning.