🤖 machine learning

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

This paper demonstrates that while q-error is a poor predictor of query-plan regret for large cardinality estimation errors typical of learned estimators, a new metric called ACS-infinity effectively identifies regret-prone queries by characterizing the geometry of the plan-cost landscape across three distinct error regimes.

Original authors: Madhulatha Mandarapu, Sandeep Kunkunuru

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Madhulatha Mandarapu, Sandeep Kunkunuru

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to navigate a city to get to a destination as quickly as possible. You have a map (the database query optimizer) and a GPS (the cardinality estimator) that tells you how many cars are on each road.

The problem is that your GPS is sometimes wrong. Sometimes it thinks a road is empty when it's actually jammed, or vice versa. When the GPS is wrong, you might pick a route that takes 30 minutes instead of the optimal 3 minutes. This difference is called "plan regret."

For a long time, researchers tried to measure how "bad" the GPS was using a single number called q-error. They assumed that if the q-error was low, your route would be good. But this paper argues that q-error is a terrible predictor of whether you'll get stuck in traffic, especially when the GPS is really bad.

Instead, the authors found that the answer depends entirely on how big the mistake is. They discovered three different "regimes" (situations) where different rules apply.

The Three Regimes of Navigation

1. The "Small Mistake" Zone (The Tightrope)

When the GPS is mostly right, but slightly off.

Imagine you are walking on a tightrope between two buildings. If you take one tiny step to the left, you fall into Building A. If you take one tiny step to the right, you fall into Building B.

The Paper's Finding: In this situation, the most important thing isn't how accurate your GPS is, but how close you are to the edge.
The Metaphor: They call this the Condition Number ( $\kappa$ ). It's like measuring the distance from your feet to the nearest railing.
- If you are far from the edge, a small GPS error won't matter; you'll stay on the right path.
- If you are standing right on the edge, even a tiny GPS error will make you fall into the wrong building.
Why it matters: In this zone, knowing where you are relative to the "switching point" predicts your failure better than knowing how wrong your GPS is.

2. The "Huge Mistake" Zone (The Dice Roll)

When the GPS is completely hallucinating.

Now imagine the GPS is so broken that it sends you to a random part of the city, far away from your actual destination. You aren't walking on a tightrope anymore; you are just guessing which building to enter.

