1. 论文基本信息

1.1. 标题

VB ASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity

中文解读： VB ASE：通过松弛单调性统一在线向量相似性搜索与关系查询

• VB ASE 是本文提出的新系统名称。

• Unifying (统一) 是核心动作，表明该工作旨在弥合两种不同技术之间的鸿沟。

• Online Vector Similarity Search (在线向量相似性搜索) 和 Relational Queries (关系查询) 是被统一的两个对象，前者是现代 AI 应用的基础，后者是传统数据库的核心。

• via Relaxed Monotonicity (通过松弛单调性) 揭示了实现这一统一的核心理论或方法。

  标题清晰地概括了论文的目标、方法和贡献：创建一个名为 VB ASE 的系统，通过引入 松弛单调性 这一新概念，将 AI 时代的向量搜索与经典的关系型数据库查询能力高效地结合起来。

1.2. 作者

Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou.

隶属机构：

• Microsoft Research Asia (微软亚洲研究院)

• East China Normal University (华东师范大学)

• University of Science and Technology of China (中国科学技术大学)

• Renmin University of China (中国人民大学)

  作者团队主要来自微软亚洲研究院，这是一个在系统研究领域享有盛誉的顶级工业研究机构。这表明该研究具有坚实的系统工程背景和解决实际工业问题的导向。

1.3. 发表期刊/会议

