[TINKERPOP-2342] FilterRankingStrategy interferes with IncidentToAdjacentStrategy

• Type: Bug
• Status: Closed
• Priority: Minor
• Resolution: Not A Problem
• Affects Version/s: 3.4.4
• Component/s: process
• Assignee: Unassigned
• Reporter: Florian G
• Created: 24/Feb/20 14:14
• Updated: 13/Oct/21 18:41
• Resolved: 13/Oct/21 18:41

Description

The implementation of IncidentToAdjacentStrategy replaces steps from V to E followed by a step from E to V by a single step from V to V. In order to avoid touching parts of the query which may not be reordered, this strategy marks certain steps with a special label.

In some cases however, these labels are pushed to other steps by the FilterRankingStrategy. As a consequence, the IncidentToAdjacentStrategy does not behave as expected anymore.

See the following example:
Assume a graph consisting of a single Vertex v connected to itself by an edge with the property dist = 10.

g.V().repeat(outE().has("dist", 10).inV().outE().inV().sideEffect{i = 0}).times(1).path()

• The sideEffect step just sets a dummy variable and is necessary to cause the problem.
• The has step has no semantic effect of filtering but is necessary to cause the problem as well.
• The path step shows how the output differs from the expected output.

One would expect a result like:

path[v[1], e[2][1->label->1], v[1], e[2][1->label->1], v[1]]

But the actual result is:

path[v[1], e[2][1->label->1], v[1], v[1]]

Let's call explain() on the above query to see why this happens:

==>Traversal Explanation
=================================================================================================================================================================================================================================================================================================
Original Traversal                          [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)]),  EdgeVertexStep(IN), VertexStep(OUT,edge), EdgeVertexStep(IN), LambdaSideEffectStep(lambda),  RepeatEndStep],until(loops(1)),emit(false)), PathStep]

ConnectiveStrategy                    [D]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)]), EdgeVertexStep(IN), VertexStep(OUT,edge), EdgeVertexStep(IN), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
EarlyLimitStrategy                    [O]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)]), EdgeVertexStep(IN), VertexStep(OUT,edge), EdgeVertexStep(IN), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
MatchPredicateStrategy                [O]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)]), EdgeVertexStep(IN), VertexStep(OUT,edge), EdgeVertexStep(IN), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
FilterRankingStrategy                 [O]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)]), EdgeVertexStep(IN), VertexStep(OUT,edge), EdgeVertexStep(IN), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
InlineFilterStrategy                  [O]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)]), EdgeVertexStep(IN), VertexStep(OUT,edge), EdgeVertexStep(IN), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
RepeatUnrollStrategy                  [O]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)]), EdgeVertexStep(IN), VertexStep(OUT,edge), EdgeVertexStep(IN), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
IncidentToAdjacentStrategy            [O]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)])@[~gremlin.incidentToAdjacent], EdgeVertexStep(IN), VertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
CountStrategy                         [O]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)])@[~gremlin.incidentToAdjacent], EdgeVertexStep(IN), VertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
PathRetractionStrategy                [O]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)])@[~gremlin.incidentToAdjacent], EdgeVertexStep(IN), VertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
AdjacentToIncidentStrategy            [O]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)])@[~gremlin.incidentToAdjacent], EdgeVertexStep(IN), VertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
LazyBarrierStrategy                   [O]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)])@[~gremlin.incidentToAdjacent], EdgeVertexStep(IN), VertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
AdjacentVertexFilterOptimizerStrategy [P]   [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,edge), HasStep([dist.eq(10)])@[~gremlin.incidentToAdjacent], EdgeVertexStep(IN), VertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
JanusGraphLocalQueryOptimizerStrategy [P]   [GraphStep(vertex,[]), RepeatStep([JanusGraphVertexStep([dist.eq(10)])@[~gremlin.incidentToAdjacent], EdgeVertexStep(IN), JanusGraphVertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
JanusGraphStepStrategy                [P]   [JanusGraphStep(vertex,[]), RepeatStep([JanusGraphVertexStep([dist.eq(10)])@[~gremlin.incidentToAdjacent], EdgeVertexStep(IN), JanusGraphVertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
JanusGraphIoRegistrationStrategy      [P]   [JanusGraphStep(vertex,[]), RepeatStep([JanusGraphVertexStep([dist.eq(10)])@[~gremlin.incidentToAdjacent], EdgeVertexStep(IN), JanusGraphVertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
ProfileStrategy                       [F]   [JanusGraphStep(vertex,[]), RepeatStep([JanusGraphVertexStep([dist.eq(10)])@[~gremlin.incidentToAdjacent], EdgeVertexStep(IN), JanusGraphVertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]
StandardVerificationStrategy          [V]   [JanusGraphStep(vertex,[]), RepeatStep([JanusGraphVertexStep([dist.eq(10)]), EdgeVertexStep(IN), JanusGraphVertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]

Final Traversal                             [JanusGraphStep(vertex,[]), RepeatStep([JanusGraphVertexStep([dist.eq(10)]), EdgeVertexStep(IN), JanusGraphVertexStep(OUT,vertex), LambdaSideEffectStep(lambda), RepeatEndStep],until(loops(1)),emit(false)), PathStep]

As one can see, after the IncidentToAdjacentStrategy call, there exists a hidden label on the HasStep. This label was originally placed on the preceeding VertexStep by the IncidentToAdjacentStrategy in order to avoid optimizations on the inner part of the query. However, an intermediate call of the FilterRankingStrategy pushes this label one step to the right, which causes the IncidentToAdjacentStrategy to "forget" it's restrictions.
Consequently, the query is in optimized by mistake.

Just for comparison: If the sideEffect step is removed, the query returns the expected result.