Reqo: A Robust and Explainable Query Optimization Cost Model

• URL: http://arxiv.org/abs/2501.17414v1
• Date: Wed, 29 Jan 2025 04:48:51 GMT
• Title: Reqo: A Robust and Explainable Query Optimization Cost Model
• Authors: Baoming Chang, Amin Kamali, Verena Kantere,
• Abstract summary: We propose a tree model architecture based on Bidirectional Graph Neural Networks (Bi-GNN) aggregated by Gated Recurrent Units (GRUs) We implement a novel learning-to-rank cost model that effectively quantifies the uncertainty in cost estimates using approximate probabilistic ML. In addition, we propose the first explainability technique specifically designed for learning-based cost models.
• Score: 2.184775414778289
• License:
• Abstract: In recent years, there has been a growing interest in using machine learning (ML) in query optimization to select more efficient plans. Existing learning-based query optimizers use certain model architectures to convert tree-structured query plans into representations suitable for downstream ML tasks. As the design of these architectures significantly impacts cost estimation, we propose a tree model architecture based on Bidirectional Graph Neural Networks (Bi-GNN) aggregated by Gated Recurrent Units (GRUs) to achieve more accurate cost estimates. The inherent uncertainty of data and model parameters also leads to inaccurate cost estimates, resulting in suboptimal plans and less robust query performance. To address this, we implement a novel learning-to-rank cost model that effectively quantifies the uncertainty in cost estimates using approximate probabilistic ML. This model adaptively integrates quantified uncertainty with estimated costs and learns from comparing pairwise plans, achieving more robust performance. In addition, we propose the first explainability technique specifically designed for learning-based cost models. This technique explains the contribution of any subgraphs in the query plan to the final predicted cost, which can be integrated and trained with any learning-based cost model to significantly boost the model's explainability. By incorporating these innovations, we propose a cost model for a Robust and Explainable Query Optimizer, Reqo, that improves the accuracy, robustness, and explainability of cost estimation, outperforming state-of-the-art approaches in all three dimensions.

Related papers

• Optimizing Sequential Recommendation Models with Scaling Laws and Approximate Entropy [104.48511402784763]
  Performance Law for SR models aims to theoretically investigate and model the relationship between model performance and data quality. We propose Approximate Entropy (ApEn) to assess data quality, presenting a more nuanced approach compared to traditional data quantity metrics.
  arXiv  Detail & Related papers  (2024-11-30T10:56:30Z)
• Model Cascading for Code: A Cascaded Black-Box Multi-Model Framework for Cost-Efficient Code Completion with Self-Testing [20.445496441396028]
  We introduce a novel framework combining model cascading and inference-time self-testing algorithms to find multiple near-optimal self-testing options on the cost-accuracy tradeoff. Our approach leverages self-generated tests to both enhance accuracy and evaluate model cascading decisions. Experimental results show that our cascading approach reduces costs by an average of 26%, and up to 70% in the best case.
  arXiv  Detail & Related papers  (2024-05-24T16:20:04Z)
• End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty [55.04219793298687]
  The Predict-Then-Forecast (PtO) paradigm in machine learning aims to maximize downstream decision quality. This paper extends the PtO methodology to optimization problems with nondifferentiable Ordered Weighted Averaging (OWA) objectives. It shows how optimization of OWA functions can be effectively integrated with parametric prediction for fair and robust optimization under uncertainty.
  arXiv  Detail & Related papers  (2024-02-12T16:33:35Z)
• Roq: Robust Query Optimization Based on a Risk-aware Learned Cost Model [3.0784574277021406]
  We propose a holistic framework that enables robust query optimization based on a risk-aware learning approach. Roq includes a novel formalization of the notion of robustness in the context of query optimization. We demonstrate experimentally that Roq provides significant improvements to robust query optimization compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2024-01-26T21:16:37Z)
• Design Amortization for Bayesian Optimal Experimental Design [70.13948372218849]
  We build off of successful variational approaches, which optimize a parameterized variational model with respect to bounds on the expected information gain (EIG) We present a novel neural architecture that allows experimenters to optimize a single variational model that can estimate the EIG for potentially infinitely many designs.
  arXiv  Detail & Related papers  (2022-10-07T02:12:34Z)
• Bayesian Optimization Over Iterative Learners with Structured Responses: A Budget-aware Planning Approach [31.918476422203412]
  This paper proposes a novel approach referred to as Budget-Aware Planning for Iterative learners (BAPI) to solve HPO problems under a constrained cost budget. Experiments on diverse HPO benchmarks for iterative learners show that BAPI performs better than state-of-the-art baselines in most of the cases.
  arXiv  Detail & Related papers  (2022-06-25T18:44:06Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  We propose a generalized iterative imputation framework for adaptively and automatically configuring column-wise models. We provide a concrete implementation with out-of-the-box learners, simulators, and interfaces.
  arXiv  Detail & Related papers  (2022-06-15T19:10:35Z)
• Neural Message Passing for Objective-Based Uncertainty Quantification and Optimal Experimental Design [15.692012868181635]
  We propose a novel scheme to reduce the computational cost for objective-UQ via MOCU based on a data-driven approach. We show that our proposed approach can accelerate MOCU-based OED by four to five orders of magnitude, without any visible performance loss.
  arXiv  Detail & Related papers  (2022-03-14T14:08:46Z)
• Conservative Objective Models for Effective Offline Model-Based Optimization [78.19085445065845]
  Computational design problems arise in a number of settings, from synthetic biology to computer architectures. We propose a method that learns a model of the objective function that lower bounds the actual value of the ground-truth objective on out-of-distribution inputs. COMs are simple to implement and outperform a number of existing methods on a wide range of MBO problems.
  arXiv  Detail & Related papers  (2021-07-14T17:55:28Z)
• A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration [17.75042918159419]
  A cost-based algorithm is adopted in almost all current database systems. In the cost model, cardinality, the number of the numbers through an operator plays a crucial role. Due to the inaccuracy in cardinality estimation, errors in cost, and the huge plan space model, the algorithm cannot find the optimal execution plan for a complex query in a reasonable time.
  arXiv  Detail & Related papers  (2021-01-05T13:47:45Z)
• On Exploiting Hitting Sets for Model Reconciliation [53.81101846598925]
  In human-aware planning, a planning agent may need to provide an explanation to a human user on why its plan is optimal. A popular approach to do this is called model reconciliation, where the agent tries to reconcile the differences in its model and the human's model. We present a logic-based framework for model reconciliation that extends beyond the realm of planning.
  arXiv  Detail & Related papers  (2020-12-16T21:25:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.