Enable multiQuery optimization for valueMap step

[li-boxuan]

We have JanusGraphPropertiesStep which extends PropertiesStep and supports multiQuery optimization, so that values() step can be optimized.

We can do something similar to PropertyMapStep so that multiQuery optimization can be applied to valueMap() step as well.

Requested by #2401

[ntrhieu89]

Hi @li-boxuan , do you still have plan to implement this optimization?

[li-boxuan]

Hi, @ntrhieu89 My recent schedule doesn't allow me to do so. I could assist and/or review if anyone wants to give it a try!

[FlorianHockmann]

This issue is mentioned explicitly in the docs about batch processing.

Just posting this here as a reminder for us that we don't forget to update the docs when we close this issue.

[porunov]

I think we could make PropertyMapStep and provide JanusGraphPropertiesStep via setPropertyTraversal(final Traversal.Admin<Element, ? extends Property> propertyTraversal) which already leverages multi-query optimization.
That said, valueMap step also accept options to retrieve id, label, key, value.
id we already know, so no need to do anything special here, but label should be retrieved.
TinkerPop doesn't have similar extension for label retrieval as it does for properties retrieval and we can't easily overwrite map method because it uses a private field TraversalRing<K, E> traversalRing which is created in the constructor for some reason.
I believe if apache/tinkerpop#2022 is merged then we will be able to make multi-query call to both properties and labels.
For properties we can use JanusGraphPropertiesStep traversal, but for labels we could use something like:

((JanusGraphMultiVertexQuery) ((BasicVertexCentricQueryBuilder) multiQuery).noPartitionRestriction())
                    .types(BaseLabel.VertexLabelEdge).direction(Direction.OUT).vertices()

We could even execute both queries (for properties and for labels) in parallel in theory, but then we should decide if it's OK to create additional Thread in this step or should we use some managed thread pool for that.

[ntrhieu89]

Is there anyone who will work ok this one? Otherwise, I could take a look.

I think ElementMapStep has the same issue, and may want to improve it also.

[porunov]

Is there anyone who will work ok this one? Otherwise, I could take a look.

I think ElementMapStep has the same issue, and may want to improve it also.

