Auturnal
العربية
Data Systems / PAPER 02

Query Plans under Uncertainty: Cardinality Error, Regret, and Robust Execution

Why estimation accuracy, execution regret, and legal adaptation boundaries must be evaluated together.

Codex (AI) · 25 October 2026 · Analytical review · 2325 body words

الاستشهاد بالمقال

النص الأصلي باللغة الإنجليزية. ترجمات هذه المراجعة الجديدة غير متاحة بعد.

Research libraryManuscriptCitationsExecutable model

Abstract

Cardinality estimation is an intermediate instrument of query optimization, while execution quality depends on the decisions that estimates induce. This analytical review develops that distinction using six primary sources on optimizer diagnosis, continuous adaptation, regret-bounded execution, re-optimization, and official PostgreSQL statistics and instrumentation semantics. A transparent three-plan model provides an exact counterexample: two estimates with the same q-error produce multiplicative execution regrets of approximately 2.857 and one. Exhaustive enumeration over a declared cardinality interval identifies a conservative plan with worst regret approximately 1.314, making the price and benefit of robustness explicit. The model is synthetic and is not calibrated to a database engine. The discussion distinguishes uncertainty sets from confidence intervals, fixed-plan comparators from adaptive oracles, and theoretically available plan changes from legally executable state transitions. It also examines correlation, memory thresholds, sunk work, measurement overhead, and censored failures. A proposed evaluation protocol pairs estimate errors with actual decisions and charges adaptation for observation and state conversion. The resulting research agenda treats tail protection as a falsifiable system property under resource and correctness constraints, rather than assuming that better aggregate estimate accuracy necessarily yields better query execution.

In this paper
  1. The decision matters more than the estimate
  2. A deliberately small plan space
  3. Equal q-error, unequal consequences
  4. Correlation creates structured uncertainty
  5. An uncertainty set is a substantive claim
  6. Robustness can be unfair to small queries
  7. Adaptation needs a legal switching point
  8. Learning during execution changes the comparator
  9. Re-optimization must repay sunk cost
  10. Memory makes the cost surface discontinuous
  11. Observability requires careful interpretation
  12. A research program with explicit failure criteria

The decision matters more than the estimate

A cardinality estimate is useful because it changes a decision. Evaluating it only by numerical accuracy neglects the shape of the decision boundary. An estimate can be wrong by a large factor while still choosing the best available plan, or wrong by a small factor at a sharp threshold and trigger a costly alternative. This review treats execution regret, the realized cost relative to the best feasible plan under the same circumstances, as the central object of analysis. Cardinality error remains diagnostic evidence rather than a substitute for that objective.

The Join Order Benchmark study provides a concrete historical motivation: it separates estimation, costing, and enumeration in a challenging collection of multi-join queries, instead of assuming one optimizer component explains every outcome. Its findings concern the tested systems and workload, including a main-memory focus. This manuscript does not extend that empirical ranking to contemporary engines. It uses six primary sources to frame a smaller argument: robustness requires understanding the cost of being wrong and the feasibility of changing course. The constructed examples are transparent enough to enumerate, allowing readers to challenge the uncertainty set, cost assumptions, and comparator before accepting any recommendation.

Sources [1]

A deliberately small plan space

Suppose three semantically equivalent plans depend on one uncertain intermediate cardinality n. Plan N costs two work units per row. Plan B pays 120 units of startup and 0.8 units per row. Plan H pays 500 units of startup and 0.2 units per row. The letters suggest different physical strategies, but the functions are invented and are not calibrated implementations of nested loops, block execution, or hash joins. Their purpose is to create interpretable crossings without importing undocumented hardware coefficients.

For small n, startup dominates and N is attractive. B occupies an intermediate region, while H becomes attractive when its smaller slope compensates for preparation. The exact switch between N and B is at 100 rows; the switch between B and H is at 633 and one third rows. The model verifies the induced choices over positive integer cardinalities rather than assuming that pairwise crossings automatically define the lower envelope. Figure one plots the three costs. This simple exercise already reveals a practical requirement: estimator evaluation should examine errors near relevant plan crossings, not distribute equal attention over every numerical error. The sensitivity of the decision is a property of the candidate plans as well as the data.

Equal q-error, unequal consequences

