Cost-based query optimizers select join orders and physical operators using cardinality estimates, yet a 2023 experimental study (Datta, Tsan, Izenov, Rusu) found on the Join Order Benchmark that the gap between optimizing with true cardinalities, with PostgreSQL's estimates, and with no estimates at all is marginal in highly parallel main-memory settings and in non-indexed settings whose optimizer is confined to hash joins, while in native non-indexed runs with unrestricted operator choice underestimation already drove the estimate-based method to 104 nested-loop joins and the slowest runtimes of the three methods; that with indexes, inaccurate estimates lead to suboptimal physical operators (index scans, nested-loop joins) even when the join order is optimal; and that exhaustive search makes optimization time explode with join count while statistics-free heuristics stay flat. The open problem asks for (i) a characterization of the conditions — schema shape, data skew and correlation, physical design and enabled operator repertoire, parallelism, system — under which cardinality-estimate accuracy does or does not determine plan quality, beyond the single JOB/IMDB evaluation; (ii) plan construction (join ordering together with physical operator selection) that is robust to absent or wrong estimates and avoids large-cost outliers in indexed environments; and (iii) criteria for choosing the enumeration strategy (exhaustive dynamic programming versus heuristics) as query complexity grows.

Background

A relational query optimizer must choose an execution plan for a SQL query: an order in which to join the tables (the join order) and a physical operator for each step, for example a hash join, a nested-loop join, an index scan, or a sequential (full-table) scan. Cost-based optimizers score candidate plans with a cost model whose dominant input is cardinality estimation (CE) — predicting how many rows each intermediate result will contain. Systems such as PostgreSQL estimate cardinalities from synopses — compact data summaries such as histograms — which rely on simplifying assumptions (uniform value distributions, independence of predicates) that real data violate, so multi-table estimates can be wrong by orders of magnitude. The seminal study of Leis et al. (PVLDB 2015) introduced the Join Order Benchmark (JOB) — 113 queries over the real, skewed, correlated Internet Movie Database (IMDB) schema — and showed that cardinality-estimation errors are widespread and that their impact on plan quality is more pronounced when more indexes are available; injecting true cardinalities (the TrueCard experiment) isolates the estimator's contribution from the cost model and the enumeration strategy. A later line of work asked how much of query optimization can be done with no estimates at all: Hertzschuch et al.'s Simplicity (CIDR 2021) derives join orders from PostgreSQL statistics without pessimistic sketches (conservative worst-case row-count summaries), and Simpli² (Datta, Izenov, Tsan, Rusu, arXiv 2021) computes a join order using only the declared foreign-key constraints (which tables reference which) and base-table sizes. The technical report (Datta, Tsan, Izenov, Rusu, arXiv:2311.17293, 2023; republished with the same findings at the SiMoD@SIGMOD 2024 workshop) compares TrueCard, PostgreSQL's CE, and a no-CE method based on Simpli² on JOB under indexed, non-indexed, and multi-threaded configurations, and inside DuckDB, Heavy.AI, and MonetDB. Its findings: in the native non-indexed setting, where the planner is free to choose among hash, merge, and nested-loop operators, underestimation made the CE method opt for nested-loop joins in 104 of JOB's 864 join operations and made CE the slowest approach — approximately fivefold and 5.8-fold slower than no-CE and TrueCard respectively, with six queries hitting the 300-second timeout; when the optimizer is confined to hash joins exclusively (the restriction the report adopts as the standard for non-indexed settings in the remainder of the paper), CE and no-CE stay close to TrueCard — cumulative cost ratios of 1.01 (CE) and 1.68 (no-CE), and runtime ratios of 1.07 and 1.28 — because the plan-cost landscape is clustered, and the expensive clusters are those that join two foreign-key tables early, which both CE and the no-CE heuristic avoid; with indexes, inaccurate estimates lead to suboptimal physical operators even with an optimal join order — on one query-18a subplan, degrading operator choices raised runtime from 0.45 s to 2.9 s; in highly parallel main-memory databases the impact of estimates is negligible; and the optimization time of exhaustive CE search grows sharply with the number of joins (PostgreSQL switches from exhaustive dynamic programming (DP) to a genetic-algorithm heuristic above a fixed join-count threshold, and the authors state that fine-tuning this transition threshold is crucial), whereas the greedy no-CE heuristic's planning time stays nearly constant. An earlier, pre-dating result on the operator half of the question is TONIC (Hertzschuch et al., PVLDB 2022), a learned, cardinality-estimation-free extension that revises physical join-operator choices from observed execution feedback — evidence that estimation-robust operator selection is feasible but was not a solved problem. What no existing work provides is a systematic answer to when estimate accuracy actually matters, or a plan-construction strategy validated to be robust across schemas, workloads, and system settings.

Problem Statement

The study established, on the single JOB/IMDB workload, that (a) plan quality is nearly insensitive to cardinality-estimate accuracy in non-indexed and highly parallel main-memory settings when the optimizer's operator choices are confined to hash joins, whereas in native non-indexed runs with unrestricted operator choice, underestimated cardinalities already induce harmful nested-loop-join selections, (b) the dominant harm of estimation error is the choice of suboptimal physical operators (for example, nested-loop joins and index scans chosen because of underestimated cardinalities) even when the join order is optimal, most acutely in indexed settings, and (c) exhaustive cost-based search makes optimization time grow sharply with the number of joins while statistics-free heuristics keep it flat, making the transition threshold between exhaustive dynamic programming and heuristic or genetic search a tuning decision. The open problem is to turn these observations into general knowledge and general machinery: (1) characterize, empirically and ideally with predictive criteria, the conditions — schema shape and size, data skew and correlation patterns, physical design and enabled operator repertoire (indexed versus non-indexed; unrestricted versus hash-join-only operator choice; rowstore versus columnstore, i.e. tables stored row-by-row versus column-by-column), degree of parallelism, and database system — under which cardinality-estimate accuracy does or does not determine end-to-end query performance, going beyond the JOB/IMDB evaluation; (2) given that characterization, construct a plan-selection method (join ordering together with physical operator selection, possibly with runtime adaptation) that remains close to true-cardinality plan quality when estimates are absent or unreliable, and in particular avoids the large-cost outliers that estimation errors cause in indexed environments, without regressing queries that the current optimizer already plans well; and (3) determine criteria, in the presence or absence of reliable estimates, for when an optimizer should use exhaustive enumeration, heuristics, or an intermediate strategy, so that planning time does not dominate execution time as query complexity grows. The three components serve one objective — making query plan construction provably or demonstrably robust to the quality of cardinality estimates.

