JanusGraph / JanusGraph/janusgraph

SubqueryIterator uses List.contains for index intersection, giving O(n*m) on an intentionally unbounded list

Open Beginner friendly
#4,932 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
5.8k
Forks
1.2k
Avg merge
13h 53m
Merged PRs (30d)
6

Description

- Version: `master` (`ac0eb23`)
- Storage Backend: any
- Mixed Index Backend: any
- Expected Behavior: intersecting results from multiple indexes should cost O(n) membership checks.
- Current Behavior: membership is tested with `List.contains`, giving O(n·m) on a list that is deliberately unbounded.

### Details

https://github.com/JanusGraph/janusgraph/blob/ac0eb2392ddad3d96ab8cde2a5a9a123dbc5d839/janusgraph-core/src/main/java/org/janusgraph/graphdb/util/SubqueryIterator.java#L73-L84

```java
elementIterator = stream
.filter(e -> otherResults == null || otherResults.contains(e))
...
```

`otherResults` is the `List` returned by `QueryUtil.processIntersectingRetrievals`, which builds an `ArrayList`:

https://github.com/JanusGraph/janusgraph/blob/ac0eb2392ddad3d96ab8cde2a5a9a123dbc5d839/janusgraph-core/src/main/java/org/janusgraph/graphdb/query/QueryUtil.java#L363-L403

So each streamed element from the first index performs a linear scan of the other indexes' intersected results.

This matters more than a typical `contains`-on-a-list nit because the list is intentionally large. `StandardJanusGraphTx` passes `Query.NO_LIMIT` when building the retrievals, with a comment explaining why:

https://github.com/JanusGraph/janusgraph/blob/ac0eb2392ddad3d96ab8cde2a5a9a123dbc5d839/janusgraph-core/src/main/java/org/janusgraph/graphdb/transaction/StandardJanusGraphTx.java#L1478-L1481

```java
// NOTE NO_LIMIT is passed to processIntersectingRetrievals to prevent incomplete intersections, which could lead to missed results
iterator = new SubqueryIterator(indexQuery.getQuery(0), indexSerializer, txHandle, indexCache, indexQuery.getLimit(), getConversionFunction(query.getResultType()),
retrievals.isEmpty() ? null: QueryUtil.processIntersectingRetrievals(retrievals, Query.NO_LIMIT));
```

With `NO_LIMIT`, `processIntersectingRetrievals` computes `subLimit = Integer.MAX_VALUE`, so every non-first index's full matching set is materialised. The linear `contains` then runs against that.

### Suggested Fix

Wrap once outside the lambda:

```java
final Set otherResultSet = otherResults == null ? null : new HashSet<>(otherResults);
...
.filter(e -> otherResultSet == null || otherResultSet.contains(e))
```

`processIntersectingRetrievals` already does exactly this internally when intersecting (`subResultSet = new HashSet<>(subResult)`), so the conversion is consistent with existing behaviour in that path.

Worth noting separately: materialising the complete result set of every non-first index is itself a memory concern for selective-looking multi-index queries, and is the deliberate tradeoff the `NO_LIMIT` comment describes. This issue is only about the avoidable quadratic factor on top of it.

Contributor guide

Open the contributing guide

Research direction

Start in janusgraph-core/src/main/java/org/janusgraph/graphdb/util/SubqueryIterator.java and inspect how the results from QueryUtil.processIntersectingRetrievals are checked during streaming. Review the related retrieval construction in QueryUtil.java and the NO_LIMIT call in StandardJanusGraphTx.java. Done means index intersection uses constant-time membership checks rather than repeatedly scanning the materialized list, with existing behavior preserved.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
databases, performance
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
78/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.