When Plans Change Answers: Formalizing Cost-Accuracy Optimization for Semantic Queries

Kyoungmin Kim

cs.DBOct 6, 2026

When Plans Change Answers: Formalizing Cost-Accuracy Optimization for Semantic Queries

Authors: Kyoungmin Kim

Organizations: KAIST

Abstract

In semantic query engines, predicates are evaluated by machine-learned models, and the choice of a query plan affects not only the cost of a query but also its result. Existing systems either apply a fixed threshold to each semantic operator or tune accuracy per operator, without accounting for how errors propagate through joins. We give a formal problem definition for cost-accuracy optimization of such queries. Our starting point is the calibrated confidence that decision models such as Jev attach to each decision. It yields an expected error for every decision; weighting these errors by each decision's contribution to the output (in the simplest case, its fan-out) gives the expected output quality of a plan without any labeled data, and the same computation in reverse turns an output-level accuracy target into a price on each base or intermediate tuple. Building on this, we define an oracle semantics for relational algebra with semantic operators, physical plans as pairs of a logical plan and a decision policy, declarative output-level targets, and a hierarchy of plan equivalence. We show that accuracy is plan-invariant under pointwise-deterministic policies, and that selection pushdown is not quality-sound when escalation bands are calibrated on the plan's own candidates. Expected quality can be computed in polynomial time under bag semantics; under set semantics it follows the dichotomy of tuple-independent probabilistic databases when every relation carries a semantic predicate. Choosing which tuples to drop is NP-hard, while the optimization problem decomposes into per-tuple decisions through two Lagrange multipliers, and, with what we call confidence-centric skipping, tuples that can no longer affect the target are skipped without being scored. Simulations on a synthetic workload illustrate these effects; an evaluation on real engines is left for future work.

Figures & tables

Review	$p$	$f$	Action	Expected error per review	Expected error in output rows
$r_{1}$	0.98	2	Accept	FP: $1-p=0.02$	FP: $0.02\cdot 2=0.04$
$r_{2}$	0.90	40	Accept	FP: $0.10$	FP: $0.10\cdot 40=4.00$
$r_{3}$	0.60	5	Accept	FP: $0.40$	FP: $0.40\cdot 5=2.00$
$r_{4}$	0.30	100	Reject	FN: $p=0.30$	FN: $0.30\cdot 100=\mathbf{30.00}$
$r_{5}$	0.05	3	Reject	FN: $0.05$	FN: $0.05\cdot 3=0.15$
Expected recall / precision				$0.88$ / $0.83$	$\mathbf{0.58}$ / $0.87$

Table 1: Running example: five reviews, their decision-model confidence

p

, and fan-out

f

(orders of the reviewed product). A plan that accepts the reviews with

p\geq 0.5

makes the expected errors on the right: per review (operator level) and per output row (output level).

Panel of Figure 1 — Figure 1: The role of calibrated confidence. Forward (solid): each decision has an expected error, which lineage weights by the decision’s contribution $c_{i}$ to the output (in the running example, its fan-out); the sum gives the expected output quality of a plan. Backward (dashed): an output-level target induces a cost–accuracy trade-off for each tuple.

Class	Action depends on	Example
Pointwise-deterministic (PD)	$\kappa$ only, fixed function	Jev with fixed $\tau$ ; JEVDB-Flash; “accept iff $p\geq 0.5$ ”
Population-calibrated (PC)	$\kappa$ and a statistic of $I_{L}(D)$	escalation band $[\ell,h)$ fit on a sample of current candidates; JEVDB’s quality-controlled mode
Context-aware (CA)	$\kappa$ , fan-out, downstream cost/selectivity	escalate $r_{4}$ because $f_{4}=100$
Sound pruning	necessary condition, sound extractor	lossless SBF; relational Bloom semijoin

Table 2: Policy classes.

Panel of Figure 2 — Figure 2: Expected errors of the plan in Table 1 . Left: per review, $r_{3}$ (accepted with confidence $0.6$ ) has the highest error probability. Right: weighted by contribution (fan-out), $r_{4}$ dominates; its error probability of $0.3$ applies to $100$ orders and accounts for $30$ of the $30.15$ expected missing output rows. An operator-level target corresponds to the left panel, while output quality corresponds to the right panel.

