JanusGraph / JanusGraph/janusgraph
Performance issue for multiple index queries when limit is given
- Dominant language
- Java
- Stars
- 5.8k
- Forks
- 1.2k
- Avg merge
- 13h 53m
- Merged PRs (30d)
- 6
Description
`g.V().has("name", "bob").limit(1)` query is very fast, provided index is built for `name`.
However, `g.V().has("name", "bob").has("age", 20).limit(1)` query is slow, provided `name` and `age` have separate indices. Ideally this should not (often) happen because a small limit is given.
I've looked through several relevant PRs:
https://github.com/JanusGraph/janusgraph/pull/481 starts to stream the result from the index backend. It leverages scroll functionality provided by some external index backends to speed up retrieval (especially the first few results). To achieve so, [this](https://github.com/JanusGraph/janusgraph/pull/481/files#diff-022be93bbc23d60a3d1be7dc205a12c3R1280-R1281) divides queries into two parts: first part fed into [SubqueryIterator](https://github.com/JanusGraph/janusgraph/pull/481/files#diff-d3269581786b8b3f748ed9ec0b653afb) directly; the rest of queries go to `QueryUtil.processIntersectingRetrievals` first where actual results are fetched and collected, and then fed into `SubqueryIterator` as well. The SubqueryIterator then does an intersection of results of two parts and returns the iterator.
The above PR introduces a bug: it feeds `QueryUtil.processIntersectingRetrievals` with the limit. As pointed out by https://github.com/JanusGraph/janusgraph/issues/1125, since the total queries are divided into two parts now, we should not use the given limit to retrieve the rest of the queries and do intersection with the first query. Thus this PR https://github.com/JanusGraph/janusgraph/pull/1330 fixes the bug by passing through Infinity as the limit. However, this means when there are more than one index query, we always need to fetch all results (except the first query whose results are streamed). This means the streaming strategy, in this case, does harm to the overall performance, though it is still very useful when there is only one index query.
Although I haven't tested the behavior thoroughly, from looking at the code I would say the performance problem exists.
Maybe we can rewrite `SubqueryIterator` by moving the intersecting logic into it, instead of splitting total queries into two parts and handling them in two different places. Then we can leverage the streaming feature for all queries, and do intersection properly. The overall goal is that when a limit is given, a query consisting of multiple indexes should be reasonably fast.
Contributor guide
Research direction
Start by reading SubqueryIterator and QueryUtil.processIntersectingRetrievals, then compare the streaming and intersection paths introduced in PRs #481 and #1330. Reproduce the multiple-index query with a small limit and measure whether all secondary results are fetched; done means the multi-index path respects the limit without incorrect intersections or regressions.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- databases, performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100