Package org.apache.druid.timeline

Class VersionedIntervalTimeline<VersionType,ObjectType extends Overshadowable<ObjectType>>

java.lang.Object

org.apache.druid.timeline.VersionedIntervalTimeline<VersionType,ObjectType>

All Implemented Interfaces:

TimelineLookup<VersionType,ObjectType>

Direct Known Subclasses:

SegmentTimeline

public class VersionedIntervalTimeline<VersionType,ObjectType extends Overshadowable<ObjectType>>
extends Object
implements TimelineLookup<VersionType,ObjectType>

VersionedIntervalTimeline is a data structure that manages objects on a specific timeline. It associates an Interval and a generically-typed version with the object that is being stored. In the event of overlapping timeline entries, timeline intervals may be chunked. The underlying data associated with a timeline entry remains unchanged when chunking occurs. After loading objects via the add(org.joda.time.Interval, VersionType, org.apache.druid.timeline.partition.PartitionChunk<ObjectType>) method, the lookup(Interval) method can be used to get the list of the most recent objects (according to the version) that match the given interval. The intent is that objects represent a certain time period and when you do a lookup(Interval), you are asking for all of the objects that you need to look at in order to get a correct answer about that time period. The findFullyOvershadowed() method returns a list of objects that will never be returned by a call to lookup(org.joda.time.Interval) because they are overshadowed by some other object. This can be used in conjunction with the add(org.joda.time.Interval, VersionType, org.apache.druid.timeline.partition.PartitionChunk<ObjectType>) and remove(org.joda.time.Interval, VersionType, org.apache.druid.timeline.partition.PartitionChunk<ObjectType>) methods to achieve "atomic" updates. First add new items, then check if those items caused anything to be overshadowed, if so, remove the overshadowed elements and you have effectively updated your data set without any user impact.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	VersionedIntervalTimeline.PartitionChunkEntry<VersionType,ObjectType>	Stores a PartitionChunk for a given interval and version.
class	VersionedIntervalTimeline.TimelineEntry

Constructor Summary

Constructors

Constructor	Description
VersionedIntervalTimeline(Comparator<? super VersionType> versionComparator)
VersionedIntervalTimeline(Comparator<? super VersionType> versionComparator, boolean skipObjectsWithNoData)

Method Summary

Modifier and Type	Method	Description
void	add(org.joda.time.Interval interval, VersionType version, PartitionChunk<ObjectType> object)
void	addAll(Iterator<VersionedIntervalTimeline.PartitionChunkEntry<VersionType,ObjectType>> objects)
PartitionChunk<ObjectType>	findChunk(org.joda.time.Interval interval, VersionType version, int partitionNum)	Finds the PartitionChunk for the given time interval, version and chunk number.
Set<TimelineObjectHolder<VersionType,ObjectType>>	findFullyOvershadowed()	This method should be deduplicated with DataSourcesSnapshot.determineOvershadowedSegments(): see https://github.com/apache/druid/issues/8070.
Set<ObjectType>	findNonOvershadowedObjectsInInterval(org.joda.time.Interval interval, Partitions completeness)	Computes a set with all objects falling within the specified interval which are at least partially "visible" in this interval (that is, are not fully overshadowed within this interval).
TimelineObjectHolder<VersionType,ObjectType>	first()
static <VersionType, ObjectType extends Overshadowable<ObjectType>> Iterable<ObjectType>	getAllObjects(List<TimelineObjectHolder<VersionType,ObjectType>> holders)
Map<org.joda.time.Interval,TreeMap<VersionType,VersionedIntervalTimeline<VersionType,ObjectType>.TimelineEntry>>	getAllTimelineEntries()
int	getNumObjects()
boolean	isEmpty()
boolean	isOvershadowed(org.joda.time.Interval interval, VersionType version, ObjectType object)
Collection<ObjectType>	iterateAllObjects()	Returns a lazy collection with all objects (including partially AND fully overshadowed, see findFullyOvershadowed()) in this VersionedIntervalTimeline to be used for iteration or Collection.stream() transformation.
TimelineObjectHolder<VersionType,ObjectType>	last()
List<TimelineObjectHolder<VersionType,ObjectType>>	lookup(org.joda.time.Interval interval)	Does a lookup for the objects representing the given time interval.
List<TimelineObjectHolder<VersionType,ObjectType>>	lookupWithIncompletePartitions(org.joda.time.Interval interval)	Does a lookup for the objects representing the given time interval.
PartitionChunk<ObjectType>	remove(org.joda.time.Interval interval, VersionType version, PartitionChunk<ObjectType> chunk)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

