When Does q-error Predict Plan Regret? Three Regimes of Cardinality-Estimation Error

2026-06-14 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, quick

Summary

A new analysis investigates when q-error, a standard metric for cardinality-estimation (CE) research, accurately predicts query-plan quality, or "plan regret." The study identifies three distinct regimes of cardinality-estimation error. For small errors, a true-point condition number kappa predicts regret better than q-error, though its predictive power diminishes as error grows. In the regime of large errors, where many deployed learned estimators operate, q-error is largely uninformative (Spearman rho ~ 0.05). Instead, an estimator-independent average-case sub-optimality measure, ACS-infinity, effectively predicts regret-prone queries (Spearman rho ~ 0.54 on STATS-CEB). The worst-case scenario is characterized by Haritsa's maximum sub-optimality (MSO). The research validates these findings on STATS-CEB and JOB-light datasets using four released estimators. It confirms ACS-infinity's predictive power on real PostgreSQL runtime, offering a conceptual and empirical contribution to robust query optimization.

Key takeaway

Database engineers optimizing query performance should recognize q-error is an unreliable metric for plan quality in scenarios with large cardinality estimation errors. Instead, focus on average-case sub-optimality measures like ACS-infinity. These demonstrably predict regret-prone queries, especially when using learned estimators. This insight suggests re-evaluating your current optimization strategies. Integrate ACS-infinity into evaluation frameworks for more robust query plans.

Key insights

The relationship between q-error and plan regret varies across three error regimes, with ACS-infinity being key for large errors.

Principles

• Plan regret is governed by plan-cost geometry.
• q-error is uninformative for large CE errors.
• ACS-infinity predicts regret-prone queries.

Topics

• Cardinality Estimation
• Query Optimization
• Plan Regret
• q-error
• ACS-infinity
• Database Performance
• Learned Estimators

Best for: AI Scientist, Research Scientist, Machine Learning Engineer

Related on AIssential

• Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret — Selectivity-estimation error causes significant plan regret in filtered ANN queries, especially near strategy phase boundaries.
• The Role of Ambiguity in Error Prediction via Uncertainty Quantification — Disentangling input ambiguity from UQ signals significantly improves LLM error prediction, especially for Question Answering tasks.
• Why are there squares everywhere in statistics (e.g., normal density, variance, least squares, etc.)? — The mean minimizes square error, while the median minimizes absolute error, foundational to statistical distributions.
• Regret-Based $(ε,δ)$-optimal Stopping Criteria for Bayesian Optimization — New regret bounds enable provably optimal stopping for Bayesian Optimization, ensuring ε-optimality with high probability.
• Revisiting Active Sequential Prediction-Powered Mean Estimation — Optimal confidence width in active sequential prediction-powered mean estimation favors a high constant query probability.
• Bulk-Calibrated Credal Ambiguity Sets: Fast, Tractable Decision Making under Out-of-Sample Contamination — Bulk-calibrated credal ambiguity sets enable tractable, finite worst-case risk in Huber contamination models for robust decision-making.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.