🤖 machine learning

Selectivity Estimation for Linear Queries via Online Learning

本文提出了一种用于在动态数据库环境中估计选择性的在线学习框架，并为静态和动态设置下的基于直方图的线性查询建立了理论遗憾界。

原作者： Fangzhu Shen, Debmalya Panigrahi, Sudeepa Roy

发布于 2026-07-07

📖 1 分钟阅读☕ 轻松阅读

原作者： Fangzhu Shen, Debmalya Panigrahi, Sudeepa Roy

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一名侦探，正试图通过特定的描述（比如“戴着红帽子”）来猜测一座大城市中有多少人符合这个特征。在数据库的世界里，这被称为选择性估计（selectivity estimation）。数据库就是这座城市，数据就是其中的人，而描述就是“查询”。如果你的猜测错了，计算机可能会选择一个糟糕的执行计划来寻找答案，从而浪费大量的时间和精力。

长期以来，侦探们（数据库系统）一直使用简单的经验法则，比如假设人们的帽子颜色与其鞋码是相互独立的。但现实生活是混乱的，这些规则往往会失效。最近，人们开始使用“AI 侦探”（机器学习）来改进，它们能从过去的猜测中学习并变得更好。然而，大多数 AI 侦探都是在实验室里训练出来的，那里的城市永远不会改变，问题也总是相同的。

这篇论文探讨的是：当城市不断变化，且问题难以预测时，会发生什么？ 作者提出了一种新的思考方式，利用**在线学习（Online Learning）**的概念来解决这个问题。

这场游戏：在黑暗中进行猜测

作者设置了一场游戏，用来测试 AI 侦探在混乱世界中的学习能力。游戏的流程如下，一轮又一轮地进行：

提出问题： 一个新的查询到达（例如：“有多少人戴着红帽子？”）。
做出猜测： AI 必须立即做出猜测，且只能基于它之前所见到的信息。它目前还不知道正确答案。
揭晓答案： 真实的答案被揭晓。
评分： 根据 AI 错得有多离谱，它会受到一个“惩罚”（称为损失/Loss）。
- 平方损失（Squared Loss）： 想象成一位“严厉的老师”。如果你只是稍微偏离，没关系；但如果你错得离谱，惩罚会呈爆炸式增长。这很重要，因为数据库中的一次巨大失误可能会导致执行计划崩溃。
- 绝对损失（Absolute Loss）： 想象成一位“公平的老师”。它只计算你偏离了多少，无论偏差的大小。

基准：最好的“静态”侦探

为了衡量 AI 的表现如何，我们需要一个参照物。作者将 AI 与**最佳固定策略（best possible fixed strategy）**进行了比较——即如果我们在预知未来所有情况的前提下，所能选出的最优策略。

静态世界： 想象这座城市的人口是固定的（没有人迁入或迁出），但提出的问题在变化。这个“最佳静态策略”就是一张关于该城市的完美地图。
动态世界： 想象这座城市是混乱的。人们不断迁入、迁出，甚至更换帽子。这个“最佳静态策略”仍然仅仅是一张固定的地图。AI 的任务是看它能多接近于那张单一的固定地图。

为什么要与固定地图进行比较？ 如果我们把 AI 与一张随时间完美变化的“魔法地图”相比，那么没有任何 AI 能赢。我们的目标是看 AI 是否能找到即使在变化的世界中依然存在的“底层模式”。

结果：它们能做得多好？

作者使用不同类型的查询和不同程度的混乱度运行了这场游戏。他们测量了“遗憾值（Regret）”，这简单来说就是 AI 的总惩罚与最佳固定策略的惩罚之间的差值。

1. 静态城市（数据不发生变化）

好消息： 如果数据是稳定的，AI 学习得非常快。
类比： 想象你在尝试猜测一块不变的岩石的重量。你问的问题类似于“它是否重于 10kg？”以及“它是否轻于 20kg？”
结果： 作者发现，对于复杂的问题，AI 的错误增长得非常缓慢——仅以可能类别的**对数（logarithm）**速度增长。用通俗的话说：即使城市有上百万个不同的社区，AI 也只需要通过增加极少量的错误就能掌握整张地图。这极其高效。

2. 动态城市（数据不断变化）

挑战： 现在，城市每秒钟都在变化。那张“最佳固定地图”在 AI 查看它时就已经过时了。
结果： 随着游戏的进行，错误会不断增加，但作者发现了特定的限制：
- 对于简单问题（点查询/Point Queries）： 错误随轮数的平方根增长。
- 对于复杂问题（范围/子集查询/Range/Subset Queries）： 错误随轮数的平方根乘以城市规模的对数增长。
- 对于“严厉的老师”（平方损失/Squared Loss）： 错误增长得非常缓慢，仅随轮数的对数增长。在如此混乱的环境中，这表现得惊人地好！

