Path-node checks do not prune failed repeat prefixes

The report identifies JanusGraph 1.1.0 with TinkerPop 3.7.3 and includes a Gremlin setup plus q1 and q2 reproductions. Start by running the reproduction and comparing the traversal behavior and timing; then trace the repeat traversal's path-node checks in the relevant JanusGraph code. Done when failed prefixes are pruned while both queries retain the reported matching row and path length.

Path-node checks do not prune failed repeat prefixes

Describe the situation

Hi, JanusGraph developers,

Please consider these two queries:

q1:

g.inject(1)
    .V()
    .hasLabel('GspLow')
    .has('id', P.eq(_gsp_p0))
    .as('_gsp_v0')
    .as('_gsp_tmp0')
    .repeat(
        __.as('_gsp_tmp2')
            .union(
                __.outE('GSP_LINK')
                    .as('_gsp_tmp1')
                    .filter(
                        __.select(Pop.all, '_gsp_tmp1')
                            .unfold()
                            .where(P.eq('_gsp_tmp1'))
                            .count()
                            .is(P.eq(1))
                    )
                    .inV(),
                __.inE('GSP_LINK')
                    .as('_gsp_tmp1')
                    .filter(
                        __.select(Pop.all, '_gsp_tmp1')
                            .unfold()
                            .where(P.eq('_gsp_tmp1'))
                            .count()
                            .is(P.eq(1))
                    )
                    .outV()
                    .where(P.neq('_gsp_tmp2'))
            )
            .as('_gsp_tmp0')
    )
    .emit(
        __.loops()
            .is(P.gte(1))
    )
    .times(3)
    .hasLabel('GspHigh')
    .as('_gsp_v1')
    .project('_nodes', '_length')
    .by(__.select(Pop.all, '_gsp_tmp0'))
    .by(
        __.coalesce(
            __.select(Pop.all, '_gsp_tmp1')
                .count(Scope.local),
            __.constant(0)
        )
    )
    .as('_gsp_v2')
    .select('_gsp_v1')
    .filter(
        __.map(
            __.coalesce(
                __.select('_gsp_v2')
                    .is(P.neq(null))
                    .select('_nodes'),
                __.constant(null)
            )
        )
            .is(P.neq(null))
            .filter(
                __.not(
                    __.unfold()
                        .as('_gsp_v3')
                        .not(
                            __.select('_gsp_v3')
                                .values('keep')
                                .is(P.eq(_gsp_p1))
                        )
                )
            )
    )
    .project('c0', 'c1', 'c2')
    .by(
        __.select('_gsp_v0')
            .coalesce(__.values('uid'), __.constant(null))
    )
    .by(
        __.select('_gsp_v1')
            .coalesce(__.values('uid'), __.constant(null))
    )
    .by(
        __.coalesce(
            __.select('_gsp_v2')
                .is(P.neq(null))
                .select('_length'),
            __.constant(null)
        )
    );

q2:

g.inject(1)
    .V()
    .hasLabel('GspHigh')
    .as('_gsp_v0')
    .as('_gsp_tmp0')
    .repeat(
        __.as('_gsp_tmp2')
            .union(
                __.outE('GSP_LINK')
                    .as('_gsp_tmp1')
                    .filter(
                        __.select(Pop.all, '_gsp_tmp1')
                            .unfold()
                            .where(P.eq('_gsp_tmp1'))
                            .count()
                            .is(P.eq(1))
                    )
                    .inV(),
                __.inE('GSP_LINK')
                    .as('_gsp_tmp1')
                    .filter(
                        __.select(Pop.all, '_gsp_tmp1')
                            .unfold()
                            .where(P.eq('_gsp_tmp1'))
                            .count()
                            .is(P.eq(1))
                    )
                    .outV()
                    .where(P.neq('_gsp_tmp2'))
            )
            .as('_gsp_tmp0')
    )
    .emit(
        __.loops()
            .is(P.gte(1))
    )
    .times(3)
    .hasLabel('GspLow')
    .has('id', P.eq(_gsp_p0))
    .as('_gsp_v1')
    .project('_nodes', '_length')
    .by(__.select(Pop.all, '_gsp_tmp0'))
    .by(
        __.coalesce(
            __.select(Pop.all, '_gsp_tmp1')
                .count(Scope.local),
            __.constant(0)
        )
    )
    .as('_gsp_v2')
    .select('_gsp_v1')
    .filter(
        __.map(
            __.coalesce(
                __.select('_gsp_v2')
                    .is(P.neq(null))
                    .select('_nodes'),
                __.constant(null)
            )
        )
            .is(P.neq(null))
            .filter(
                __.not(
                    __.unfold()
                        .as('_gsp_v3')
                        .not(
                            __.select('_gsp_v3')
                                .values('keep')
                                .is(P.eq(_gsp_p1))
                        )
                )
            )
    )
    .project('c0', 'c1', 'c2')
    .by(
        __.select('_gsp_v1')
            .coalesce(__.values('uid'), __.constant(null))
    )
    .by(
        __.select('_gsp_v0')
            .coalesce(__.values('uid'), __.constant(null))
    )
    .by(
        __.coalesce(
            __.select('_gsp_v2')
                .is(P.neq(null))
                .select('_length'),
            __.constant(null)
        )
    );

