Repository: alibaba/GraphScope (language: python)

Issue:
[BUG] Unexpected Type Inference in PathExpand
**Describe the bug**

On LDBC Dataset (sf=0.1), we can run the following two queries:
```
# gremlin tests
gremlin> g.V().hasLabel("PERSON").has("id",933).out("5..6").endV().hasLabel("PLACE").has("id",999).count()
==>392
```
while a simiilar query in cypher is:
```
# cypher tests
@neo4j> Match (a:PERSON{id:933})-[c*5..6]->(b:PLACE{id:999})
        return a.id, b.id
        Limit 10;
+----------+
| id | id0 |
+----------+
+----------+
```
The results in the Cypher is empty, which is not as expected. The reason is that, in this case, the type inference tells that the type of `c` should be `isLocatedIn` (from the edge type that `Person-isLocatedIn-Place`). However, in PathExpand, this is not as expected. The path could be like `Person-Knows[4..5]-Person-IsLocatedIn-Place`, etc.




Discussion / hints:
/cc @shirly121, this issus/pr has had no activity for for a long time, could you folks help to review the status ? 
 To suppress further notifications,
 - for issues, 
   - if it is waiting for further response from the reporter/author, please help to add the label `requires-further-info`, 
   - if you have already started working on it, please add the label `work-in-progress` to the issue, 
   - if this issue requires further designing discussion and not in current plan, or won't be fixed, please add the label `requires-further-discussion` or `wontfix` to the issue, 
 - for pull requests, 
   - if you are still working on it and it is not ready for reviewing, please convert this pull request as draft PR, 
   - if you have decided to hold this development on, please add the `requires-further-discussion` label to the pull request. 
 Thanks!
Fixed in #3837 
There leaves a bug in the type infer in PathExpand.

For example, running the following query on LDBC dataset,
```
MATCH(a)-[*1..2]->(b) RETURN COUNT(a) AS pathCnt;
```

The inferred type of PathExpandBase within PathExpand is:
`ExpandEdge`(with direction IN) type ids: {0,1,3,5,6,7,10,11,12,13,15,16,17,21,22};
`GetV` type ids: {0,1,2,3,5,6,7}

While here the `GetV` types missed 4, i.e., `Forum`, while `Forum` is also a valid type for the expanded vertices (i.e., of `a`). 

I guess, the reason is that the direction is not correctly considered in path, since forum only has out-neighbors in schema, but in this case, the expand direction is IN.

Fix patch:
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/planner/GraphIOProcessor.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/planner/GraphIOProcessor.java
index 557ff6d10361..3ebc09bf5221 100644
--- a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/planner/GraphIOProcessor.java
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/planner/GraphIOProcessor.java
@@ -760,11 +760,10 @@ private RelNode createExpandGetV(
             if (srcInTargetOrderId == null) {
                 srcInTargetOrderId = -1;
             }
+            PatternVertex src =
+                    glogueEdge.getSrcPattern().getVertexByOrder(edge.getSrcVertexOrder());
             DataValue srcValue =
-                    getVertexValue(
-                            new VertexDataKey(srcInTargetOrderId),
-                            edgeDetails,
-                            glogueEdge.getSrcPattern().getVertexByOrder(edge.getSrcVertexOrder()));
+                    getVertexValue(new VertexDataKey(srcInTargetOrderId), edgeDetails, src);
             PatternVertex target =
                     glogueEdge.getDstPattern().getVertexByOrder(extendStep.getTargetVertexOrder());
             DataValue targetValue =
@@ -797,7 +796,12 @@ private RelNode createExpandGetV(
                 GetVConfig innerGetVConfig =
                         new GetVConfig(
                                 getVConfig.getOpt(),
-                                createLabels(edge.getElementDetails().getPxdInnerGetVTypes(), true),
+                                createLabels(
+                                        createInnerGetVTypes(
+                                                src.getVertexTypeIds(),
+                                                target.getVertexTypeIds(),
+                                                edge.getElementDetails()),
+                                        true),
                                 getVConfig.getAlias());
                 pxdBuilder
                         .getV(innerGetVConfig)
@@ -823,9 +827,6 @@ private RelNode createExpandGetV(
                                         getVConfig.getLabels(),
                                         getVConfig.getAlias(),
                                         getVConfig.getStartAlias()));
-                if (targetValue.getFilter() != null) {
-                    builder.filter(targetValue.getFilter());
-                }
             } else {
                 GraphLogicalExpand expand =
                         createExpandWithOptional(
@@ -839,13 +840,34 @@ private RelNode createExpandGetV(
                     builder.filter(edgeValue.getFilter());
                 }
                 builder.getV(getVConfig);
-                if (targetValue.getFilter() != null) {
-                    builder.filter(targetValue.getFilter());
-                }
+            }
+            if (targetValue.getFilter() != null) {
+                builder.filter(targetValue.getFilter());
             }
             return builder.build();
         }
 
