【图数据库内核】遍历与 Expand：从索引起点走到邻居的执行骨架

第 07–08 篇解决「从哪里开始」。本篇解决「开始之后怎么走」：Cypher 计划里的 Expand 家族如何按类型与方向读出邻居，变长路径如何爆炸或剪枝，最短路径为何换成另一套搜索。计划基数与「看起来对但跑爆」留给第 10 篇；本篇钉算子语义与存储耦合。

本文是「图数据库内核」系列第 9 篇（共 16 篇）。→ 系列目录

篇目	核心内容
第 7–8 篇 · 索引入口	选出起点集合 \(S\)
第 9 篇 · Expand	单跳 / 变长 / 最短路径算子
第 10 篇 · Cypher 计划	基数、算子组合事故

版本锚定：Cypher Manual current / 5 Planning and tuning → Operators（含 Expand / VarLengthExpand / StatefulShortestPath 细则；示例 Runtime 版本号随文档刷新）。变长语法：Patterns → Variable length paths（量化路径 / 量化关系；旧 *min..max 仍可用但非 GQL 对齐）。不粘贴本机未跑的 PROFILE 行数；手册示例中的 Rows/DB Hits 仅作形态参考。

一、Expand 在流水线里的位置

最小故事：

Leaf（IndexSeek / LabelScan / …）
  → 产生起点行
  → Expand*（读邻接）
  → Filter / Projection / …

每一次 Expand 在存储层对应第 02–05 篇的 hop：record 链或 block 主块/dense 树 + page cache pin。算子名字描述的是结果语义（要全部邻居还是只要两端之间的边、要路径还是只要终点），不是另一种存盘格式。

flowchart LR
  S["Start rows |S|"] --> E["Expand"]
  E --> N["Neighbor rows ~ |S| × f"]
  N --> E2["Next Expand"]
  E2 --> Out["Cardinality product"]

平均有效扇出 \(f\)（含类型/方向过滤后）使 \(k\) 跳无共享时行数可按 \(|S|\cdot f^{k}\) 量级膨胀——这是变长路径事故的代数来源。

二、单跳：Expand(All) 与 Expand(Into)

2.1 Expand(All)

手册：给定起点，按模式关系遍历入边或出边（及类型等谓词）。典型计划片段：

NodeIndexSeek → Expand(All) → ProduceResults

对应 Cypher 形态：(p)-[:FRIENDS_WITH]->(fof)，其中 p 已求出，fof 由扩张产生。

存储耦合：

• 类型已知时，dense/group 或 block dense 树可少读无关类型（第 03–04 篇）；
• 无类型、无方向的 -[]- 逼近扫该点全部邻接——超节点上最痛。

2.2 Expand(Into)

当两端节点都已在作用域内，要用边把它们连起来时，用 Expand(Into)：找连接这两点的全部匹配关系。手册关键句：两端已知时，会从度数较小的一端发起——dense 端点出现时差别可观。

典型场景：已经通过其它模式绑定了 a 与 b，再匹配 (a)-[:R]->(b)；或闭环模式里一端先 Expand(All) 再 Expand(Into) 回到已知点。

工程直觉：Into = 「验证/枚举已知两点之间的边」；All = 「从一点生成邻居」。把 Into 误写成从超节点 All 出去再 Filter 到目标点，会白付扇出。

2.3 OptionalExpand

OptionalExpand(All|Into) 与上类似，但无匹配时仍产出一行，关系与终点为 null——对应 OPTIONAL MATCH。可选扩张不会消灭超节点上的读价；只改变「零匹配是否丢行」。

三、变长路径：All、Into、Pruning

3.1 VarLengthExpand(All)

从给定起点遍历变长关系（含量化关系）。语义重心常是路径：不同路径到达同一终点可产生多行。无上界或上界过大时，路径排列组合可爆炸——Support/KB 与手册量化路径章节反复强调必须加有限上界。

旧语法：(a)-[:R*1..5]->(b)。新语法倾向量化关系 / 量化路径模式（QPP），便于在重复段内写谓词；旧 * 形式仍可用，手册标明非 GQL 对齐。

3.2 VarLengthExpand(Into)

两端已知时的变长版：枚举连接两点的变长匹配。仍受上界与中间扇出约束。

3.3 VarLengthExpand(Pruning)

手册条件（A 级）：

1. 不关心个别路径（只要终点等）；
2. 关系模式有上界。