Panel of Figure 3 — Figure 3: The physical plan space of the running example, predicted from confidences alone. Each point is one plan: a logical plan (pushdown or pull-up) and an action per review ( $3^{5}\times 2=486$ plans). Equivalence: all points are oracle-equivalent (same $Q^{*}$ ); a PD policy gives two points at the same height, the same answer at different cost (black segment); points at the same height are $M$ -equivalent ( Definition 5.6 ). Optimization: the admissible plans are the shaded band, and cost–accuracy optimization picks its leftmost point. A classical optimizer with a fixed threshold only chooses between the two ends of the black segment and keeps the cheaper one, at predicted quality $0.58$ ; the operator-level band is admissible but costs $1.8\times$ the optimum.

Level	$P_{1}$ and $P_{2}$ are related iff	In Fig. 3	Checkable without labels?
Oracle ( $\equiv^{*}$ )	same answer under oracle predicates	all $486$ points	yes (classical rules)
Implementation	same answer under the implemented predicates	two ends of a black segment (PD policy)	yes, for PD policies
Confidence-relative ( $\equiv_{M}$ )	same predicted output recall and precision	points at the same height	yes, from confidences
Admissibility ( $\mathcal{A}$ )	both meet the output target	points in the shaded band	predicted form ( $\mathcal{A}_{M}$ ) only

Table 3: Four levels of plan equivalence, from strongest to weakest. Only the last two levels distinguish plans of different quality, and checking them before execution requires calibrated confidences.

Panel of Figure 4 — Figure 4: Propagation of contributions from the output to intermediate and base decisions ( Example 6.3 ). Orange: the contribution of a decision is the expected number of true outputs it contributes to, computed top-down. Because the second predicate is selective, the contribution of $r_{4}$ is $18$ rather than $100$ , and rejecting $r_{4}$ loses $5.4$ instead of $30$ expected rows. Blue: an intermediate decision only matters if its base tuple is kept, so if $r_{4}$ is rejected, the $100$ decisions of the second predicate on its rows need not be evaluated.

Result	Statement	Status
Quality evaluation	Bag: PTIME. Set: PTIME for hierarchical, #P-hard for non-hierarchical with all atoms probabilistic	Theorem 7.3
Plan invariance	Under PD policies, CASQO separates into classical cost-based QO plus a plan-independent policy choice	Proposition 5.3
PC unsoundness	Selection pushdown is not quality-sound for population-calibrated policies	Proposition 5.11
Per-tuple decomposition	Two prices push an output target down to independent per-tuple decisions	Proposition 8.2
Instance-level drop	NP-hard, even with one filter, one join, and $p\equiv 1$	Proposition 8.6
Confidence-centric skipping	Unprocessed instances can be skipped unscored once a bound on their contribution meets the target	Proposition 8.4

Table 4: Results and their status.

Plan	Output recall	Output precision	F1	Cost	Admissible
PD, pushdown	0.997 $\pm$ 0.001	0.983 $\pm$ 0.011	0.990 $\pm$ 0.006	1.00	100%
PD, pull-up	0.997 $\pm$ 0.001	0.983 $\pm$ 0.011	0.990 $\pm$ 0.006	88.22	100%
PC, pushdown	0.992 $\pm$ 0.020	0.924 $\pm$ 0.064	0.956 $\pm$ 0.037	0.86	62%
PC, pull-up	0.950 $\pm$ 0.020	0.977 $\pm$ 0.021	0.963 $\pm$ 0.016	71.40	96%

Table 5: E1 and E2: pushdown vs. pull-up under a pointwise-deterministic band

[0.1,0.9)

and under bands calibrated on a sample of

200

instances of each plan’s own population (operator-level target

0.95

). Quality is measured on output rows. Cost is relative to PD pushdown; pull-up evaluates every joined row and does not cache decisions. Admissible: fraction of instances meeting the output target

(0.9,0.9)

Panel of Figure 5 — Figure 5: Plan space of one simulated database ( $2{,}000$ reviews, confidence independent of fan-out). Each point is a candidate plan: every band on a $0.05$ grid under pushdown and pull-up, and the per-tuple priced policies of Proposition 8.2 under pushdown. Plans differ by up to $1,261\times$ in cost and from $0.00$ to $1$ in output quality; even among plans that meet the target, cost varies $307\times$ . The cost-only plan is cheap but misses about a third of the true orders. Our policy meets the predicted target (realized recall 0.90, precision 0.93) at about $1/16$ of the cost of escalating all decisions and $1/7$ of the cost of an operator-level target.