I traverse the same undirected trails from opposite endpoints and check that all path nodes have keep=true. Both queries return the same one row, including its path length. On the graph below, q2 takes about 13.91 times as long as q1 and extends paths after they have already reached a node with keep=false.

Which JanusGraph versions are affected?

I reproduced this on JanusGraph 1.1.0 with Apache TinkerPop 3.7.3, using Gremlin-Groovy over HTTP, BerkeleyJE storage, and a 4 GiB JVM heap in an ARM64 Docker container on macOS. The client and server evaluation limits were 30 seconds.

How to reproduce

Use an empty dedicated graph and fresh schema. For HTTP requests, use language=gremlin-groovy and aliases {"g":"g","_gsp_graph":"graph"}. Run this setup, then run q1 and q2 above with bindings {"_gsp_p0":1,"_gsp_p1":true}:

def _gsp_graph = g.getGraph();
{ ->
    _gsp_graph.tx().rollback();
    if (g.V().limit(1).hasNext() || g.E().limit(1).hasNext())
        throw new IllegalStateException('Use an empty graph');
    _gsp_graph.tx().rollback();
    def m = _gsp_graph.openManagement();
    try {
        if (['_gsp_identity', 'id', 'keep', 'uid'].any { m.getPropertyKey(it) != null })
            throw new IllegalStateException('Use fresh experiment schema')
    } finally {
        m.rollback()
    };
    true
}.call();
{ ->
    _gsp_graph.tx().rollback();
    def m = _gsp_graph.openManagement();
    if (m.getPropertyKey("_gsp_identity") == null)
        m.makePropertyKey("_gsp_identity")
            .dataType(String.class)
            .cardinality(org.janusgraph.core.Cardinality.SINGLE)
            .make();
    if (m.getPropertyKey("uid") == null)
        m.makePropertyKey("uid")
            .dataType(Long.class)
            .cardinality(org.janusgraph.core.Cardinality.SINGLE)
            .make();
    if (m.getPropertyKey("id") == null)
        m.makePropertyKey("id")
            .dataType(Long.class)
            .cardinality(org.janusgraph.core.Cardinality.SINGLE)
            .make();
    if (m.getPropertyKey("keep") == null)
        m.makePropertyKey("keep")
            .dataType(Boolean.class)
            .cardinality(org.janusgraph.core.Cardinality.SINGLE)
            .make();
    if (m.getVertexLabel("GspLow") == null)
        m.makeVertexLabel("GspLow").make();
    if (m.getVertexLabel("GspMiddle") == null)
        m.makeVertexLabel("GspMiddle").make();
    if (m.getVertexLabel("GspHigh") == null)
        m.makeVertexLabel("GspHigh").make();
    if (m.getVertexLabel("GspBad") == null)
        m.makeVertexLabel("GspBad").make();
    if (m.getEdgeLabel("GSP_LINK") == null)
        m.makeEdgeLabel("GSP_LINK")
            .multiplicity(org.janusgraph.core.Multiplicity.MULTI)
            .make();
    if (m.getGraphIndex("gsp_internal_identity") == null)
        m.buildIndex(
            "gsp_internal_identity",
            org.apache.tinkerpop.gremlin.structure.Vertex.class
        )
            .addKey(m.getPropertyKey("_gsp_identity"))
            .unique()
            .buildCompositeIndex();
    if (m.getGraphIndex("gsp_cost_lookup_GspLow_id") == null)
        m.buildIndex(
            "gsp_cost_lookup_GspLow_id",
            org.apache.tinkerpop.gremlin.structure.Vertex.class
        )
            .addKey(m.getPropertyKey("id"))
            .indexOnly(m.getVertexLabel("GspLow"))
            .buildCompositeIndex();
    m.commit();
    true
}.call();
if (!({ ->
    org.janusgraph.graphdb.database.management.ManagementSystem
        .awaitGraphIndexStatus(_gsp_graph, "gsp_internal_identity")
        .status(
            org.janusgraph.core.schema.SchemaStatus.REGISTERED,
            org.janusgraph.core.schema.SchemaStatus.ENABLED
        )
        .timeout(30, java.time.temporal.ChronoUnit.SECONDS)
        .call()
        .getSucceeded()
}.call())) throw new IllegalStateException('index registration timed out');
{ ->
    def m = _gsp_graph.openManagement();
    def i = m.getGraphIndex("gsp_internal_identity");
    if (i.getFieldKeys().any {
        i.getIndexStatus(it) != org.janusgraph.core.schema.SchemaStatus.ENABLED
    })
        m.updateIndex(i, org.janusgraph.core.schema.SchemaAction.ENABLE_INDEX)
            .get();
    m.commit();
    true
}.call();
if (!({ ->
    org.janusgraph.graphdb.database.management.ManagementSystem
        .awaitGraphIndexStatus(_gsp_graph, "gsp_cost_lookup_GspLow_id")
        .status(
            org.janusgraph.core.schema.SchemaStatus.REGISTERED,
            org.janusgraph.core.schema.SchemaStatus.ENABLED
        )
        .timeout(30, java.time.temporal.ChronoUnit.SECONDS)
        .call()
        .getSucceeded()
}.call())) throw new IllegalStateException('index registration timed out');
{ ->
    def m = _gsp_graph.openManagement();
    def i = m.getGraphIndex("gsp_cost_lookup_GspLow_id");
    if (i.getFieldKeys().any {
        i.getIndexStatus(it) != org.janusgraph.core.schema.SchemaStatus.ENABLED
    })
        m.updateIndex(i, org.janusgraph.core.schema.SchemaAction.ENABLE_INDEX)
            .get();
    m.commit();
    true
}.call();
def nodeGroups = [
    ['count': 1L, 'labels': ['GspLow'], 'properties': ['uid': 1L, 'id': 1L, 'keep': true]],
    ['count': 1L, 'labels': ['GspMiddle'], 'properties': ['uid': 2L, 'keep': true]],
    ['count': 1L, 'labels': ['GspHigh'], 'properties': ['uid': 3L, 'keep': true]],
    ['count': 1L, 'labels': ['GspBad'], 'properties': ['uid': 0L, 'keep': false]],
    [
        'count': 200L,
        'labels': ['GspMiddle'],
        'properties': ['uid': ['base': 895442L, 'step': 2L], 'keep': true]
    ],
    [
        'count': 200L,
        'labels': ['GspHigh'],
        'properties': ['uid': ['base': 895443L, 'step': 2L], 'keep': true]
    ]
];
def edgeGroups = [
    [
        'count': 1L,
        'source': 1L,
        'target': 2L,
        'source_label': 'GspLow',
        'target_label': 'GspMiddle',
        'type': 'GSP_LINK',
        'properties': [:]
    ],
    [
        'count': 1L,
        'source': 2L,
        'target': 3L,
        'source_label': 'GspMiddle',
        'target_label': 'GspHigh',
        'type': 'GSP_LINK',
        'properties': [:]
    ],
    [
        'count': 1L,
        'source': 1L,
        'target': 0L,
        'source_label': 'GspLow',
        'target_label': 'GspBad',
        'type': 'GSP_LINK',
        'properties': [:]
    ],
    [
        'count': 200L,
        'source': 0L,
        'target': ['base': 895442L, 'step': 2L],
        'source_label': 'GspBad',
        'target_label': 'GspMiddle',
        'type': 'GSP_LINK',
        'properties': [:]
    ],
    [
        'count': 200L,
        'source': ['base': 895442L, 'step': 2L],
        'target': ['base': 895443L, 'step': 2L],
        'source_label': 'GspMiddle',
        'target_label': 'GspHigh',
        'type': 'GSP_LINK',
        'properties': [:]
    ]
];
def at = { value, i -> value instanceof Map ? value.base + value.step * i : value };
def nodes = [];
nodeGroups.each { group ->
    for (def i = 0L; i < group.count; i++) {
        def props = group.properties.collectEntries { k, v -> [(k): at(v, i)] };
        nodes.add([uid: props.uid, labels: group.labels, properties: props]);
    }
};
nodes.collate(250).each { gsp_rows ->
    gsp_rows.each { r ->
        def v = g.addV(r.labels[0])
            .property('_gsp_identity', r.labels[0] + ':' + r.uid)
            .next();
        r.properties.each { k, x ->
            if (x != null) v.property(k, x instanceof Number ? x.longValue() : x)
        }
    };
    gsp_rows.size();
    _gsp_graph.tx().commit()
};
def edges = [];
def ordinal = 0L;
edgeGroups.each { group ->
    for (def i = 0L; i < group.count; i++) {
        edges.add([
            source: at(group.source, i),
            target: at(group.target, i),
            source_label: group.source_label,
            target_label: group.target_label,
            type: group.type,
            ordinal: ordinal++,
            properties: group.properties.collectEntries { k, v -> [(k): at(v, i)] }
        ]);
    }
};
edges.collate(250).each { gsp_rows ->
    gsp_rows.each { r ->
        def a = g.V()
            .has('_gsp_identity', r.source_label + ':' + r.source)
            .next();
        def b = g.V()
            .has('_gsp_identity', r.target_label + ':' + r.target)
            .next();
        def e = a.addEdge(r.type, b);
        r.properties.each { k, x ->
            if (x != null) e.property(k, x instanceof Number ? x.longValue() : x)
        }
    };
    gsp_rows.size();
    _gsp_graph.tx().commit()
};
[[vertices: g.V().count().next(), edges: g.E().count().next()]]

The GspLow vertex with uid=1 has a valid two-edge trail through GspMiddle(uid=2) to GspHigh(uid=3). It also connects to GspBad(uid=0, keep=false). Beyond that vertex are 200 separate Middle-to-High branches. All other vertices have keep=true. The edge-identity check preserves TRAIL semantics, including distinct parallel edges, and allows vertex revisits.

For q1, I get one row:

[
  {
    "c0": 1,
    "c1": 3,
    "c2": 2
  }
]

Median runtime: 13.570770 ms.

For q2, I get one row:

[
  {
    "c0": 1,
    "c1": 3,
    "c2": 2
  }
]

Median runtime: 182.579020 ms.

Native PROFILE excerpt, with step bodies shortened and fields rearranged; elementCount counts the elements emitted by each step:

q1:
  JanusGraphStep([],[~label.eq(GspLow), id.eq(1)])@[_gsp_v0, _gsp_tmp0]  elementCount=1
  RepeatStep(...)  elementCount=403
  JanusGraphVertexStep(OUT,[GSP_LINK],edge)@[_gsp_tmp1]  elementCount=403
  JanusGraphVertexStep(IN,[GSP_LINK],edge)@[_gsp_tmp1]  elementCount=203
  JanusGraphHasStep([~label.eq(GspHigh)])@[_gsp_v1]  elementCount=201
  JanusGraphPropertiesStep([keep],value)  elementCount=403
  ProjectStep([c0, c1, c2],...)  elementCount=1
