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)
