HelixDB 选择性等式谓词的成本建模：空统计下索引交集 vs 标签扫描的完整成本比较与验证

• 数据库
• 图数据库
• 向量数据库
• AI 应用
• RAG

导读

本文聚焦 HelixDB 查询规划器在**空统计（empty statistics）**场景下对“多个选择性等式谓词”进行成本评估与计划选择的实现细节。它回答一个核心问题：当数据库没有可用统计信息、多个等式谓词串行计费时，索引交集候选计划如何避免错误地输给标签扫描（label scan），以及完整的成本比较应当包含哪些项（标签位图、graph-row hydration、行构造、残差求值）。读完本文，你将掌握 HelixDB 成本模型的构成单元、串行计费修正的来龙去脉、共享查找的分摊问题，以及对应的回归测试与复现命令。

本文依据仓库文档 docs/SELECTIVE_EQUALITY_COSTING_VALIDATION.md，并结合规划器成本公式与端到端测试源码展开。

问题背景：空统计下三个选择性等式谓词的成本陷阱

HelixDB 是一个构建在对象存储上的 OLTP 图数据库，查询规划器在没有任何统计信息时，只能依赖默认的存储成本画像（StorageCostProfile）来估计候选计划的代价。文档明确指出：

在空统计下，三个选择性等式谓词（three selective equality predicates）在交叉子项被串行计费之后，可能输给标签扫描。两个候选计划都能通过探索（exploration）存活下来。

这意味着：规划器既会生成“走索引交集”的候选计划，也会生成“先按标签扫描、再逐行求残差”的候选计划。如果对索引交叉子项的计费方式不合理（例如把本可以并行的位图读取按串行累加），索引候选计划就会被高估，从而被错误地淘汰。因此，两者的比较必须包含标签位图（label bitmap）、graph-row hydration（图行读取/解码）、行构造（row construction）以及残差求值（residual evaluation），缺任何一项都会扭曲对比结果。

从源码结构看，这一逻辑落在规划器的可执行计划 lowering 与成本公式层：crates/planner/src/exec/lowering/costing.rs 负责把访问计划降级为成本向量，crates/planner/src/cost/profile/formulas.rs 提供各项成本公式，而 crates/planner/src/planning/tests/optimizer/selective_equality.rs 则存放了覆盖该场景的端到端规划测试。

完整成本比较：一份估算微秒的对照表

文档给出了一份合成 fixture 的成本对照：三个已索引等式（indexed equalities）、1,000 行估计扫描行数（estimated scan rows）、每个等式估计 10 行。需要特别强调的是，表中所有数值都是估算微秒（estimated microseconds），不是实测查询延迟。

对照表揭示了修正前后的三个关键变化：

1. 并行计费（Previous parallel costing）：三个等式子项按并行读取计费，总成本只有 5,155，索引候选明显占优（6,155 < 13,000 + 1,000）。但并行计费低估了真实执行的开销，因为等式位图在底层读取存在串行约束。
2. 串行计费、修复前（Serial costing before fix）：等式子项被串行累加后，Equality child reads/decode 从 5,135 跳到 15,180，完整索引访问成本达到 15,200；此时标签扫描加投影为 14,000，规划器错误地选择了扫描（表格最后一行的 “14,000 scan”）。
3. 修复后（Fixed）：索引候选的完整成本是 16,220，仍然低于扫描替代方案（19,050，含投影），因此正确地回到索引交集计划。其中“Intersection membership work”从 10 修正为 30，反映了串行集合操作的真实开销。

文档还进一步拆解了修复后标签候选的成本构成：

• 5,050：位图准备（bitmap setup）
• 1,000：位图解码（bitmap decode）
• 10,000：graph-row 读取/解码（graph-row read/decode）
• 1,000：行构造（row construction）
• 1,000：残差求值（residual evaluation）

合计 18,050，加上投影 1,000 后，扫描替代方案总成本为 19,050。

从源码看，这些成本项与 crates/planner/src/cost/profile/formulas.rs 中的公式一一对应：bitmap_equality_lookup（formulas.rs#L173）负责位图点读与按 ID 解码，secondary_set_operation（formulas.rs#L318）负责位图/集合操作，authoritative_verification（formulas.rs#L305）负责权威图行读取，secondary_row_materialization（formulas.rs#L329）负责结果行构造。这正是文档强调“比较必须包含标签位图、graph-row hydration、行构造与残差求值”的原因——四项分别由这几条公式覆盖。

