apache / apache/druid

VersionedIntervalTimeline.lookup() and findEntry() can take O(log(N)) instead of O(N) time

Open
#8,069 1 comment 0 reactions 0 assignees View on GitHub
Contributions Welcome Performance
Dominant language
Java
Stars
14.1k
Forks
3.8k
Avg merge
2d 58m
Merged PRs (30d)
233

Description

Instead of this code:
https://github.com/apache/incubator-druid/blob/abf9843e2a217656c4fa4bc79ffd771b13680281/core/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java#L584-L588

We can create some synthetic intervals (either zero-length intervals `(start, start)` and `(end, end)`, or `(-INF, start)`, or `(start, INF)` to navigate to the only relevant place in the `NavigableMap`.

Secondary timeline `NavigableMap`s sorted by interval's end-then-start may be needed. The extra memory footprint may be insignificant compared to the cost of `TimelineEntry`, `Interval`, `PartitionHolder`, and `PartitionChunk` objects (the secondary `NavigableMap`s can point to the same `TimelineEntry` objects).

The same applies to `findEntry()`.

FYI @jihoonson

Contributor guide

Open the contributing guide

Research direction

Start in core/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java around lines 584-588, then trace lookup() and findEntry(). Compare the current NavigableMap traversal with the proposed interval-navigation approach and assess its memory implications. Done means both methods achieve the requested logarithmic lookup behavior without changing their results.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
backend, performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.