JanusGraph / JanusGraph/janusgraph

Avoid unnecessary and expensive index calls

Open
#3,234 4 comments 1 reaction 0 assignees View on GitHub
area/index kind/performance
Dominant language
Java
Stars
5.8k
Forks
1.2k
Avg merge
13h 53m
Merged PRs (30d)
6

Description

Consider the following scenario:
- We have a graph of vertices labeled `"Agent"`.
- Each `Agent` has properties `AgentId: string` and `Modified: Date`.
- We operate a unique composite index on `AgentId` and a mixed index on `Modified`.

Leveraging the composite index, we can answer the following query efficiently:
```
gremlin> g.V().has("Agent", "AgentId", "my-agent-id").profile()
==>Traversal Metrics
Step Count Traversers Time (ms) % Dur
=============================================================================================================
JanusGraphStep([],[~label.eq(Agent), AgentI... 1 1 1.475 100.00
constructGraphCentricQuery 0.128
GraphCentricQuery 1.204
\_condition=(~label = Agent AND AgentId = my-agent-id)
\_isFitted=true
\_query=multiKSQ[1]
\_index=AgentByAgentId
\_orders=[]
\_isOrdered=true
backend-query 1 1.170
\_query=AgentByAgentId:multiKSQ[1]
>TOTAL - - 1.475 -
```
Since in our case, the `AgentId` is unique, we are guaranteed to receive either 0 or 1 result. Now imagine we want to verify that the retrieved vertex also has the property `Modified`. We can simply do this by appending `.has("Modified")` to the query. Ideally, this step would check the single traverser within microseconds. In reality, however, the impact on performance is immense:
```
gremlin> g.V().has("Agent", "AgentId", "my-agent-id").has("Modified").profile()
==>Traversal Metrics
Step Count Traversers Time (ms) % Dur
=============================================================================================================
JanusGraphStep([],[~label.eq(Agent), AgentI... 1 1 617.892 100.00
constructGraphCentricQuery 0.737
GraphCentricQuery 616.975
\_condition=(~label = Agent AND AgentId = my-agent-id AND Modified <> null)
\_isFitted=true
\_query=[AgentByAgentId:multiKSQ[1], verticesByModified:[(Modified <> null)]:verticesByModified]
\_orders=[]
\_isOrdered=true
AND-query 0.000
\_query=multiKSQ[1]
\_index=AgentByAgentId
backend-query 1 1.265
\_query=AgentByAgentId:multiKSQ[1]
AND-query 0.000
\_query=[(Modified <> null)]:verticesByModified
\_index=verticesByModified
\_index_impl=search
backend-query 23853 615.541
\_query=verticesByModified:[(Modified <> null)]:verticesByModified
>TOTAL - - 617.892 -
```

What is going on here? JanusGraph's `IndexSelectionStrategy` (no matter which exact implementation) is aware of the index on `Modified` and happily accepts it as a valid index to answer the query with. And that's for a reason because it can't know that in our case, the majority of vertices has this property set and therefore, the index lookup is very unrestrictive. On the bright side, JanusGraph attributes a higher priorization to the composite index, which is therefore queried first.
The remainder of the execution is done in [`QueryUtil`](https://github.com/JanusGraph/janusgraph/blob/ac9e1fe8e95326104a141ceeefda52648324ba7c/janusgraph-core/src/main/java/org/janusgraph/graphdb/query/QueryUtil.java#L363). After the first index has been queried, each subsequent index is also queried and the results are intersected with the overall result.

My suggestion to fix the issue I described earlier is to bypass further index queries as soon as the size of the overall result set falls short of a reasonable limit, where it is more performant to check the condition on each traverser manually.

Contributor guide

Open the contributing guide

Research direction

Start in janusgraph-core/src/main/java/org/janusgraph/graphdb/query/QueryUtil.java around the referenced logic, then trace how IndexSelectionStrategy selects and executes additional indexes. Use the provided Gremlin profile scenarios to measure the behavior. Done means avoiding unnecessary follow-up index queries when the existing result set is sufficiently small while preserving correct intersections.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
databases, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.