VersionedIntervalTimeline

public VersionedIntervalTimeline(Comparator<? super VersionType> versionComparator)

VersionedIntervalTimeline

public VersionedIntervalTimeline(Comparator<? super VersionType> versionComparator,
 boolean skipObjectsWithNoData)

Method Details

getAllObjects

public static <VersionType,
ObjectType extends Overshadowable<ObjectType>>
Iterable<ObjectType> getAllObjects(List<TimelineObjectHolder<VersionType,ObjectType>> holders)

getAllTimelineEntries

public Map<org.joda.time.Interval,TreeMap<VersionType,VersionedIntervalTimeline<VersionType,ObjectType>.TimelineEntry>> getAllTimelineEntries()

iterateAllObjects

public Collection<ObjectType> iterateAllObjects()

Returns a lazy collection with all objects (including partially AND fully overshadowed, see findFullyOvershadowed()) in this VersionedIntervalTimeline to be used for iteration or Collection.stream() transformation. The order of objects in this collection is unspecified. Note: iteration over the returned collection may not be as trivially cheap as, for example, iteration over an ArrayList. Try (to some reasonable extent) to organize the code so that it iterates the returned collection only once rather than several times.

getNumObjects

public int getNumObjects()

findNonOvershadowedObjectsInInterval

public Set<ObjectType> findNonOvershadowedObjectsInInterval(org.joda.time.Interval interval,
 Partitions completeness)

Computes a set with all objects falling within the specified interval which are at least partially "visible" in this interval (that is, are not fully overshadowed within this interval). Note that this method returns a set of VersionedIntervalTimeline. Duplicate objects in different time chunks will be removed in the result.

add

public void add(org.joda.time.Interval interval,
 VersionType version,
 PartitionChunk<ObjectType> object)

addAll

public void addAll(Iterator<VersionedIntervalTimeline.PartitionChunkEntry<VersionType,ObjectType>> objects)

remove

@Nullable
public PartitionChunk<ObjectType> remove(org.joda.time.Interval interval,
 VersionType version,
 PartitionChunk<ObjectType> chunk)

findChunk

@Nullable
public PartitionChunk<ObjectType> findChunk(org.joda.time.Interval interval,
 VersionType version,
 int partitionNum)

Description copied from interface: TimelineLookup

Finds the PartitionChunk for the given time interval, version and chunk number.

Specified by:

findChunk in interface TimelineLookup<VersionType,ObjectType extends Overshadowable<ObjectType>>

lookup

public List<TimelineObjectHolder<VersionType,ObjectType>> lookup(org.joda.time.Interval interval)

Does a lookup for the objects representing the given time interval. Will *only* return PartitionHolders that are complete.

Specified by:

lookup in interface TimelineLookup<VersionType,ObjectType extends Overshadowable<ObjectType>>

Parameters:

interval - interval to find objects for

Returns:

Holders representing the interval that the objects exist for, PartitionHolders are guaranteed to be complete

lookupWithIncompletePartitions

public List<TimelineObjectHolder<VersionType,ObjectType>> lookupWithIncompletePartitions(org.joda.time.Interval interval)

Description copied from interface: TimelineLookup

Does a lookup for the objects representing the given time interval. Will also return incomplete PartitionHolders.

Specified by:

lookupWithIncompletePartitions in interface TimelineLookup<VersionType,ObjectType extends Overshadowable<ObjectType>>

Parameters:

interval - interval to find objects for

Returns:

Holders representing the interval that the objects exist for, PartitionHolders can be incomplete. Holders returned sorted by the interval.

isEmpty

public boolean isEmpty()

first

public TimelineObjectHolder<VersionType,ObjectType> first()

last

public TimelineObjectHolder<VersionType,ObjectType> last()

findFullyOvershadowed

public Set<TimelineObjectHolder<VersionType,ObjectType>> findFullyOvershadowed()

This method should be deduplicated with DataSourcesSnapshot.determineOvershadowedSegments(): see https://github.com/apache/druid/issues/8070.

isOvershadowed

public boolean isOvershadowed(org.joda.time.Interval interval,
 VersionType version,
 ObjectType object)