[GitHub] [incubator-druid] leventov opened a new issue #8069: VersionedIntervalTimeline.lookup() and findEntry() can take O(log(N)) instead of O(N) time

[GitBox <gi...@apache.org>]

leventov opened a new issue #8069: VersionedIntervalTimeline.lookup() and findEntry() can take O(log(N)) instead of O(N) time
URL: https://github.com/apache/incubator-druid/issues/8069
 
 
   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 

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services

---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org