Learned cardinality estimators are usually trained to minimize prediction error (Q-Error) against true sub-plan cardinalities, yet only some estimation errors degrade the query plans an optimizer chooses. Cost-guided cardinality estimation (Negi et al., ICDEW 2020) introduced the complementary idea: train estimators so that the estimates that matter for plan cost are accurate, tolerating error elsewhere. The open question left by that work — whether cost-guided learning generalizes across the growing diversity of learned cardinality estimation approaches, at acceptable training cost — remains only partially answered: the authors' successor Flow-Loss (VLDB 2021) and its AQP training-data extension demonstrated the principle for two supervised architectures (a fully connected network and the multi-set convolutional network MSCN) on two DBMSs, while later work developed plan-aware evaluation metrics (P-Error, L1-error, ACS-infinity) but largely did not extend plan-aware training itself to the further learned models the source names for evaluation (the local per-schema models of Woltmann et al.) or to query-driven architectures beyond those two. The problem is to establish, by systematic study, whether plan-aware training objectives generalize across learned cardinality estimation architectures and deployment conditions, and at what training-time cost they do so.

Background

Cardinality estimation (CE) is the task of predicting the number of rows produced by sub-plans of a relational query — the outputs of table filters and of intermediate joins. A query optimizer (the database system component that chooses, for example, the order in which tables are joined) compares candidate plans using a cost model driven by these cardinality estimates, so cardinality misestimates translate directly into slow query plans. Learned cardinality estimators replace the traditional histogram-based estimates with machine-learned models. Most are trained by minimizing Q-Error, the ratio-style prediction error max⁡(y/y^,y^/y)\max(y/\hat y, \hat y/y) between the true cardinality yy and the estimate y^\hat y of each sub-plan.

However, not all sub-plan estimates are equally important: an optimizer's plan choice may be very sensitive to the cardinality of one large join while being indifferent to others. Negi, Marcus, Mao, Tatbul, Kraska, and Alizadeh (ICDEW 2020) made this observation operational. They defined the Plan-Error of a set of estimates as the difference between (i) the optimizer cost of the plan chosen using the estimates, evaluated under the true cardinalities, and (ii) the cost of the truly optimal plan; and they trained estimators by prioritized sampling, drawing training sub-queries with probability proportional to a moving average of their Plan-Error raised to a power α\alpha (a scheme adapted from prioritized experience replay in reinforcement learning, where training experience is sampled non-uniformly, with probability proportional to its importance, rather than uniformly). In a preliminary study on a newly generated workload of 8746 queries over the IMDb dataset, this cost-guided training reduced mean query runtime by 1.7–2× while making average prediction error (Q-Error) worse — evidence that prediction accuracy is not the right training target for query optimization.

The paper's conclusion (Section V) listed open directions: expand the experimental study to more recent cardinality estimation models; measure training time and investigate trends in the Plan-Error metric; evaluate the several hyper-parameters related to prioritization and training that had not yet been fully evaluated (Section II-B sets the prioritization exponent α\alpha to 2 and uses a moving average of the last four epochs); and investigate approximate query processing (AQP — sampling-based techniques such as wander join and index-based join sampling that estimate query answers approximately but much faster than exact execution) to gather ground-truth cardinality training data more cheaply. The models the paper names as expected to benefit from cost-guided training appear in Section III (Models) rather than in the conclusion: the query-driven models of Ortiz et al. and the local deep learning models of Woltmann et al.