优化：若某条继续探索保证只能得到已经发现过的终点，则不再探索。保证产出的终点唯一。常与 RETURN DISTINCT / WITH DISTINCT 等「只要唯一终点」的查询形态一起被规划出来（KB 补充触发条件为 B 级运维经验；以计划里是否出现 VarLengthExpand(Pruning) 为准）。

算子一览表中还有 VarLengthExpand(Pruning,BFS)：同样「只要唯一终点」，搜索策略标为 BFS 变体——读 EXPLAIN 时按字面区分，勿与「所有路径 All」混谈。

重要限制（手册 + KB 共识）：Pruning 避免的是「重复终点上的无效继续」；在高度数、弱约束图上，为找到全部可达终点仍可能探索大量路径。它不是「免费 BFS 闭包」。若只要可达集合且图很稠，有时需 APOC path expander 等专用遍历（KB 建议；本系列不展开 APOC API）。

3.4 量化路径：把过滤推进扩张

量化路径模式把重复段提成 (… ){m,n}，段内可写节点/关系谓词，从而更早剪枝——Support 文将其与 Neo4j 5.x 推荐实践对齐。相对「先 *..k 拉出巨量子图再 WHERE」，这是控制 \(\mathrm{Cost}_{\mathrm{expand}}\) 的语法杠杆。

段内声明、段外引用的变量是 group variables（列表）——语义与「单跳绑定一个节点」不同，写错会放大结果基数（第 10 篇基数节回指）。

四、最短路径：另一套算法，不是「变长 + LIMIT 1」

StatefulShortestPath(Into) 手册要点：左右边界各跑 BFS；首次交集即成功；一侧耗尽或触达跳数上界则无路径。这与「枚举所有 *1..k 路径再取最短」不是同一复杂度阶级。

谓词若必须看完整路径才能判定，旧版 shortest 规划可能回退到穷尽搜索（4.x 手册有 fallback 叙事）——写最短路径查询时，尽量让谓词可在搜索中局部判定。细节随版本以 current Shortest paths 页为准。

不要用无界变长匹配冒充最短路径：变长 All 的目标是模式枚举；最短路径的目标是长度最优（及并列）。

五、和存储、索引、语义入口的接合表

方向与类型是最便宜的剪枝；属性过滤能下推到 Expand/OptionalExpand 细节里时（计划 Details 可见），优于扩张后再 Filter。

六、实操清单（执行层）

1. 变长必写上界；业务上真正需要的最大跳数写进模式，而不是 * 开盲盒。
2. 只要终点时写清 DISTINCT（或等价），并确认计划出现 Pruning 而非 All。
3. 闭环 / 两端已知优先让规划器走 Into，避免从超节点 All 扫出再过滤。
4. 能进段内的谓词用量化路径写进扩张，而不是扩张后 WHERE。
5. 最短用最短算子/选择器，不用「变长 + 应用层比长度」。
6. PROFILE 看 Rows 在哪一层炸（有环境时）——炸在 VarLengthExpand 就回到本篇；炸在估算与 Join 顺序则第 10 篇。

七、争论与开放问题

1. 枚举所有路径 vs 只要可达终点：Cypher 默认变长偏前者；Pruning/专用遍历偏后者。API 选择即复杂度选择。
2. 声明式 expand vs 命令式 traversal API：声明式利于优化器改写；命令式（APOC/Traversal Framework）利于 BFS/唯一终点等控制。本系列主线留在 Cypher 算子。
3. 开放问题：幂律下 \(f\) 的估计（第 10 篇）；量化路径与 StatefulShortest 在流水线 runtime 上的内存记账；与 GDS 图算法引擎的分工（分析闭包不走 OLTP Expand）。

谱系：图遍历是图数据库的老本行；Cypher 把它收成关系代数风格的算子树——代价是「路径 = 行」时基数与 SQL JOIN 爆炸同构。

八、来源与实验台账（本篇）

九、小结

1. Expand(All) 生成邻居；Expand(Into) 连接已知两端（偏小度数端）。
2. 变长默认可以按路径爆炸；Pruning 要上界 +「不要单条路径」；仍不是免费闭包。
3. 最短路径走双向 BFS 类算子，不是变长的特例写法。
4. 下一篇：规划器如何估计 \(|S|\) 与 \(f\)，以及算子树何时「局部合理、全局爆掉」。

→ 系列目录 · 上一篇：全文与向量边界 · 下一篇：Cypher 计划