+        // Handle a special case for path expand: re-infer the type of inner getV in path expand.
+        // Before optimization, the type of path expand is inferred based on the user's query order,
+        // resulting in the type of inner endV being bound to this order.
+        // However, if the optimizer reverses the order of the path expand, the type of inner endV
+        // also needs to be reversed accordingly.
+        private List<Integer> createInnerGetVTypes(
+                List<Integer> startVTypes, List<Integer> endVTypes, ElementDetails details) {
+            List<Integer> originalInnerVTypes = details.getPxdInnerGetVTypes();
+            if (!originalInnerVTypes.isEmpty()) {
+                if (!endVTypes.isEmpty() && originalInnerVTypes.containsAll(endVTypes)) {
+                    return originalInnerVTypes;
+                } else if (!startVTypes.isEmpty() && originalInnerVTypes.containsAll(startVTypes)) {
+                    List<Integer> reverseTypes = Lists.newArrayList(originalInnerVTypes);
+                    reverseTypes.removeAll(startVTypes);
+                    reverseTypes.addAll(endVTypes);
+                    return reverseTypes.stream().distinct().collect(Collectors.toList());
+                }
+            }
+            return endVTypes;
+        }
+
         private GraphLogicalPathExpand createPathExpandWithOptional(
                 GraphLogicalPathExpand pxd, boolean optional) {
             if (pxd.getFused() != null) {


Test patch:
diff --git a/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/planner/cbo/CBOTest.java b/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/planner/cbo/CBOTest.java
index a7cb81b06001..8d53370bebea 100644
--- a/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/planner/cbo/CBOTest.java
+++ b/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/planner/cbo/CBOTest.java
@@ -193,4 +193,50 @@ public void Q4_test() {
                     + " alias=[forum], opt=[VERTEX])",
                 com.alibaba.graphscope.common.ir.tools.Utils.toString(after).trim());
     }
+
+    @Test
+    public void Q5_test() {
+        GraphBuilder builder = Utils.mockGraphBuilder(optimizer, irMeta);
+
+        // The optimized order is from 'b' to 'a', which is opposite to the user-given order.
+        // Verify that the path expand type is correctly inferred in this situation.
+        RelNode before1 =
+                com.alibaba.graphscope.cypher.antlr4.Utils.eval(
+                                "Match (a)-[*1..2]->(b:COMMENT) Return a", builder)
+                        .build();
+        RelNode after1 = optimizer.optimize(before1, new GraphIOProcessor(builder, irMeta));
+        Assert.assertEquals(
+                "GraphLogicalProject(a=[a], isAppend=[false])\n"
+                    + "  GraphLogicalGetV(tableConfig=[{isAll=false, tables=[PERSON, COMMENT]}],"
+                    + " alias=[a], opt=[END])\n"
+                    + "    GraphLogicalPathExpand(fused=[GraphPhysicalExpand(tableConfig=[[EdgeLabel(LIKES,"
+                    + " PERSON, COMMENT), EdgeLabel(REPLYOF, COMMENT, COMMENT)]], alias=[_],"
+                    + " opt=[IN], physicalOpt=[VERTEX])\n"
+                    + "], offset=[1], fetch=[1], path_opt=[ARBITRARY], result_opt=[END_V],"
+                    + " alias=[_], start_alias=[b])\n"
+                    + "      GraphLogicalSource(tableConfig=[{isAll=false, tables=[COMMENT]}],"
+                    + " alias=[b], opt=[VERTEX])",
+                after1.explain().trim());
+
+        // check the type of path expand if the order is from 'a' to 'b'
+        RelNode before2 =
+                com.alibaba.graphscope.cypher.antlr4.Utils.eval(
+                                "Match (a {id: 1})-[*1..2]->(b:COMMENT) Return a", builder)
+                        .build();
+        RelNode after2 = optimizer.optimize(before2, new GraphIOProcessor(builder, irMeta));
+        Assert.assertEquals(
+                "GraphLogicalProject(a=[a], isAppend=[false])\n"
+                    + "  GraphLogicalGetV(tableConfig=[{isAll=false, tables=[COMMENT]}], alias=[b],"
+                    + " opt=[END])\n"
+                    + "    GraphLogicalPathExpand(fused=[GraphPhysicalGetV(tableConfig=[{isAll=false,"
+                    + " tables=[COMMENT]}], alias=[_], opt=[END], physicalOpt=[ITSELF])\n"
+                    + "  GraphPhysicalExpand(tableConfig=[[EdgeLabel(LIKES, PERSON, COMMENT),"
+                    + " EdgeLabel(REPLYOF, COMMENT, COMMENT)]], alias=[_], opt=[OUT],"
+                    + " physicalOpt=[VERTEX])\n"
+                    + "], offset=[1], fetch=[1], path_opt=[ARBITRARY], result_opt=[END_V],"
+                    + " alias=[_], start_alias=[a])\n"
+                    + "      GraphLogicalSource(tableConfig=[{isAll=false, tables=[PERSON,"
+                    + " COMMENT]}], alias=[a], fusedFilter=[[=(_.id, 1)]], opt=[VERTEX])",
+                after2.explain().trim());
+    }
 }