Subsequent literature has reshaped this agenda. The same authors' Flow-Loss paper (VLDB 2021) replaced the non-differentiable Plan-Error prioritization with a differentiable loss that approximates the optimizer's cost model and dynamic-programming plan search as a flow-routing problem on a 'plan graph'; it evaluated this loss on two architectures — a fully connected neural network (FCNN) in the style of Ortiz et al., and the multi-set convolutional network (MSCN) of Kipf et al., which encodes a query as sets of table, join, and predicate features — across PostgreSQL and MySQL, on the Cardinality Estimation Benchmark (CEB), an expanded 16K-query benchmark over IMDb and StackExchange, and measured a 3–5× training-time overhead for the loss. It also demonstrated the AQP direction: a modified wander join supplies training cardinalities 10–100× faster than exact ground truth, with models trained on these noisy estimates (especially Flow-Loss models) performing nearly as well as when trained on true cardinalities. The original Plan-Error prioritization scheme was retained only as a baseline ('Prioritized Q-Error') and shown to be clearly inferior to Flow-Loss with respect to plan cost, so the Plan-Error-specific questions (its training-time behavior, convergence dynamics, and the α\alpha/window sensitivity analysis) are superseded for the differentiable-loss lineage; prioritization-based objectives nevertheless remain admissible as plan-aware training schemes in their own right. Flow-Loss also states its own scope explicitly: it targets supervised parametric models, and mentions unsupervised (data-driven) estimators only as possible providers of cardinality estimates used as features by a query-driven model. Independently, Han et al. (VLDB 2021) benchmarked many CE methods inside a real database management system (DBMS) and proposed P-Error, a plan-error-like evaluation metric, concluding that Q-Error cannot reflect end-to-end plan quality; Kim et al. (SIGMOD 2022) compared learned estimators including their impact on query optimization; Izenov et al. (SIGMOD 2024) proposed the L1-error permutation distance for identifying sub-optimal join orders; and Mandarapu and Kunkunuru (arXiv 2026) gave a regime-dependent theory of when q-error predicts plan regret. These works develop the evaluation side of 'which errors matter' but do not extend plan-aware training: no published work applies cost-guided or plan-aware training to the local models of Woltmann et al. (one model per table or schema rather than a single global model for the whole database) or to query-driven architectures beyond the FCNN and MSCN evaluated in Flow-Loss.

Problem Statement

