Reqo: A Robust and Explainable Query Optimization Cost Model
Baoming Chang, Amin Kamali, Verena Kantere · 2025
Read Reqo: A Robust and Explainable Query Optimization Cost Model by Baoming Chang, Amin Kamali, Verena Kantere (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-17414.txt.
Introduction
Baoming Chang, Amin Kamali, and Verena Kantere presented Reqo in twenty twenty-five, a learning-based cost model for database query planning. A database must guess which plan for a query will run fastest, and learned models promise better guesses. Yet learned cost models can be brittle, and users cannot see why they pick a plan, which erodes trust.
Reqo improves all three stages of planning. An explanation method scores which parts of a plan drive its cost and hints at better plans. A two-way graph network reads plan trees in full detail. A ranking method folds in its own uncertainty when picking a winner. Wide tests show Reqo beats prior methods at each stage, making learned planning both stronger and easier to inspect.
Catalog record
| CREATOR | Baoming Chang, Amin Kamali, Verena Kantere |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-17414
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reqo: A Robust and Explainable Query Optimization Cost Model Baoming Chang, Amin Kamali, Verena Kantere 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 R obust and E xplainable Q uery O ptimizer, Reqo, that improves the accuracy, robustness, and explainability of cost estimation, outperforming state-of-the-art approaches in all three dimensions. † † authors: . PVLDB Reference Format: PVLDB, 18(1): XXX-XXX, 2025. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 18, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/BaomingChang/Reqo-on-PostgreSQL . 1. Introduction Query optimization is crucial for database management systems (DBMSs), directly impacting query execution performance. Accurately and efficiently estimating the cost of candidate query execution plans and selecting the optimal one remains a significant challenge. A query execution plan is typically represented as a tree, where nodes contain information about operators for accessing, joining, or aggregating data, and edges represent dependencies between parent and child nodes. An optimal plan allows the system to handle data efficiently. Traditional query optimizers use cost models based on statistical methods like histograms ( Ioannidis 2003 ) , which often introduce errors due to their limitations in capturing complex characteristics, such as join-crossing correlations. ML offers promising solutions for enhancing query optimization. Recent learning-based optimizers follow a common architecture (Figure 1 ), encoding node-level information into features that are then aggregated into a graph-level representation for each candidate plan. A cost estimator predicts execution costs based on these representations, enabling the optimizer to select the most efficient plan. However, preserving both node-level features and structural information between nodes when transforming tree-structured plans into representations is challenging, and any omission of key structural or operator details can diminish the effectiveness of downstream optimization. Figure 1 . Basic learning-based query optimizer framework Furthermore, due to ML models’ "black box" nature ( Lipton 2018 ) , the underlying rationale behind the predictions of learning-based cost models remains difficult for humans to understand and trust. Current approaches often overlook the explainability of these models, meaning that while they theoretically aggregate plan node features and structural information to generate representation and estimated cost, it remains unclear how specific subgraphs or operations within the query plan impact these predictions. Consequently, the lack of transparency on how specific plan components influence outcomes limits its effectiveness in trust-critical real-world applications. Additionally, plan selection usually relies on the ranking of the cost model’s estimated costs for all candidate query plans. Due to inherent uncertainty, the plan selected by the query optimizer may not have the shortest execution runtime. Query optimization methods that are less sensitive to such estimation errors and do not rely on simplifying assumptions are considered robust ( Kamali et al. 2024 ) , which is a critical avenue for improving the overall performance of the optimizer. Recent learning-based cost models have increasingly addressed robustness. Some approaches ( Marcus et al. 2019 ; Marcus et al. 2021 ; Chen et al. 2023b ) implement it by mitigating misestimation of the input parameters or minimizing the possibility of selecting a worse plan through specific mechanisms. However, the state-of-the-art approaches ( Zhao et al. 2022b ; Liu et al. 2021 ; Chen et al. 2023a ; Doshi et al. 2023 ; Kamali et al. 2024 ) change to quantify the uncertainty in data and model predictions, applying such measures to improve the robustness of query optimization. These methods usually use approximate probabilistic ML to quantify uncertainties and apply them for more robust plan selection. Despite their superior performance, these models’ training (including cost and uncertainty estimation) remains decoupled from its plan selection strategy, limiting uncertainty exploitation and self-improvement through selection feedback. In this paper, we focus on improving these challenges: query plan representation, cost estimation explainability, and plan selection robustness. Comparative studies on tree models ( Zhao et al. 2023 ; Chang et al. 2024 ) highlight their critical role in query plan representation. Therefore, we propose a novel tree model architecture BiGG ( Chang et al. 2024 ) that leverages Bi-GNNs ( Rossi et al. 2023 ) and a GRU-based aggregator ( Buterez et al. 2022 ) . This approach captures both node and structural information in query plan trees more effectively, providing superior representation learning capabilities compared to other advanced tree models ( Tai et al. 2015 ; Mou et al. 2016 ) . Additionally, we propose the first explainability technique for learning-based cost models that captures subtree-level contributions by quantifying similarities in subtree–plan representations. This approach pinpoints high-impact subgraphs that significantly influence execution cost, thereby enhancing transparency and improving trust in cost-based decisions. By identifying these critical subgraphs, developers can focus manual optimization efforts and increase efficiency in the query optimization process. To enhance robustness, we introduce a learning-to-rank cost model with uncertainty quantification. This approach adaptively integrates cost estimates and uncertainty for plan selection, benefiting from pairwise plan comparisons during training without requiring pairwise inputs at test time. As a result, it achieves considerable improvements in plan selection robustness. To summarize, our main contributions are: • We propose a novel, more powerful query plan tree model based on our previous work BiGG ( Chang et al. 2024 ) with Bi directional G NNs and a G RU-based aggregator. • We introduce explainability into learning-based cost models for the first time by quantifying how query plan subgraphs affect cost estimation. This approach fosters transparency, provides a basis for targeted optimizations, and increases trust in the learning-based cost model’s predictions. • We design and implement an uncertainty-aware cost model that employs a learning-to-rank mechanism capable of adaptively integrating the qualified cost estimation and uncertainty for query plan comparison while significantly improving the robustness of the model. • We develop Reqo , a comprehensive query optimization