研究近似最近邻查询中选择性估计误差如何导致执行计划失误。
Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret
- 通过相变模型分析三种查询策略在不同选择性下的优劣边界。
- 估计误差仅在边界附近引发显著性能损失，且损失呈对数楔形分布。
- 适用于需要高精度查询优化的数据库系统与索引设计者。
过滤型近似最近邻（ANN）查询返回满足属性谓词P的k个最近向量，其选择性为s。最优执行策略（预过滤、后过滤或内过滤）随s变化，系统需估算s并决策。本文将此建模为景观上的最大值问题，其中各策略胜出区域被边界分隔，边界附近的估计误差会导致计划后悔——即相对于理想策略的召回率损失。该后悔表现为宽度为乘法估计误差ε的对数楔形，高度与局部陡度|V'(s*)|ε成正比；翻转裕度1/|V'(s*)|是兄弟基数估计研究中出现的条件数，重现为局部边界理论。两个相变边界源于独立数学：顺序统计学表明后过滤边界位于s ~ k/K，站点渗透理论指出内过滤边界位于s_c ~ 0.83/M（M为图度，与语料库大小无关）。临界性仅在受限预算B < sqrt(k n)下存在。在预注册决策规则下，合成测试与真实SIFT1M数据验证了后悔集中在边界处约290倍，并且后悔曲线在跨两个数量级的语料库规模上服从有限尺寸标度坍缩至单一通用楔形。真实近似索引未错位边界，但有偏成本模型引入持续校准偏差，而估计误差鲁棒性无法修复。贡献为机制刻画，非新索引。代码与完整预注册公开。
原文摘要 · Abstract (English)
A filtered approximate-nearest-neighbor (ANN) query returns the k nearest vectors among those satisfying an attribute predicate P of selectivity s. The best execution strategy -- pre-filter, post-filter, or in-filter -- changes with s, so a system must estimate s and choose. We model this as an argmax over a landscape with phases (regions where each strategy wins) separated by boundaries, and show that selectivity-estimation error produces plan regret -- recall lost versus the oracle strategy -- only in the critical regions around those boundaries. The regret is a wedge of log-width equal to the multiplicative estimation error epsilon and height equal to the local cliff |V'(s*)| epsilon; the flip-margin 1/|V'(s*)| is the condition number of a sibling cardinality-estimation study reappearing as the local boundary theory. The two phase boundaries follow from independent mathematics: order statistics place the post-filter cliff at s ~ k/K, and site percolation places the in-filter cliff at s_c ~ 0.83/M for graph degree M (corpus-size independent). Criticality exists only under a constrained budget B < sqrt(k n). Under pre-registered decision rules we confirm, on synthetic sweeps and real SIFT1M, that regret concentrates ~290x at the boundary and that the regret curves obey a finite-size scaling collapse onto one universal wedge across two decades of corpus size. A real approximate index does not mis-locate the boundary, but a biased cost model opens a persistent miscalibration band that estimation-error robustness cannot fix. The contribution is a characterization, not a new index. Code and the full pre-registration are public.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。