# Reqo: A Comprehensive Learning-Based Cost Model for Robust and Explainable Query Optimization

arXiv: https://arxiv.org/abs/2501.17414 · HTML: https://mlsanity.com/paper/2501.17414/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 50 references that are in the map.
- First posted on arXiv 29 Jan 2025.

## Builds on (most cited first, 23 of 23)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Tune: A Research Platform for Distributed Model Selection and Training](https://mlsanity.com/paper/1807.05118/) (2018)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [Edge Directionality Improves Learning on Heterophilic Graphs](https://mlsanity.com/paper/2305.10498/) (2023)
- [Neo: A Learned Query Optimizer](https://mlsanity.com/paper/1904.03711/) (2019)
- [Bao: Learning to Steer Query Optimizers](https://mlsanity.com/paper/2004.03814/) (2020)
- [A Simple Approach to Improve Single-Model Deep Uncertainty via Distance-Awareness](https://mlsanity.com/paper/2205.00403/) (2022)
- [An End-to-End Learning-based Cost Estimator](https://mlsanity.com/paper/1906.02560/) (2019)
- [Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation](https://mlsanity.com/paper/2109.05877/) (2021)
- [Graph Neural Networks with Adaptive Readouts](https://mlsanity.com/paper/2211.04952/) (2022)
- [Lero: A Learning-to-Rank Query Optimizer](https://mlsanity.com/paper/2302.06873/) (2023)
- [Flow-Loss: Learning Cardinality Estimates That Matter](https://mlsanity.com/paper/2101.04964/) (2021)
- [Zero-Shot Cost Models for Out-of-the-box Learned Cost Prediction](https://mlsanity.com/paper/2201.00561/) (2022)
- [Kepler: Robust Learning for Faster Parametric Query Optimization](https://mlsanity.com/paper/2306.06798/) (2023)
- [HERO: Hint-Based Efficient and Reliable Query Optimizer](https://mlsanity.com/paper/2412.02372/) (2024)
- [Robust Plan Evaluation based on Approximate Probabilistic Machine Learning](https://mlsanity.com/paper/2401.15210/) (2024)
- [A Novel Technique for Query Plan Representation Based on Graph Neural Nets](https://mlsanity.com/paper/2405.04814/) (2024)

## Abstract (arXiv)

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 Robust and Explainable Query Optimization 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.