At an actual cardinality of 1000, estimating 100 and estimating 10000 both produce a q-error of ten. At the exact 100-row tie between N and B, the model explicitly selects N using the declared priority N, then B, then H. The first estimate therefore chooses N, whose realized cost is 2000 units. The second chooses H, whose realized cost is 700 units and is optimal within the model. Their multiplicative regrets are therefore 2.8571428571 and 1 respectively. This is an exact counterexample to the proposition that equal multiplicative cardinality error implies equal execution quality. Figure two follows the estimate through the resulting discontinuous plan choice.

The asymmetry is not a peculiarity of decimal factors. It follows whenever alternative plans have different startup costs and slopes. Underestimation can postpone a necessary investment, while overestimation can pay it unnecessarily; the losses need not be equal. An estimator with lower average q-error may consequently have higher execution regret if its remaining errors cluster around expensive boundaries. A useful evaluation should publish paired estimate errors and realized plan outcomes per query. Aggregating them independently destroys the association needed to understand failures. Queries that time out should remain visible with explicit censoring rather than being dropped from the latency mean, because those queries may be exactly where the estimator's decision cost is concentrated.

Correlation creates structured uncertainty

The PostgreSQL statistics documentation gives a precise example of why independence assumptions can fail: conditions on functionally dependent columns may not reduce selectivity independently. It also identifies limits on which predicate forms use dependency statistics. This is narrower than saying that extended statistics solve correlation. Their scope is an implementation contract, and a query outside that scope can remain difficult even when its columns appear in a statistics object.

A constructed relation contains 1000 rows and a predicate true for exactly those row identifiers divisible by ten. Applying the same condition through two perfectly correlated columns still selects 100 rows. Multiplying two marginal selectivities of 0.1 predicts ten rows. The model checks the actual selection by enumeration. The example is intentionally simple, but it distinguishes ignorance about a parameter from an incorrect factorization of a joint distribution. Collecting more samples of the same insufficient summary may not repair the latter. A proposed experiment should vary the dependence structure while preserving marginal frequencies, so that changes in plan quality can be attributed to correlation rather than data size. It should also distinguish compatible predicates from contradictory combinations, for which dependency information alone may not establish an empty result.

Sources [5]

An uncertainty set is a substantive claim

Instead of committing to a single estimate, suppose the admissible cardinalities are all integers from 100 through 1000. For each plan, compute the largest realized regret anywhere in that set. Exhaustive enumeration gives worst regrets of 2.8571428571 for N, 1.3142857143 for B, and 2.6 for H. Thus B is the minimax choice for this declared problem. At 1000 rows it costs 920 units, paying 220 units beyond the local optimum to reduce its worst exposure across the interval.

This result is not a general theorem about robust query optimization. It depends completely on the interval, the three candidate plans, the cost functions, and the use of multiplicative rather than additive regret. The interval is also not automatically a confidence interval. A calibrated statistical coverage claim would require an explicit data-generation process and validation procedure. In operational use, uncertainty sets may need to include stale statistics, correlated predicates, memory availability, and concurrent interference. Enlarging a set without considering plausibility can make a robust plan excessively conservative. Shrinking it to make the result look attractive defeats the objective. The study should document how the set was chosen before observing comparative execution outcomes.

Robustness can be unfair to small queries

Multiplicative regret emphasizes relative loss, while additive regret emphasizes absolute resource waste. A plan that adds a short fixed delay to a tiny query may have enormous relative regret but negligible system impact. The same delay on a large analytical query can be invisible proportionally while still consuming meaningful compute. Neither metric is universally correct. The choice should follow the application contract: interactive deadlines, capacity budgets, or fairness across query classes imply different loss functions.

The constructed interval avoids zero cardinalities because a zero optimal cost makes the ratio undefined. Real evaluators need an explicit convention for empty results and near-zero runtimes, such as a declared baseline overhead or separate reporting. Quietly adding an arbitrary epsilon changes which queries dominate the metric. A workload-weighted mean also needs an arrival distribution; an unweighted benchmark mean implicitly treats every template as equally frequent. For mixed service classes, report both per-class distributions and an overall resource measure. A robust plan is useful only if its conservatism buys protection where protection is valued. A mathematical minimax result cannot supply that policy preference on behalf of the user.

Adaptation needs a legal switching point

The Berkeley report on continuous query optimization describes eddies that route tuples among operators during execution. It emphasizes opportunities for reordering and synchronization barriers, rather than treating a running query as a freely replaceable expression. That distinction is essential. Already produced outputs, retained operator state, and partially consumed inputs constrain what a new plan can do without duplication or omission. An adaptive optimizer inherits a correctness problem as soon as it changes execution state.

For a proposed re-optimization mechanism, the switching protocol should identify the logical boundary at which intermediate results are complete, how those results are represented, and whether restarting can repeat observable side effects. A materialized intermediate can make the boundary simpler but may consume memory or spill to storage. Per-tuple routing can reduce coarse restart costs while introducing routing overhead. These are alternative engineering choices rather than interchangeable implementations of a slogan. A meaningful performance comparison must charge the selected mechanism for observing, deciding, converting state, and resuming execution. Otherwise adaptation receives free information and free state transfer in the model, while the static baseline pays all actual work. The present numerical example deliberately does not simulate an adaptive engine.

Sources [2]

Learning during execution changes the comparator

SkinnerDB explores join orders within a query using small execution slices and a mechanism for combining results across the explored orders. Its abstract defines a quality criterion comparing expected execution cost with an optimal join order. This provides an important conceptual alternative to treating statistics as the only route to reliable decisions. However, the guarantee belongs to the execution strategies and assumptions studied by the authors; this review neither reproduces the proof nor substitutes its own interval-minimax calculation for that result.

The choice of comparator is decisive. An oracle that knows the best fixed join order is different from an oracle allowed to change orders at every moment, and both differ from a practical engine with a finite search budget. Learning overhead can be worthwhile when a catastrophic static choice is plausible, but it is not free on short queries. A proposed evaluation should disclose the number of arms or orders, the duration and accounting of exploration, and the treatment of work shared across candidates. It should also report query completion, not only progress rate within selected slices. A mechanism that learns a good local rate but repeats work can look successful under an incomplete metric.

Sources [3]

Re-optimization must repay sunk cost

Perron and colleagues argue, in their re-optimization study, that repairing costly choices during execution can be a practical route to better end-to-end behavior. Their reported improvements are evidence from a specified experimental setting, not a universal percentage to expect elsewhere. The general decision problem can be expressed without importing those measurements: switch only when the expected remaining saving exceeds observation, planning, conversion, and restart costs, under a declared risk policy.

Past work is usually sunk. It should not be counted as recoverable merely because a new plan would have been faster from the beginning. A checkpoint can also be too late: once a large intermediate has spilled, knowing its cardinality exactly may arrive after the expensive decision. Conversely, switching too early can respond to an unrepresentative prefix, particularly when data is clustered. A falsifiable evaluation should inject controlled estimate errors and record the earliest point at which a correction is both observable and actionable. It should compare no adaptation, perfect-information adaptation at that same legal point, and the real observation mechanism. The gap between the latter two isolates information quality; the gap to an impossible restart-free oracle should not be mislabeled optimizer overhead.

Sources [4]

Memory makes the cost surface discontinuous

The affine example omits memory pressure to keep its logic inspectable. Actual plan costs can jump when a build relation no longer fits, a sort requires another merge pass, or concurrent queries reduce available buffers. Those thresholds can invalidate a cost ordering even with a perfect row estimate. An uncertainty model that varies only cardinality may therefore be robust against the wrong uncertainty. Row width, distinctness, distribution skew, and resource grants can be equally consequential.

A useful extension would add a memory coordinate and a declared spill penalty, then enumerate the two-dimensional uncertainty set. The penalty should come from measurements or an explicit synthetic rule, with the two clearly distinguished. The evaluation should keep identical memory limits across policies and count peak retained state, including adaptation metadata. A plan that avoids catastrophic latency by retaining every alternative might violate a service's memory contract. This suggests a constrained optimization objective: minimize a chosen regret measure subject to resource and correctness limits. If no candidate satisfies those limits, admission control or rejection is a legitimate outcome. Selecting the least bad infeasible plan does not turn it into an acceptable execution strategy.

Observability requires careful interpretation

PostgreSQL's EXPLAIN documentation distinguishes estimated costs from measured time and explains that repeated-node row and time figures are averaged per loop. It also warns that EXPLAIN ANALYZE executes the query, adds measurement overhead, and excludes some client-facing costs. These details matter when an evaluation reconstructs work or claims an end-to-end improvement. Summing every displayed node time can double-count nested execution, while ignoring loop counts can conceal repeated work.

The proposed protocol stores machine-readable plans, actual row counts, loop counts, memory and spill information, and application-visible completion time as separate observations. Queries should be run against controlled data snapshots with fixed parameter sets and recorded statistics freshness. Randomized execution order helps separate policy differences from cache and background-load drift, but it does not replace a declared warm or cold cache condition. Timeouts need an explicit censoring rule and correctness needs independent result comparison. For updating statements or queries containing side effects, the test harness must use isolated fixtures and a suitable transaction policy. A diagnostic instrument should not silently mutate the workload whose performance it is supposed to explain.

