Adaptive Cost Models for Query Optimization

In the world of databases, when a user runs a query, the system has to figure out the best way to execute it. This involves picking a plan from many possible options, which can sometimes number in the thousands. The method that optimizers use to choose these plans relies heavily on a cost model. Essentially, the goal is to estimate how long a query will take based on various factors, allowing the system to select the most efficient plan for execution.

A traditional cost model considers different factors, particularly how much CPU power and disk space will be needed. These values are usually set by someone who understands how the database works, but they can change depending on user behavior and workload. Because of this, using a fixed set of values may not always lead to the best performance.

To address this challenge, we propose an Adaptive Cost Model (ACM). This model continuously monitors how queries are executed and adjusts the cost parameters on the fly. By doing this, it can optimize how resources like CPU and disk I/O are used without needing constant input from a database expert. This approach allows the system to respond to changing demands, which results in better performance overall.

#Query Optimization Basics

When a database processes a SQL query, there can be several execution plans created for that query, making it difficult to find the one that will run the fastest. A cost model helps by providing a way to estimate how long each plan will take. The accuracy of this cost model is crucial because it directly affects which plan the optimizer chooses. If the model is off, the optimizer may select a plan that looks good on paper but performs poorly in reality.

A typical optimizer has three main tasks: estimating how many records will come out of a certain plan, estimating how much CPU and disk resources will be used, and then finding a plan that minimizes these costs. However, traditional methods can struggle, especially when dealing with complex queries with multiple joins because the cost estimates may be highly inaccurate.

Recently, some have started using machine learning techniques to learn from past query executions. While these methods can improve performance in certain situations, they often require a steady workload or risk needing a complete retrain when faced with changing data or query patterns.

The main idea behind our approach is that by adjusting the parameters related to CPU and disk costs dynamically, we can enhance the optimizer's ability to find the best plans.

#Issues with Traditional Cost Models

In standard cost models, a database administrator manually sets parameters related to costs. This can be challenging since finding the right parameters relies on a deep understanding of the database and its workload. Additionally, the effectiveness of these parameter settings can degrade over time as workloads change, making it necessary to revisit the parameters frequently.

An alternative method involves running a specific set of calibration queries to collect statistics, which are then used to adjust cost parameters. However, executing these calibration queries can be burdensome and may not accurately represent real workloads.

Our adaptive cost model (ACM) offers a solution by utilizing machine learning techniques that allow for automatic adjustments based on query execution statistics. There are two main components of ACM: one focuses on the cost parameters associated with disk I/O and the other on CPU costs.

#Disk-Related Parameters

ACM calculates the cost associated with disk access by considering the state of the database buffer cache. When a query is run, ACM checks how much of the needed data is already in memory and how much still needs to be fetched from the disk. By continuously collecting statistics on how data is used, ACM can provide more accurate cost estimates.

For example, if a table is mostly stored in the buffer cache, the model can predict that accessing it will be faster than if it were to require multiple disk reads. This dynamic estimation is important because it reduces errors in the optimizer's cost predictions.

The model also employs a hit ratio, which simply indicates how often the data needed for a query can be found in memory versus on disk. By estimating this hit ratio based on historical data, ACM adjusts the cost for random disk access dynamically.

#CPU-Related Parameters

While disk access patterns can change based on the state of the database, CPU-related parameters remain more constant. However, they still need adjustments to accurately reflect the current hardware setup and database conditions.

After executing a query, ACM gathers statistics on how long various operations take and how many records are processed for each operation. By comparing this real execution time with the expected cost calculated beforehand, ACM can continuously refine the cost parameters associated with CPU operations.

The idea is to ensure that the calculated costs closely align with the actual time taken for each operation. This ongoing adjustment helps improve the optimizer's decisions when selecting execution plans.

#Experimental Evaluation

To test the effectiveness of ACM, we ran experiments using a common benchmark called TPC-H, which includes a series of standard queries and datasets. The primary aim was to see whether ACM could improve the correlation between estimated costs and actual execution times, as well as observe any impact it had on overall query Latency.

The results indicated that using ACM significantly improved the correlation between predicted costs and actual execution times, indicating a much more accurate model. Furthermore, the overall execution latency improved as well, suggesting that ACM allows the optimizer to select better plans more often.

While not every query benefitted from ACM, it showed a noticeable increase in performance for many. Some slow queries were still hindered by errors in estimating the number of records being processed, which highlights that while ACM improves cost estimation, it doesn't resolve all issues in query optimization.

#Conclusion

The adaptive cost model presented here proves to be a useful tool for dynamically adjusting CPU and disk-related parameters in a database optimizer. Unlike traditional approaches, ACM doesn't require pre-training or periodic calibration queries, making it easier to implement in real-world applications. It provides a more accurate cost estimation by reacting to workload changes in real time, which has been shown to improve query performance.

In future work, there is potential to combine ACM with techniques aimed at improving cardinality estimation, further enhancing the optimizer's capabilities. The findings so far underscore the importance of dynamically adjusting cost parameters, affirming that this can lead to significant improvements in query latency and database performance.