Unexpected mixed index usage in queries with both "or" and "not"

[WeilingDu]

When a query uses both or-step and not-step, the usage of mixed index is not expected. Specifically, the index query does not include the conditions in the or-step, when the Gremlin query uses or-step and not-step at the same time.

For example, we built the mixed index 'PersonalInfo' on properties 'name', 'age' and 'address'.

gremlin> mgmt = graph.openManagement()
==>org.janusgraph.graphdb.database.management.ManagementSystem@4d3ce310

gremlin>  mgmt.printSchema()
==>------------------------------------------------------------------------------------------------
Vertex Label Name              | Partitioned | Static                                             |
---------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------
Edge Label Name                | Directed    | Unidirected | Multiplicity                         |
---------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------
Property Key Name              | Cardinality | Data Type                                          |
---------------------------------------------------------------------------------------------------
name                           | SINGLE      | class java.lang.String                             |
age                            | SINGLE      | class java.lang.Integer                            |
address                        | SINGLE      | class java.lang.String                             |
---------------------------------------------------------------------------------------------------
Graph Index (Vertex)           | Type        | Unique    | Backing        | Key:           Status |
---------------------------------------------------------------------------------------------------
PersonalInfo                   | Mixed       | false     | mixedIndex     | name:         ENABLED |
                               |             |           |                | age:          ENABLED |
                               |             |           |                | address:      ENABLED |
---------------------------------------------------------------------------------------------------
Graph Index (Edge)             | Type        | Unique    | Backing        | Key:           Status |
---------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------
Relation Index (VCI)           | Type        | Direction | Sort Key       | Order    |     Status |
---------------------------------------------------------------------------------------------------

We added three vertices to the graph as follows:

gremlin> :remote config alias g graphtest_traversal
==>g=graphtest_traversal

gremlin> g.V().valueMap()
==>{name=[Allen], age=[27], address=[China]}
==>{name=[Alice], age=[25]}
==>{name=[Bob], age=[29], address=[China]}

The following query will result in a full scan.

gremlin> g.V().or(__.has('name', textPrefix('A')), __.has('name', textPrefix('B'))).not(has('address')).profile()
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
JanusGraphStep(vertex,[])                                                                     47.449    99.78
  constructGraphCentricQuery                                                                   0.019
  constructGraphCentricQuery                                                                   0.003
  GraphCentricQuery                                                                           47.302
    \_condition=()
    \_orders=[]
    \_isFitted=false
    \_isOrdered=true
    \_query=[]
    scan                                                                                      47.201
      \_query=[]
      \_fullscan=true
      \_condition=VERTEX
JanusGraphMultiQueryStep                                                                       0.012     0.03
NoOpBarrierStep(2500)                                                                          0.010     0.02
NotStep([TraversalFilterStep([JanusGraphPropert...                                             0.006     0.01
  TraversalFilterStep([JanusGraphPropertiesStep...                                             0.000
    JanusGraphPropertiesStep([address],property)                                               0.000
JanusGraphMultiQueryStep                                                                       0.045     0.10
NoOpBarrierStep(2500)                                                                          0.019     0.04
JanusGraphHasStep([name.or(textPrefix(A), textP...                                             0.008     0.02
                                            >TOTAL                     -           -          47.551        -

The following query only leverages the mixed index on the condition (age >= 20 AND age < 30) without including the conditions on 'name'.

gremlin> g.V().has('age',between(20,30)).or(__.has('name', textPrefix('A')), __.has('name', textPrefix('B'))).not(has('address')).profile()
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
JanusGraphStep([],[age.and(>=(20), <(30))])                                                   60.218    99.34
  constructGraphCentricQuery                                                                   0.381
  GraphCentricQuery                                                                           59.306
    \_condition=(age >= 20 AND age < 30)
    \_orders=[]
    \_isFitted=true
    \_isOrdered=true
    \_query=[(age >= 20 AND age < 30)]:PersonalInfo
    \_index=PersonalInfo
    \_index_impl=mixedIndex
    backend-query                                                      0                      59.225
      \_query=PersonalInfo:[(age >= 20 AND age < 30)]:PersonalInfo
JanusGraphMultiQueryStep                                                                       0.316     0.52
NoOpBarrierStep(2500)                                                                          0.004     0.01
NotStep([TraversalFilterStep([JanusGraphPropert...                                             0.006     0.01
  TraversalFilterStep([JanusGraphPropertiesStep...                                             0.000
    JanusGraphPropertiesStep([address],property)                                               0.000
JanusGraphMultiQueryStep                                                                       0.050     0.08
NoOpBarrierStep(2500)                                                                          0.012     0.02
JanusGraphHasStep([name.or(textPrefix(A), textP...                                             0.008     0.01
                                            >TOTAL                     -           -          60.618        -

The underlying reason could be:
For these queries, the not-step is moved in front of or-step because of the FilterRankingStrategy. Then, in foldInHasCotainer method of HasStepFolder.java, when the current step is NotStep, it will break the traversal. This means it does not condition the steps after NotStep also might be folded in has container, which would be used for index query.

Thus, it is recommended to handle NotStep case in foldInHasCotainer method to improve Or-step support on mixed index.