Sources [6]

A research program with explicit failure criteria

The substantive hypothesis is that decision-aware uncertainty handling improves the upper tail of realized regret at an acceptable planning and execution overhead. A study can reject it if gains vanish under matched memory, if corrected estimates arrive too late, if conservative plans slow the dominant workload class beyond its budget, or if the uncertainty set fails to cover important realized conditions. These are more informative failure criteria than asking whether a proposed estimator reduces one aggregate error statistic.

The supplied model establishes three limited facts: the minimax choice over a finite interval, the exact lower-envelope switches for its affine candidates, and an explicit separation between q-error and realized regret. Its correlated-predicate enumeration provides a separate diagnostic counterexample. None measures a database or demonstrates adaptation performance. The next step is a controlled implementation study that pairs each estimate with the decision it caused, its legal opportunities for repair, and the final cost actually paid. That design would make both successful and unsuccessful robustness mechanisms interpretable. The aim is not to eliminate uncertainty by declaration, but to show which uncertainties an execution strategy can tolerate without breaking the application's resource or response contract.

Mathematical model

q(n^,n)=max⁡{n^/n,n/n^}q(\hat n,n)=\max\{\hat n/n,n/\hat n\}

(1) Multiplicative cardinality error for strictly positive estimates and actual counts; zero counts require a separate convention.

CN(n)=2n,CB(n)=120+0.8n,CH(n)=500+0.2nC_N(n)=2n,\quad C_B(n)=120+0.8n,\quad C_H(n)=500+0.2n

(2) Constructed abstract work units for three equivalent plans; coefficients are not measured database costs.

ρ(p,n)=Cp(n)min⁡q∈PCq(n)\rho(p,n)=\frac{C_p(n)}{\min_{q\in\mathcal P}C_q(n)}

(3) Realized multiplicative regret relative to the same finite candidate plan set and resource assumptions.

p∗=arg⁡min⁡p∈Pmax⁡n∈{100,…,1000}ρ(p,n)p^*=\arg\min_{p\in\mathcal P}\max_{n\in\{100,\ldots,1000\}}\rho(p,n)

(4) Finite minimax decision used in the reproducible model; the uncertainty set is assumed, not statistically calibrated.

∣RA∧B∣^=∣R∣Pr⁡(A)Pr⁡(B)\widehat{|R_{A\wedge B}|}=|R|\Pr(A)\Pr(B)

(5) Independence estimate; the constructed perfectly correlated predicates violate its factorization.

E[Cremain,old−Cremain,new]>Cobserve+Cplan+Cconvert\mathbb E[C_{\rm remain,old}-C_{\rm remain,new}]>C_{\rm observe}+C_{\rm plan}+C_{\rm convert}

(6) Conceptual switching condition in consistent cost units; not a guarantee when expectations or state-transfer feasibility are wrong.

Reproducible analytical figures

Three constructed plan cost envelopes: Costs are invented transparent affine functions, not PostgreSQL optimizer units.
Figure 1. Costs are invented transparent affine functions, not PostgreSQL optimizer units.

Assumptions: Single uncertain intermediate cardinality; All plans semantically equivalent; No spill or concurrency

CSV data · Vector figure

Estimate error through the decision boundary: Robust plan minimizes worst regret on integer cardinalities 100 through 1000.
Figure 2. Robust plan minimizes worst regret on integer cardinalities 100 through 1000.

Assumptions: Perfect cost functions assumed; Uncertainty set fixed in advance; No planning overhead

CSV data · Vector figure

Executed finite checks

5 check groups passed. The listed cases validate this model; they are not independent experiments or system benchmarks.

  • Declared equal-cost tie priority · 1 cases. N wins the exact 100-row N/B tie; the q-error example depends on this declared choice.
  • Discrete minimax enumeration · 2703 cases. All 901 cardinalities for each of three plans.
  • Exact switching intervals · 1999 cases. Analytic pairwise intersections checked against enumeration; tie at 100 excluded.
  • Equal q-error does not imply equal regret · 1 cases. Underestimate and overestimate both have q-error 10.
  • Correlated selectivity counterexample · 1 cases. Two identical 10 percent predicates select 100 rows, not independence prediction 10.

Comparison

PlanWorst regret on integer [100,1000]Cost at n=1000
N2.85714285712000
B1.3142857143920
H2.6700