Panel of Figure 6 — Figure 6: Cost of meeting an output-level target, averaged over $10$ simulated databases (confidence independent of fan-out). Both policies are chosen on predicted quality and meet the target on realized labels on average. Per-tuple pricing is cheaper than the best operator-level band by a factor of $1.9$ to $5.3$ . The gap narrows as $\rho$ approaches $1$ , since then almost all uncertain tuples have to be escalated.

Policy	Cost	Escalations	Output recall	Output precision
Operator-level band	37,256	688	0.917 $\pm$ 0.027	0.911 $\pm$ 0.033
Instance-level (priced)	7,164	87	0.921 $\pm$ 0.022	0.910 $\pm$ 0.021

Table 6: E3: cheapest operator-level band vs. instance-level policy ( Proposition 8.2 , grid search over the two prices), both chosen on predicted output quality to meet

(0.9,0.9)

and evaluated on realized quality. Workload with confidence independent of fan-out;

50

instances.

Decision model	Pred. recall	True recall	Pred. precision	True precision	$\|$ Error $\|$ (precision)
Calibrated	0.997	0.997	0.983	0.982	0.008 $\pm$ 0.006
Overconfident	1.000	0.994	0.981	0.872	0.109 $\pm$ 0.027
Overconfident + PPI	0.995	0.994	0.874	0.872	0.028 $\pm$ 0.020

Table 7: E4: predicted vs. realized output quality of the PD band policy, averaged over

200

instances. Overconfident: logit of

p

scaled by

2.5

. PPI: contribution-weighted correction with

100

gold labels drawn in proportion to fan-out. Last column: mean absolute error of predicted precision per instance.

Panel of Figure 7 — Figure 7: (a) Each dot is one of $200$ simulated databases. A band calibrated on the pushdown population often falls below the output precision target; calibrated on the pull-up population it rarely does ( Proposition 5.11 ). (b) Predicted output precision from $\sum_{i}c_{i}(1-\mathrm{conf}_{i})$ against realized precision. Calibrated confidences lie on the diagonal; an overconfident model predicts about $0.98$ for databases that deliver $0.87$ ; contribution-weighted PPI with $100$ labels moves the predictions back to the diagonal, with more spread.

Model cost	Policy	Reviews scored	Escalations	Cost	Output recall	Output precision
1	score all	2,000	145	18,389	0.924 $\pm$ 0.021	0.918 $\pm$ 0.016
1	staged + skip	806	144	17,063	0.915 $\pm$ 0.019	0.916 $\pm$ 0.016
10	score all	2,000	145	36,389	0.924 $\pm$ 0.021	0.918 $\pm$ 0.016
10	staged + skip	712	157	24,149	0.925 $\pm$ 0.022	0.913 $\pm$ 0.014

Table 8: E5: scoring every review vs. staged processing with confidence-centric skipping ( Proposition 8.4 ), both chosen on predicted output quality to meet

(0.9,0.9)

. Heavy-tailed fan-out,

2{,}000

reviews,

20

