Database Systems

Redshift previously used AutoWLM(Auto Workload Manager) predictor for estimating query execution time.

• AutoWLM predictor takes a physical execution plan of a query as input and flattens it into a vector. Then, a lightweight XGBoost model is used to predict the query’s exec-time.
• As queries are executed in each instance, their feature vector and observed exec-time are added to the XGBoost model’s training set.

1. Inaccurate estimation
   • Due to AutoWLM’s lightweight nature and simplified query featurization techniques.
2. Cold start issue
   • AutoWLM predictor requires a sufficient amount of executed queries as training examples, which may not be available for a new instance.
3. Not consistent over workload/data changes
   • Whenever the customers’ data or query workload changes, it can provide unreliable predictions until the predictor’s training set “catches up” with the change.
   • The AutoWLM predictor provides confidence intervals which are used to ensure good worst-case behavior of the changes in the cluster. These confidence intervals use simple global statistics, which can be improved.

A new exec time predictor named Stage predictor

• A hierarchical query performance predictor.
• Hierarchical means that the predictor has 3 decision-making levels.

The 3 levels are:

1. Execution time cache

   • Information about an incoming query is checked in the cache to do prediction based on previously observed exec-time if the query is present in the cache.

2. A lightweight local ML model optimized for a specific DB instance with uncertainty measurement.

   • If query info is not present in the cache, the local model is used.
   • Local model (Bayesian ensemble of lightweight XGBoost models) provides a query exec-time prediction and a reliable uncertainty measure associated with the prediction with a very low inference latency.
   • Local model never learns a fully generalizable model of query performance, but it accurately predicts queries similar to the past-seen queries. Thus, acting more as a “fuzzy cache”.
   • The prediction uncertainty can be high if the local model does not have enough training examples, or if the query is very different from previously seen queries.

3. A complex global model that is transferable across all instances in Redshift.

   • If the local model returns high prediction uncertainty, the global model is used.
   • Global model is a graph neural network that take physical query execution plan for exec-time prediction.
   • Redshift trains a single global model on a diverse set of instances to facilitate transferable knowledge of exec-time prediction across various instances, resulting in accurate prediction of exec-time of queries on unseen clusters.
   • Has non-trivial inference time, up to 100ms, thus is only used if the local model has high uncertainty and believes that query could take longer than a couple of seconds. Since the global model is rarely used, the inference overhead will be amortized.

This new exec-time predictor resulted in an average query execution latency improvement of 20%.