The Paper's Finding: In this chaotic zone, your distance to the edge (Condition Number) doesn't matter anymore. Instead, what matters is how "risky" the city layout is for this specific trip.
The Metaphor: They call this ACS∞ (Average-Case Sub-optimality). Think of it as a "Difficulty Score" for the query.
- Some queries are like a city with only one good road; even if you guess randomly, you might still get lucky.
- Other queries are like a city with 100 roads, but 99 of them lead to a dead end or a traffic jam. If your GPS is broken, you are almost guaranteed to pick a bad road.
The Surprise: The authors tested this on real-world data and found that q-error was useless here (it couldn't predict anything). But their new "Difficulty Score" (ACS∞) successfully predicted which queries would fail. It's like saying, "This specific trip is inherently dangerous if your map is wrong," regardless of exactly how wrong the map is.

3. The "Worst-Case" Zone (The Nightmare)

When you want to be 100% safe.

This is the scenario where you assume the GPS will make the absolute worst possible mistake imaginable.

The Paper's Finding: This is known as MSO (Maximum Sub-optimality). It's the "worst-case scenario" metric that researchers have used before.
The Connection: The authors show that all three of these concepts (Condition Number, Difficulty Score, and Worst-Case) are actually just different ways of looking at the same underlying map. They are just weighting the "badness" of the roads differently:
- Small errors: Focus on the nearest bad road.
- Large errors: Focus on the average bad road.
- Worst case: Focus on the most bad road.

The Big Takeaway

The paper solves a long-standing debate in the database world: "Does a lower q-error mean a better plan?"

The answer is: It depends.

If your estimation errors are tiny, q-error doesn't matter as much as your proximity to a decision boundary.
If your estimation errors are huge (which is where modern AI-based estimators often operate), q-error is almost useless. It tells you nothing about whether you'll get stuck in traffic.

Instead, for big errors, we need a new metric (ACS∞) that measures the inherent difficulty of the query itself. The authors proved this mathematically and tested it on real database software (PostgreSQL), showing that their new metric predicts real-world slowdowns much better than the old standard.

In short: You can't use a single ruler to measure everything. When the map is slightly off, you need to know how close you are to the cliff. When the map is totally broken, you need to know if the terrain itself is a minefield. The paper gives us the right tool for each job.

Technical Summary: When Does q-error Predict Plan Regret?

Problem Statement

The field of cardinality estimation (CE) traditionally ranks estimators using q-error ( $\max(\hat{c}/c, c/\hat{c})$ ). While q-error offers a worst-case guarantee that bounding the maximum error over sub-expressions bounds plan sub-optimality, empirical evidence suggests this bound is often loose and impractical. Specifically, large improvements in q-error do not consistently translate to better query plans, and conversely, large q-errors do not always result in poor plans. The core problem addressed is determining when q-error serves as a reliable proxy for plan regret (the cost ratio of the chosen plan to the optimal plan under true cardinalities) and identifying what metric predicts regret when q-error fails.

Methodology

The authors model plan selection as an $\text{argmin}$ operation over a piecewise-linear cost landscape (in log-cardinality space). They analyze the relationship between estimation error and plan regret across three distinct regimes defined by the magnitude of the error ( $\sigma$ ):

Small-Error Regime: The estimation error is small enough that the estimated cardinalities remain within the "plan-optimality cell" of the true optimal plan.
- Metric: A per-query condition number ( $\kappa$ ), defined as the inverse of the distance to the nearest plan-switch boundary (where the cost of the optimal plan equals the cost of an alternative).
- Hypothesis: Regret is governed by local geometry; $\kappa$ predicts regret only when the error is small enough for local linearization to hold.
Large-Error Regime: The estimation error is large (typical of deployed learned estimators), causing the estimate to land in any cell within the cost landscape, far from the true optimal cell.
- Metric: Average-Case Sub-optimality ( $ACS_\infty$ ). This is defined as the limit of the expected regret as error variance approaches infinity ( $\sigma \to \infty$ ).
- Hypothesis: In this regime, local quantities like $\kappa$ and q-error become uninformative. Instead, regret is predicted by the "typical badness" of a random plan for a specific query, independent of the specific estimator used.
Worst-Case Regime: The theoretical upper bound of sub-optimality.
- Metric: Maximum Sub-optimality (MSO), defined as $\max_k r_k$ , where $r_k$ is the true cost ratio of plan $k$ to the optimal plan.

The authors derive a limit law showing that $ACS_\infty$ can be expressed as a weighted sum of the true cost-ratio spectrum ( $\{r_k\}$ ) with cardinality-independent combinatorial weights ( $\pi_k$ ):
$ACS_\infty(q) = \sum_{k} r_k \pi_k$
This contrasts with MSO, which uses a max-weighting, and $\kappa$ , which uses a nearest-gap weighting.

Experimental Setup

Datasets: STATS-CEB (where estimators are known to be inaccurate) and JOB-light (IMDB schema).
Estimators: Four released estimators (BayesCard, DeepDB, FLAT, NeuroCard) and the native DuckDB optimizer.
Validation:
- Synthetic: Error injection with varying $\sigma$ to test regime transitions.
- Real-World: Injecting estimator cardinalities into PostgreSQL 13.1 to measure actual runtime regret, comparing it against the theoretical $C_{out}$ model predictions.
Rigor: The study utilizes pre-registered decision rules, including a rejected hypothesis and a "near-miss" kept on record, to ensure statistical validity.

Key Results

1. The Small-Error Regime

The condition number $\kappa$ strongly predicts plan regret (Spearman $\rho \approx 0.70$ on STATS-CEB, $0.79$ on JOB-light).
$\kappa$ outperforms q-error in this regime.
As error magnitude ( $\sigma$ ) increases, the predictive power of $\kappa$ decays to zero, confirming its nature as a local linearization tool.

2. The Large-Error Regime

In the regime where deployed learned estimators operate (median q-error 2 to $10^5$ ), q-error is nearly uninformative for predicting query-level regret ( $\rho \approx 0.05$ ).
$ACS_\infty$ is the superior predictor: It achieves a Spearman correlation of $\rho \approx 0.54$ with query regret on STATS-CEB, significantly outperforming both q-error and $\kappa$ ( $\rho \approx 0.20$ ).
PostgreSQL Validation: When tested against actual PostgreSQL runtimes, $ACS_\infty$ (computed purely from $C_{out}$ geometry without seeing the DB) predicts runtime regret with $\rho = 0.42$ , whereas q-error shows a negative correlation ( $\rho = -0.16$ ).

3. The Limit Law

The paper proves that as $\sigma \to \infty$ , the optimizer's selection converges to a cardinality-free minimax-rank rule.
$ACS_\infty$ factorizes into the true cost-ratio spectrum and combinatorial weights determined solely by the plan set-system, making it an estimator-independent measure of query difficulty.

Claims and Significance

The paper modestly claims to provide a conceptual and empirical reconciliation of the "q-error vs. plan-cost" tension, rather than proposing a new estimator.

Regime-Dependent Prediction: The paper establishes that no single scalar metric (like q-error) can predict plan regret across all error magnitudes. The predictive power depends entirely on the error regime:
- Small Error: Predicted by Condition Number ( $\kappa$ ).
- Large Error: Predicted by Average-Case Sub-optimality ( $ACS_\infty$ ).
- Worst Case: Bounded by Maximum Sub-optimality (MSO).
Geometric Insight: These three metrics are revealed to be different weightings of the same underlying plan cost-ratio spectrum ( $\{r_k\}$ ).
Practical Implication: For deployed learned estimators (which operate in the large-error regime), q-error is a poor indicator of plan quality. $ACS_\infty$ serves as a companion to worst-case robust query optimization, offering an average-case measure of which queries are inherently "regret-prone" due to their plan-cost geometry, regardless of the specific estimator used.

The authors emphasize that their contribution is the characterization of when accuracy metrics track plan quality and the introduction of $ACS_\infty$ as a query-level difficulty measure, validated through rigorous pre-registration and real-world runtime testing.