PaperlayerView exact revision on arXiv

Source-linked AI summary

Plan-Structured Deep Neural Network Models for Query Performance Prediction

Ryan Marcus, Olga Papaemmanouil

arXiv:1902.00132v1cs.DB

TL;DR

Query performance prediction is difficult because existing methods depend on human-engineered features and struggle with complex interactions in diverse query plans. The paper introduces plan-structured neural networks assembled from operator-level units, and reports that the approach outperforms state-of-the-art solutions with manageable training overhead. The paper also identifies scope boundaries involving concurrent queries and cloud-environment performance variation.

  • Problem

    Query performance prediction must estimate query latency despite complex interactions among operators, input relations, execution plans, and data distributions that existing human-engineered approaches do not naturally capture.

  • Method

    The paper assembles operator-level neural units into neural-network trees isomorphic to optimizer-generated query plans, using shared units to model operator behavior and interactions.

  • Results

    The plan-structured neural network outperforms state-of-the-art query performance prediction solutions with manageable training overhead.

  • Takeaways & Limitations

    The approach provides a plan-matched architecture that predicts execution time while avoiding human-engineered features and simplified assumptions.

  • Takeaways & Limitations

    The evaluated architecture targets queries on bare-metal servers; concurrent-query handling and cloud performance fluctuations remain future-work concerns.

Abstract

from arXiv · show

Query performance prediction, the task of predicting the latency of a query, is one of the most challenging problem in database management systems. Existing approaches rely on features and performance models engineered by human experts, but often fail to capture the complex interactions between query operators and input relations, and generally do not adapt naturally to workload characteristics and patterns in query execution plans. In this paper, we argue that deep learning can be applied to the query performance prediction problem, and we introduce a novel neural network architecture for the task: a plan-structured neural network. Our approach eliminates the need for human-crafted feature selection and automatically discovers complex performance models both at the operator and query plan level. Our novel neural network architecture can match the structure of any optimizer-selected query execution plan and predict its latency with high accuracy. We also propose a number of optimizations that reduce training overhead without sacrificing effectiveness. We evaluated our techniques on various workloads and we demonstrate that our plan-structured neural network can outperform the state-of-the-art in query performance prediction.

1 INTRODUCTION

Query performance prediction is important but difficult because query latency depends on execution plans, data distributions, and complex operator interactions. The paper proposes plan-structured deep neural networks to learn these interactions without human-engineered features.

  • Query performance prediction supports admission control, resource management, and SLA maintenance but remains difficult because latency depends on plans, data distributions, and complex operator interactions.
  • Previous approaches rely on hand-derived metrics, plan-level information, mathematical operator models, or ad-hoc combinations requiring substantial human feature engineering.
  • Deep neural networks can automatically derive useful input combinations and learn complex models without human feature engineering beyond network architecture.
  • Applying DNNs to query plans is challenging because plans are tree-structured and require vectorization that captures structure, intermediate results, and operators.
  • Plan-structured neural networks assign operator-specific neural units to an execution-plan-shaped network, modeling operator latency and interactions through shared weights.
  • The paper contributes operator-level neural units, plan-structured networks, training optimizations, and experiments reporting better performance than state-of-the-art methods.
  • The paper claims to eliminate human-engineered features and models while avoiding simplified assumptions used by previous approaches.

2 NEURAL NETWORKS BACKGROUND

The paper introduces neural-network foundations relevant to query performance prediction, including layered transformations, loss functions, and gradient-based training. These components map inputs to predictions and adjust model parameters using observed errors.

  • DNNs transform input vectors through successive layers and use an output layer to map the final representation to a prediction.
  • 2.2 Gradient descent: A loss function measures prediction error against target values and is minimized during training.
  • 2.1 Layers: Each layer applies an affine transformation followed by a nonlinear activation function, with weights and biases controlling the transformation.
  • 2.1 Layers: Neural networks compose layers by feeding each layer’s output into the next layer.
  • 2.2 Gradient descent: Gradient descent adjusts weights and biases using derivatives of the loss with respect to model parameters.
  • 2.2 Gradient descent: Stochastic gradient descent estimates the full-dataset gradient from a random sample of inputs and corresponding targets.

3 DL-BASED LATENCY PREDICTION: CHALLENGES

