Raised in review of PR #6306 (issues #6295/#6300/#6301/#6302) and deliberately not folded into it: the reviewer proposed routing algo.kShortestPaths and algo.msa through the new GraphData.weightedAdjacency, and that was declined there because it is not a bug fix. It is worth doing on its own terms, and the set is larger than those two.
The set
Verified on 0237e7b - these six contain zero references to loadGraph or findProvider:
| Procedure |
Cost |
Loads with |
algo.kShortestPaths |
O(k x pathLength x V²) |
getAllVertices + buildRidIndex |
algo.mst |
O(E log E) |
getAllVertices + buildRidIndex |
algo.msa |
O(V x E) |
getAllVertices + buildRidIndex |
algo.maxFlow |
O(V x E²) |
getAllVertices + buildRidIndex |
algo.betweenness |
O(V x E) |
getAllVertices + HashMap<Vertex, Integer> |
algo.degreeCentrality |
O(V + E) |
getAllVertices |
Every other procedure in the package resolves a provider through loadGraph and uses the CSR when one is available. These six cannot be accelerated by a Graph Analytical View at all - building one changes nothing for them. Five of the six are among the most expensive procedures in the package, which is the opposite of the set you would choose to leave on the OLTP path.
Two things follow from it
They duplicate the code #6306 consolidated. algo.kShortestPaths and algo.msa each hand-roll the RID resolution, weight extraction and ghost-edge skip that GraphData.weightedAdjacency now owns. Neither carries the #6301 alignment bug - both resolve the neighbour by index (ridToIdx.get(e.getIn())) rather than by iteration position, which is why they were correct - but they are independent copies of a pattern that has now been got wrong four times in this package. A future fix to the shared helper will not reach them.
algo.betweenness keys its index by Vertex rather than by RID. HashMap<Vertex, Integer> relies on Vertex.equals/hashCode where every other procedure uses buildRidIndex's Map<RID, Integer>. Worth checking on its own: two Vertex instances for the same record are equal only if the implementation says so, and a mismatch here silently drops neighbours from the BFS rather than failing.
Suggested shape
Move all six onto loadGraph + GraphData, and the two weighted ones onto weightedAdjacency. That is the change, but the reason it was declined from #6306 is worth restating so it is not underestimated: it newly routes these procedures through the CSR when a view exists, which changes neighbour ordering, and therefore tie-breaking, and therefore which of several equal-cost answers comes back. algo.kShortestPaths returns paths in rank order, algo.mst and algo.msa return an edge set whose composition is tie-sensitive - so each needs a CSR-vs-OLTP equivalence test of the kind Issue6301AlgoSteinerTreeWeightAlignmentTest.theAnalyticalViewDoesNotChangeTheTree uses, asserting CommandContext.CSR_ACCELERATED_VAR so it cannot silently pin the OLTP path twice. That is the work; the mechanical part is small.
algo.degreeCentrality is the cheap one to do first - GraphTraversalProvider.getDegrees already exists for exactly it, and the answer has no ties to break.
Related
#6301, #6302, PR #6306, #6263.
Raised in review of PR #6306 (issues #6295/#6300/#6301/#6302) and deliberately not folded into it: the reviewer proposed routing
algo.kShortestPathsandalgo.msathrough the newGraphData.weightedAdjacency, and that was declined there because it is not a bug fix. It is worth doing on its own terms, and the set is larger than those two.The set
Verified on
0237e7b- these six contain zero references toloadGraphorfindProvider:algo.kShortestPathsgetAllVertices+buildRidIndexalgo.mstgetAllVertices+buildRidIndexalgo.msagetAllVertices+buildRidIndexalgo.maxFlowgetAllVertices+buildRidIndexalgo.betweennessgetAllVertices+HashMap<Vertex, Integer>algo.degreeCentralitygetAllVerticesEvery other procedure in the package resolves a provider through
loadGraphand uses the CSR when one is available. These six cannot be accelerated by a Graph Analytical View at all - building one changes nothing for them. Five of the six are among the most expensive procedures in the package, which is the opposite of the set you would choose to leave on the OLTP path.Two things follow from it
They duplicate the code #6306 consolidated.
algo.kShortestPathsandalgo.msaeach hand-roll the RID resolution, weight extraction and ghost-edge skip thatGraphData.weightedAdjacencynow owns. Neither carries the #6301 alignment bug - both resolve the neighbour by index (ridToIdx.get(e.getIn())) rather than by iteration position, which is why they were correct - but they are independent copies of a pattern that has now been got wrong four times in this package. A future fix to the shared helper will not reach them.algo.betweennesskeys its index byVertexrather than byRID.HashMap<Vertex, Integer>relies onVertex.equals/hashCodewhere every other procedure usesbuildRidIndex'sMap<RID, Integer>. Worth checking on its own: twoVertexinstances for the same record are equal only if the implementation says so, and a mismatch here silently drops neighbours from the BFS rather than failing.Suggested shape
Move all six onto
loadGraph+GraphData, and the two weighted ones ontoweightedAdjacency. That is the change, but the reason it was declined from #6306 is worth restating so it is not underestimated: it newly routes these procedures through the CSR when a view exists, which changes neighbour ordering, and therefore tie-breaking, and therefore which of several equal-cost answers comes back.algo.kShortestPathsreturns paths in rank order,algo.mstandalgo.msareturn an edge set whose composition is tie-sensitive - so each needs a CSR-vs-OLTP equivalence test of the kindIssue6301AlgoSteinerTreeWeightAlignmentTest.theAnalyticalViewDoesNotChangeTheTreeuses, assertingCommandContext.CSR_ACCELERATED_VARso it cannot silently pin the OLTP path twice. That is the work; the mechanical part is small.algo.degreeCentralityis the cheap one to do first -GraphTraversalProvider.getDegreesalready exists for exactly it, and the answer has no ties to break.Related
#6301, #6302, PR #6306, #6263.