JanusGraph / JanusGraph/janusgraph

Performance issue for multiple index queries when limit is given

Open
#2,032 6 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.