共享查找的分摊问题：每个分支计费会把索引候选推下悬崖

文档给出了一个更精细的场景：一个共享等式（shared equality）与一个两值等式并集（two-value equality union）相交时，如何对共享查找计费会直接影响计划选择：

• 分摊共享查找（factoring out）：成本 6,020，索引候选胜出。
• 在每个分支重复计费（distributing and charging in every branch）：成本 20,320，会错误地偏向成本为 18,050 的扫描替代方案。

也就是说，如果规划器在并集的每个分支里都重复计算共享等式的查找成本，索引交集候选会被系统性高估约 14,300，从而把正确的索引计划挤出选择范围。正确的做法是只计费一次共享查找，并把它放在交叉操作之外。

这一行为在 crates/planner/src/planning/tests/optimizer/selective_equality.rs 中有直接验证：selective_equality_type_union_preserves_unindexed_residuals测试断言索引读取与残差读取的数量关系，而selective_equality_type_union_keeps_the_tenant_intersection测试（该文件#L142）覆盖了共享tenant等式与type并集相交的场景，验证无论并集分支数量（2/3/8）与参数化与否，规划器都保留租户索引交集（Intersect），且不会退化为逐行 Filter 或扫描（range_nexts为 0）。

保留的成本契约（Preserved contracts）

修复并非简单地把所有成本都调大，而是以“契约”的形式固定了一批不可破坏的行为，文档逐条列出：

1. 串行子执行计费仍在：交叉子项（intersection children）依然按串行方式计费，不再退回并行计费。
2. 无序集合成员关系使用所有输入基数：包括估计输出为零的情况——零估计不是“空集”的证据，不能因此跳过查找。
3. 最终行构造只按输出基数计费一次：避免在成员关系阶段重复收取行构造成本。
4. 饱和求和（saturating sums）保持成本域：成本累加使用饱和加法，防止溢出破坏成本向量域。
5. 物理候选计费与可执行 lowering 一致：规划阶段对物理访问计划的计费，与最终可执行计划（executable lowering）的成本一致，避免“规划时说便宜、执行时变贵”的偏差。
6. 已填充统计仍可让扫描胜出：修复并不禁止扫描；当统计信息表明标签基数很小时，小标签扫描依然是更便宜的选择。

此外，**有序范围驱动（ordered range drivers）**保留既有语义：visited-entry 计费、membership-first 验证、反向迭代、动态限制（dynamic limits）以及 tie 语义（并列时如何取舍）都保持不变。也就是说，本次修复是“选择性等式集合操作”这个局部路径的修正，不触及有序范围扫描的既定行为。

从源码印证：成本向量的串行累加由 crates/planner/src/cost/vector.rs#L47 的serial方法实现，并行读取的临界路径计费在 formulas.rs#L560 的parallel_reads；而“估计为零不得当作空集”的防御性逻辑，直接体现在 selective_equality.rs 中selective_equality_intersects_every_index_with_absent_or_stale_statistics测试的注释里：“An estimate of zero is not a proof of emptiness: stale statistics must never suppress the actual lookup”（零估计不是空集的证据：过时统计绝不能抑制真实查找），该测试将deleted属性基数分别设为 0、1、10 并断言所有合取项都被索引服务。

成本公式与源码实现：每个数字从哪来

要理解表格中的数字，需要知道StorageCostProfile的默认字段与公式。规划器默认画像定义在 crates/planner/src/cost/profile.rs（如default_equality_index_rows，profile.rs#L81），公式实现在 crates/planner/src/cost/profile/formulas.rs：

• bitmap_equality_lookup(rows)（formulas.rs#L173）：一次 V4 非唯一等式位图的点读与解码，延迟 =object_get_latency + sstable_filter_probe + bitmap_decode_per_id × rows，object_reads = 1，cpu_units = rows。这正是表格里 “Equality child reads/decode” 每份 5,060（5,135/次左右的量级）的构成基础。
• bitmap_equality_batch(values, rows)（formulas.rs#L206）：close-key 的批量multi_get，每RECORD_BATCH_ROWS个键追加一次调用开销，行数决定解码成本。
• secondary_set_operation(rows)（formulas.rs#L318）：位图/集合交叉操作，按secondary_set_per_id × rows计费。
• authoritative_verification(rows)（formulas.rs#L305）：权威图属性验证，每候选 ID 一次读取，object_reads = rows、authoritative_graph_reads = rows，对应文档中的 “graph-row read/decode”。
• secondary_row_materialization(rows)（formulas.rs#L329）：验证完成后构造结果行，按输出基数计费一次，对应 “Final access-row construction”。