17th USENIX Symposium on Operating Systems Design and Implementation (OSDI '23)

OSDI 是计算机系统领域的顶级学术会议之一，与 SOSP (Symposium on Operating Systems Principles) 齐名。能在 OSDI 上发表论文，意味着该研究在系统设计、实现和评估方面都达到了极高的标准，具有重要的学术价值和业界影响力。这篇论文关注的是数据库与向量搜索的系统级融合，完全符合 OSDI 的主题。

1.4. 发表年份

2023

1.5. 摘要

高维向量的近似相似性查询已成为许多关键在线服务的基石。日益增长的对更复杂向量查询的需求，要求将向量搜索系统与关系型数据库集成。然而，高维向量索引不具备单调性 (monotonicity)，而这是传统索引的一个关键属性。单调性的缺失迫使现有向量系统依赖于为目标向量的 TopK 近邻临时建立的、保持单调性的试探性索引 (tentative indices) 来支持查询。由于难以预测最优的 $K$ 值，这种方法导致了次优的性能。

本文提出了 VB ASE，一个能够高效支持包含近似相似性搜索和关系操作符的复杂查询的系统。VB ASE 识别出一个共同属性——松弛单调性 (relaxed monotonicity)，以统一这两个看似不兼容的系统。这个共同属性使得 VB ASE 能够规避仅支持 TopK 接口的限制，实现显著更高的效率，同时在理论上保证与基于 TopK 的解决方案的语义等价。

评估结果显示，在复杂的在线向量查询上，VB ASE 提供了比最先进的向量系统高出三个数量级的性能。VB ASE 还进一步支持了以前向量系统无法实现的分析性相似查询，并展示了比精确查询7000倍的加速和**99.9%**的准确率。

1.6. 原文链接

• 链接: https://www.usenix.org/system/files/osdi23-zhang-qianxi_1.pdf

• 发布状态: 已在 OSDI '23 会议上正式发表。

  ---

2. 整体概括

2.1. 研究背景与动机

随着深度学习的发展，图像、文本、音频等各种数据都能被转换为高维向量，使得基于语义的相似性搜索成为可能。这催生了大量的在线应用，如搜索引擎、电商推荐、问答系统等。这些“在线”服务对查询延迟有极高的要求，通常需要在毫秒级别内完成。

然而，一个日益增长的趋势是，查询不再是简单的“找最像的”，而是混合了多种条件的复杂查询。例如，“寻找与这张图片最相似，但价格低于100元，且属于‘夏季’分类的商品”。这种查询混合了向量相似性搜索（找最像的图片）和传统数据库中的关系查询（按价格和分类进行过滤）。

这就引出了一个核心矛盾和挑战：

1. 传统数据库索引的特性： 像 B-Tree 这样的经典数据库索引具有单调性 (monotonicity)。这意味着索引的遍历是沿着某个方向（如升序或降序）单调进行的。例如，在 B-Tree 中查找大于100的数，一旦扫描到小于100的区域，就可以确定后面不会再有满足条件的数，从而提前终止。这种特性是数据库高效执行查询的基础。

2. 高维向量索引的特性： 由于维度灾难 (curse of dimensionality)，高维空间中的向量索引（如 HNSW, IVFFlat）为了追求效率，采用了近似搜索（ANN）算法。它们的索引结构（如图、或聚类）导致遍历过程不具备单调性。在搜索过程中，遍历到的向量与目标向量的距离会上下波动，无法保证越来越近或越来越远。

现有方案的空白 (Gap)： 为了弥合这一鸿沟，现有的向量数据库（如 Milvus, PASE）采用了一种妥协的、效率低下的方法：

• 两阶段处理：

  1. 第一阶段 (向量搜索): 调用向量索引的 TopK 接口，取回一个非常大的候选集（比如，需要最终返回10个结果，但可能会先取回1000个）。

  2. 第二阶段 (关系查询): 将这1000个结果按与目标向量的距离排序，构建一个临时的、具有单调性的索引，然后在这个临时索引上执行后续的过滤、排序等关系操作。

     这种方法的致命缺陷在于无法预知第一阶段的 $K$ 应该设为多大。如果 $K$ 太小，经过后续过滤可能得不到足够的结果，影响准确性；如果 $K$ 太大，又会造成大量的无效计算和 I/O，严重影响性能。现有系统要么设置一个保守的、非常大的 $K$，要么反复尝试不同的 $K$ 值，两者都会导致性能低下。

本文的切入点： 作者没有停留在如何“猜对 K”这个问题上，而是深入思考：向量索引的遍历过程虽然不是严格单调的，但它是否也遵循某种“规律”？作者观察到，主流向量索引的遍历过程普遍呈现出一种“先逼近、后远离”的两阶段模式。基于此，论文提出了松弛单调性 (Relaxed Monotonicity) 这一概念，将其作为统一向量索引和传统标量索引的共同基础，从而设计出一个无需TopK接口、更加原生的统一查询引擎。

2.2. 核心贡献/主要发现

本文的核心贡献可以总结为以下四点：

1. 提出了“松弛单调性”理论： 首次形式化地定义了 Relaxed Monotonicity 这一属性。该属性揭示了设计良好的向量索引之所以有效的内在核心——它们的遍历过程虽然有波动，但宏观上存在一个从“探索”到“稳定远离”的转折点。这为统一不同类型的索引提供了理论基础。

2. 构建了统一的查询引擎： 基于松弛单调性，VB ASE 构建了一个统一的查询执行引擎。该引擎不依赖于 TopK 接口，而是将所有索引（无论是向量还是标量）的遍历都抽象为统一的 Next 迭代器接口。引擎通过一个通用的终止条件（结合了具体查询要求和松弛单调性检查）来高效地执行查询。

3. 证明了结果等价性与高效性： 论文从理论上证明了，VB ASE 的查询结果与使用“最优 $K$ 值”的 TopK 方法是等价的。这意味着 VB ASE 在保证结果质量的同时，通过“即时”判断终止时机而非“预先”猜测 $K$ 值，实现了远超后者的执行效率。

4. 实现了高性能系统并验证了其价值：

   • 作者基于 PostgreSQL 实现了 VB ASE 原型系统，证明了该思想可以与现有成熟数据库无缝集成。

   • 在复杂的混合查询场景下，VB ASE 的性能比现有最先进系统高出1到3个数量级。

   • VB ASE 能够支持现有系统无法高效处理的新型查询，例如基于向量相似度的 JOIN 操作，相比于暴力全表扫描，实现了超过7000倍的性能提升，同时保持了 99.9% 的准确率。

     ---

3. 预备知识与相关工作

3.1. 基础概念

• 高维向量 (High-Dimensional Vector): 在 AI 领域，这通常指由深度学习模型（如 BERT, ResNet）生成的、包含几百甚至上千个浮点数的数组。这些向量是原始数据（如文本、图像）在数学空间中的“嵌入”表示，向量之间的距离（如余弦相似度、欧氏距离）可以衡量原始数据在语义上的相似性。

• 近似最近邻搜索 (Approximate Nearest Neighbor Search, ANNS): 在高维空间中，精确地找到一个给定向量的最近邻居，计算复杂度会随维度和数据量的增加而爆炸式增长，这被称为维度灾难 (curse of dimensionality)。对于要求毫秒级响应的在线服务，精确搜索是不可行的。因此，业界普遍采用近似算法，牺牲极小的精度（例如，找到的不是真正的第一名，而是前几名中的一个）来换取几十甚至几百倍的速度提升。

• 单调性 (Monotonicity): 这是传统数据库索引（如 B-Tree）的一个核心性质。它保证了沿着索引结构进行扫描时，被访问数据项的某个属性值是单向变化的（递增或递减）。例如，在一个按年龄排序的索引中，当你从头开始扫描，你看到的年龄只会越来越大。这个性质使得范围查询和 TopK 查询可以高效地提前终止。

• TopK 查询: 一种常见的查询类型，旨在从一个大数据集中找出与查询目标最相似（或最大/最小）的 $K$ 个项目。

• 关系型数据库 (Relational Database) 与关系操作符 (Relational Operators): 一种以表格（关系）形式组织数据的数据库。查询数据是通过一系列标准操作符来完成的，如：

  • FILTER (或 WHERE 子句): 筛选满足特定条件的行。
  • JOIN: 将多个表基于某个共同字段连接起来。
  • ORDER BY: 对结果进行排序。
  • LIMIT: 限制返回结果的数量。

3.2. 前人工作

论文中提到的相关工作主要分为两类：独立的向量索引库和尝试集成向量搜索的数据库系统。

1. 向量索引库 (Vector Indices):

   • 代表: FAISS [5], HNSW [58, 89], SPANN [25]。
   • 工作方式: 这些是专门为 ANNS 设计的高性能算法库。它们通过构建复杂的内存数据结构（如图、倒排索引、树等）来加速搜索。
   • 接口: 它们通常只暴露一个 TopK(query_vector, K) 这样的接口，返回与 query_vector 最相似的 $K$ 个结果。其内部的遍历过程、终止判断等细节对外部用户是不透明的 (opaque)。
   • 局限性: TopK 接口表达能力有限，无法直接支持“先过滤再找 TopK”这类复杂逻辑。

2. 基于 TopK 的向量数据库 (Vector Databases based on TopK):

   • 代表: Milvus [76], PASE [86], AnalyticDB-V [80], Elasticsearch [4]。
   • 工作方式: 这些系统试图在数据库的框架内支持向量查询。它们的核心思想是“先捞后筛”：
     1. 用户发起一个复杂的混合查询（如 TopK + Filter）。
     2. 系统将 TopK 部分交给底层的向量索引库处理，并请求一个远大于最终所需数量的候选集（例如，最终需要50个，系统会请求 TopK(K')，其中 $K'$ 可能为1000或更大）。
     3. 系统获取这 $K'$ 个向量后，在内存中为它们创建一个临时的、具有单调性的索引（本质上就是一个排好序的列表）。
     4. 然后，在这个临时的小数据集上执行 Filter 等关系操作，最后返回满足条件的前50个结果。
   • 局限性: 这种方法的性能和准确性严重依赖于对 $K'$ 的猜测。
     • Milvus [76] 采用了一种试错法 (trial-and-error)，如果第一次 $K'$ 不够，就将 $K'$ 加倍再试一次，这会导致大量的重复计算。
     • PASE [86] 和 AnalyticDB-V [80] 倾向于让用户设置一个固定的、保守的大 $K'$，这在过滤选择性高（大部分数据被过滤掉）的场景下会造成巨大的性能浪费。

3.3. 技术演进

该领域的技术演进脉络可以看作是不断深化数据库与向量搜索集成的过程：

1. 阶段一：外部工具 - 开发者手动使用 ANNS 库（如 FAISS）进行向量搜索，然后将获得的结果 ID 再到传统数据库（如 PostgreSQL）中查询完整的元数据。流程繁琐，效率低下。
2. 阶段二：封装集成 - 向量数据库（如 Milvus）出现，将 ANNS 库作为黑盒引擎封装起来，提供统一的接口管理向量数据和执行混合查询。这简化了开发，但由于其“先捞后筛”的 TopK-based 架构，性能瓶颈依然存在。
3. 阶段三：深度融合 (本文工作) - VB ASE 打破了 TopK 接口的黑盒，深入到底层向量索引的遍历过程本身，从中抽象出更通用的 松弛单调性 属性，并基于此构建了一个真正统一的查询引擎。这代表了从“封装”到“原生融合”的演进。

3.4. 差异化分析

VB ASE 与现有工作最核心的区别在于查询执行模型的根本性转变：

• 现有系统 (TopK-based): 是一个两步、批量的模型。向量搜索 和 关系操作 是割裂的两个阶段。第一阶段批量获取大量数据，第二阶段在内存中处理这批数据。

• VB ASE (Iterator-based): 是一个单步、流式的模型。向量索引遍历 和 关系操作 被统一在一个查询计划中。数据像流水一样，从索引中一条一条地流出（通过 Next 接口），立刻经过关系操作符（如 Filter），查询引擎可以根据流经的数据动态判断是否满足 松弛单调性 和其他终止条件，从而在最优点即时终止整个查询流。

  这种转变使得 VB ASE 避免了对 $K$ 值的猜测，从而在各种复杂查询场景下都能达到近似最优的性能。

---

4. 方法论

本章节将深入剖析 VB ASE 的核心技术——松弛单调性及其在统一查询引擎中的应用。

4.1. 方法原理

传统数据库索引因其严格单调性而高效。相反，高维向量索引的遍历过程在距离上呈现振荡，不具备此特性。如下图（原文 Figure 1）所示，无论是基于聚类的 FAISS IVFFlat 还是基于图的 HNSW，在遍历过程中，访问到的向量与目标向量的距离都忽远忽近。

该图像是图表，展示了两种向量索引的遍历模式，分别是(a) FAISS IVFFlat 和 (b) HNSW。横轴表示步骤数，纵轴表示距离，反映两种索引在搜索过程中的距离变化趋势。

然而，作者观察到，尽管存在振荡，这些“设计良好”的向量索引的遍历过程普遍遵循一个两阶段模式 (two-phase pattern)：

1. 第一阶段（逼近阶段）: 遍历过程大致上是在向目标向量所在的区域靠近，尽管中间会有大的波动。

2. 第二阶段（远离阶段）: 在找到目标区域后，遍历过程会稳定地、渐进地离开这个区域。

   这个观察是 VB ASE 的核心直觉：如果系统能够识别出遍历过程已经进入了第二阶段，并且已经收集到了足够的结果，那么就可以安全地提前终止查询，因为后续的遍历不太可能找到更优的结果了。

基于此，VB ASE 的核心方法就是：

1. 形式化定义一个标准来判断遍历过程是否进入了“稳定远离”的第二阶段。这个标准就是松弛单调性 (Relaxed Monotonicity)。
2. 构建一个统一的查询引擎，该引擎在每次迭代时都使用这个标准来检查是否可以终止。

4.2. 核心方法详解 (逐层深入)

4.2.1. 松弛单调性的形式化定义

为了形式化地定义“稳定远离”阶段，我们需要量化两个概念：1）目标向量的“邻域”有多大；2）当前的遍历过程是否已经离开了这个“邻域”。

如下图（原文 Figure 2）所示，VB ASE 使用一个以查询向量 $q$ 为中心、半径为 $R_q$ 的球体来定义其“邻域”。

该图像是一幅示意图，展示了图2中松弛单调性的直观含义。它说明了目标向量$q$的邻域为半径$R_q$的邻居球，邻居球内包含与$q$最近的$E$个向量，遍历路径中当前位置的窗口大小为$w$，窗口内向量到$q$的中位距离记为$M_q^s$。

1. 邻域半径 $R_q$ 的定义: 在遍历到第 $s$ 步时，我们已经访问了 s-1 个向量。$R_q$ 被定义为在这些已访问向量中，离 $q$ 最近的 $E$ 个向量中最远的那一个的距离。 $$R _ { q } = M a x ( T o p E ( \{ D i s t a n c e ( q , \nu _ { j } ) | j \in [ 1 , s - 1 ] \} ) )$$

   • 符号解释:

     • $q$: 查询向量。

     • $\nu_j$: 历史上遍历过的第 $j$ 个向量。

     • $s$: 当前的遍历步数。

     • $Distance(q, \nu_j)$: 向量 $q$ 和 $\nu_j$ 之间的距离。

     • $TopE(\cdot)$: 一个函数，返回集合中距离最小的 $E$ 个值。

     • $Max(\cdot)$: 取集合中的最大值。

     • $E$: 一个超参数，定义了邻域的大小。对于一个 TopK 查询，必须有 $E \geq K$。

       直观理解： $R_q$ 代表了到目前为止我们找到的“最好结果”的边界。在遍历初期（逼近阶段），我们会不断发现更近的向量，所以 $R_q$ 会逐渐变小。进入稳定阶段后，$R_q$ 趋于稳定。

2. 当前遍历区域 $M_q^s$ 的定义: 为了衡量当前遍历的“位置”，VB ASE 不看单个向量，而是看最近一小段时间（一个窗口）的趋势，以平滑振荡。$M_q^s$ 被定义为最近 $w$ 步遍历到的所有向量与 $q$ 之间距离的中位数 (median)。 $$M _ { q } ^ { s } = M e d i a n ( \{ D i s t a n c e ( q , \nu _ { i } ) | i \in [ s - w + 1 , s ] \} )$$

   • 符号解释:
     • $w$: 一个超参数，定义了滑动窗口的大小。
     • $Median(\cdot)$: 取集合中的中位数。使用中位数是为了抵抗窗口中个别离群点（特别近或特别远的点）的干扰，使估计更稳健。

3. 松弛单调性 (Relaxed Monotonicity) 的最终定义: 一个索引的遍历过程如果满足以下条件，就被认为具有松弛单调性：

   Definition 1 Relaxed Monotonicity $$> \exists s , M _ { q } ^ { t } \geq R _ { q } , \forall t \geq s . >$$

   • 符号解释:

     • $\exists s$: “存在一个步数 $s$”。

     • $\forall t \geq s$: “对于所有大于等于 $s$ 的步数 $t$”。

       直观理解： 这条公式的含义是，遍历过程中存在一个转折点 $s$，从这个点之后，当前遍历区域的距离 ($M_q^t$) 将持续地大于等于我们已知的最优结果边界 ($R_q$)。这标志着遍历过程已经稳定地进入了“远离阶段”。

4.2.2. 统一查询执行引擎

基于松弛单调性，VB ASE 构建了一个统一查询引擎，其核心组件如下：

1. 统一的迭代器模型 (Iterator Model): VB ASE 对现有的向量索引库（如 HNSW, IVFFlat）进行了微小的改造，将它们原本不透明的 TopK 接口，改造成了符合传统数据库火山模型 (Volcano Model) 的 Open, Next, Close 接口。

   • Open: 初始化一次查询，例如在 HNSW 中定位到上层图的入口点。
   • Next: 返回下一个最值得探索的向量，并更新内部状态以供下一次调用。
   • Close: 清理查询状态。 这样，无论是 B-Tree 索引还是 HNSW 索引，对于上层查询引擎来说，都变成了可以逐条吐出数据的“迭代器”，实现了接口层面的统一。

2. 通用的终止条件检查 (Generalized Termination Condition Check): 在流式查询执行过程中，每当 Next 接口返回一个新元组，系统都会检查是否可以终止。VB ASE 的终止条件是复合的： $Query Termination = Original Condition AND Relaxed Monotonicity Condition$

   • Original Condition: 这是由具体查询类型决定的传统终止条件。
     • 对于 TopK 查询：已经收集到 $K$ 个结果。
     • 对于 $Range Filter(distance < D)$ 查询：当前遍历到的向量距离已经大于 $D$。
   • Relaxed Monotonicity Condition: 这是一个简化的实时检查，即 $M_q^s > R_q$。一旦这个条件成立，系统就认为定义中的 $\forall t \geq s$ 都会成立，从而触发终止判断。

   示例 (TopK + Filter): 假设查询是“寻找价格低于100元的最相似的10个商品”。VB ASE 的执行流程如下：

   1. 调用索引的 Next 接口，获取一个向量。
   2. 检查其价格是否低于100元。
   3. 如果是，则将其放入一个大小为10的优先队列（候选结果集）。
   4. 更新 $R_q$ 和 $M_q^s$。
   5. 检查终止条件：候选结果集是否已满10个 并且 $M_q^s > R_q$ 是否成立？
   6. 如果两个条件都满足，则终止查询并返回结果。否则，回到步骤1。

4.2.3. 结果等价性证明

VB ASE 的一个强大之处在于，它不仅更快，而且能保证结果的质量。论文证明了其结果与使用“最优 $\widetilde{K}$”的 TopK 方法等价。

如下图（原文 Figure 3）所示，我们对比两种方法处理 $TopK+Filter$ 查询的流程。

该图像是论文中图3的示意图，展示了基于TopK接口的系统与VB ASE系统在索引遍历和查询处理上的结果等价性及流程对比，强调VB ASE利用松弛单调性替代传统的TopK方法。

• TopK-based 方法:

  1. 遍历索引，访问 $R_1$ 个向量。
  2. 用 $TopK'(Sort(R_1))$ 选出距离最近的 $K'$ 个，构建临时单调索引。
  3. 对这 $K'$ 个结果进行 Filter 和 $Limit_K$ 操作。
  4. 假设系统能奇迹般地猜到最优的 $\widetilde{K}$（即扫描 $\widetilde{K}$ 个数据后，经过过滤正好得到 $K$ 个结果），其最终结果可以表示为：$r_1 = Limit\_K(Filter(Sort(R_1)))$。

• VB ASE 方法:

  1. 遍历索引，访问 $R_2$ 个向量，在遍历过程中同时进行 Filter。
  2. 满足 Filter 条件的向量被放入一个优先队列并排序 Sort。
  3. 当收集满 $K$ 个结果并且满足松弛单调性时终止。
  4. 其最终结果可以表示为：$r_2 = Limit\_K(Sort(Filter(R_2)))$。

证明的关键： 由于 VB ASE 和最优 TopK 方法都使用相同的底层向量索引、相同的遍历算法，并且都依赖于（等价的）松弛单调性作为终止遍历的信号，因此它们在终止前所访问的原始向量集合是完全相同的，即 $R_1 = R_2$。

因为 Filter 和 Sort 两个操作对于最终的 TopK 结果来说是可交换的（先过滤再排序，和先排序再过滤，只要扫描的数据集相同，最终得到的前K个结果是一样的），所以可以得出 $r_1 = r_2$。

这个证明揭示了 VB ASE 高效的本质：它通过流式处理，在遍历过程中动态地确定了最优扫描范围 $\widetilde{K}$，而无需像其他系统一样去猜测。

4.2.4. 查询规划与优化

VB ASE 作为一个数据库系统，还包含了查询优化器来选择最佳执行计划。

• 成本估算: 为了在多个可能的查询计划（例如，先用B-Tree索引过滤价格，还是先用向量索引过滤相似度）中做出选择，VB ASE 扩展了传统的成本模型：

  • 向量计算成本 $t_v$: 不再是常数，而是与向量维度 dim 相关： $$t _ { \nu } ( d i m ) = t \cdot c \cdot d i m$$
  • 选择性估算 (Selectivity Estimation): 对于过滤器将过滤掉多少数据，VB ASE 采用采样的方法。通过在一个小的随机样本上运行过滤器来估算其在整个数据集上的选择性。
  • 索引扫描成本: 论文为分区式索引（IVFFlat）和图索引（HNSW）分别给出了详细的成本估算公式 $C_p$ 和 $C_g$，综合考虑了启动成本、I/O成本和向量计算成本。

• 多列扫描优化: 对于涉及多个向量列的查询（如“图片和描述都很像”），传统的 NRA 算法采用轮询 (round-robin) 方式依次访问每个索引。作者发现当不同列的权重不同时，这种方式效率低下。VB ASE 提出了一种自适应加权扫描算法：

  1. 算法会跟踪每个索引返回结果的“质量”（平均得分）。
  2. 在每一轮扫描中，它会更频繁地访问那些历史上返回结果质量更高的索引（利用），但同时也会以较低的频率访问其他索引以避免陷入局部最优（探索）。
  3. 分配给索引 $i$ 的额外扫描次数 $W_i$ 与其平均得分 $avg_i$ 的倒数成正比： $$W _ { i } = \left\lceil n _ { 2 } \times \frac { 1 / a \nu g _ { i } } { \underset { j = 1 } { \sum } 1 / a \nu g _ { j } } \right\rceil$$ 这个优化使得查询能够更快地收敛到高质量结果。

---

5. 实验设置

5.1. 数据集

• 来源: 实验基于 Recipe1M [68] 数据集构建，这是一个包含超过100万份食谱的大型公开数据集，每个食谱都包含配料、烹饪说明和菜品图片。
• 构建: 作者从中抽取数据并构建了两个表格，以模拟真实的向量与标量混合数据场景。

  • Recipe Table (食谱表): 包含约33万条食谱。其表结构（原文 Table 2）如下：

    Column Name	Data Type	Example
    recipe_id	identifier	1
    images	list of strings	["data/images/1/0.jpg", . . ]
    description	text	[ingredients] + [instruction]
    images_embedding	vector	[0.0421, 0.0296, . . , 0.0273]
    description_embedding	vector	[0.0056, 0.0487, … * , 0.0034]
    popularity	integer	300

    此表包含了两个1024维的向量列 images_embedding 和 description_embedding，以及一个标量列 popularity（热度）。

  • Tag Table (标签表): 包含1万个从食谱中提取的标签。其表结构（原文 Table 3）如下：

    Column Name	Data Type	Example
    id	identifier	1
    tag_name	text	"salad"
    tag_vector	vector	[0.0137, 0.0421, · · , 0.0183]

    此表用于 JOIN 查询实验，通过 tag_vector 与食谱的 images_embedding 进行相似度匹配。

• 查询: 论文设计了8个SQL查询（Q1-Q8）覆盖了从简单到复杂的各种场景，包括单向量TopK、带标量过滤的TopK、多向量TopK、向量范围过滤以及向量JOIN。

5.2. 评估指标

实验主要使用两个指标来评估系统性能：查询延迟和召回率。

• 延迟 (Latency):

  1. 概念定义: 指的是从发出查询到接收到完整结果所花费的时间。这是衡量在线服务性能的核心指标。论文报告了平均、中位数和99百分位 (99th percentile)延迟。99百分位延迟尤其重要，因为它反映了系统的“最坏情况”下的性能表现（即尾延迟），对于保证用户体验的稳定性至关重要。
  2. 数学公式: 直接测量时间，单位通常是毫秒 (ms)。
  3. 符号解释: N/A。

• 召回率 (Recall):

  1. 概念定义: 由于 ANNS 是近似搜索，其结果可能不是100%精确的。召回率用于衡量查询结果的准确性或完整性。它回答了这样一个问题：“在所有真正应该被找到的相关结果中，我们的系统实际找到了多少？”。召回率越高，说明结果质量越好。
  2. 数学公式: $$\text{Recall} = \frac{|\text{Retrieved Results} \cap \text{Ground Truth}|}{|\text{Ground Truth}|}$$
  3. 符号解释:
     • Retrieved Results: 系统返回的结果集合。
     • Ground Truth: 真实、准确的结果集合。在实验中，这通常是通过运行一个极慢但精确的算法（如全表扫描）得到的。
     • $|\cdot|$: 表示集合中元素的数量。
     • $\cap$: 集合的交集。

5.3. 对比基线

VB ASE 与以下四种代表性的系统进行了比较：

• PostgreSQL [12]: 一个功能强大的开源关系型数据库。在这里它作为精确搜索的基准，通过全表扫描来执行向量查询。它的结果被用作计算其他系统召回率的 真实标注数据 (Ground Truth)，但其延迟非常高，不适用于在线场景。

• PASE [86]: 一个基于 PostgreSQL 的扩展，它实现了与 VB ASE 相同的目标——在数据库中支持向量查询。但它采用的是基于 TopK 的方法，即先获取一个大的候选集再处理，是 VB ASE 想要超越的直接竞争对手。

• Milvus [76]: 一个非常流行的、专门为向量搜索设计的开源数据管理系统。它也采用基于 TopK 的方法，并通过试错法处理复杂查询。

• Elasticsearch [4]: 一个广泛使用的分布式搜索引擎，它通过插件支持基于 HNSW 的向量搜索。它同样采用基于 TopK 的方法。

  为了公平比较，所有支持近似搜索的系统（PASE, Milvus, Elasticsearch, VB ASE）都配置了相同的底层向量索引算法—— HNSW，并使用了相同的参数。

---

6. 实验结果与分析

6.1. 核心结果分析

实验的核心结果汇总在原文的 Table 4 中。下表是该表格的完整转录，由于其结构复杂，使用 HTML $<div class="table-wrapper"><table>$ 格式呈现。

点击展开/折叠 原文 Table 4: 8个查询的总体结果 (延迟单位: ms)

System	Recall	Q1: Single-Vector TopK			Recall	Q2: Single-Vector TopK+Numeric Filter			Recall	Q3: Single-Vector TopK+String Filter			Recall	Q4: Multi-Column TopK
		average	median	99th		average	median	99th		average	median	99th		average	median	99th
PostgreSQL	1	2,980.1	3,021.7	3,133.6	1	1,108.3	1,124.1	2,286.2	1	4,322.2	3,529.3	9,953.0	1	5,610.0	5,604.7	5,769.8
PASE	0.9949	4.8	3.5	5.1	0.9987	29.3	28.7	61.7	0.9982	13.2	10.7	17.9	-	-	-	-
Milvus	0.9949	9.4	9	12.7	0.9919	33.7	23.9	121.4	-	-	-	-	0.9041	6,696.4	8,349.3	9,299.0
Elasticsearch	0.9949	43.1	41.8	48.9	0.5010	97.9	98.1	118.1	0.8378	79.9	90.0	100.9	-	-	-	-
VBase	0.9949	4.9	3.9	5.3	0.9989	11.7	6.3	51.7	0.9983	7.9	6.7	10.4	0.9696	19.8	18.4	46.4
System	Recall	Q5: Multi-Column TopK+Numeric Filter			Recall	Q6: Multi-Column TopK+String Filter			Recall	Q7: Vector Range Filter			Recall	Q8: Join
		average	median	99th		average	median	99th		average	median	99th		average	median	99th
PostgreSQL	1	1,192.9	1,234.4	2,343.6	1	6,543.2	5,996.3	16,734.6	1	8,244.9	8,212.6	8,641.6	1	129,051,273.9
PASE	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
Milvus	0.9691	12,637.9	5,617.4	36,887.9	-	-	-	-	-	-	-	-	-	-	-	-
Elasticsearch	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
VBase	0.9805	35.8	24.9	160.7	0.9626	21.6	18.3	64.8	0.9840	10.8	2.2	168.9	0.9992	16,335.9

从上表可以得出以下关键分析：

• Q1 (简单 TopK): 在这个最简单的场景下，所有近似系统的召回率都一样高 (0.9949)。VB ASE 的性能 (4.9ms) 与同样基于C语言实现的 PASE (4.8ms) 几乎持平，比 Milvus(Go/C++) 和 Elasticsearch(Java/C++) 快。这表明 VB ASE 的基础框架开销很小。

• Q2/Q3 (TopK + 标量过滤): 这是 VB ASE 优势开始显现的地方。

  • 性能: 在 Q2 中，VB ASE (11.7ms) 比 PASE (29.3ms) 快了 2.5倍，比 Milvus (33.7ms) 快了 2.8倍。这是因为 PASE 和 Milvus 必须预先获取一个很大的候选集（即猜测一个大的 $K'$），导致了不必要的扫描。VB ASE 则在遍历中动态判断，只扫描了必要数量的数据。
  • 准确性: Elasticsearch 试图用一个较小的 $K'$ 来提升性能，但导致其召回率大幅下降（Q2 中仅为 0.5010），说明其猜测失败，返回的结果不足。
  • 结论: VB ASE 在保持与 PASE/Milvus 同等高召回率的同时，实现了显著的性能提升。

• Q4/Q5/Q6 (多列 TopK): VB ASE 的优势变得极为巨大。

  • 在 Q4 中，VB ASE (19.8ms) 比 Milvus (6,696.4ms) 快了超过300倍。
  • 在 Q5 中，VB ASE (35.8ms) 比 Milvus (12,637.9ms) 快了超过350倍。
  • 原因: Milvus 处理多列查询的“试错法”效率极低，它需要为每一列反复执行 TopK 查询并猜测 $K$ 值，导致查询延迟甚至高于 PostgreSQL 的全表扫描。而 VB ASE 的统一流式引擎和自适应扫描策略可以非常高效地处理这类查询。

• Q7 (向量范围过滤): 同样地，VB ASE (10.8ms) 表现出色。对于基于 TopK 的系统，这类查询更难处理，因为满足范围条件的结果数量是完全未知的，使得对 $K'$ 的猜测变得更加困难。如原文 Table 6 所示，PASE 只有在将 $K'$ 设置到10000时才能达到高召回率，但此时延迟高达 392.1ms，是 VB ASE 的36倍。

• Q8 (Join): 这是 VB ASE 的“杀手级应用”。

  • VB ASE 在 16.3 秒内完成了查询，而 PostgreSQL 的暴力嵌套循环连接需要 129,051秒（约35.8小时），VB ASE 比它快了将近 7900倍。

  • 同时，VB ASE 的召回率高达 0.9992，结果质量非常高。

  • 其他所有基线系统都无法高效执行这种查询。这充分证明了 VB ASE 的统一引擎模型极大地扩展了向量数据库的能力边界。

    下图（原文 Figure 8）展示了 VB ASE 查询优化器的有效性。在混合过滤查询中，VB ASE 的成本模型能准确预测是使用 B-Tree 索引更优还是使用向量索引更优，并选择与“真实最优”几乎一致的执行计划，而 PASE 的默认策略则会做出错误的判断。

    该图像是图8，展示了不同估计方法下查询执行时间的曲线图，图(a)中标量过滤器选择性固定为0.13，图(b)中区间过滤器选择性固定为0.90，比较了Ground Truth、VBase和默认方法的性能表现。

6.2. 数据呈现 (表格)

除了上述核心结果表，论文中的其他关键表格也支撑了其结论。例如，原文 Table 5 详细对比了在不同过滤选择性下 VB ASE 和 PASE 的表现，清晰地展示了 PASE 这类 TopK-based 方法对固定 $K'$ 的敏感性，以及 VB ASE 在各种情况下的稳健性。

以下是原文 Table 5 的转录：

分析:

• 当过滤选择性很低 (Selectivity = 0.03) 时，意味着需要扫描大量数据才能找到足够的结果（平均最优 $\widetilde{K}$ 为1772）。PASE 只有在设置 $K'$=10000 时才能获得高召回率，但延迟高达 62.8ms。而 VB ASE 自动适应了这种情况，以 34.5ms 的延迟获得了近乎完美的召回率。
• 当过滤选择性很高 (Selectivity = 0.9) 时，PASE 使用 $K'$=100 已经能获得不错的召回率，但 VB ASE 依然以更低的延迟 (5.7ms vs 10.4ms) 获得了同样高的召回率。
• 这有力地证明了 VB ASE 对不同查询场景的强大适应能力。

6.3. 消融实验/参数分析

• 多列扫描策略分析 (原文 Table 7): 这部分可以看作是对多列扫描优化模块的消融实验。实验对比了轮询 (Round-Robin)、贪心 (Greedy) 和 VB ASE 的自适应策略。结果表明，当权重差异大时，贪心策略表现好；但当权重相近时，贪心策略容易陷入局部最优，导致召回率下降。而 VB ASE 的自适应策略在所有情况下都取得了高召回率和稳健的低延迟，证明了其设计的优越性。

• 索引类型支持 (原文 Table 8): 论文还展示了 VB ASE 集成 SPANN（一种基于磁盘的分区式索引）的结果。虽然由于磁盘I/O导致整体延迟高于内存中的 HNSW，但实验结果依然显示出 VB ASE 在各种复杂查询上的巨大性能优势。这证明了 松弛单调性 框架的通用性，它不仅适用于图索引，也适用于分区式索引；不仅适用于内存索引，也适用于磁盘索引。

---

7. 总结与思考

7.1. 结论总结

本文提出了 VB ASE，一个旨在统一在线向量相似性搜索和传统关系查询的新型数据库系统。其核心创新在于识别并形式化定义了松弛单调性 (Relaxed Monotonicity)，将其作为连接高维向量索引和传统标量索引的共同理论基础。

基于这一理论，VB ASE 构建了一个流式、迭代的统一查询引擎，它抛弃了现有系统所依赖的、低效且笨拙的 TopK 接口。通过在查询执行过程中动态检查松弛单调性来即时终止遍历，VB ASE 能够在保证结果质量与“最优 TopK 方法”等价的同时，实现远超现有系统的性能。

实验结果强有力地证明了 VB ASE 的价值：

• 在带有过滤和多列聚合的复杂在线查询中，VB ASE 的性能比 Milvus、PASE 等最先进系统高出1到3个数量级。

• VB ASE 成功地将查询能力扩展到了以往向量数据库无法高效支持的领域，如分析性的向量 JOIN 查询，实现了超过7000倍的性能飞跃。

  总而言之，VB ASE 通过一个优雅的理论抽象和扎实的系统实现，为解决 AI 时代数据管理的核心挑战——如何高效融合非结构化语义搜索与结构化数据查询——提供了一个开创性的解决方案。

7.2. 局限性与未来工作

尽管论文取得了显著成功，但仍可从以下几个方面思考其潜在的局限性和未来工作：

• 超参数调优: 松弛单调性 的定义引入了两个关键超参数 $E$ (邻域大小) 和 $w$ (滑动窗口大小)。论文提到这些参数的设置与具体索引算法和数据分布有关，并可以通过调优来平衡延迟和准确率。然而，如何自动化、自适应地设置这些参数，以适应不同的查询和数据，是一个值得深入研究的未来方向。一个全自动的系统对用户会更加友好。
• 松弛单调性的普适性: 论文验证了该属性在 HNSW、IVFFlat、SPANN 等主流索引上的有效性。但未来可能会出现更多新型的向量索引结构。松弛单调性 是否对所有（或绝大多数）设计合理的 ANNS 算法都适用，仍有待进一步的探索和验证。
• 更复杂的查询支持: 实验主要集中在 TopK, Filter, Join 的组合上。对于更复杂的分析查询，如带有向量相似度的分组聚合 (Group-by)，VB ASE 的框架是否依然适用和高效，是另一个可以探索的方向。
• 分布式环境: 本文的实现和评估主要在单机环境下进行。如何将 VB ASE 的统一查询引擎扩展到分布式环境中，并处理分布式数据带来的数据分区、负载均衡、结果合并等新挑战，是其走向大规模工业应用必须解决的问题。

7.3. 个人启发与批判

• 启发:

  1. 深入本质，而非封装黑盒: 这篇论文给我最大的启发是，面对一个棘手的系统集成问题时，最有力的解决方案往往不是在现有组件的接口层面进行修补或封装，而是敢于打破黑盒，深入理解组件的内部工作原理，并从中抽象出更基本、更通用的属性。松弛单调性 就是这样一个深刻的洞察，它直接绕开了 TopK 接口带来的所有问题。
  2. 理论与实践的完美结合: VB ASE 不仅提出了一个新颖的理论概念，还通过严谨的数学证明、扎实的系统工程（基于PostgreSQL的扩展）和详尽的实验评估，完整地展示了从理论到实践的闭环。这是一个非常出色的系统研究范例。
  3. 流式处理的威力: 将批量处理模型（先捞后筛）转变为流式处理模型（边走边看），是 VB ASE 高效的关键。这种思想在许多计算领域（如大数据处理的 Spark Streaming vs. MapReduce）都显示出巨大威力，本文则成功地将其应用于数据库查询执行。

• 批判性思考:

  1. 实现的复杂性: VB ASE 要求对底层向量索引进行改造以支持 Next 接口。虽然作者声称对 HNSW 的修改不到200行代码，但对于一个组织来说，维护一个“魔改”版的向量索引库，而不是直接使用社区标准版，可能会带来额外的工程和维护成本。
  2. 成本模型 vs. 现实: 论文提出的查询计划成本模型依赖于采样来估计选择性。虽然实验表明这在大多数情况下是有效的，但在数据分布极度不均或查询条件非常罕见的情况下，采样的准确性可能会下降，从而导致优化器选择次优计划。
  3. “在线”与“分析”的界限: VB ASE 成功将在线查询（TopK）和分析查询（Join）统一在了一个引擎下。但在实际部署中，这两类查询对资源的需求和性能目标（低延迟 vs. 高吞吐）可能存在冲突。一个混合负载的 VB ASE 系统将如何进行资源调度和隔离，是一个有趣的实际问题。