Cole Greer created TINKERPOP-2940: ------------------------------------- Summary: 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
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 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)