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

[batrived]

• 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

janusgraph/janusgraph-core/src/main/java/org/janusgraph/graphdb/util/SubqueryIterator.java

Lines 73 to 84 in ac0eb23

	throw new JanusGraphException("Could not call index", e);
	}
	}
	elementIterator = stream
	.filter(e -> otherResults == null || otherResults.contains(e))
	.map(e -> {
	JanusGraphElement r = function.apply(e);
	if (r == null) {
	log.warn("Subquery returned invalid element id: {}", e);
	}
	return r;
	})

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

otherResults is the List<Object> returned by QueryUtil.processIntersectingRetrievals, which builds an ArrayList:

janusgraph/janusgraph-core/src/main/java/org/janusgraph/graphdb/query/QueryUtil.java

Lines 363 to 403 in ac0eb23

	public static <R> List<R> processIntersectingRetrievals(List<IndexCall<R>> retrievals, final int limit) {
	Preconditions.checkArgument(!retrievals.isEmpty());
	Preconditions.checkArgument(limit >= 0, "Invalid limit: %s", limit);
	List<R> results;
	/*
	* Iterate over the clauses in the and collection
	* query.getCondition().getChildren(), taking the intersection
	* of current results with cumulative results on each iteration.
	*/
	//TODO: smarter limit estimation
	final int multiplier = Math.min(16, (int) Math.pow(2, retrievals.size() - 1));
	int subLimit = Integer.MAX_VALUE;
	if (Integer.MAX_VALUE / multiplier >= limit) subLimit = limit * multiplier;
	boolean exhaustedResults;
	do {
	exhaustedResults = true;
	results = null;
	for (final IndexCall<R> call : retrievals) {
	Collection<R> subResult;
	try {
	subResult = call.call(subLimit);
	} catch (final Exception e) {
	throw new JanusGraphException("Could not process individual retrieval call ", e);
	}
	if (subResult.size() >= subLimit) exhaustedResults = false;
	if (results == null) {
	results = new ArrayList<>(subResult);
	} else {
	final Set<R> subResultSet;
	if(subResult instanceof Set){
	subResultSet = (Set<R>) subResult;
	} else {
	subResultSet = new HashSet<>(subResult);
	}
	results.removeIf(o -> !subResultSet.contains(o));
	}
	}
	subLimit = (int) Math.min(Integer.MAX_VALUE - 1, Math.max(Math.pow(subLimit, 1.5),(subLimit+1)*2));
	} while (results != null && results.size() < limit && !exhaustedResults);
	return results;

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:

janusgraph/janusgraph-core/src/main/java/org/janusgraph/graphdb/transaction/StandardJanusGraphTx.java

Lines 1478 to 1481 in ac0eb23

	public final QueryExecutor<GraphCentricQuery, JanusGraphElement, JointIndexQuery> elementProcessor;
	public final QueryExecutor<GraphCentricQuery, JanusGraphElement, JointIndexQuery> elementProcessorImpl = new QueryExecutor<GraphCentricQuery, JanusGraphElement, JointIndexQuery>() {

// 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:

final Set<Object> 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.