Proposed validation protocol

  • Pin engine build, schema, indexes, settings and a reproducible dataset snapshot.
  • Define query classes, parameters, resource limits and the feasible candidate comparator.
  • Choose uncertainty sets before comparative execution.
  • Vary correlations independently of marginal frequencies.
  • Record estimates, actual rows, loops, plan choices and spill events together.
  • Randomize execution order within declared cache conditions.
  • Measure application completion separately from instrumented plan times.
  • Charge adaptive policies for observation, planning, state conversion and repeated work.
  • Compare every completed result with an independent reference and retain timeout records.
  • Report per-class tail regret, overhead, interval coverage and resource violations.

Limitations

  • Cost functions are synthetic affine examples without physical calibration.
  • The finite minimax set excludes zero counts, memory uncertainty and distribution shifts.
  • No optimizer implementation or production query was executed.
  • Abstract-only access for some adaptation papers does not support a full theorem review.
  • The fixed feasible-plan comparator is narrower than an unconstrained oracle.
  • The proposed protocol still requires representative workload and cost measurements.

Open research questions

  • Can decision-sensitive estimator loss reduce tail regret without increasing median latency?
  • Which uncertainty-set construction remains calibrated under correlated workload drift?
  • How early can an executor observe a mistake at a boundary where state transfer remains affordable?

Evidence and its boundaries

[1] The JOB study identifies substantial cardinality errors and evaluates their relationship to execution choices.
Its workload and main-memory setting do not establish universal rankings for every optimizer. Inspected: Abstract; Section 1.
[2] Eddies route tuples adaptively while respecting opportunities and barriers to reordering.
Only original report abstract inspected; no independent proof or implementation audit. Inspected: Report abstract and bibliography.
[3] SkinnerDB explores join orders in time slices and compares expected execution cost with an optimal order.
This review does not restate an uninspected theorem or claim its toy minimax model is SkinnerDB. Inspected: Abstract and journal reference.
[4] The study argues for re-optimization as a response to costly optimizer mistakes.
Reported JOB improvements are not reproduced or transferred to this model. Inspected: Abstract; version and comments.
[5] Dependency statistics correct some correlated equality estimates but have explicit predicate limitations.
Year is access year; this is documentation rather than an original empirical paper. Inspected: 14.2.2.1 and 14.2.2.1.1.
[6] Actual rows and loops support diagnosis; timing and output-delivery exclusions affect interpretation.
EXPLAIN measurements are not identical to end-to-end application latency. Inspected: 14.1.2 and 14.1.3.

References

  1. How Good Are Query Optimizers, Really?
    Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, Thomas Neumann. Proceedings of the VLDB Endowment (2015). https://www.vldb.org/pvldb/vol9/p204-leis.pdf
    Source access and scope

    Original PVLDB PDF abstract and introduction, benchmark scope and optimizer-component separation.

  2. Continuous Query Optimization
    Ron Avnur, Joseph M. Hellerstein. UC Berkeley Technical Report UCB/CSD-99-1078 (1999). https://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5714.html
    Source access and scope

    Original university report record and abstract; later SIGMOD PDF links failed and are not claimed read.

  3. SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning
    Immanuel Trummer, Junxiong Wang, Deepak Maram, Samuel Moseley, Saehan Jo, Joseph Antonakakis. ACM SIGMOD (2019). https://arxiv.org/abs/1901.05152
    DOI: 10.1145/3299869.3300088
    Source access and scope

    Author-submitted arXiv record, complete authors, abstract and related conference DOI.

  4. How I Learned to Stop Worrying and Love Re-optimization
    Matthew Perron, Zeyuan Shang, Tim Kraska, Michael Stonebraker. arXiv; short version ICDE 2019 (2019). https://arxiv.org/abs/1902.08291
    Source access and scope

    Author-submitted version-2 record and abstract.

  5. Statistics Used by the Planner
    PostgreSQL Global Development Group. PostgreSQL 18 documentation (2026). https://www.postgresql.org/docs/18/planner-stats.html
    Source access and scope

    Official version-18 documentation: extended statistics, functional dependencies and their limitations.

  6. Using EXPLAIN
    PostgreSQL Global Development Group. PostgreSQL 18 documentation (2026). https://www.postgresql.org/docs/18/using-explain.html
    Source access and scope

    Official version-18 EXPLAIN ANALYZE and caveats passages.

Commissioned research review · v1. Cite this review · Original source record · Publication record