Full pruning var expand #9062
Merged
Full pruning var expand #9062
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This is an extended version of the Pruning Var Expand algorithm, improving performance on paths with a max length of 5 or more, on randomized graphs. The Full Pruning Var Expand (FullPrune) manages to prune paths below the min-length by storing emit-state for all touched nodes, apart from the full expand depths. This also makes the algorithm fully distinct, so no additional distinct operator is needed afterwards.
systay
reviewed
Mar 21, 2017
| assert(min <= max) | ||
|
|
||
| /* | ||
| This algorithm has been implemented using a state machine. This Cypher statement shows the static connections between the states. |
systay
reviewed
Mar 21, 2017
| * @return the full expand depth | ||
| */ | ||
| def minOutgoingDepth(incomingRelId: Long): Int = { | ||
| var max = Constants.VERY_BIG_VALUE |
There was a problem hiding this comment.
Maybe call this variable min instead?
There was a problem hiding this comment.
How about using Integer.MAX_VALUE instead of this arbitrarily chosen VERY_BIG_VALUE?
This is the only place VERY_BIG_VALUE is used, so if that is changed, we no longer need to declare that constant - making the code easier to read (because a reader no longer needs to try to understand why the value is what it is).
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
New Cypher operator for improved handling of longer var-length expands with distinct start node / end node combinations. This new operator is called FullPruningVarExpand, and is planned for var-lengths above
4..5. Above this length the FullPruningVarExpand gives improved execution times in most cases, with speed-ups of an order of magnitude or more on even longer var-lengths.changelog: Improved cypher execution speed on variable length queries where only the distinct pairs of start and end node are of interest. One query to benefit would be
MATCH (a)-[*4..5]->(b) RETURN DISTINCT a, b.