Amazon Neptune
User Guide (API Version 2017-11-29)

Gremlin Query Hints repeatMode

The Neptune repeatMode query hint how the Neptune engine evaluates the repeat() step in a Gremlin traversal: breadth first, depth first, or chunked depth first.

The evaluation mode of the repeat() step is important when it is used to find or follow a path, rather than simply repeating a step a limited number of times.

Syntax

The repeatMode query hint is specified by adding a withSideEffect step to the query.

g.withSideEffect('Neptune#repeatMode', 'mode').gremlin-traversal

Note

All Gremlin query hints side effects are prefixed with Neptune#.

Available Modes

  • BFS

    Breadth-First Search.

    Default execution mode for the repeat() step. This gets all sibling nodes before going deeper along the path.

    This version is memory-intensive and frontiers can get very large. There is a higher risk that the query will run out of memory and be cancelled by the Neptune engine. This most closely matches other Gremlin implementations.

  • DFS

    Depth-First Search.

    Follows each path to the maximum depth before moving on to the next solution.

    This uses less memory. It may provide better performance in situations like finding a single path from a starting point out multiple hops.

  • CHUNKED_DFS

    Chunked Depth-First Search.

    A hybrid approach that explores the graph depth-first in chunks of 1,000 nodes, rather than 1 node (DFS) or all nodes (BFS).

    The Neptune engine will get up to 1,000 nodes at each level before following the path deeper.

    This is a balanced approach between speed and memory usage.

    It is also useful if you want to use BFS, but the query is using too much memory.

Example

The following section describes the effect of the repeat mode on a Gremlin traversal.

In Neptune the default mode for the repeat() step is to perform a breadth-first (BFS) execution strategy for all traversals.

In most cases, the TinkerGraph implementation uses the same execution strategy, but in some cases it will alter the execution of a traversal.

For example, the TinkerGraph implementation will modify the following query.

g.V("3").repeat(out()).times(10).limit(1).path()

The repeat() step in this traversal will be "unrolled" into the following traversal, which will result in a depth-first (DFS) strategy.

g.V(<id>).out().out().out().out().out().out()out().out().out().out().limit(1).path()

Important

The Neptune query engine will not do this automatically.

Breadth-first (BFS) is the default execution strategy, and is similar to TinkerGraph in most cases, however there are certain cases where depth-first (DFS) strategies are preferable.

BFS (default)

Breadth-first (BFS) is the default execution strategy for the repeat() operator.

g.V("3").repeat(out()).times(10).limit(1).path()

The Neptune engine will full explore the first nine-hop frontiers fully before finding a solution ten hops out. This effective in many cases, such as shortest-path query.

However, in the case of the preceding example, the traversal would be much faster using the depth-first (DFS) mode for the repeat() operator.

DFS

The following query uses the depth-first (DFS) mode for the repeat() operator.

g.withSideEffect("Neptune#repeatMode", "DFS").V("3").repeat(out()).times(10).limit(1)

This follows each individual solution out to the maximum depth before exploring the next solution.

On this page: