Skip to content

quiver.md

Latest commit

 

History

History
88 lines (58 loc) · 9.77 KB

quiver.md

File metadata and controls

88 lines (58 loc) · 9.77 KB
Raw

QuIVer 向量索引

当前版本：0.9.0；见中英文变更说明。

QuIVer 是 TriviumDB 的近似最近邻（ANN）图索引，使用紧凑量化表示完成图导航，再从原始向量计算余弦相似度。SM-L2 导航从 0.8.9 起默认启用，0.8.10 增加构图连通性与增量维护保护，详见 版本变更。

自动构建阈值

从 0.9.0-beta.2 起按 ceil(666,667 / dim) 计算自动构建节点阈值，并限制在 209–834 节点，约为此前阈值的十二分之一。384/768 维为 834，1024 维为 652，1536 维为 435，2048 维为 326，3072 维为 218。达到阈值后，在下一次符合条件的查询准备或显式预热中构建；普通查询与连续向量视图入口共享同一判断。

auto_build_quiver=false 关闭自动构建；高于 3072 维继续使用精确 BruteForce。ANN 查询通过紧凑导航缩小原始向量精排范围，实例容量还需计入索引常驻结构、首次构建工作区与向量页驻留。

默认查询路径

数据库的 f32/f16 浮点向量查询采用：原 BQ 快速构图 → 签名多样性保护与入口可达性修复 → 无训练 SM-L2 导航 → 有界原始向量余弦精排 → 按需读取 Payload。近邻选择沿用原 QuIVer 的 BQ 路径；最终剪枝出现同签名近邻挤占时，利用既有容量保留其他签名的候选。随后仅给不可达区域补边。没有签名碰撞且原本全可达的图，其拓扑保持不变。

u64 用于 SimHash 等二进制指纹，查询按原始整数位模式执行精确汉明检索，分数为各分量的匹配位数之和。自动查询、批量查询和重开保持相同度量；加载时跳过历史 u64 QuIVer sidecar，只读打开保留原文件。显式 QuIVer 构建适用于 f32/f16，对 u64 返回 TDB_INVALID_INPUT。

环节 当前行为
构图 使用低位 BQ 编码和批量并行图构建路径，保留签名多样性并保护入口可达性
表示 两个位平面保存符号与强弱分组，并保存每向量弱幅值、幅值差与重建范数等紧凑元数据
导航 结合位计数和幅值运算，计算重建向量的平方 L2 评分
精排 默认查询仍按原始向量余弦相似度返回分数，SM-L2 名称不表示切换了用户查询的度量
训练 默认路径无需查询样本校正、锚点拟合、码本或旋转训练；每向量幅值由该向量自身计算
执行 768 维保留专用实现，其他合法维度使用通用实现；运行时选择可用 SIMD，保留标量和尾部处理
维度 支持 1..=3072，包括非 64 倍数；更高维数据库保持精确 BruteForce 路由

概念上，每维重建值为 符号 × (弱幅值 + 强位 × 幅值差)；SM-L2 比较重建向量之间的平方距离。它不等同于仅比较两个位串的 Hamming 距离，也不保证近似候选与精确余弦 Top-K 完全相同。

底层 QuIVerSearchConfig 的有效候选宽度至少覆盖 top_k，并受节点数限制。未显式指定 rerank_limit 时默认预算为 64，实际预算按 min(有效候选宽度, max(top_k, 指定预算或64)) 计算。上层管线显式传入的预算继续生效；过滤拒绝和墓碑不占成功精排名额。低 ef 会收紧有效精排预算，普通默认查询不因此静默回退旧 BQ。

默认、显式与兼容模式

候选按近似距离进入精排名额，截断处的同分候选按外部 NodeId 升序选择，最终结果按精确分数降序、外部 NodeId 升序排列；顺序适用于实际搜索到的候选集合。默认 SM 与公开 BQ 精排路径采用同一结果同分规则。直接调用 QuIVer::search、search_with_scorer、search_dual_queue 时，维度错误、非有限查询及 top_k=0 返回空结果；冷向量回调中的维度错误和非有限分量会使对应候选被拒绝。

模式 启用与度量 边界
默认无训练 SM-L2 数据库构图和加载后自动准备；最终余弦精排 Python、Node.js 和 Rust 普通查询共用 Core，无需手动调用启用函数
显式校正 SM Rust 显式安装带校正系数和锚点的模型 需要显式安装校正模型；默认查询不执行模型拟合
显式原生 L2 Rust enable_quiver_sm_native_l2()；保留原始幅值与合法零向量，返回负平方欧氏距离 不是数据库全局度量开关；不等同于普通余弦查询，也不保证欧氏数据上的高召回
自定义导航 使用 NavigationScorer 的 TSNG 等入口 按所选 scorer 计算导航得分
独立旧索引兼容 仅从字节加载、尚未绑定原始向量的 QuIVer 对象 可保留旧 BQ 路径；数据库加载流程会补齐默认 SM 状态