I was trying to do that today, but stuck a little bit with vertex labels multi-query retrieval due to small TinkerPop limitation (tying to fix it here: apache/tinkerpop#2022 ).
I will try again on Monday or so. I think I will be able to add properties multi-query fetch to PropertyMapStep next week but for labels we will need to wait until JanusGraph is uses TinkerPop version with apache/tinkerpop#2022 included.

I think I would better prefer help with #3244 (multi-query optimization for has step). I don't know if changes on TinkerPop side will be needed or not for #3244 . Maybe we could create some custom step which pre-fetches vertex properties in-memory and inject that step before has steps, but I really didn't think about that issue yet. Maybe some changes on TinkerPop side may be required (like making some fields / methods as protected instead of public).

[ntrhieu89]

In my query testing with profile(), having this option query.batch-property-prefetch=true prefetches all vertex properties in JanusGraphVertexStep, and hence HasStep just does the filtering in-memory.

[porunov]

In my query testing with profile(), having this option query.batch-property-prefetch=true prefetches all vertex properties in JanusGraphVertexStep, and hence HasStep just does the filtering in-memory.

I need to check that, but last time I was checking I had a problem with has steps after an index. In my situation the prefetching didn’t kick in.

Something like:
g.V().has(“name”, “foo”).has(“age”, 123)

in the above query if an index exists for name but not for age, then we will not use prefetch in the above case which will lead poor filtering performance because age properties will be prefetched one by one instead of using multi-query optimisation.
I might be wrong but a while ago I had such problem. I doubt anything changed.
Thus, I think it would make sense to collect properties of each “has” step using multi-query optimisation before kicking in that filtering.

P.S. I think it would make sense to keep discussion about multi-query for has step in the linked issue #3244 (sorry for staring one here)

[porunov]

Related PR: apache/tinkerpop#2027
In the above PR we add additional getter methods which will allow to copy tokens and traversalRing into the replacement PropertyMap step.

[porunov]

TinkerPop 3.6.3 is released. After we update TinkerPop to 3.6.3 in JanusGraph we will be able to implement this optimization issue.
This issue is blocked by #3766

[ntrhieu89]

Hi @porunov, thanks for the recent commits. I will look at the changes to learn from them.
In our deployment, we also experience high latency with this query:

g.V().has('place', 'id', 1).inE('isLocatedIn').outV().label().dedup()

I troubleshooted it and realized that to be able to get all labels, currently multiQuery optimization is not applied and hence sequential getRange()s are used. If there are thousands of vertices found, label() will take long time. Could this also leverage the multiQuery optimization as well?

[porunov]

Hi @porunov, thanks for the recent commits. I will look at the changes to learn from them. In our deployment, we also experience high latency with this query:

g.V().has('place', 'id', 1).inE('isLocatedIn').outV().label().dedup()

I troubleshooted it and realized that to be able to get all labels, currently multiQuery optimization is not applied and hence sequential getRange()s are used. If there are thousands of vertices found, label() will take long time. Could this also leverage the multiQuery optimization as well?

Yes, this is on my radar. The dedicated issue for ‘label’ step is: #3813

It’s now fairly easy to add multi-query support for label step. I think we can simply replace TinkerPops label step with our label step with the optimisation in place. The only thing we need to ensure that the any strategy which uses TinkerPops label step is applied before the replacement strategy is applied OR we simply need to remove ‘final’ keyword from TinkerPops ‘LabelStep’. I will see if TinkerPop folks are OK with it and will fix #3813 after that.

[ntrhieu89]

Thanks. I think it is worth mentioning that hasLabel() also has the same issue. I am not sure whether label() and hasLabel() share the same code path for retrieving labels or not.

The query we encountered filter the vertices based on label and then get their ids like this:

g.V().has('place', 'id', 1).inE('isLocatedIn').outV().hasLabel('comment').id().toList()

Currently I don't think there is a work-around until hasLabel() is improved with multiQuery.

[porunov]

Thanks. I think it is worth mentioning that hasLabel() also has the same issue. I am not sure whether label() and hasLabel() share the same code path for retrieving labels or not.

The query we encountered filter the vertices based on label and then get their ids like this:

g.V().has('place', 'id', 1).inE('isLocatedIn').outV().hasLabel('comment').id().toList()

Currently I don't think there is a work-around until hasLabel() is improved with multiQuery.

hasLabel and has optimizations were merged in master branch a week ago. The optimization should be available in the latest commit release 1.0.0-20230614-232843.207d6bb.

[ntrhieu89]

Hi @porunov , in my test it looks like the multiQuery optimization sometimes does not apply to anonymous traversal.

For example, the twos below both use multiQuery:

gremlin> g.V().has("_label_", "LB").values('name').profile()
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
JanusGraphStep([],[_label_.eq(LB)])                                  650         650          20.641    46.71
  constructGraphCentricQuery                                                                   0.080
  GraphCentricQuery                                                                           20.688
    \_condition=(_label_ = LB)
    \_orders=[]
    \_isFitted=true
    \_isOrdered=true
    \_query=multiKSQ[1]{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
    \_index=Idx_comidx_Vertex__label_
    backend-query                                                    650                      20.644
      \_query=Idx_comidx_Vertex__label_:multiKSQ[1]{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
JanusGraphMultiQueryStep                                             650         650           0.837     1.90
JanusGraphPropertiesStep([name],value)                               650         650          22.710    51.39
  \_condition=type[name]
  \_orders=[]
  \_isFitted=true
  \_isOrdered=true
  \_query=name:SliceQuery[0x5010A0,0x5010A1)
  \_multi=true
  \_vertices=650
  optimization                                                                                 0.035
  backend-query                                                      650                      20.499
    \_query=name:SliceQuery[0x5010A0,0x5010A1)
                                            >TOTAL                     -           -          44.189        -

gremlin> g.V().has("_label_", "LB").sideEffect(__.values('name')).profile()
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
JanusGraphStep([],[_label_.eq(LB)])                                  650         650          16.409    39.90
  constructGraphCentricQuery                                                                   0.078
  GraphCentricQuery                                                                           16.455
    \_condition=(_label_ = LB)
    \_orders=[]
    \_isFitted=true
    \_isOrdered=true
    \_query=multiKSQ[1]{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
    \_index=Idx_comidx_Vertex__label_
    backend-query                                                    650                      16.407
      \_query=Idx_comidx_Vertex__label_:multiKSQ[1]{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
JanusGraphMultiQueryStep                                             650         650           0.882     2.15
TraversalSideEffectStep([JanusGraphPropertiesSt...                   650         650          23.835    57.96
  JanusGraphPropertiesStep([name],value)                             650         650          23.030
    \_condition=type[name]
    \_orders=[]
    \_isFitted=true
    \_isOrdered=true
    \_query=name:SliceQuery[0x5010A0,0x5010A1)
    \_multi=true
    \_vertices=650
    optimization                                                                               0.034
    backend-query                                                    650                      20.524
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
                                            >TOTAL                     -           -          41.127        -

However, with the two queries below, only the first one uses multiQuery:

gremlin> g.V().has("_label_", "LB").limit(200).in('Links').values('name').profile()
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
JanusGraphStep([],[_label_.eq(LB)])                                  200         200          15.586     2.59
  constructGraphCentricQuery                                                                   0.072
  GraphCentricQuery                                                                           15.420
    \_condition=(_label_ = LB)
    \_orders=[]
    \_limit=200
    \_isFitted=true
    \_isOrdered=true
    \_query=multiKSQ[1]@200{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
    \_index=Idx_comidx_Vertex__label_
    backend-query                                                    200                      15.353
      \_query=Idx_comidx_Vertex__label_:multiKSQ[1]@200{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
      \_limit=200
JanusGraphMultiQueryStep                                             200         200           0.284     0.05
JanusGraphVertexStep(IN,[Links],vertex)                       14879       14879          35.007     5.82
  \_condition=type[Links]
  \_orders=[]
  \_isFitted=true
  \_isOrdered=true
  \_query=Links:SliceQuery[0x7AC1,0x7AC2)
  \_multi=true
  \_vertices=200
  optimization                                                                                 0.072
  backend-query                                                    14879                      13.124
    \_query=Links:SliceQuery[0x7AC1,0x7AC2)
JanusGraphMultiQueryStep                                           14879       14803          23.386     3.89
JanusGraphPropertiesStep([name],value)                             14879       14803         527.611    87.66
  \_condition=type[name]
  \_orders=[]
  \_isFitted=true
  \_isOrdered=true
  \_query=name:SliceQuery[0x5010A0,0x5010A1)
  \_multi=true
  \_vertices=14803
  optimization                                                                                 0.060
  backend-query                                                    14803                     469.270
    \_query=name:SliceQuery[0x5010A0,0x5010A1)
                                            >TOTAL                     -           -         601.875        -

gremlin> g.V().has("_label_", "LB").limit(200).sideEffect(__.in('Links').values('name')).profile()
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
JanusGraphStep([],[_label_.eq(LB)])                                  200         200          15.385     2.09
  constructGraphCentricQuery                                                                   0.084
  GraphCentricQuery                                                                           15.214
    \_condition=(_label_ = LB)
    \_orders=[]
    \_limit=200
    \_isFitted=true
    \_isOrdered=true
    \_query=multiKSQ[1]@200{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
    \_index=Idx_comidx_Vertex__label_
    backend-query                                                    200                      15.169
      \_query=Idx_comidx_Vertex__label_:multiKSQ[1]@200{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
      \_limit=200
JanusGraphMultiQueryStep                                             200         200           0.508     0.07
TraversalSideEffectStep([JanusGraphVertexStep(I...                   200         200         721.249    97.84
  JanusGraphVertexStep(IN,[Links],vertex)                     14879       14879          46.080
    \_condition=type[Links]
    \_orders=[]
    \_isFitted=true
    \_isOrdered=true
    \_query=Links:SliceQuery[0x7AC1,0x7AC2)
    \_multi=true
    \_vertices=200
    optimization                                                                               0.076
    backend-query                                                  14879                      14.930
      \_query=Links:SliceQuery[0x7AC1,0x7AC2)
  JanusGraphMultiQueryStep                                         14879       14879          18.304
  JanusGraphPropertiesStep([name],value)                           14879       14879         653.346
    \_condition=type[name]
    \_orders=[]
    \_isFitted=true
    \_isOrdered=true
    \_query=name:SliceQuery[0x5010A0,0x5010A1)
    \_multi=true
    \_vertices=4
    optimization                                                                               0.035
    backend-query                                                     71                       3.232
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
    optimization                                                                               0.011
    backend-query                                                     11                       0.999
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
    optimization                                                                               0.008
    backend-query                                                    200                       6.128
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
    optimization                                                                               0.009
    backend-query                                                    107                       3.123
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
    optimization                                                                               0.008
    backend-query                                                     45                       2.029
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
    optimization                                                                               0.009
    backend-query                                                    285                       8.636
      \_query=name:SliceQuery[0x5010A0,0x5010A1)

...

Or maybe the second one actually uses it, but the barrier is somehow set to 4?

 \_vertices=4

[porunov]

Hi @porunov , in my test it looks like the multiQuery optimization sometimes does not apply to anonymous traversal.

For example, the twos below both use multiQuery:

gremlin> g.V().has("_label_", "LB").values('name').profile()
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
JanusGraphStep([],[_label_.eq(LB)])                                  650         650          20.641    46.71
  constructGraphCentricQuery                                                                   0.080
  GraphCentricQuery                                                                           20.688
    \_condition=(_label_ = LB)
    \_orders=[]
    \_isFitted=true
    \_isOrdered=true
    \_query=multiKSQ[1]{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
    \_index=Idx_comidx_Vertex__label_
    backend-query                                                    650                      20.644
      \_query=Idx_comidx_Vertex__label_:multiKSQ[1]{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
JanusGraphMultiQueryStep                                             650         650           0.837     1.90
JanusGraphPropertiesStep([name],value)                               650         650          22.710    51.39
  \_condition=type[name]
  \_orders=[]
  \_isFitted=true
  \_isOrdered=true
  \_query=name:SliceQuery[0x5010A0,0x5010A1)
  \_multi=true
  \_vertices=650
  optimization                                                                                 0.035
  backend-query                                                      650                      20.499
    \_query=name:SliceQuery[0x5010A0,0x5010A1)
                                            >TOTAL                     -           -          44.189        -

gremlin> g.V().has("_label_", "LB").sideEffect(__.values('name')).profile()
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
JanusGraphStep([],[_label_.eq(LB)])                                  650         650          16.409    39.90
  constructGraphCentricQuery                                                                   0.078
  GraphCentricQuery                                                                           16.455
    \_condition=(_label_ = LB)
    \_orders=[]
    \_isFitted=true
    \_isOrdered=true
    \_query=multiKSQ[1]{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
    \_index=Idx_comidx_Vertex__label_
    backend-query                                                    650                      16.407
      \_query=Idx_comidx_Vertex__label_:multiKSQ[1]{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
JanusGraphMultiQueryStep                                             650         650           0.882     2.15
TraversalSideEffectStep([JanusGraphPropertiesSt...                   650         650          23.835    57.96
  JanusGraphPropertiesStep([name],value)                             650         650          23.030
    \_condition=type[name]
    \_orders=[]
    \_isFitted=true
    \_isOrdered=true
    \_query=name:SliceQuery[0x5010A0,0x5010A1)
    \_multi=true
    \_vertices=650
    optimization                                                                               0.034
    backend-query                                                    650                      20.524
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
                                            >TOTAL                     -           -          41.127        -

However, with the two queries below, only the first one uses multiQuery:

gremlin> g.V().has("_label_", "LB").limit(200).in('Links').values('name').profile()
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
JanusGraphStep([],[_label_.eq(LB)])                                  200         200          15.586     2.59
  constructGraphCentricQuery                                                                   0.072
  GraphCentricQuery                                                                           15.420
    \_condition=(_label_ = LB)
    \_orders=[]
    \_limit=200
    \_isFitted=true
    \_isOrdered=true
    \_query=multiKSQ[1]@200{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
    \_index=Idx_comidx_Vertex__label_
    backend-query                                                    200                      15.353
      \_query=Idx_comidx_Vertex__label_:multiKSQ[1]@200{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
      \_limit=200
JanusGraphMultiQueryStep                                             200         200           0.284     0.05
JanusGraphVertexStep(IN,[Links],vertex)                       14879       14879          35.007     5.82
  \_condition=type[Links]
  \_orders=[]
  \_isFitted=true
  \_isOrdered=true
  \_query=Links:SliceQuery[0x7AC1,0x7AC2)
  \_multi=true
  \_vertices=200
  optimization                                                                                 0.072
  backend-query                                                    14879                      13.124
    \_query=Links:SliceQuery[0x7AC1,0x7AC2)
JanusGraphMultiQueryStep                                           14879       14803          23.386     3.89
JanusGraphPropertiesStep([name],value)                             14879       14803         527.611    87.66
  \_condition=type[name]
  \_orders=[]
  \_isFitted=true
  \_isOrdered=true
  \_query=name:SliceQuery[0x5010A0,0x5010A1)
  \_multi=true
  \_vertices=14803
  optimization                                                                                 0.060
  backend-query                                                    14803                     469.270
    \_query=name:SliceQuery[0x5010A0,0x5010A1)
                                            >TOTAL                     -           -         601.875        -

gremlin> g.V().has("_label_", "LB").limit(200).sideEffect(__.in('Links').values('name')).profile()
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
JanusGraphStep([],[_label_.eq(LB)])                                  200         200          15.385     2.09
  constructGraphCentricQuery                                                                   0.084
  GraphCentricQuery                                                                           15.214
    \_condition=(_label_ = LB)
    \_orders=[]
    \_limit=200
    \_isFitted=true
    \_isOrdered=true
    \_query=multiKSQ[1]@200{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
    \_index=Idx_comidx_Vertex__label_
    backend-query                                                    200                      15.169
      \_query=Idx_comidx_Vertex__label_:multiKSQ[1]@200{KeySliceQuery(0x015289A04CC2)[0x00,0xFF)}
      \_limit=200
JanusGraphMultiQueryStep                                             200         200           0.508     0.07
TraversalSideEffectStep([JanusGraphVertexStep(I...                   200         200         721.249    97.84
  JanusGraphVertexStep(IN,[Links],vertex)                     14879       14879          46.080
    \_condition=type[Links]
    \_orders=[]
    \_isFitted=true
    \_isOrdered=true
    \_query=Links:SliceQuery[0x7AC1,0x7AC2)
    \_multi=true
    \_vertices=200
    optimization                                                                               0.076
    backend-query                                                  14879                      14.930
      \_query=Links:SliceQuery[0x7AC1,0x7AC2)
  JanusGraphMultiQueryStep                                         14879       14879          18.304
  JanusGraphPropertiesStep([name],value)                           14879       14879         653.346
    \_condition=type[name]
    \_orders=[]
    \_isFitted=true
    \_isOrdered=true
    \_query=name:SliceQuery[0x5010A0,0x5010A1)
    \_multi=true
    \_vertices=4
    optimization                                                                               0.035
    backend-query                                                     71                       3.232
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
    optimization                                                                               0.011
    backend-query                                                     11                       0.999
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
    optimization                                                                               0.008
    backend-query                                                    200                       6.128
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
    optimization                                                                               0.009
    backend-query                                                    107                       3.123
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
    optimization                                                                               0.008
    backend-query                                                     45                       2.029
      \_query=name:SliceQuery[0x5010A0,0x5010A1)
    optimization                                                                               0.009
    backend-query                                                    285                       8.636
      \_query=name:SliceQuery[0x5010A0,0x5010A1)

...

Or maybe the second one actually uses it, but the barrier is somehow set to 4?

 \_vertices=4

vertices stat is incorrectly named. This represents only vertices retrieved using the last batch operation, and not all the batch operations.
However, it's strange that the execution of g.V().has("_label_", "LB").limit(200).in('Links').values('name').profile() and g.V().has("_label_", "LB").limit(200).sideEffect(__.in('Links').values('name')).profile() were executed with different batch sizes. Are you using JanusGraph 1.0.0? Did you rollback the transaction between those query executions (g.tx().tollback())?

[ntrhieu89]

It is not 1.0.0 but close. The commit ID is 0cb1221 back in August: https://github.com/JanusGraph/janusgraph/tree/0cb12219b23264060e1ecdf4a6b06832e9575e9d

We could not wait for 1.0.0 so we picked that version.