Establish whether cost-guided (plan-aware) training of learned cardinality estimators is a generally applicable improvement, and at what practical cost. Concretely: expand the experimental study of cost-guided training to more recent learned cardinality estimation models beyond those already evaluated — covering both the local per-schema models of Woltmann et al. (one model per table or schema rather than one global model for the whole database) and at least one query-driven architecture other than the FCNN and MSCN covered by Flow-Loss — and determine whether training with an optimizer-aware objective (a plan-cost-based loss in the lineage of Plan-Error and Flow-Loss, or the source's Plan-Error-based prioritized sampling of training sub-queries) yields better plan quality (optimizer plan cost) and end-to-end query runtimes than accuracy-based training (Q-Error), across more than one DBMS/optimizer and workload; and measure the training time that such plan-aware training requires relative to Q-Error training for the models studied. This is the open question left by Negi et al. (ICDEW 2020): whether cost-guided learning generalizes beyond the architectures and systems in which it has so far been demonstrated (FCNN and MSCN on PostgreSQL and MySQL, and the Flow-Loss wander-join proof of concept for cheap approximate training data). The enumerated study is sufficient scope: the task is resolved by its reported outcome over that coverage — the extent of generality demonstrated and the training-time cost measured — and not by a class-level guarantee of generality beyond it. Training-data acquisition by approximate query processing, the trend of the Plan-Error metric over training, and a sensitivity study of the prioritization exponent α\alpha and the moving-average window are out of scope; prioritization-based plan-aware objectives remain admissible.

References

  1. Parimarjan Negi, Ryan Marcus, Hongzi Mao, Nesime Tatbul, Tim Kraska, Mohammad Alizadeh. Cost-Guided Cardinality Estimation: Focus Where it Matters. In 2020 IEEE 36th International Conference on Data Engineering Workshops (ICDEW), IEEE, 2020, pp. 154–157. DOI: 10.1109/ICDEW49219.2020.00034. https://doi.org/10.1109/ICDEW49219.2020.00034 (author-hosted full text: https://parimarjan.github.io/papers/focus.pdf)
  2. Parimarjan Negi, Ryan Marcus, Andreas Kipf, Hongzi Mao, Nesime Tatbul, Tim Kraska, Mohammad Alizadeh. Flow-Loss: Learning Cardinality Estimates That Matter. Proceedings of the VLDB Endowment, 14(11): 2019–2032, 2021. DOI: 10.14778/3476249.3476259. https://www.vldb.org/pvldb/vol14/p2019-negi.pdf (also arXiv:2101.04964, https://arxiv.org/abs/2101.04964)
  3. Lucas Woltmann, Claudio Hartmann, Maik Thiele, Dirk Habich, Wolfgang Lehner. Cardinality estimation with local deep learning models. In Proceedings of the Second International Workshop on Exploiting Artificial Intelligence Techniques for Data Management (aiDM@SIGMOD 2019), 2019, pp. 1–8. DOI: 10.1145/3329859.3329875. https://doi.org/10.1145/3329859.3329875
  4. Jennifer Ortiz, Magdalena Balazinska, Johannes Gehrke, S. Sathiya Keerthi. An Empirical Analysis of Deep Learning for Cardinality Estimation. arXiv preprint arXiv:1905.06425, 2019. https://arxiv.org/abs/1905.06425
  5. Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, Alfons Kemper. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. CIDR 2019. https://www.cidrdb.org/cidr2019/papers/p101-kipf-cidr19.pdf
  6. Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Jiangneng Li, Bin Cui. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. Proceedings of the VLDB Endowment, 14(4): 752–765, 2021. DOI: 10.14778/3503585.3503586. https://doi.org/10.14778/3503585.3503586
  7. Kyoungmin Kim, Jisung Jung, In Seo, Wook-Shin Han, Kangwoo Choi, Jaehyok Chong. Learned Cardinality Estimation: An In-depth Study. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD 2022), 2022, pp. 1214–1227. DOI: 10.1145/3514221.3526154. https://doi.org/10.1145/3514221.3526154
  8. Parimarjan Negi, Ziniu Wu, Andreas Kipf, Nesime Tatbul, Ryan Marcus, Sam Madden, Tim Kraska, Mohammad Alizadeh. Robust Query Driven Cardinality Estimation under Changing Workloads. Proceedings of the VLDB Endowment, 16(7): 1520–1533, 2023. DOI: 10.14778/3583140.3583164. https://doi.org/10.14778/3583140.3583164
  9. Yesdaulet Izenov, Asoke Datta, Brian Tsan, Florin Rusu. Sub-optimal Join Order Identification with L1-error. Proceedings of the ACM on Management of Data (SIGMOD 2024), 2(1), 2024. DOI: 10.1145/3639272. https://doi.org/10.1145/3639272
  10. Madhulatha Mandarapu, Sandeep Kunkunuru. When Does q-error Predict Plan Regret? Three Regimes of Cardinality-Estimation Error. arXiv preprint arXiv:2606.15600, 2026. https://arxiv.org/abs/2606.15600
  11. Yannis Chronis, Yawen Wang, Yu Gan, Sami Abu-El-Haija, Chelsea Lin, Carsten Binnig, Fatma Özcan. CardBench: A Benchmark for Learned Cardinality Estimation in Relational Databases. arXiv preprint arXiv:2408.16170, 2024. https://arxiv.org/abs/2408.16170
  12. Parimarjan Negi, Matteo Interlandi, Ryan Marcus, Mohammad Alizadeh, Tim Kraska, Marc Friedman, Alekh Jindal. Steering Query Optimizers: A Practical Take on Big Data Workloads. In Proceedings of the 2021 International Conference on Management of Data (SIGMOD 2021), 2021. DOI: 10.1145/3448016.3457568. https://doi.org/10.1145/3448016.3457568
  13. Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Alizadeh, Tim Kraska. Bao: Making Learned Query Optimization Practical. In Proceedings of the 2021 International Conference on Management of Data (SIGMOD 2021), 2021. DOI: 10.1145/3448016.3452838. https://doi.org/10.1145/3448016.3452838
  14. Laurent Bindschaedler, Andreas Kipf, Tim Kraska, Ryan Marcus, Umar Farooq Minhas. Towards a Benchmark for Learned Systems. In 2021 IEEE 37th International Conference on Data Engineering Workshops (ICDEW), 2021. DOI: 10.1109/ICDEW53142.2021.00029. https://doi.org/10.1109/ICDEW53142.2021.00029
  15. Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, Thomas Neumann. How Good Are Query Optimizers, Really? Proceedings of the VLDB Endowment, 9(3): 204–215, 2015. DOI: 10.14778/2850583.2850594. https://doi.org/10.14778/2850583.2850594
  16. Feifei Li, Bin Wu, Ke Yi, Zhuoyue Zhao. Wander Join: Online Aggregation via Random Walks. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD 2016), 2016, pp. 615–629. DOI: 10.1145/2882903.2915235. https://doi.org/10.1145/2882903.2915235