秘密武器（算法）

他们是如何实现这些结果的呢？他们不仅仅是在瞎猜，而是使用了巧妙的数学技巧：

“最平衡”的猜测（序贯最大熵/Sequential Maximum Entropy）：
- 类比： 想象你有一个装满弹珠的袋子，你知道一些关于它们的规则（例如：“其中 50% 是红色的”）。但你不知道剩下的部分。最聪明的猜测是假设剩余的弹珠分布得尽可能均匀。这就是“最大熵（Maximum Entropy）”。
- 作用： AI 会保留一份所有符合目前线索的城市地图清单。它不会从清单中随机挑选一张地图，而是挑选那张“最平衡”的地图。如果它猜错了，它就会意识到真实的城市情况与这个平衡猜测相去甚远，从而能迅速缩小搜索范围。
“哈达玛”谜题（Hadamard Puzzle，用于证明极限）：
- 为了证明没有任何 AI 能做得比某个极限更好，作者创建了一个使用特殊数字矩阵（哈达玛矩阵/Hadamard matrix）构成的复杂谜题。他们在城市的变化中隐藏了看起来像噪声的随机变化。这证明了即使是最聪明的 AI 也会陷入猜测的困境，从而为 AI 能够达到的表现水平设定了一个“底线”。

总结

这篇论文为在数据库中使用 AI 提供了一个理论上的安全网。它证明了即使数据是混乱的，且问题是不可预测的，我们依然可以构建出高效学习的算法。

如果数据是稳定的： AI 几乎能瞬间学到完美的程度。
如果数据是混乱的： AI 依然在学习，并且我们确切知道它收敛到良好解决方案的速度。

作者的结论是，尽管他们的数学推导很复杂，但传达的信息很简单：基于学习的选择性估计不仅仅是一个幸运的猜测；它是一种在即使是最狂野、变化最剧烈的环境中也能奏效的、具有数学依据的策略。 他们也为未来的研究留下了空间，例如在真实数据库上测试这些想法，或者处理更复杂的查询类型，比如多个表之间的连接（Join）。

技术摘要：通过在线学习进行线性查询的选择性估计

问题陈述

选择性估计是查询优化的一个基本组成部分，它使数据库优化器能够选择高效的执行计划。虽然传统方法依赖于强假设（例如属性独立性）和预计算统计量（直方图、草图），但近期的基于学习的方法通过利用机器学习捕捉复杂的数分布，展现出了经验性的潜力。然而，现有对这些基于学习的方法的理论研究主要局限于具有固定查询分布的静态数据库。

在实践中，现实世界的数据库环境是动态的：数据在不断地被插入、更新和删除，且查询负载可能会发生不可预测的偏移，而不遵循平稳分布。基于历史数据训练的静态模型会变得过时，导致准确性下降或需要昂贵的重新训练。本文通过提出一个针对全动态、无分布假设设置下的选择性估计的理论框架来解决这一差距。

核心问题被形式化为一个在线学习任务，其中：

在每一轮 $t$ ，到达一个查询向量 $v_t$ 。
学习器预测选择性 $\hat{\sigma}_t$ 。
真实的选择性 $\sigma_t = \langle v_t, w_t \rangle$ 被揭示，其中 $w_t$ 是底层的数据库状态（ $k$ 维单纯形 $\Delta_k$ 中的一个向量）。
学习器根据预测误差产生损失。

目标是最小化遗憾值（Regret），定义为学习器的累积损失与最佳固定数据库向量（在事后选定的）的累积损失之差。本文明确拒绝将算法与动态基准（即数据库在每一轮都发生变化）进行比较，因为正如文中所证明的，在对抗性设置下，没有任何算法能针对此类基准实现非平凡的遗憾保证。

方法论与框架

作者分析了两种不同的数据库设置：

静态数据库： 底层数据库向量 $w^*$ 是固定但未知的，而查询可能是任意的。
动态数据库： 数据库向量 $w_t$ 除了查询之外，还可能在每一轮中发生任意变化。

本研究侧重于线性查询（包括点查询、范围查询和子集查询），其由向量 $v \in [0, 1]^k$ 表示。考虑了两种标准的损失函数：

平方损失 (Squared Loss)： $(\sigma_t - \hat{\sigma}_t)^2$ ，对大误差惩罚较重。
绝对损失 (Absolute Loss)： $|\sigma_t - \hat{\sigma}_}_t|$ ，捕捉平均误差。

