How can I optimize a query in Neptune that needs to filter a few edges in a node with thousands

user_5760547 0
Viewed 195

I'm having performace issues with a query in Gremlin using AWS Neptune graph database.

This is the scenario:

1

Basically, there are 5000+ users connected by the same IP node.

I want all users that have a connection with the ip node at a date that matches one of the dates of the connections from user-1 with a window of 1 day. For example, starting from user-1 I want to find only user-2 and user-4.

I already have a query that works, thanks to the responses in this question I posted a while back, and looks something like this:

g.V('user-1')
   .outE().as('ip_edges')
   .inV().inE('uses_ip').as('related')
   .where(P.lte('related')).by(math('ip_edges - 86400000').by('date_millis')).by('date_millis')
   .where(P.gte('related')).by(math('ip_edges + 86400000').by('date_millis')).by('date_millis')
   .outV()

But I'm experiencing performance issues in this scenario because the query is traversing through all of the 5000+ edges of the ip node.

I understand that Neptune has indexes that should allow me to filter edges by the property date_millis without having to go through all 5000+ edges. But I'm failing to write a query that actually uses those indexes.

This is how the profiling of the query looks like (the node ids are a bit different because i simplified it for the example here):

*******************************************************
                Neptune Gremlin Profile
*******************************************************

Query String
==================
g.V('user-lt1001').outE().as('ip_edges').inV().inE('uses_ip').as('related').where(P.lte('related')).by(math('ip_edges - 86400000').by('at_millis')).by('at_millis').where(P.gte('related')).by(math('ip_edges + 86400000').by('at_millis')).by('at_millis').outV()

Original Traversal
==================
[GraphStep(vertex,
    [user-lt1001
    ]), VertexStep(OUT,edge)@[ip_edges
    ], EdgeVertexStep(IN), VertexStep(IN,
    [uses_ip
    ],edge)@[related
    ], WherePredicateStep(lte(related),
    [
        [MathStep(ip_edges - 86400000,
            [value(at_millis)
            ])
        ], value(at_millis)
    ]), WherePredicateStep(gte(related),
    [
        [MathStep(ip_edges + 86400000,
            [value(at_millis)
            ])
        ], value(at_millis)
    ]), EdgeVertexStep(OUT)
]

Optimized Traversal
===================
Neptune steps: [
    NeptuneGraphQueryStep(Edge) {
        JoinGroupNode {
            PatternNode[(?1=<user-lt1001>, ?5, ?3, ?6) . project ?1,?6,?3 . IsEdgeIdFilter(?6) .
            ],
            {estimatedCardinality=3, expectedTotalOutput=2, indexTime=0, joinTime=0, numSearches=1, actualTotalOutput=2
            }
            PatternNode[(?8, ?10=<uses_ip>, ?3, ?11) . project ?3,?11 . IsEdgeIdFilter(?11) .
            ],
            {estimatedCardinality=10022, indexTime=0, joinTime=13, numSearches=1
            }
        }, annotations={path=[Vertex(?1):GraphStep, Edge(?6):VertexStep@[ip_edges
                ], Vertex(?3):EdgeVertexStep, Edge(?11):VertexStep@[related
                ]
            ], joinStats=true, optimizationTime=1, maxVarId=12, executionTime=633
        }
    },
    NeptuneTraverserConverterStep
]
+ not converted into Neptune steps: [WherePredicateStep(lte(related),
    [
        [MathStep(ip_edges - 86400000,
            [value(at_millis)
            ]), ProfileStep
        ], value(at_millis)
    ]), NoOpBarrierStep(2500), WherePredicateStep(gte(related),
    [
        [MathStep(ip_edges + 86400000,
            [value(at_millis)
            ]), ProfileStep
        ], value(at_millis)
    ]), NoOpBarrierStep(2500), EdgeVertexStep(OUT)
]

WARNING: >> WherePredicateStep(lte(related),
[
    [MathStep(ip_edges - 86400000,
        [value(at_millis)
        ]), ProfileStep
    ], value(at_millis)
]) << (or one of its children) is not supported natively yet

Physical Pipeline
=================
NeptuneGraphQueryStep
    |-- StartOp
    |-- JoinGroupOp
        |-- SpoolerOp(1000)
        |-- DynamicJoinOp(PatternNode[(?1=<user-lt1001>, ?5, ?3, ?6) . project ?1,?6,?3 . IsEdgeIdFilter(?6) .
],
{estimatedCardinality=3, expectedTotalOutput=2
})
        |-- SpoolerOp(1000)
        |-- DynamicJoinOp(PatternNode[(?8, ?10=<uses_ip>, ?3, ?11) . project ?3,?11 . IsEdgeIdFilter(?11) .
],
{estimatedCardinality=10022
})

