[
https://issues.apache.org/jira/browse/TINKERPOP-2940?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Yang Xia updated TINKERPOP-2940:
--------------------------------
Priority: Critical (was: Major)
> Strategy Dependent Behavior of Ternary Boolean Logic
> ----------------------------------------------------
>
> Key: TINKERPOP-2940
> URL: https://issues.apache.org/jira/browse/TINKERPOP-2940
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
> Affects Versions: 3.6.2
> Reporter: Cole Greer
> Priority: Critical
>
> The current implementation of [ternary boolean
> logic|https://tinkerpop.apache.org/docs/3.6.2/dev/provider/#_ternary_boolean_logics]
> in TinkerPop leads to inconsistent and unexpected behavior depending on
> strategy application. This stems from the binary reduction logic implemented
> [here|https://github.com/Bit-Quill/tinkerpop/blob/d653b2401271ff9eb8e2249f878344c27ac81418/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/FilterStep.java#L44].
> `TraversalFilterStep` and `WhereStep` are currently special cases which will
> trigger early reduction of boolean error states to false. The issue is that
> some strategies such as `InlineFilterStrategy` will sometimes remove such
> steps to produce optimized traversals which are almost equivalent, but don't
> have this early reduction behavior.
> Here is a simple example of this in TinkerGraph 3.6.2:
> {code:bash}
> gremlin>
> g.withoutStrategies(InlineFilterStrategy).inject(1).not(where(is(lt(NaN))))
> ==>1
> gremlin>
> g.withoutStrategies(InlineFilterStrategy).inject(1).not(where(is(lt(NaN)))).explain()
> ==>Traversal Explanation
> ==========================================================================================================
> Original Traversal [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> ConnectiveStrategy [D] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> CountStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> IdentityRemovalStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> EarlyLimitStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> MatchPredicateStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> IncidentToAdjacentStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> AdjacentToIncidentStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> FilterRankingStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> ByModulatorOptimizationStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> RepeatUnrollStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> PathRetractionStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> LazyBarrierStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> TinkerGraphCountStrategy [P] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> TinkerGraphStepStrategy [P] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> ProfileStrategy [F] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> StandardVerificationStrategy [V] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> Final Traversal [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> gremlin> g.inject(1).not(where(is(lt(NaN))))
> gremlin> g.inject(1).not(where(is(lt(NaN)))).explain()
> ==>Traversal Explanation
> ==========================================================================================================
> Original Traversal [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> ConnectiveStrategy [D] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> CountStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> IdentityRemovalStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> EarlyLimitStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> MatchPredicateStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> FilterRankingStrategy [O] [InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]
> InlineFilterStrategy [O] [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> IncidentToAdjacentStrategy [O] [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> AdjacentToIncidentStrategy [O] [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> ByModulatorOptimizationStrategy [O] [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> RepeatUnrollStrategy [O] [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> PathRetractionStrategy [O] [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> LazyBarrierStrategy [O] [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> TinkerGraphCountStrategy [P] [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> TinkerGraphStepStrategy [P] [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> ProfileStrategy [F] [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> StandardVerificationStrategy [V] [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> Final Traversal [InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]
> {code}
>
> In the first case, the final traversal contains `[InjectStep([1]),
> NotStep([TraversalFilterStep([IsStep(lt(NaN))])])]`. In this example, the
> `error` from the `IsStep` get's reduced early to `false` by the
> `TraversalFilterStep`. Therefore it is evaluated to `not(false)` which is
> `true`.
> In the second case, the `TraversalFilterStep` is removed by the
> `InlineFilterStrategy` which leads to a final traversal of `[InjectStep([1]),
> NotStep([IsStep(lt(NaN))])]`. In this case there is no early reduction step,
> so it evaluates to `not(error)`, which produces the result `error`, which is
> then reduced to `false`.
> The interaction between the strategies and the early reduction behavior of
> the where step can lead to very unpredictable results. For example, here is a
> query which I would expect to behave in the same manner as the second
> traversal from above.
> {code:bash}
> gremlin> g.addV().property("test", 1)
> ==>v[2]
> gremlin> g.V().not(where(values('test').is(lt(NaN))))
> ==>v[2]
> gremlin> g.V().not(where(values('test').is(lt(NaN)))).explain()
> ==>Traversal Explanation
> ===================================================================================================================================================
> Original Traversal [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> ConnectiveStrategy [D] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> CountStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> IdentityRemovalStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> EarlyLimitStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> MatchPredicateStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> FilterRankingStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> InlineFilterStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> IncidentToAdjacentStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> AdjacentToIncidentStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> ByModulatorOptimizationStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> RepeatUnrollStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> PathRetractionStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> LazyBarrierStrategy [O] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> TinkerGraphCountStrategy [P] [GraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> TinkerGraphStepStrategy [P] [TinkerGraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> ProfileStrategy [F] [TinkerGraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> StandardVerificationStrategy [V] [TinkerGraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> Final Traversal [TinkerGraphStep(vertex,[]),
> NotStep([TraversalFilterStep([PropertiesStep([test],value),
> IsStep(lt(NaN))])])]
> {code}
> This is essentially the same traversal as above, but in this case the
> TraversalFilterStep is preserved, leading to the early reduction of the
> `error`.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
