Expand StatefulShortestPath to FindShortestPaths specialization for simple QPP node groups

Is your feature request related to a problem? Please describe.

StatefulShortestToFindShortestRewriter currently misses some cases where StatefulShortestPath can be replaced by the simpler FindShortestPaths operator.

I found two independent restrictions that are more conservative than the execution semantics require.

First, the rewriter currently identifies the candidate selective path pattern from the accumulated solved query graph. If another SPP has already been solved in the same query graph, an otherwise eligible StatefulShortestPath can remain on PPBFS simply because more than one SPP is present.

The SPP introduced by the current operator can instead be identified from the solved-state delta:

solved(ssp) - solved(ssp.source)

and the rewrite can conservatively fall back when that delta is not exactly one SPP.

Second, single-relationship QPPs are currently rejected when their node group variables are consumed.

For a repeated pattern such as:

(c)-[r:R]->(d)

and a returned path:

v0,e1,v1,e2,...,ek,vk

the node groups are completely determined by the path:

c = [v0, ..., v(k-1)]
d = [v1, ..., vk]

So producing these groups does not require PPBFS/NFA state during traversal. They can be materialized after FindShortestPaths has found the path.

Describe the solution you'd like

Extend the existing SSP → FindShortestPaths rewrite

• identify the SPP owned by the current StatefulShortestPath using the solved-state delta against its source;
• allow consumed node groups for directed, single-relationship QPPs by having FindShortestPaths materialize the left/right node lists from the returned path.

The traversal itself remains unchanged. This does not add NFA states, product-graph traversal, signposts, propagation, or general QPP machinery to FindShortestPaths.

The existing restrictions remain in place for cases that genuinely need more state, including:

• lower bounds greater than 1;
• SHORTEST k / SHORTEST k GROUPS for k > 1;
• unbound-target searches;
• multi-relationship QPPs;
• non-inlineable/path-global predicates.

Grouped undirected QPPs are also left on StatefulShortestPath. Differential testing found an existing FSP/SSP discrepancy around undirected same-node paths, so this change deliberately does not expand FSP into that region.

Why this is a useful specialization

For these single-rel QPPs, the automaton state is not needed to decide which relationship can be traversed next. The general PPBFS machinery is therefore avoidable; the only extra work is O(path length) result materialization after the shortest path has already been found.

On Neo4j 2026.08 (736cad02a36bb4a0d32c1064f44768339c814269), paired fresh-JVM measurements of the actual patched operator gave:

chain16       1.89x
chain64       1.92x
diamond       1.42x
tree b4/d6    5.49x

The solved-SPP change also turns a stacked eligible case from FSP + SSP into FSP + FSP; the isolated comparison was 1.47x.

Node-group materialization itself was within measurement noise, and existing ordinary FindShortestPaths cases showed no measurable regression.

Correctness validation

The implementation was tested by running the same queries with the rewrite disabled (StatefulShortestPath reference) and enabled (FindShortestPaths) and comparing complete results.

The final guarded implementation passed:

1500 / 1500 randomized differential cases

covering directed single-rel QPPs with cycles, self-loops, parallel relationships, relationship-type unions, different bounds/selectors, predicates, and group-variable combinations.

Planner tests also cover the newly eligible forms as well as nearby cases that must remain on StatefulShortestPath.

Alternatives considered

I did not extend FindShortestPaths into cases that would require recreating the general shortest-path machinery:

• arbitrary lower bounds require additional depth/acceptance state;
• k > 1 requires a k-shortest-path algorithm;
• multi-rel QPPs generally require automaton state to determine the legal next transition;
• general path predicates cannot safely be implemented as shortest-path-then-filter.

The goal here is to enlarge the simple specialization boundary, not make FindShortestPaths another PPBFS implementation.

Implementation

The proposed implementation is available as a clean branch based directly on Neo4j 2026.08 (736cad02a36bb4a0d32c1064f44768339c814269):

Implementation: Draft PR #13970 https://github.com/neo4j/neo4j/pull/13970 The PR contains the production implementation and permanent tests only. Research/benchmark harnesses are kept separately on research/ssp-to-fsp-p10.

The larger differential-testing and benchmark harnesses are kept separately:

Research / qualification branch: https://github.com/iancuuandrei/neo4j-contributions/tree/research/ssp-to-fsp-p10

That branch is not part of the proposed production change; it contains the validation tooling and experimental evidence used to qualify it.