Runtime (ms)
============
Query Execution: 633.282

Traversal Metrics
=================
Step                                                               Count  Traversers       Time (ms)    % Dur
-------------------------------------------------------------------------------------------------------------
NeptuneGraphQueryStep(Edge)                                         9358        9358          20.431     3.23
NeptuneTraverserConverterStep                                       9358        9358          23.427     3.70
WherePredicateStep(lte(related),
[
    [MathStep(ip_e...                     7           7         588.350    92.96
  MathStep(ip_edges - 86400000,
        [value(at_millis)
        ])                  9358        9358         293.918
NoOpBarrierStep(2500)                                                  7           7           0.036     0.01
WherePredicateStep(gte(related),
        [
            [MathStep(ip_e...                     5           5           0.542     0.09
  MathStep(ip_edges + 86400000,
                [value(at_millis)
                ])                     7           7           0.285
NoOpBarrierStep(2500)                                                  5           5           0.023     0.00
EdgeVertexStep(OUT)                                                    5           5           0.118     0.02
                                            >TOTAL                     -           -         632.929        -

Predicates
==========
# of predicates: 38

Results
=======
Count: 5
Output: [v[user-lt1001
                    ], v[user-lt1004
                    ], v[user-lt1001
                    ], v[user-lt1003
                    ], v[user-lt1002
                    ]
                ]


Index Operations
================
Query execution:
    # of statement index ops: 18737
    # of unique statement index ops: 4686
    Duplication ratio: 4.00
    # of terms materialized: 0

To compare execution times, while this query takes 600+ ms, the same query without those 5000 extra edges takes 8ms.

EDIT 1

Here's a query that improves the execution times, but stills traverses all the edges.

g.V('user-1')
   .outE().as('ip_edges')
   .values('at_millis').math('_ + 86400001').as('plus_one_day')
   .select('ip_edges').values('at_millis').math('_ - 86400001').as_('minus_one_day')
   .select('ip_edges')
   .inV().inE('uses_ip').as('result')
   .values('at_millis')
   .where(P.between('minus_one_day', 'plus_one_day'))
   .select('result')
   .outV()

And this is the profiling of this query:

*******************************************************
                Neptune Gremlin Profile
*******************************************************

Query String
==================
g.V('user-lt1001').outE().as('ip_edges').values('at_millis').math('_ + 86400001').as('plus_one_day').select('ip_edges').values('at_millis').math('_ - 86400001').as_('minus_one_day').select('ip_edges').inV().inE('uses_ip').as('result').values('at_millis').where(P.between('minus_one_day', 'plus_one_day')).select('result').outV()

Original Traversal
==================
[GraphStep(vertex,
    [user-lt1001
    ]), VertexStep(OUT,edge)@[ip_edges
    ], PropertiesStep([at_millis
    ],value), MathStep(_ + 86400001)@[plus_one_day
    ], SelectOneStep(last,ip_edges), PropertiesStep([at_millis
    ],value), MathStep(_ - 86400001)@[minus_one_day
    ], SelectOneStep(last,ip_edges), EdgeVertexStep(IN), VertexStep(IN,
    [uses_ip
    ],edge)@[result
    ], PropertiesStep([at_millis
    ],value), WherePredicateStep(and(gte(minus_one_day), lt(plus_one_day))), SelectOneStep(last,result), EdgeVertexStep(OUT)
]

Optimized Traversal
===================
Neptune steps: [
    NeptuneGraphQueryStep(PropertyValue) {
        JoinGroupNode {
            PatternNode[(?1=<user-lt1001>, ?5, ?3, ?6) . project ?1,?6 . IsEdgeIdFilter(?6) .
            ],
            {estimatedCardinality=3, expectedTotalOutput=2, indexTime=0, joinTime=0, numSearches=1, actualTotalOutput=2
            }
            PatternNode[(?6, ?7=<at_millis>, ?8, <~>) . project ?6,?8 .
            ],
            {estimatedCardinality=8892, indexTime=0, joinTime=0, numSearches=1
            }
        }, annotations={path=[Vertex(?1):GraphStep, Edge(?6):VertexStep@[ip_edges
                ], PropertyValue(?8):PropertiesStep
            ], joinStats=true, optimizationTime=1, maxVarId=9, executionTime=271
        }
    },
    NeptuneTraverserConverterStep
]
+ not converted into Neptune steps: [MathStep(_ + 86400001)@[plus_one_day
    ], NoOpBarrierStep(2500), SelectOneStep(last,ip_edges), NoOpBarrierStep(2500), PropertiesStep([at_millis
    ],value), MathStep(_ - 86400001)@[minus_one_day
    ], NoOpBarrierStep(2500), SelectOneStep(last,ip_edges), NoOpBarrierStep(2500), EdgeVertexStep(IN), VertexStep(IN,
    [uses_ip
    ],edge)@[result
    ], PropertiesStep([at_millis
    ],value), WherePredicateStep(and(gte(minus_one_day), lt(plus_one_day))), NoOpBarrierStep(2500), SelectOneStep(last,result), NoOpBarrierStep(2500), EdgeVertexStep(OUT)
]

WARNING: >> MathStep(_ + 86400001)@[plus_one_day
] << (or one of its children) is not supported natively yet

Physical Pipeline
=================
NeptuneGraphQueryStep
    |-- StartOp
    |-- JoinGroupOp
        |-- SpoolerOp(1000)
        |-- DynamicJoinOp(PatternNode[(?1=<user-lt1001>, ?5, ?3, ?6) . project ?1,?6 . IsEdgeIdFilter(?6) .
],
{estimatedCardinality=3, expectedTotalOutput=2
})
        |-- SpoolerOp(1000)
        |-- DynamicJoinOp(PatternNode[(?6, ?7=<at_millis>, ?8, <~>) . project ?6,?8 .
],
{estimatedCardinality=8892
})

Runtime (ms)
============
Query Execution: 271.410

Traversal Metrics
=================
Step                                                               Count  Traversers       Time (ms)    % Dur
-------------------------------------------------------------------------------------------------------------
NeptuneGraphQueryStep(PropertyValue)                                   2           2           0.338     0.12
NeptuneTraverserConverterStep                                          2           2           0.058     0.02
MathStep(_ + 86400001)@[plus_one_day
]                                  2           2           0.085     0.03
NoOpBarrierStep(2500)                                                  2           2           0.027     0.01
SelectOneStep(last,ip_edges)                                           2           2           0.015     0.01
NoOpBarrierStep(2500)                                                  2           2           0.012     0.00
PropertiesStep([at_millis
],value)                                      2           2           0.215     0.08
MathStep(_ - 86400001)@[minus_one_day
]                                 2           2           0.064     0.02
NoOpBarrierStep(2500)                                                  2           2           0.051     0.02
SelectOneStep(last,ip_edges)                                           2           2           0.014     0.01
NoOpBarrierStep(2500)                                                  2           2           0.012     0.00
EdgeVertexStep(IN)                                                     2           2           0.097     0.04
VertexStep(IN,
[uses_ip
],edge)@[result
]                              9358        9358          28.307    10.45
PropertiesStep([at_millis
],value)                                   9358        9358         233.549    86.18
WherePredicateStep(and(gte(minus_one_day), lt(p...                     5           5           8.080     2.98
NoOpBarrierStep(2500)                                                  5           5           0.042     0.02
SelectOneStep(last,result)                                             5           5           0.013     0.01
NoOpBarrierStep(2500)                                                  5           5           0.013     0.00
EdgeVertexStep(OUT)                                                    5           5           0.012     0.00
                                            >TOTAL                     -           -         271.012        -

Predicates
==========
# of predicates: 38

Results
=======
Count: 5
Output: [v[user-lt1001
    ], v[user-lt1003
    ], v[user-lt1002
    ], v[user-lt1004
    ], v[user-lt1001
    ]
]


Index Operations
================
Query execution:
    # of statement index ops: 9366
    # of unique statement index ops: 4686
    Duplication ratio: 2.00
    # of terms materialized: 0

Any help will be really appreciated! Thanks!

amazon-neptune gremlin
1 Answers

Looking at the profile, there is quite a bit more going on than just looking things up in an index. First of all there are a lot more than 5K edges being found. The number of traversers indicates the actual number is 9,358 (so almost 10K). For each of those edges the time property has to be found and the math step applied. This is done twice, once for each where, but note that most of the time is spent on the first where as that filters out most of the edges. The second where has a lot less work to do. If this IP address node has the potential to grow and grow in degree (number of edges connected) you likely will want to change your data model to add some intermediate nodes that break the times up into chunks or ranges something similar and then precompute a value and use that to home in on the data you need. Given the amount of work the query is having to do the time does not seem that unreasonable.

user_54420340
Related