instances. Model cost: cost of one decision-model call (one LLM call costs

50

Panel of Figure 8 — Figure 8: Confidence-centric skipping on one simulated database with heavy-tailed fan-out (same prices for all three runs). The lower bound treats every unscored row as a true positive, or uses a block’s maximum confidence when a zone-map summary is available; it requires no scoring of the unscored reviews. Once it reaches the target, the remaining reviews are skipped. In decreasing order of fan-out, the first 653 reviews carry 98% of the output rows; with a zone map clustered by confidence, the bound reaches the target after 260 reviews. In storage order the bound never reaches the target.

Order and summary	Unscored	Cost saving	Output recall	Output precision
Decreasing fan-out	58% / 67%	7.0% / 9.3%	0.912 $\pm$ 0.017	0.913 $\pm$ 0.016
Storage (random) order	1% / 2%	0.7% / 1.7%	0.914 $\pm$ 0.021	0.916 $\pm$ 0.016
Increasing fan-out	0% / 0%	0.7% / 1.7%	0.911 $\pm$ 0.015	0.916 $\pm$ 0.016
Fan-out $\times$ noisy prior	24% / 29%	2.6% / 3.3%	0.920 $\pm$ 0.018	0.917 $\pm$ 0.016
Zone map, random layout	58% / 67%	7.1% / 9.3%	0.912 $\pm$ 0.017	0.914 $\pm$ 0.016
Zone map, clustered	82% / 87%	11.8% / 13.8%	0.896 $\pm$ 0.015	0.912 $\pm$ 0.016

Table 9: E6: processing order and confidence summaries for confidence-centric skipping, on the E5 workload (

10

instances). Prices are re-tuned for each configuration. Unscored: fraction of reviews never scored; cost saving relative to the cheapest score-all policy; both given as mean / max over instances. Zone maps store the maximum confidence of each block of

64

reviews.

Explore similar work

Jun 14, 2026cs.DB

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

Cardinality-estimation (CE) research ranks estimators by q-error, yet it is well known that q-error is an imperfect proxy for query-plan quality. We give a measurement-driven account of when it is a good proxy and when it is not, and why. Modeling plan selection as an argmin over a piecewise-linear cost landscape, we find that plan regret (the cost of the chosen plan relative to the optimal, under true cardinalities) is governed by plan-cost geometry in a regime-dependent way. (i) For small errors, a true-point condition number kappa predicts regret and out-predicts q-error; its predictive power decays to zero as error grows, as a local linearization must. (ii) For large errors -- where deployed learned estimators operate -- an estimator-independent average-case sub-optimality measure ACS-infinity predicts which queries are regret-prone (Spearman rho ~ 0.54 on STATS-CEB), while q-error is nearly uninformative at the query level (rho ~ 0.05). (iii) The worst case is Haritsa's maximum sub-optimality (MSO). The three are one cost-ratio spectrum under three weightings. We prove a limit law ACS-infinity = sum_k r_k pi_k with cardinality-independent combinatorial weights, and validate every claim on STATS-CEB and JOB-light with four released estimators under pre-registered decision rules, and confirm on real PostgreSQL runtime that ACS-infinity predicts regret where q-error does not. The contribution is conceptual and empirical -- an average-case companion to worst-case robust query optimization, and a characterization of when an accuracy metric tracks plan quality -- rather than a new estimator. Code and the full pre-registration are public.

Madhulatha Mandarapu, Sandeep Kunkunuru

VaidhyaMegha Private Limited, India

Topic pending

Ask PDF

Sep 23, 2026cs.DB

KathDB-FAO: Synthesized Query Plans in a Multimodal DBMS

We design, implement, and evaluate KathDB-FAO, a new query evaluation subsystem for our KathDB multimodal DBMS. KathDB-FAO takes as input a query in natural language (NL) and converts it into a query execution plan where each operator is a function whose body is synthesized during query evaluation, which allows powerful query-specific optimizations. To generate accurate and efficient plans from NL, KathDB-FAO first extracts fine-grained atomic actions for correctness, then establishes contracts on the inputs and outputs of those actions and groups them for efficiency, and finally synthesizes the function for each group on the fly. On SemBench, KathDB-FAO cuts execution cost by 58.8% on average across scenarios compared with the next best system, at comparable or better quality.

Guorui Xiao, Douglas Brown, Artur Borycki +1

University of Washington · Teradata

Relational Databases

Ask PDF

May 18, 2026cs.LG

Agentic Cost-Aware Query Planning with Knowledge Distillation for Big Data Analytics

Query optimization in big data analytics remains computationally expensive, particularly for resource-constrained environments where traditional optimizers fail to satisfy memory and latency constraints. We present an agentic query planning system that combines a rule-based teacher planner, UCB1 bandit exploration, cost-aware prediction, and knowledge distillation to a lightweight student planner. Our teacher planner generates SQL plans using six key optimization strategies, while UCB1 bandit search efficiently explores the plan space under explicit resource constraints. A Random Forest cost model predicts query latency from plan features, enabling cost-aware decisions. A distilled student planner (Logistic Regression or Gradient Boosting) learns to mimic teacher-bandit decisions for fast inference. Evaluation on NYC Taxi and IMDB datasets demonstrates 23% latency reduction compared to default planners while maintaining 94% constraint satisfaction. The student planner achieves 89% accuracy in replicating optimal plans with 15x faster inference time. Our single-file implementation enables reproducible big-data analytics on resource-limited machines and is publicly available at https://github.com/mahdinaser/agentic-kd-planner.

Mahdi Naser-Moghadasi

Research Division, BrightMind AI, Seattle, WA · Texas Tech University, Lubbock, TX

Learning to Optimize

Ask PDF