fix multi-hop traverse with name path #2743

nafraf · 2022-12-01T12:33:08Z

This PR is to solve #2739 "Exact path length queries don't seem to respect the path length"

The problem seems to be that QGEdge_VariableLength() can't detect correctly that the edge has variable length when minHops == maxHops, because it returns (e->minHops != e->maxHops).

In queries like the following, there are variable length edges where minHops == maxHops, and ```QGEdge_VariableLength()`` erroneously return false:

GRAPH.QUERY g "MATCH p = ({v:'a'})-[*2]-({v:'c'}) RETURN length(p)"

GRAPH.QUERY g "MATCH p = ({v:'a'})-[*2..2]-({v:'c'}) RETURN length(p)"

Then, the idea is to create a new property varLen that is true when the edge has variable length specified, without consider the values of minHops, maxHops or even if they are missing.

Comments are welcome.

codecov · 2022-12-01T13:14:56Z

Codecov Report

Base: 91.19% // Head: 91.17% // Decreases project coverage by -0.03% ⚠️

Coverage data is based on head (cc8251a) compared to base (f0b0c27).
Patch coverage: 100.00% of modified lines in pull request are covered.

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #2743      +/-   ##
==========================================
- Coverage   91.19%   91.17%   -0.03%     
==========================================
  Files         267      267              
  Lines       25516    25519       +3     
==========================================
- Hits        23270    23267       -3     
- Misses       2246     2252       +6

Impacted Files	Coverage Δ
...on_plan/execution_plan_build/build_match_op_tree.c	`100.00% <100.00%> (ø)`
src/graph/entities/qg_edge.c	`98.64% <100.00%> (+0.05%)`	⬆️
src/graph/rg_matrix/rg_set_element_uint64.c	`89.36% <0.00%> (-8.52%)`	⬇️
src/query_ctx.c	`87.68% <0.00%> (-4.35%)`	⬇️
src/procedures/proc_sp_paths.c	`95.41% <0.00%> (-0.86%)`	⬇️
src/index/index_construct.c	`96.70% <0.00%> (+1.09%)`	⬆️
src/procedures/proc_ss_paths.c	`91.86% <0.00%> (+1.74%)`	⬆️

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

☔ View full report at Codecov.
📢 Do you have feedback about the report comment? Let us know in this issue.

AviAvni

see comments

src/graph/query_graph.c

AviAvni · 2022-12-04T12:05:05Z

tests/flow/test_variable_length_traversals.py

+        query = """CREATE (a {v:'a'}), (b {v:'b'}), (c {v:'c'}), (d {v:'d'}), (a)-[:R]->(b), (b)-[:R]->(c), (c)-[:R]->(a), (d)-[:R]->(d)"""
+        actual_result = redis_graph.query(query)
+        query_to_expected_result = {
+            "MATCH p = ({v:'a'})-[*2]-({v:'c'}) RETURN length(p)" : [[2]],


this one is not variable length it fixed length

You are right, it's fixed length.
Should I rename the QGEdge_VariableLength() method and the property varLen? Because with the change of this PR, it detects if a range length was specified, fixed or variable.

And maybe the function NewCondVarLenTraverseOp() should be renamed too.

I renamed some functions. Please check if you agree.
QGEdge_RangeLength() to QGEdge_RangeLength()
_AlgebraicExpression_IsVarLen() to _AlgebraicExpression_IsRangeLen()

Property varLen renamed to rangeLen

The test were not removed, just renamed, for all tests rangeLen == true
test11_variable_length_edges() to test11_range_length_edges()

AviAvni · 2022-12-04T12:05:11Z

tests/flow/test_variable_length_traversals.py

+        query_to_expected_result = {
+            "MATCH p = ({v:'a'})-[*2]-({v:'c'}) RETURN length(p)" : [[2]],
+            "MATCH p = ({v:'a'})-[*2..]-({v:'c'}) RETURN length(p)" : [[2]],
+            "MATCH p = ({v:'a'})-[*2..2]-({v:'c'}) RETURN length(p)" : [[2]],


this one is not variable length it fixed length

AviAvni · 2022-12-04T12:05:24Z

tests/flow/test_variable_length_traversals.py

+            "MATCH p = ({v:'a'})-[*2..2]-({v:'c'}) RETURN length(p)" : [[2]],
+            "MATCH p = ({v:'a'})-[*]-({v:'c'}) RETURN length(p)" : [[2],[1]],
+            "MATCH p = ({v:'a'})-[*..]-({v:'c'}) RETURN length(p)" : [[2],[1]],
+            "MATCH p = ({v:'d'})-[*0]-() RETURN length(p)" : [[0]],


this one is not variable length it fixed length

swilly22 · 2023-01-17T09:05:25Z

Following up on this, the original issue:

GRAPH.QUERY g "CREATE (a{v:'a'}),(b{v:'b'}),(c{v:'c'}),(a)-[:R]->(b),(b)-[:R]->(c),(c)-[:R]->(a)"
GRAPH.QUERY g "MATCH p = ({v:'a'})-[*2]-({v:'c'}) RETURN length(p)"

Creates a graph where c can be reached from a in multiple ways:
1. a->b->c
2. a<-c

The request in the READ query is to get from a to c via 2 hops ({v:'a'})-[*2]-({v:'c'})
The only path which will get us there is: a->b->c

The appropriate Algebraic expression which denotes this pattern is: THE_ADJ * THE_ADJ applied by a single
Conditional Traverse operation.

GRAPH.explain g "MATCH p = ({v:'a'})-[*2]->({v:'c'}) RETURN p"
1) "Results"
2) "    Project"
3) "        Filter"
4) "            Conditional Traverse | (@anon_0)-[@anon_2*2..2]->(@anon_1)"
5) "                Filter"
6) "                    All Node Scan | (@anon_0)"

The problem here is that Conditional Traverse performs traversal via matrix matrix multiplication which "losses" traversed edges along the path. after the operation finishes we're left with the following information:

src node
dest node
last traversed edge

This lost of path critical information makes the Path object construction not possible.

There are two solutions as we see it:

when dealing with named paths of length > 1 always use DFS (Conditional Variable Length Traverse) (probably less performant compared to BFS via MxM)
use multiple Conditional Traverse operations one for each hop along the constant length path. (We might want to consider introducing a variant to our Conditional Traverse one which performs multiple traversals via MxM, this should yield better performance then multiple Conditional Traverse operations)

This PR seems to have taken the first approach which is OK, but performance wise we might want to use multiple Conditional Traverse operations if the number of hops is say less than 5.

tests/flow/test_variable_length_traversals.py

src/graph/entities/qg_edge.h

src/graph/query_graph.c

src/arithmetic/algebraic_expression/algebraic_expression_construction.c

src/execution_plan/execution_plan_build/build_match_op_tree.c

src/execution_plan/optimizations/traverse_order_utils.c

AviAvni · 2023-01-18T15:53:09Z

src/graph/entities/qg_edge.h

@@ -62,6 +62,12 @@ bool QGEdge_VariableLength
 	const QGEdge *e
 );

+// determine whether this is a edge with a range of length defined (variable length [*minHops..maxHops] or fixed length [*Hops])


I think comment need update here

When I was updating the comment I noticed that maybe this function should be replaced by a QGEdge_LengthOne(). See comment below.

nafraf · 2023-01-19T03:14:37Z

Thanks for the comments and description of the algorithm. Now the code is more clear to me.

With the first approach, to support the case ()-[*0]-() I had to use the Conditional Variable Length Traverse, then I think that QGEdge_RangeLength() should be replaced by a function QGEdge_LengthOne() which returns true if length is one. What do you think about it?

AviAvni

rename function

* Add varLen property to QGEdge * Test variable-length edge queries * Fix spacing * Fix test, remove direction * Fix test * Test zero length edge * Init varLen in QGEdge_New() * rename varLen to rangeLen * Rewrite test11_range_length_edges() * Use QGEdge_VariableLength() and QGEdge_RangeLength * Replace QGEdge_RangeLength() by QGEdge_LengthOne() * rename function Co-authored-by: Roi Lipman <swilly22@users.noreply.github.com> Co-authored-by: Avi Avni <avi.avni@gmail.com>

* Fix toInteger() and toIntegerOrNull() don't convert Booleans (#2797) * AR_TOINTEGER: add case for type T_BOOL * skip [8] toInteger() failing on invalid arguments * Update TypeConversion2.feature Co-authored-by: Avi Avni <avi.avni@gmail.com> * Fix right(), left() length validation (#2801) * Fix AR_LEFT, AR_RIGHT length validation * Test mistmatch type and fix error message * left(), right(): NULL is a valid type for lenght * Fix argument validation Co-authored-by: Avi Avni <avi.avni@gmail.com> * fix using timeout max as default when default not configured (#2808) * fix using timeout max as default when default not configured * fix * do not cache query params (#2803) * do not cache query params * address PR comments * fix leak * fix test * convert params to SIValues * wip * delay freeing of parsed params to after the query is parsed * free parse params when freeing AST * revert changes to ast_validations.c * revert arithmetic_expression_construct changes * emit an error when param value eval fails Co-authored-by: Avi Avni <avi.avni@gmail.com> * fix multi-hop traverse with name path (#2743) * Add varLen property to QGEdge * Test variable-length edge queries * Fix spacing * Fix test, remove direction * Fix test * Test zero length edge * Init varLen in QGEdge_New() * rename varLen to rangeLen * Rewrite test11_range_length_edges() * Use QGEdge_VariableLength() and QGEdge_RangeLength * Replace QGEdge_RangeLength() by QGEdge_LengthOne() * rename function Co-authored-by: Roi Lipman <swilly22@users.noreply.github.com> Co-authored-by: Avi Avni <avi.avni@gmail.com> * indegree(), outdegree() - accept array of strings (#2807) * _AR_NodeDegree() support T_ARRAY argument * Add tests * Fix argument validation * Free array in case of error detected. * Duplicate comments and use siarray.array[i] * Update AR_IN() to use SI_ArrayContainsValue() * Validate comparedNull pointer * Support only the following two signatures: * Test indegree() wrong argument number * Test wrong signature: string and list * clean * revert Co-authored-by: Avi Avni <avi.avni@gmail.com> * Add ipv6 capability (#2842) * fix heap remove item (#2827) * fix heap remove item * remove utf8 deps * add test * wip * wip * all unit tests pass * heap remove element should use pointer cmp instead of cmp cb * spaces to tabs Co-authored-by: swilly22 <roi@redislabs.com> Co-authored-by: Roi Lipman <swilly22@users.noreply.github.com> * bump version 2.10.6 * Improve edge deletion performance (#2758) * improve edge deletion * update simple timer * improve edge deletion perf * fix build * fix test * fix test * clean * address review Co-authored-by: Roi Lipman <swilly22@users.noreply.github.com> * update ramp Co-authored-by: nafraf <nafraf@users.noreply.github.com> Co-authored-by: Avi Avni <avi.avni@gmail.com> Co-authored-by: Roi Lipman <swilly22@users.noreply.github.com> Co-authored-by: Guy Korland <gkorland@gmail.com> Co-authored-by: swilly22 <roi@redislabs.com>

* do not cache query params (#2803) * do not cache query params * address PR comments * fix leak * fix test * convert params to SIValues * wip * delay freeing of parsed params to after the query is parsed * free parse params when freeing AST * revert changes to ast_validations.c * revert arithmetic_expression_construct changes * emit an error when param value eval fails Co-authored-by: Avi Avni <avi.avni@gmail.com> * fix multi-hop traverse with name path (#2743) * Add varLen property to QGEdge * Test variable-length edge queries * Fix spacing * Fix test, remove direction * Fix test * Test zero length edge * Init varLen in QGEdge_New() * rename varLen to rangeLen * Rewrite test11_range_length_edges() * Use QGEdge_VariableLength() and QGEdge_RangeLength * Replace QGEdge_RangeLength() by QGEdge_LengthOne() * rename function Co-authored-by: Roi Lipman <swilly22@users.noreply.github.com> Co-authored-by: Avi Avni <avi.avni@gmail.com> * Add ipv6 capability (#2842) * fix heap remove item (#2827) * fix heap remove item * remove utf8 deps * add test * wip * wip * all unit tests pass * heap remove element should use pointer cmp instead of cmp cb * spaces to tabs Co-authored-by: swilly22 <roi@redislabs.com> Co-authored-by: Roi Lipman <swilly22@users.noreply.github.com> * bump version 2.8.22 * update ramp * Improve edge deletion performance (#2758) * improve edge deletion * update simple timer * improve edge deletion perf * fix build * fix test * fix test * clean * address review Co-authored-by: Roi Lipman <swilly22@users.noreply.github.com> * fix build * fix build * fix test * fix * fix test * fix * fix * fix Co-authored-by: Roi Lipman <swilly22@users.noreply.github.com> Co-authored-by: Avi Avni <avi.avni@gmail.com> Co-authored-by: nafraf <nafraf@users.noreply.github.com> Co-authored-by: Guy Korland <gkorland@gmail.com> Co-authored-by: swilly22 <roi@redislabs.com>

* Add varLen property to QGEdge * Test variable-length edge queries * Fix spacing * Fix test, remove direction * Fix test * Test zero length edge * Init varLen in QGEdge_New() * rename varLen to rangeLen * Rewrite test11_range_length_edges() * Use QGEdge_VariableLength() and QGEdge_RangeLength * Replace QGEdge_RangeLength() by QGEdge_LengthOne() * rename function Co-authored-by: Roi Lipman <swilly22@users.noreply.github.com> Co-authored-by: Avi Avni <avi.avni@gmail.com>

nafraf added 5 commits November 30, 2022 22:23

Add varLen property to QGEdge

51f715c

Test variable-length edge queries

d7a5f93

Fix spacing

fe4c146

Fix test, remove direction

f7f9cf3

Fix test

04d5d7f

nafraf marked this pull request as ready for review December 2, 2022 00:19

Test zero length edge

0adf17d

AviAvni suggested changes Dec 4, 2022

View reviewed changes

nafraf and others added 3 commits December 4, 2022 12:55

Merge branch 'RedisGraph:master' into bug#2739

a192ed6

Init varLen in QGEdge_New()

ec8e720

Merge branch 'RedisGraph:master' into bug#2739

cca27fd

nafraf changed the title ~~Add varLen property to QGEdge~~ Add rangeLen property to QGEdge Dec 6, 2022

nafraf and others added 12 commits December 5, 2022 23:21

rename varLen to rangeLen

2a00d20

Merge branch 'RedisGraph:master' into bug#2739

823e3cf

Merge branch 'RedisGraph:master' into bug#2739

2aa7215

Merge branch 'RedisGraph:master' into bug#2739

f039bca

Merge branch 'RedisGraph:master' into bug#2739

27d32bb

Merge branch 'RedisGraph:master' into bug#2739

fa8fd83

Merge branch 'RedisGraph:master' into bug#2739

9e1c4bb

Merge branch 'RedisGraph:master' into bug#2739

895f9ef

Merge branch 'RedisGraph:master' into bug#2739

3c5454c

Merge branch 'RedisGraph:master' into bug#2739

f6ab69e

Merge branch 'RedisGraph:master' into bug#2739

94cf53f

Merge branch 'RedisGraph:master' into bug#2739

b88390b

Merge branch 'master' into bug#2739

43905b1

swilly22 suggested changes Jan 17, 2023

View reviewed changes

nafraf added 2 commits January 17, 2023 06:49

Rewrite test11_range_length_edges()

a590ea7

Use QGEdge_VariableLength() and QGEdge_RangeLength

86aab51

AviAvni reviewed Jan 18, 2023

View reviewed changes

Replace QGEdge_RangeLength() by QGEdge_LengthOne()

7765a98

Merge branch 'RedisGraph:master' into bug#2739

2e99190

AviAvni reviewed Jan 23, 2023

View reviewed changes

rename function

cc8251a

AviAvni changed the title ~~Add rangeLen property to QGEdge~~ fix multi-hop traverse with name path Jan 23, 2023

AviAvni merged commit cc57c35 into RedisGraph:master Jan 23, 2023

nafraf deleted the bug#2739 branch January 25, 2023 01:49

fix multi-hop traverse with name path #2743

fix multi-hop traverse with name path #2743

Uh oh!

Conversation

nafraf commented Dec 1, 2022

Uh oh!

codecov bot commented Dec 1, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

AviAvni left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

AviAvni Dec 4, 2022

Choose a reason for hiding this comment

Uh oh!

nafraf Dec 4, 2022

Choose a reason for hiding this comment

Uh oh!

nafraf Dec 6, 2022

Choose a reason for hiding this comment

Uh oh!

AviAvni Dec 4, 2022

Choose a reason for hiding this comment

Uh oh!

AviAvni Dec 4, 2022

Choose a reason for hiding this comment

Uh oh!

swilly22 commented Jan 17, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

AviAvni Jan 18, 2023

Choose a reason for hiding this comment

Uh oh!

nafraf Jan 19, 2023

Choose a reason for hiding this comment

Uh oh!

nafraf commented Jan 19, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

AviAvni left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

codecov bot commented Dec 1, 2022 •

edited

Loading

swilly22 commented Jan 17, 2023 •

edited

Loading

nafraf commented Jan 19, 2023 •

edited

Loading