JanusGraph / JanusGraph/janusgraph
Avoid unnecessary and expensive index calls
- 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
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