JanusGraph / JanusGraph/janusgraph

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

Open
#4,931 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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: 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.**

https://github.com/JanusGraph/janusgraph/blob/ac0eb2392ddad3d96ab8cde2a5a9a123dbc5d839/janusgraph-core/src/main/java/org/janusgraph/graphdb/query/graph/JointIndexQuery.java#L109-L121

```java
public JointIndexQuery updateLimit(int newLimit) {
List 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".**

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

```java
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:

```groovy
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:

```java
// 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.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with JointIndexQuery.java and SubqueryIterator.java, then trace IndexQuery limit and cache-key handling through the reproduction steps. Verify the fix with two matching indexes: after consuming a limit(10) query, a later limit(1000) query in the same transaction must return more than the cached truncated set when enough matches exist.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.