q2:
  JanusGraphStep([],[~label.eq(GspHigh)])@[_gsp_v0, _gsp_tmp0]  elementCount=201
  RepeatStep(...)  elementCount=40403
  JanusGraphVertexStep(OUT,[GSP_LINK],edge)@[_gsp_tmp1]  elementCount=40203
  JanusGraphVertexStep(IN,[GSP_LINK],edge)@[_gsp_tmp1]  elementCount=602
  JanusGraphHasStep([~label.eq(GspLow), id.eq(1)])@[_gsp_v1]  elementCount=201
  JanusGraphPropertiesStep([keep],value)  elementCount=603
  ProjectStep([c0, c1, c2],...)  elementCount=1

Both queries apply the all-node check after RepeatStep; the check itself stops at the first false node. In q2, the 200 branch High vertices each reach the shared Bad vertex and then produce 200 further trails, including trails into the other Middle branches. Those 40,000 extensions cannot contribute a passing result because their prefix already contains keep=false. q1 starts at the single Low vertex and avoids this quadratic combination of branch starts and continuations, although it also checks completed paths. This is a request to recognize the monotone path predicate across repeat, path-node projection and the later filter; the measured q2/q1 ratio is not a measured speedup from a pruning patch.

Expected performance

Please stop extending a path when its prefix contains a node with keep=false, while preserving TRAIL semantics, so q2 can skip the rejected combinations that q1 avoids through its starting endpoint.