References

  1. Asoke Datta, Brian Tsan, Yesdaulet Izenov, Florin Rusu. "Analyzing Query Optimizer Performance in the Presence and Absence of Cardinality Estimates." Technical report, arXiv:2311.17293, 2023. DOI: 10.48550/arXiv.2311.17293. https://arxiv.org/abs/2311.17293
  2. Asoke Datta, Brian Tsan, Yesdaulet Izenov, Florin Rusu. "Simpli-Squared: Optimizing Without Cardinality Estimates." Proceedings of the 2nd Workshop on Simplicity in Management of Data (SiMoD@SIGMOD), pp. 1-10, 2024. DOI: 10.1145/3663351.3663879. https://doi.org/10.1145/3663351.3663879
  3. Asoke Datta, Yesdaulet Izenov, Brian Tsan, Florin Rusu. "Simpli-Squared: A Very Simple Yet Unexpectedly Powerful Join Ordering Algorithm Without Cardinality Estimates." arXiv:2111.00163, 2021. DOI: 10.48550/arXiv.2111.00163. https://arxiv.org/abs/2111.00163
  4. 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
  5. Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, Thomas Neumann. "Still Asking: How Good Are Query Optimizers, Really?" Proceedings of the VLDB Endowment 18(12):5531-5536, 2025. DOI: 10.14778/3750601.3760521. https://www.vldb.org/pvldb/vol18/p5531-viktor.pdf
  6. Kukjin Lee, Anshuman Dutt, Vivek R. Narasayya, Surajit Chaudhuri. "Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server." Proceedings of the VLDB Endowment 16(11):2871-2883, 2023. DOI: 10.14778/3611479.3611494. https://www.vldb.org/pvldb/vol16/p2871-dutt.pdf
  7. Axel Hertzschuch, Claudio Hartmann, Dirk Habich, Wolfgang Lehner. "Simplicity Done Right for Join Ordering." Proceedings of the 8th Biennial Conference on Innovative Data Systems Research (CIDR), 2021. https://www.cidrdb.org/cidr2021/papers/cidr2021_paper01.pdf
  8. Axel Hertzschuch, Claudio Hartmann, Dirk Habich, Wolfgang Lehner. "Turbo-charging SPJ Query Plans with Learned Physical Join Operator Selections." Proceedings of the VLDB Endowment 15(11):2706-2718, 2022. DOI: 10.14778/3551793.3551825. https://doi.org/10.14778/3551793.3551825
  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 2(1):1-24, SIGMOD 2024. DOI: 10.1145/3639272. https://doi.org/10.1145/3639272
  10. Asoke Datta, Yesdaulet Izenov, Brian Tsan, Abylay Amanbayev, Florin Rusu. "PLANSIEVE: Real-time Suboptimal Query Plan Detection Through Incremental Refinements." arXiv:2501.16544, 2025. DOI: 10.48550/arXiv.2501.16544. https://arxiv.org/abs/2501.16544
  11. Yesdaulet Izenov, Asoke Datta, Brian Tsan, Abylay Amanbayev, Florin Rusu. "Spanning Tree-based Query Plan Enumeration." arXiv:2403.04026, 2024. DOI: 10.48550/arXiv.2403.04026. https://arxiv.org/abs/2403.04026
  12. Madhulatha Mandarapu, Sandeep Kunkunuru. "When Does q-error Predict Plan Regret? Three Regimes of Cardinality-Estimation Error." arXiv:2606.15600, 2026. DOI: 10.48550/arXiv.2606.15600. https://arxiv.org/abs/2606.15600
  13. Mihail Stoian, Tiemo Bang, Hangdong Zhao, Jesús Camacho-Rodríguez, Yuanyuan Tian, Andreas Kipf. "The Case for Cardinality Lower Bounds." arXiv:2601.13117, 2026. DOI: 10.48550/arXiv.2601.13117. https://arxiv.org/abs/2601.13117
  14. 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 15(4):752-765, 2021 (arXiv:2109.05877). DOI: 10.14778/3503585.3503586. https://www.vldb.org/pvldb/vol15/p752-zhu.pdf
  15. Roman Heinrich, Manisha Luthra, Johannes Wehrstein, Harald Kornmayer, Carsten Binnig. "How Good are Learned Cost Models, Really? Insights from Query Optimization Tasks." arXiv:2502.01229, 2025. DOI: 10.48550/arXiv.2502.01229. https://arxiv.org/abs/2502.01229
  16. Hyunjoon Kim, Chaerim Lim, Hyeonjun An, Rathijit Sen, Kwanghyun Park. "Exqutor: Extended Query Optimizer for Vector-Augmented Analytical Queries." 2026 IEEE 42nd International Conference on Data Engineering (ICDE), pp. 72-86, 2026 (arXiv:2512.09695). DOI: 10.1109/ICDE65706.2026.00013. https://arxiv.org/abs/2512.09695