[TINKERPOP-2940] Strategy Dependent Behavior of Ternary Boolean Logic

• Type: Improvement
• Status: Open
• Priority: Critical
• Resolution: Unresolved
• Affects Version/s: 3.6.2
• Component/s: process
• Assignee: Unassigned
• Reporter: Cole Greer
• Created: 01/May/23 18:54
• Updated: 15/Jun/23 19:05

Description

The current implementation of ternary boolean logic in TinkerPop leads to inconsistent and unexpected behavior depending on strategy application. This stems from the binary reduction logic implemented here. `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:

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))])]

 
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.

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))])])]

This is essentially the same traversal as above, but in this case the TraversalFilterStep is preserved, leading to the early reduction of the `error`.