arXiv：cs.AI· Kyoungmin Kim·· 6 小时前AI 评分35
当计划改变答案：语义查询的成本-精度优化形式化
When Plans Change Answers: Formalizing Cost-Accuracy Optimization for Semantic Queries
AI 导读
针对语义查询中查询计划同时影响成本与结果的问题，研究者给出了成本-精度优化的形式化问题定义，以决策模型（如 Jev）的校准置信度推导每个决策的期望误差，并按决策对输出的贡献加权，从而无需标注数据即可估算计划的期望输出质量。
正文
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. Simulations on a synthetic workload illustrate these effects; an evaluation on real engines is left for future work.
| Subjects: | Databases (cs.DB); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.08089 [cs.DB] |
| (or arXiv:2610.08089v1 [cs.DB] for this version) | |
| https://doi.org/10.48550/arXiv.2610.08089 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Kyoungmin Kim [view email]
[v1]
Tue, 6 Oct 2026 10:19:43 UTC (53 KB)
来源：arXiv：cs.AI · arxiv.org