JanusGraph / JanusGraph/janusgraph
SubqueryIterator uses List.contains for index intersection, giving O(n*m) on an intentionally unbounded list
- 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
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