显式覆盖在图或向量变化后失效，普通查询恢复默认 SM-L2。显式校正锚点被过滤屏蔽时，可以采用无锚点默认 SM。

增量维护、重载与内存

  • 构图时准备默认 SM 状态，插入时追加新节点的紧凑行。墓碑可以参与导航，但不进入结果，也不能将已复用 slot 中的新向量当作旧节点向量。
  • 构图和加载时派生从当前入口覆盖全图的导航树，每节点保存一个 u32 父节点，计入索引热内存。增量剪枝保留树边，入口升层时连接旧树；补边使用既有邻接表容量，不自动扩大存储步长。必要时出度可高于常规 m0，但不超过原有 2*m0 容量；无碰撞且全可达的正常图不额外加环。
  • 入口全可达保证的是图拓扑可以遍历全库，不代表有限 ef、精排预算下的 Recall@K 必然为 100%；近重复、量化签名碰撞和低内在维度数据仍需独立验证召回和性能。
  • 旧索引通过重新构建应用本次修复，不提供加载时补边或独立的旧图修复入口。加载发现入口不可达节点时返回需要重建的错误，数据库沿用现有缺失/无效索引处理流程：通常在首次查询时重建，严格索引策略则返回错误。
  • .quiver 磁盘格式仍为 v1。重建后的索引加载时保持邻接表逐边不变，仅派生运行期导航树。数据库从实际向量池按 slot 流式恢复默认 SM 状态；恢复需要读取冷向量，启动成本取决于数据量与存储性能。加载扫描结束后回收干净向量页：Unix 提交释放建议，Windows 从原文件句柄重建同代冷映射，后续精排按需触及向量。启动峰值与加载结束后的驻留工作集分别采集。
  • 默认准备过程不保留第二份全库 FP32 向量。显式模式的安装路径可能使用全量临时 FP32 缓冲，安装峰值与稳定驻留应分别计量；显式原生 L2 的度量选择不由旧图文件自动恢复。
  • 热内存包括索引 BQ、默认/显式 SM 状态、图、ID/slot 映射、派生缓存和每线程工作区。
  • 原始向量及 Payload 冷层、映射文件、RSS/PSS、OS PageCache 和安装临时峰值分别报告。SM 拥有内存进入索引及内核预算，不代表预算覆盖整个进程或 OS PageCache。

性能评估

召回率与吞吐取决于向量分布、图参数、搜索宽度和精排预算。应使用业务数据测量 Recall@K、QPS、P50/P95/P99 延迟以及构图、加载成本；对比时保持数据、度量、硬件与线程数一致。默认余弦查询与显式原生 L2 使用不同的评分语义，应分别生成精确 ground truth。

内存测量应区分索引热内存、原始向量和 Payload 冷层、OS PageCache 与临时工作区。基准入口及数据准备步骤见 基准测试指南。

检查与复现入口

源码入口：QuIVer 构图与查询路由、SM 查询内核、数据库生命周期。

cargo test --lib index::quiver::corrected_sm::production_tests
cargo test --lib index::quiver::corrected_sm::native_l2_tests
cargo test --lib index::quiver::tests::test_quiver_中等规模搜索 -- --exact
cargo test --lib index::quiver::connectivity_tests
RAYON_NUM_THREADS=1 cargo bench --features ablation --bench bench_quiver_connectivity

这些命令检查默认路由、预算、维度、增量/slot 复用、重载、原生 L2 和基础图查询。连通性基准覆盖七组合成数据和四个查询宽度，运行时输出逐轮召回、耗时和热内存指标。可设置 TRIVIUM_NO_AVX512=1 验证禁用 AVX-512 的路径。

0.9.0-beta.3 检索与计量

BruteForce 使用分片有界 Top-K 堆，并按分数降序、外部 NodeId 升序合并。QuIVer 的 SM 与公开 BQ 检索入口统一采用外部 NodeId 处理同分；查询维度、有限值与冷向量视图按入口契约校验。写入准入直接读取增量维护的热内存计量，完整图统计用于诊断。详见版本说明。

索引事实绑定与 BQ 边界

.quiver.meta v2 使用 60 字节固定布局，记录文件长度、节点数、维度、QuIVer CRC、主文件与分离向量文件的 CRC，并校验元数据自身 CRC。主文件摘要覆盖节点身份和 slot 映射；加载后逐项核对活跃 ID 与冷向量 slot。相同文件长度下的节点替换、向量更新和旧索引混入均参与一致性检查。

v1 元数据通过既有 MissingIndexPolicy 处理：默认回退读取当前事实；严格模式返回 ImmutableArtifactInvalid。只读回退保留原 sidecar，可写实例可显式重建并随文件组发布更新后的索引与元数据。

Rust 底层 Bq2Signature::distance 及 Bq2Store 的 distance、distance_to_sig、distance_to_sig_cheap、get_sig、from_raw 返回 Result。调用方使用 ? 处理索引、维度和平面几何错误。预取忽略无效行；便宜距离按有效维度屏蔽尾位。合法输入继续使用现有 SIMD/标量内核。