ReaderMX.
PostgreSQL码农集散地

OceanBase 源码学习: 2.6 向量索引系统

Pdigoal约 6 分钟

OceanBase 源码学习: 2.6 向量索引系统

向量索引系统在 OceanBase 分布式数据库架构下提供向量相似性搜索能力，该系统通过HNSW（Hierarchical Navigable Small World）、IVF（Invert File）以及量化(quantization)等多种索引算法/技术，实现对高维向量数据的高效最近邻查询。

该系统通过 DAS（数据访问服务）层与 OceanBase 的 SQL 处理流水线集成，支持独立的向量查询，以及向量相似度与传统 SQL 谓词相结合的混合查询。

架构概述

向量索引系统采用插件式架构，将外部向量索引库（主要是 VSAG lib 库）与 OceanBase 的存储层、查询处理层集成。

高级系统架构



Image

源文件:

  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_plugin_vector_index_service.h
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/sql/das/iter/ob_das_hnsw_scan_iter.h
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_plugin_vector_index_adaptor.h

核心组件

向量索引适配器

ObPluginVectorIndexAdaptor 作为 OceanBase 与外部向量索引库的主要接口，管理多种类型的向量索引数据结构，并协调不同索引类型之间的内存管理。



Image

适配器管理三个主要数据结构：

  • 索引增量（VIRT_INC）：处理新插入和更新
  • 索引快照（VIRT_SNAP）：维护历史快照以确保查询一致性
  • 向量位图（VIRT_BITMAP）：使用 roaring bitmaps 跟踪删除和插入的向量

源文件:

  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_plugin_vector_index_adaptor.h#L77-L85
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_plugin_vector_index_adaptor.cpp#L424-L481

算法支持

系统通过 ObVectorIndexAlgorithmType 枚举支持多种向量索引算法：

向量索引算法类型
描述
用例
VIAT_HNSW
分层可导航小世界网络(HNSW)
通用 ANN 搜索
VIAT_HNSW_SQ
采用标量量化的 HNSW
内存优化搜索
VIAT_HNSW_BQ
采用二进制量化的 HNSW
超快速近似搜索
VIAT_IVF_FLAT
向量的倒排文件(通过kmeans计算N个中心点, 按距离放入各中心点, 形成多中心点聚集存储)
大规模精确向量搜索
VIAT_IVF_PQ
量化后再倒排
压缩向量存储
VIAT_HGRAPH
带有额外元数据的 HNSW
增强型 HNSW 变体(牺牲一定精确度换取低内存消耗和更高性能)

更多可参考:

支持的距离度量包括 L2 欧几里得 (VIDA_L2)、内积 (VIDA_IP) 和余弦相似度 (VIDA_COS)。

源文件:

  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_vector_index_util.h#L77-L89
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_vector_index_util.h#L54-L60

查询处理管道

HNSW 查询执行

向量查询通过 ObDASHNSWScanIter 进行处理，它实现了支持多种过滤策略的复杂查询执行管道。



Image

查询执行遵循以下阶段：

  • 1 查询向量准备：从 SQL 表达式中提取并验证查询向量
  • 2 索引选择：根据数据新鲜度在增量索引和快照索引之间进行选择
  • 3 过滤策略：根据查询特征应用预过滤、后过滤或自适应过滤
  • 4 结果聚合：合并来自多个辅助表(疑问: 辅助表是不是指多个向量索引/标量索引? 结果聚合是不是类似PG的多index扫描中的 bitmapAnd/bitmapOr 合并? 看下一节)的结果
  • 5 距离计算：计算最终的相似度分数进行排名(reranking)

源文件:

  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/sql/das/iter/ob_das_hnsw_scan_iter.h#L29-L40
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/sql/das/iter/ob_das_hnsw_scan_iter.cpp#L502-L600

查询上下文管理

ObVectorQueryAdaptorResultContext 管理查询状态和结果处理：



Image

源文件:

  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_plugin_vector_index_adaptor.h#L253-L328
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_plugin_vector_index_adaptor.cpp#L163-L188

存储架构

辅助表结构

向量索引由多个辅助表支持，这些辅助表维护向量 ID 和物理表 RowID(row keys) 之间的映射：

表类型
目的
Key 列
rowkey_vid_table
将行键(row key)映射到向量 ID
rowkey → vid
vid_rowkey_table
将向量 ID 映射到行键
vid → rowkey
inc_index_table
增量索引数据
vid, vector, metadata
vbitmap_table
删除/插入跟踪
vid, operation_type
snapshot_index_table
历史索引快照s
vid, vector, scn

从辅助表的设计, 可看到OceanBase沿袭了LSM-tree的思想(并非完全一样), 也将数据分成了增量数据、持久化数据, 通过合并将增量数据合并到持久化快照.



Image

源文件:

  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_plugin_vector_index_adaptor.h#L39-L72
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_plugin_vector_index_adaptor.cpp#L713-L813

内存管理

系统采用专门的内存管理来进行向量运算：

  • ObVsagMemContext ：管理 VSAG 库操作的内存
  • ObVsagSearchAlloc ：搜索操作的自定义内存分配器
  • Roaring Bitmap Memory ：专门用于位图操作的内存分配

源文件:

  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_plugin_vector_index_adaptor.h#L231-L251
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_plugin_vector_index_adaptor.cpp#L348-L422

异步任务管理

后台优化

ObPluginVectorIndexScheduler 管理用作索引优化和维护的后台任务：



Image

后台任务包括：

  • 索引构建：从数据表构建新的向量索引
  • 索引优化：将增量更新合并到快照索引中
  • 内存清理：释放未使用的索引内存并清理弃用的适配器
  • IVF 维护：导入和清空 IVF 辅助表

源文件:

  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_plugin_vector_index_scheduler.h
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_vector_index_async_task_util.h#L53-L75

任务执行框架



Image

源文件:

  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_vector_index_async_task_util.h#L86-L115
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/share/vector_index/ob_vector_index_async_task.cpp#L22-L46

集成点

DAS(Data Access Service) 层集成

向量索引系统通过专门的迭代器和算子与 OceanBase 的 DAS（数据访问服务）集成：

  • ObDASHNSWScanIter ：基于 HNSW 的向量扫描主迭代器
  • ObVectorIndexLookupOp ：向量扫描运算符
  • ObDASVecAuxScanCtDef ：控制向量辅助扫描的定义

SQL 表达式集成

在SQL 表达式内即可使用向量运算符，并可与 WHERE 子句和 ORDER BY 运算中的传统谓词结合使用。

源文件:

  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/sql/das/iter/ob_das_hnsw_scan_iter.h
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/sql/das/ob_vector_index_lookup_op.h
  • https://github.com/oceanbase/oceanbase/blob/8e2580cf/src/sql/das/ob_das_vec_define.h

更多详细内容请关注我的github: https://github.com/digoal/blog

KEEP THE THREAD GOING

更多来源文章