search

opencypher / cypher-for-gremlin

Cypher for Gremlin adds Cypher support to any Gremlin graph database.
Apache License 2.0
359 stars 48 forks source link

Non optimal query when direct Id queries #226

Closed mad closed 5 years ago

mad commented 5 years ago

This issue may relate with lack of JanusGraph optimization strategy

Sample query

MATCH (n1), (n2)
WHERE id(n1) = {id1} AND id(n2) = {id2} 
RETURN n1.value < n2.value

Translated to:

g.V().as('n1').V().as('n2') \
.where( \
  __.and( \
    __.choose(__.constant(786472), __.constant(786472), __.constant('  cypher.null')).is(neq('  cypher.null')).as('  GENERATED1') \
      .select('n1') \
      .choose(neq('  cypher.null'), __.id(), __.constant('  cypher.null')).is(neq('  cypher.null')) \
      .where(eq('  GENERATED1')), \
    __.choose(__.constant(1891), __.constant(1891), __.constant('  cypher.null')).is(neq('  cypher.null')).as('  GENERATED2') \
      .select('n2').choose(neq('  cypher.null'), __.id(), __.constant('  cypher.null')).is(neq('  cypher.null')) \
      .where(eq('  GENERATED2')))) \
.select('n1', 'n2') \
.project('n1.value < n2.value') \
.by(__.select('n2') \
   .choose(neq('  cypher.null'), \
           __.choose(__.values('value'),__.values('value'), __.constant('  cypher.null')), \
           __.constant('  cypher.null')).as('  GENERATED3') \
  .select('n1') \
  .choose(neq('  cypher.null'), __.choose(__.values('value'), __.values('value'), __.constant('  cypher.null')), __.constant('  cypher.null')) \
  .choose(__.or(__.is(eq('  cypher.null')), __.select('  GENERATED3').is(eq('  cypher.null'))), __.constant('  cypher.null'), __.choose(__.where(lt('  GENERATED3')), __.constant(true), __.constant(false)))).profile()

And profile 

=============================================================================================================
JanusGraphStep(vertex,[])@[n1]                                        14          14           9.147     5.01
    \_condition=()
    \_isFitted=false
    \_query=[]
    \_orders=[]
    \_isOrdered=true
  optimization                                                                                 0.039
  optimization                                                                                 0.019
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
JanusGraphStep(vertex,[])@[n2]                                       196         196         149.761    82.06
    \_condition=()
    \_isFitted=false
    \_query=[]
    \_orders=[]
    \_isOrdered=true
  optimization                                                                                 0.048
  optimization                                                                                 0.019
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.023
  optimization                                                                                 0.013
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.022
  optimization                                                                                 0.010
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.027
  optimization                                                                                 0.016
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.031
  optimization                                                                                 0.014
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.022
  optimization                                                                                 0.008
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.033
  optimization                                                                                 0.018
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.032
  optimization                                                                                 0.016
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.028
  optimization                                                                                 0.012
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.031
  optimization                                                                                 0.018
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.037
  optimization                                                                                 0.021
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.030
  optimization                                                                                 0.018
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.032
  optimization                                                                                 0.016
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
  optimization                                                                                 0.043
  optimization                                                                                 0.016
  scan                                                                                         0.000
    \_condition=VERTEX
    \_query=[]
    \_fullscan=true
AndStep([[ChooseStep([ConstantStep(786472), Pro...                                            22.617    12.39
  ChooseStep([ConstantStep(786472), ProfileStep...                   196         196           5.869
    ConstantStep(786472)                                             196         196           0.384
    HasNextStep                                                      196         196           0.573
    ConstantStep(  cypher.null)                                                                0.684
    EndStep                                                                                    0.519
    ConstantStep(786472)                                             196         196           0.696
    EndStep                                                          196         196           0.702
  IsStep(neq(  cypher.null))@[  GENERATED1]                          196         196           0.771
  SelectOneStep(last,n1)                                             196         196           1.825
  ChooseStep([LambdaFilterStep(neq(  cypher.nul...                   196         196           5.911
    LambdaFilterStep(neq(  cypher.null))                             196         196           0.666
    HasNextStep                                                      196         196           0.431
    ConstantStep(  cypher.null)                                                                0.524
    EndStep                                                                                    0.501
    IdStep                                                           196         196           0.942
    EndStep                                                          196         196           0.703
  IsStep(neq(  cypher.null))                                         196         196           0.661
  WherePredicateStep(eq(  GENERATED1))                                                         2.351
SelectStep(last,[n1, n2])                                                                      0.931     0.51
ProjectStep([n1.value < n2.value],[[SelectOneSt...                                             0.050     0.03
                                            >TOTAL                     -           -         182.507        -

Multiple full scan instead indices

TinkerGraph profile result, second line say n^2 nodes compared

TinkerGraphStep(vertex,[])@[n1]                                      102         102           5.644     2.02
TinkerGraphStep(vertex,[])@[n2]                                    10404       10404          11.404     4.08
AndStep([[ChooseStep([ConstantStep(786472), Pro...                                           261.033    93.46
  ChooseStep([ConstantStep(786472), ProfileStep...                 10404       10404          85.047
    ConstantStep(786472)                                           10404       10404           3.697
    HasNextStep                                                    10404       10404           4.678
    ConstantStep(  cypher.null)                                                               11.331
    EndStep                                                                                   11.115
    ConstantStep(786472)                                           10404       10404          12.697
    EndStep                                                        10404       10404          13.638
  IsStep(neq(  cypher.null))@[  GENERATED1]                        10404       10404          10.827
  SelectOneStep(last,n1)                                           10404       10404          15.474
  ChooseStep([LambdaFilterStep(neq(  cypher.nul...                 10404       10404          86.273
    LambdaFilterStep(neq(  cypher.null))                           10404       10404           6.224
    HasNextStep                                                    10404       10404           3.901
    ConstantStep(  cypher.null)                                                               10.639
    EndStep                                                                                   10.413
    IdStep                                                         10404       10404          14.213
    EndStep                                                        10404       10404          13.267
  IsStep(neq(  cypher.null))                                       10404       10404           9.972
  WherePredicateStep(eq(  GENERATED1))                                                        18.005
SelectStep(last,[n1, n2])                                                                      1.076     0.39
ProjectStep([n1.value < n2.value],[[SelectOneSt...                                             0.133     0.05
                                            >TOTAL                     -           -         279.292
dwitry commented 5 years ago

Hello @mad,

as you correctly noted, this is related to lack of JanusGraph optimization strategy and improvement of GroupStepFilters rewriter. Closing as duplicate of #223.