Traditional DNNs fit query performance prediction poorly because query plans vary in structure, operator types, and predictive properties. Tree-structured learning methods also mismatch query-plan branch isolation, while vector concatenation introduces sparsity.

  • A naive whole-query neural network can miss plan structure, intermediate-result features, and non-leaf operators that correlate with execution time.
  • Query plans vary in operator types, operator counts, correlations, and properties, whereas traditional DNNs use static architectures and fixed-size inputs.
  • Isolated branches: In query plans, changing a branch affects only its ancestors and not unrelated nodes such as sibling branches.
  • Isolated branches: Tree-structured neural models assume changes in one branch can affect other branches, conflicting with query-plan branch isolation.
  • Concatenating operator-specific vectors creates increasingly sparse representations as the number of heterogeneous operator types grows.
  • Position-independent operator behavior: Instances of the same operator can share performance characteristics across plans because relevant factors such as relation sizes remain correlated with latency.

4 PLAN-STRUCTURED DNNS

The paper models query plans with operator-specific neural units and composes them into networks whose tree structure matches the execution plan. Units use optimizer features and child outputs to predict operator latency and emit data features for parent operators.

  • 4.1 Operator-level neural units: Each logical operator type is represented by a distinct neural unit that learns its performance from operator-specific input features.Candidate inputs include operator type, estimated rows and I/Os, data-distribution statistics, selectivity uncertainty, and available buffer space.
  • 4.1 Operator-level neural units: A neural unit transforms its inputs through hidden layers into a latency prediction and an output data vector.The first output element estimates latency, while the remaining d elements form the data vector passed to parent operators.
  • 4.1.2 Internal neural units: Internal operator units concatenate operator features with the output vectors of their children before producing their own latency and data outputs.For joins, inputs include the join’s optimizer information plus latency and data outputs from both children.
  • 4.2 Trees of neural units: The complete neural network replaces every query-plan operator with its corresponding neural unit, creating a tree isomorphic to the execution plan.The root unit’s first output element is the predicted latency of the query execution plan.
  • 4.3 Model benefits: Shared units for repeated operator types support position-independent behavior and weight sharing, while fixed-size child vectors allow arbitrary plan structures.Branch isolation is respected because an operator can affect its ancestors but not its siblings or children.

5 MODEL TRAINING

The model is trained with gradient descent over executed query plans, using latency errors from operators throughout each plan. Specialized batching and tree-aware computation reduce the overhead caused by variable plan structures and repeated intermediate computations.

  • 5 MODEL TRAINING: Training minimizes a latency-prediction loss over operator instances in a corpus of executed query plans.The loss compares each operator unit’s predicted latency with its observed latency, covering leaf, internal, and root operators.
  • 5 MODEL TRAINING: Output data vectors are learned indirectly because gradient descent adjusts them to provide information useful to parent neural units.They are not constrained to represent predefined values, allowing the model to discover parent-relevant operator properties automatically.
  • 5.1 Batch training: Variable query-plan structures make naive stochastic-gradient vectorization difficult because a weight’s symbolic derivative depends on each sample’s tree.Grouping batches only by identical plan structure would permit vectorization but bias the gradient estimate.
  • 5.1.1 Batch training: Plan-based batching computes gradients within groups of identical tree structures, then combines and normalizes them by group size to avoid bias.This preserves random-sample gradient estimation while gaining efficiency from batch processing.
  • 5.1.2 Tree-aware computation: Tree-aware loss computation reuses child outputs that are needed for both parent and child error terms, reducing redundant computation.For a root and sole child, the child output is computed once rather than separately for each loss term.

6 EXPERIMENTAL RESULTS