关键算法

序贯最大熵 (Sequential Maximum Entropy, SeqMaxEnt)： 针对静态设置提出。该算法维护一个与所有观察到的查询-选择性对一致的数据库向量可行域。在每一轮中，它预测该可行域内最大熵分布的选择性。其直觉是，如果算法遭受了巨大的损失，那么真实的数据库必然“远离”当前的当前最大熵估计，从而确保在识别真实状态方面取得了显著进展。
指数加权在线优化 (Exponentially Weighted Online Optimization, EWOO)： 应用于针对平方损失的动态设置。
跟随正则化领导者 (Follow-the-Regularized-Leader, FTRL)： 应用于针对绝对损失的动态设置，并使用不同的正则化项（针对点查询使用 $\ell_2$ 正则，针对子集/线性查询使用负熵）。

关键结果与遗憾界限

本文建立了接近紧致的遗憾上界和下界，总结如下。这些界限取决于支持集大小 $k$ （分箱数量）和时间跨度 $T$ 。

1. 静态数据库

在此设置下，遗憾主要取决于 $k$ ，且与 $T$ 无关。

平方损失：
- 上界： 对于范围、子集和线性查询，由 SeqMaxEnt 实现的 $O(\log k)$ 。
- 下界： 对于范围查询，为 $\Omega(\log k)$ 。
- 结果： $\Theta(\log k)$ 遗憾。
绝对损失：
- 上界： 对于一般线性查询，由 SeqMaxEnt 实现的 $O(\sqrt{k \log k})$ 。
- 下界： 对于子集查询，为 $\Omega(\sqrt{k / \log k})$ 。
- 结果： $\tilde{\Theta}(\sqrt{k})$ 遗憾。
点查询： 在两种损失函数下，遗憾均为常数级 ( $O(1)$ )，因为数据库可以被快速识别。

2. 动态数据库

在此设置下，遗憾主要取决于 $T$ 。

平方损失：
- 下界： 对于点查询，为 $\Omega(\log T)$ 。
- 上界： 使用 EWOO 实现的 $O(k \log T)$ 。
- 结果： 在 $\Omega(\log T)$ 和 $O(k \log T)$ 之间存在差距。
绝对损失：
- 点查询： 紧确界为 $\Theta(\sqrt{T})$ 。
- 子集/线性查询： 紧确界为 $\Theta(\sqrt{T \log k})$ 。
- 结果： 在主参数（ $T$ ）上，平方损失（ $\log T$ ）与绝对损失（ $\sqrt{T}$ ）之间存在多项式级分离。

下界技术

静态绝对损失： 作者利用归一化的 Hadamard 矩阵 构建了一个下界。他们将独立的随机变量编码到一个单一的固定数据库向量中。查询序列逐一揭示这些变量，迫使学习器在每一轮中产生预期损失。通过在扰动幅度（以确保向量保持在单纯形内）与产生的损失之间进行权衡来管理这一过程。
动态平方损失： 其下界是通过将问题归约为估计从均匀分布中抽取的参数 $\mu$ 来推导的，其中数据库状态是 Bernoulli( $\mu$ ) 样本。遗憾对应于 $\mu$ 的后验方差，该方差之和为一个调和级数，从而得出 $\Omega(\log T)$ 。

意义与贡献

本文声称其贡献如下：

无分布假设的公式化： 它提供了一种选择性估计的在线学习公式，该公式对数据或查询不施加任何分布假设，解决了以往基于 PAC 学习的研究中假设固定分布的局限性。
理论保证： 它在两种损失函数（平方损失和绝对损失）以及两种数据库设置（静态和动态）下，为常见的查询类（点、范围、子集、线性查询）建立了（近乎）紧致的遗憾界限。
算法框架： 它引入了 SeqMaxEnt 算法，该算法利用最大熵原理在静态设置下实现对数级遗憾，并在动态设置下应用了标准的在线优化技术（EWOO, FTRL）。
对损失函数的洞察： 该工作强调了平方损失函数与绝对损失函数之间的根本区别，展示了它们在动态条件下的遗憾缩放存在多项式级分离。

作者指出，虽然实际系统通常使用定期重新训练，但这项工作为理解动态环境下无需分布假设的学习极限提供了严谨的理论基础。确定的未来研究方向包括：缩小动态平方损失的上界与下界之间的差距、确定绝对损失下范围查询的最优界限，以及将框架扩展到更丰富的查询类（如连接查询/joins）。