在 crates/planner/src/exec/lowering/costing.rs 中，selective_equality_lowering_costs_scan_and_bitmap_work_consistently（该文件#L547）直接断言：两个位图先并行读取、再串行做一次集合操作，期望延迟为 5,130 微秒、并行宽度为 2；交叉（Intersect）与并集（Union）两种表达式分别得到 10 行与 20 行的输出估计。这与文档表格中 “Equality child reads/decode = 5,135”“Intersection membership work = 10/30” 的数字互相印证——5,135 正是 “两个位图并行读取 + 一次集合操作” 的默认画像估值，说明该测试就是本验证文档所对应的 lowering 层回归用例。

验证覆盖与复现命令

文档列出了完整的验证矩阵，全部在仓库中有对应的测试文件：

• 合成回归覆盖：节点与边等式索引（node/edge equality indexes）、空与已填充统计、参数绑定（parameter bindings）、嵌套合取（nested conjunctions）、带析取的共享谓词（shared predicates with disjunctions）、未索引残差（unindexed residuals）、租户目录隔离（tenant catalog isolation）、保留快照（retained snapshots）以及并发存储变更（concurrent storage changes）。这些分别对应 crates/planner/src/planning/tests/optimizer/selective_equality.rs 中的unique_membership_keeps_bounded_index_access_without_statistics、indexed_conjunctions_are_permutation_invariant_full_intersections（120 种谓词排列均得到全交叉）、indexed_conjunction_avoids_the_scan_cliff、null_equality_intersects_with_the_selective_index_before_sorting等用例。
• 基准 oracle：检查完整响应，并拒绝缺失行、重复行与外来行（foreign rows）。oracle 实现见 docker-image/tests/test_equality_benchmark.py，其中test_oracle_selects_all_and_only_matching_fixture_rows验证“只返回匹配的行”，test_oracle_ignores_output_order_but_checks_complete_rows显式注入{"id": "foreign"}并断言其被拒绝。
• 端到端数据库契约：租户隔离与快照保留由 crates/db/src/query_service/selective_equality_tests.rs 承载——selective_equality_preserves_tenant_snapshot_and_churn_results（该文件#L301）在两个租户作用域下为 5 个属性创建节点/边等式索引，写入 32 行数据并验证查询结果；unique_membership_reader_uses_batch_and_honors_cancellation（该文件#L10）则验证唯一成员读取支持批量读取与取消。
• 有序存储与镜像检查：既有的有序存储测试与成对的内置镜像检查（paired built-image checks）覆盖宽/窄两种有序投影。
• 本地检查清单：规划器单元测试与 doctests、query-service 与数据库契约、有序存储、Python 基准 oracle、Clippy、格式化、覆盖率，以及内置镜像的 smoke 与持久化行为，全部通过。

聚焦复现命令（文档原文）：

cargo test -p helix-planner --lib selective_equality cargo test -p db --lib selective_equality python3 -m unittest discover -s docker-image/tests -p 'test_equality_benchmark.py'

前两条分别运行规划器端（crates/planner/src/planning/tests/optimizer/selective_equality.rs 中的全部用例）与数据库端（crates/db/src/query_service/selective_equality_tests.rs 中的契约测试），第三条运行 docker-image/tests/test_equality_benchmark.py 的基准 oracle 校验。这三条命令即可覆盖从“成本公式 → 计划选择 → 执行结果完整性”的完整验证链。

小结

HelixDB 对选择性等式谓词的成本修复本质上是一次“计费语义校准”：把等式子项的读取按串行累加、把集合成员关系按所有输入基数计费、把行构造只按输出基数计费一次、用饱和求和保护成本域，并且不把共享查找重复摊到每个析取分支。修复后，空统计下三个选择性等式的索引交集候选计划以 16,220 对 19,050 的估算成本胜出标签扫描，同时保留了已填充统计下小标签扫描仍可胜出的弹性。所有关键数字都可在 crates/planner/src/cost/profile/formulas.rs 与 crates/planner/src/exec/lowering/costing.rs 中找到对应的公式与断言，读者可用上面的三条命令在本地复现全部验证。

• 数据库
• 图数据库
• 向量数据库
• AI 应用
• RAG