Experiments on TPC-H and TPC-DS evaluate QPP Net against SVM, RBF, and TAM, showing stronger accuracy and manageable training overhead. Additional analyses examine workload complexity, prediction distributions, query-template errors, optimization effects, convergence, and architecture size.

  • Prediction Accuracy: QPP Net outperformed RBF, SVM, and TAM on relative and absolute error across TPC-H and TPC-DS.Relative error improved over RBF by 9% and 5%, over SVM by 25% and 24%, and over TAM by 28% and 21% for TPC-DS and TPC-H, respectively.
  • Prediction Accuracy: QPP Net’s gains were larger on TPC-DS, whose average plans contain 22 operators versus 18 for TPC-H.The authors attribute this to more training data and QPP Net’s ability to learn complex workload interactions.
  • Prediction Distribution: 89% of TPC-DS and 93% of TPC-H predictions were within a factor of 1.5 of actual latency.These proportions exceeded TAM, SVM, and RBF on both workloads.
  • Errors by Query Template: QPP Net’s mean absolute error was lower than or within 5% of other models for every query template.Its relative performance increased especially on long-running templates, including TPC-DS templates 6, 17, and 81.
  • Training Overhead: Information sharing reduced training time from over a week to just under 3 days, while the cache never exceeded 20MB.The authors conclude that information sharing and batch sampling are worthwhile training accelerators.
  • Training Convergence: QPP Net exceeded RBF after about 350 epochs for TPC-H and 250 epochs for TPC-DS.Training displayed diminishing returns: mean absolute error fell by 20 during the first 100 epochs but by only 2 during epochs 400–500.
  • Network Architecture: Using 1024 neurons per hidden layer nearly quadrupled training time while increasing accuracy by less than 1% relative to 128 neurons.Increasing hidden layers likewise produced diminishing benefits beyond five layers at 128 neurons each.
  • Network Architecture: Training time initially grew logarithmically with neuron count and eventually became linear as GPU parallelism was saturated.The authors relate the later slowdown to approximately one weight per vector-processing core and eventual capacity excess.

7 RELATED WORK

Prior QPP methods use hand-engineered features and often impose workload or query-structure assumptions. The paper positions its deep-learning approach as avoiding these requirements and learning interactions among plan components.

  • Paper's positioning: The paper argues that existing techniques do not learn interactions among various combinations of query operators.This limitation is presented alongside their dependence on human experts to transform plans and operators into machine-learning features.
  • Prior QPP approaches: Earlier concurrent-QPP techniques assume query templates or structures, require extensive offline training, and target analytical workloads.Their hand-tuned features, metrics, and models limit applicability to diverse workloads.
  • Prior QPP approaches: Progress estimators refine latency predictions during execution, but their inaccurate initial estimates limit ahead-of-time applicability.They repeatedly update predictions as the query runs, rather than providing a reliable estimate before execution.

8 CONCLUSIONS AND FUTURE WORK

The paper concludes that plan-structured neural networks assemble operator-level units into query-plan-shaped models and can be trained with manageable overhead. It identifies concurrent queries, cloud variability, and training efficiency as directions for future work.

  • Conclusions: Plan-structured networks assemble operator-level neural units into a tree matching the optimizer-generated query plan.The paper describes two optimizations for effective training and reports manageable training overhead.
  • Future work: Future work includes adapting the architecture to concurrent queries by modeling resource usage and resource competition.The proposed extension would address whether two queries must compete for resources.
  • Future work: The current architecture predicts queries on a bare-metal server, while cloud performance may vary with time of day or seemingly randomly.Future work could monitor system performance and make the model aware of these fluctuations.
  • Future work: Alternative optimizers and transfer learning are suggested as possible ways to improve neural-network training time.The paper leaves these improvements for future investigation.

A TPC-DS TEMPLATE LATENCY

Figure 12 reports the mean latency for each TPC-DS query template.

  • TPC-DS template latency: Figure 12 shows mean query latency by TPC-DS query template.The figure summarizes latency at the template level.

B FEATURES

The feature appendix describes QPP Net inputs and their encoding, including common inputs for all operators and specialized inputs for join, scan, and aggregate units.

  • Input table: Table 2 lists each input quantity, the PostgreSQL operators using it, and its neural-network encoding.The table is titled “QPP Net Inputs.”
  • Encoding strategies: Inputs use numeric whitening, Boolean zero-or-one encoding, or one-hot vectors for categorical values.Whitening scales training-set values to mean zero and variance one, with the same scaling at inference.
  • Operator-specific inputs: The first five input values are available for every PostgreSQL operator and therefore appear in all neural units.Other input groups are specific to join, scan, or aggregate neural units.
  • Operator-specific inputs: Join inputs span “Join Type” to “Sort Method,” scan inputs span “Relation Name” to “Scan Direction,” and aggregate inputs span “Strategy” to “Operator.”Some scan values may be missing for a selected physical operator type and are set to zero.
Loading 1902.00132v1…