Reqo: A Comprehensive Learning-Based Cost Model for Robust and Explainable Query Optimization
Open Access
- 2 April 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (1) , 1-27
Abstract
Although machine learning (ML) shows potential in improving query optimization by generating and selecting more efficient plans, ensuring the robustness of learning-based cost models (LCMs) remains challenging. These LCMs currently lack explainability, which undermines user trust and limits the ability to derive insights from their cost predictions to improve plan quality. Accurately converting tree-structured query plans into representations via tree models is also essential, as omitting any details may negatively impact subsequent cost model performance. Additionally, inherent uncertainty in cost estimation leads to inaccurate predictions, resulting in suboptimal plan selection. To address these challenges, we introduce Reqo, a R obust and E xplainable Q uery O ptimization cost model that comprehensively enhances three main stages in query optimization: plan generation, plan representation, and plan selection. Reqo integrates three innovations: the first explainability technique for LCMs that quantifies subgraph contributions and produces plan generation hints to enhance candidate plan quality; a novel tree model based on Bidirectional Graph Neural Networks (Bi-GNNs) with a Gated Recurrent Unit (GRU) aggregator to further capture both node-level and structural information and effectively strengthen plan representation; and an uncertainty-aware learning-to-rank cost estimator that adaptively integrates cost estimates with uncertainties to enhance plan selection robustness. Extensive experiments demonstrate that Reqo outperforms state-of-the-art approaches across all three stages.Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- A Novel Technique for Query Plan Representation Based on Graph Neural Nets2024
- Kepler: Robust Learning for Parametric Query OptimizationProceedings of the ACM on Management of Data, 2023
- Efficient Learning with Pseudo Labels for Query Cost Estimation2022
- Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process2022
- Bao: Making Learned Query Optimization PracticalACM SIGMOD Record, 2021
- Reinforcement Learning with Tree-LSTM for Join Order Selection2020
- Automatic View Generation with Deep Learning and Reinforcement Learning2020
- The Mythos of Model InterpretabilityQueue, 2018
- Plan bouquets2014
- Estimating the mean and variance of the target probability distribution1994