#13968·neo4j

StatefulShortestPath: avoid redundant WALK tracing after target saturation

Author: iancuuandreiCreated Sep 9, 2026Updated Sep 10, 2026
Labelsteam-cypherGithub Issue

In unbound StatefulShortestPath WALK execution, a target can become saturated while PathTracer still has represented path combinations remaining. Because tracing currently also establishes bookkeeping such as target-signpost/propagation metadata, the tracer continues after no further row from that target can be useful.

For WALK, the remaining bookkeeping continuation is history-independent and can be memoized by structural (NodeState, sourceLength) state rather than re-enumerating equivalent path suffixes.

I implemented a WALK-only fast path against 2026.08 (736cad02a36bb4a0d32c1064f44768339c814269). On a repeated-diamond depth-6 mechanism test, trace pushes dropped from 948 to 200, while differential tests produced identical rows, propagation schedules, target-signpost registrations, and pruning results. Bound-target and TRAIL controls show zero push delta.

The implementation intentionally leaves TRAIL/ACYCLIC unchanged because their validity depends on relationship/node history.

Query-level/JFR qualification is still pending; I am opening this primarily to check whether this optimization direction is consistent with the intended PPBFS architecture before taking it further.

Implementation (clean branch, 4 files, additions only): https://github.com/iancuuandrei/neo4j-contributions/tree/contrib/ppbfs-walk-post-saturation-bookkeeping

  • PostSaturationMemo.java (new): completed/on-path (NodeState -> source-length) sets with exact memory-tracker accounting
  • PathTracer.java (+59): suspended-DFS continuation with post-saturation skip logic, gated on unbound WALK + saturation
  • PGPathPropagatingBFS.java (+5): P7 force-disabled for bound intoTarget searches
  • PGPathPropagatingBFSP7Test.scala (new): on/off differential tests (rows, schedules, target-signpost registrations, prunes) plus bound/Trail zero-delta controls

Further detail (research reports and public case study — status Candidate, mechanism-level evidence only):

One scoping note: existing PPBFS suites (110 tests on the 2026.08 base, including the generated exhaustive suite) pass unchanged with the patch.