Joint-index subquery cache stores limit-truncated results as complete, causing silently missing results

[batrived]

• Version: master (ac0eb23)
• Storage Backend: any
• Mixed Index Backend: any
• Expected Behavior: the per-transaction subquery cache should only serve a cached result set when that set is complete for the cached key.
• Current Behavior: for a multi-index (joint) query, a result set truncated by the outer limit is cached under the unlimited subquery key, so a later query in the same transaction with a larger limit silently receives too few results.

Details

Three pieces combine.

1. updateLimit does not propagate the limit when there is more than one subquery.

janusgraph/janusgraph-core/src/main/java/org/janusgraph/graphdb/query/graph/JointIndexQuery.java

Lines 109 to 121 in ac0eb23

	public JointIndexQuery updateLimit(int newLimit) {
	List<Subquery> subqueries;
	if(queries.size() == 1){
	subqueries = new ArrayList<>(1);
	subqueries.add(queries.get(0).updateLimit(newLimit));
	} else {
	subqueries = new ArrayList<>(queries);
	}
	JointIndexQuery jointIndexQuery = new JointIndexQuery(subqueries);
	jointIndexQuery.observeWith(this.profiler, false);
	jointIndexQuery.setLimit(newLimit);
	return jointIndexQuery;
	}

public JointIndexQuery updateLimit(int newLimit) {
    List<Subquery> subqueries;
    if(queries.size() == 1){
        subqueries = new ArrayList<>(1);
        subqueries.add(queries.get(0).updateLimit(newLimit));
    } else {
        subqueries = new ArrayList<>(queries);      // limits left untouched
    }
    ...
}

So with two or more subqueries, subquery 0 keeps the Query.NO_LIMIT it was constructed with (IndexSerializer.getQuery builds new IndexQuery(store, condition, orders), which defaults to NO_LIMIT).

2. The cache key includes the limit. IndexQuery.equals/hashCode incorporate getLimit(). Since subquery 0's limit is NO_LIMIT regardless of the outer query's limit, two graph queries with the same conditions but different limits produce the same cache key.

3. SubqueryIterator caches on exhaustion, and cannot distinguish "source exhausted" from "limit reached".

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

Lines 68 to 111 in ac0eb23

	currentIds = new ArrayList<>();
	profiler = QueryProfiler.startProfile(subQuery.getProfiler(), subQuery);
	isTimerRunning = true;
	stream = indexSerializer.query(subQuery, backendTx, tx).peek(r -> currentIds.add(r));
	} catch (final Exception e) {
	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;
	})
	.filter(r -> r != null) // ignore invalid elements
	.limit(limit)
	.iterator();
	}
	@Override
	protected JanusGraphElement computeNext() {
	if (elementIterator.hasNext()) {
	return elementIterator.next();
	}
	close();
	return endOfData();
	}
	/**
	* Close the iterator, stop timer and update profiler.
	* Put results into cache if the underlying elementIterator is exhausted.
	*/
	@Override
	public void close() {
	if (isTimerRunning) {
	assert currentIds != null;
	if (!elementIterator.hasNext()) {
	indexCache.put(subQuery, currentIds);
	}
	profiler.setResultSize(currentIds.size());
	profiler.stopTimer();

stream = indexSerializer.query(subQuery, tx).peek(r -> currentIds.add(r));
...
elementIterator = stream.filter(...).map(...).limit(limit).iterator();
...
public void close() {
    if (isTimerRunning) {
        if (!elementIterator.hasNext()) {
            indexCache.put(subQuery, currentIds);   // caches a truncated list
        }
        ...
    }
}

When .limit(limit) short-circuits the stream, hasNext() is false, so the partial currentIds is cached as if complete.

Result, within one transaction:

g.V().has('a', x).has('b', y).limit(10)     // joint query over two indexes
                                            // caches ~10 ids under the NO_LIMIT key
g.V().has('a', x).has('b', y).limit(1000)   // cache hit, returns at most ~10

Single-index queries are unaffected, because updateLimit propagates there and the limit is part of the key.

Steps to Reproduce

1. Create two indexes such that a query is covered by both (so JointIndexQuery.size() > 1), over data with more than 10 matches.
2. In one transaction, run the query with limit(10), consume it fully.
3. In the same transaction, run the identical query with limit(1000).
4. Observe: the second query returns roughly 10 results rather than up to 1000.

Suggested Fix

Either track whether the underlying stream was exhausted and only cache when it was:

// pseudocode
boolean sourceExhausted = !rawIterator.hasNext();
if (sourceExhausted) indexCache.put(subQuery, currentIds);

or make the cache key reflect the effective truncation limit, or propagate the limit to subquery 0 in updateLimit for the multi-subquery case as well. The first is the least invasive.

Related

While in this file: line 77 filters with otherResults.contains(e) where otherResults is the ArrayList returned by QueryUtil.processIntersectingRetrievals, giving O(n·m) behaviour on the intersection path. Filed separately.