Apache Pinot

So I’m a bit confused in the code here — it appears that when nothing is referencing a `SegmentDataManager` anymore, it gets destroyed. But it still remains in the `_segmentDataManagerMap`. Which means potentially people can acquire destroyed segments?

Seems like they _must_ be getting reloaded every time? Or something?

iirc it gets off the map when he segment gets unloaded, and the last call to release the segment destroys the segment.

Look in `BaseTableDataManager`. The code has moved around a bit since I wrote it, but the logic is still the same.

I have been. The issue is that it destroys the segment, but it still exists in the map

Now maybe that’s fine because all the metadata on that segment is already defined at this point?

But it seems for sure the only way for it to get formally removed so that it cannot be retrieved via `acquireSegment` is `removeSegment`. Therefore `acquireSegment` can potentially return segments that have been “released”. Is this an issue?

The call `removeSegment` removes it from the map.

Yes, but that call is not used on `releaseSegment`

No that is not an issue, The last call to release the segment will destroy it. Ths i s because there can be queries in the pipeline

Because it sounds like a segment can be destroyed but not removed.

removed == Segment has been dropped from the table.
destroyed == data of the segment is released from the server's memory

acquire == get a segment for querying
release == release the segment you have acquired (locked)

Okay. So what happens, then, when someone acquires a segment manager that has been released?

The underlying `ImmutableSegment` has been destroyed.

So, the following sequence can happen:
T1 acquires a segment
T2 (helix) removes the segment while query is in progress
T1 releases the segment

In this case, T1 wil end up destroying the data (unmapping the segment)

Another possible sequence could be that no thread is querying the segment, and helix calls remove(). In that case, the segment is destroyed directly

What about:

```Query 1 acquires a segment
Query 1 releases the segment
This is the last reference, so segment is destroyed
Query 2 acquires the same segment (no remove call happened)```

This usually cannot happen, unless the segment has been replaced by another one in the same name.

In an offline table, presumably you have segments laying around that multiple queries use, past and future?

Unless there is something that is calling `removeSegment` every time a query finishes? Or something is calling `addSegment` every time a new query starts?

yes, multiple queries can use the same segment

You may want to look at the test `BaseTableDataManagerTest` has a demonstration

We can represent this as a state machine, right.

Segment goes from

ADDED --&gt; IN USE --&gt; RELEASED --&gt; IN USE

Because RELEASED != DROPPED

```
  /**
   * Increases the reference count. Should be called when acquiring the segment.
   *
   * @return Whether the segment is still valid (i.e. reference count not 0)
   */
  public synchronized boolean increaseReferenceCount() {
    if (_referenceCount == 0) {
      return false;
    } else {
      _referenceCount++;
      return true;
    }
  }```
Figured it out.

There’s a guard here that when the ref count goes to 0, this always returns false, which keeps it from being returned in acquireSegments.

A bit wasteful on memory. I’m going to include in my PR also removing it from the map when it gets released.

Thanks for the help. I’m getting pretty close on the segment cold storage. Also just released I posted in the wrong channel :face_palm:

Are you saying segments that would be deleted due to retention are still kept in SegmentDatamanager? That sounds like a bug to fix

Will have to look into it more, but maybe.

It's just a dangling ref in the concurrent hashmap that would keep the segment manager object from being garbage collected

ok, back. <@U01D36XR6CW> I dont understand your logic.

So, acquire and release can happen independent of removing the segment,

the segment data should be cleaned up only when the last reference to it goes away.

If there is no reference, then the remove operation should clean up the data.

Yeah. Need to look at the code again. But I think my point of confusion was that it starts at ref count one. And it locks at 0. And the return result of inc or dec is used in filtering

So the ref counting is for query processing only

The removal happens from a different call stack 

Yeah. And query processing or acquisition can never result in a removal from the segment data manager hash map

Should be fine. Just a bit of a learning curve here haha

<@U01CSLE7R5Z> has a proposal he will share.

Hi Noah, I added some comments about approaches we considered with pros and cons on the issue: <https://github.com/apache/incubator-pinot/issues/6189#issuecomment-724346637>

How can we search on the sorted set of the start times, can you elaborate?

Yeah. So you have a sorted set of start times. You then break down a query into ranges of start times. You then use the find range on that structure for each start ts range

But that sorted set could work for all sorts of things. Like sequence numbers, or sequentially increasing ids

So really anything where you store a min/max this could be useful. Doesn't have to be a sorted set. Could be another data structure. But it would be very cool to not have this only on time

Suppose i have a sorted mapping(start time to range) of current segments: 1-&gt; ([1, 5], [1, 7]),  5-&gt; ([5, 6], [5, 10]). A query search for [2,10], we then break the search range to [2, 5] and [5, 10], find intersection segments in entry(key 1) with [2, 5], and find intersection segments in entry(key 5) with range [5, 10] . And merge the result, is this what you mean?

More so you have those same segments.

Sorted set would look as your mapping, except map directly to segments

Query from 2,10 you plug directly into the sorted set find range function. That gives you a list of segments that are relevant

If I query [2, 10], I will miss the segments starts less than 2? Since start time is the key, the `subSet(fromElement, toElement)`  in SortedSet should return the results with 2 &lt;= key &lt; 10.

I think the harder part is that the data structure has all the segments. But the pruner gets a subset to sort through

Not sure the time complexity of an intersect operation

I see, if we have a sorted set of start time and another set of end time. We can exclude some segments from the first set, and exclude some segments from the second set. But I think the intersection of two subsets will take O(n) time.

Well, I'm also concerned about the intersection of segments left over from the previous pruners

Really you want to prune the most segments first with this type of sorted set filter. Then do the rest

If we only have a time range pruner, the pruner will get all online segments. If both partition and time range pruner are involved, and partition pruning is done first, the time range pruner will get a subset of segments. But since the partition pruning is O(n), in this way we can't get a solution better than O(n). It's better to prune based on time first O(m*logn) and prune with partition O(m), which gives total time O(m*logn). In this way the input for time pruner should be all online segments.

Perhaps we could move the discussion on the doc? The retention on slack messages is very limited.

Yeah. The doc is just a little less real time for discussion, which stinks. But yeah I think the order of pruning should be configurable

Ok, in that case, we can have the discussion in whatever platform is more realtime, but then copy-paste it over to the doc <@U01CSLE7R5Z>

Either works for me. If we don't mind a long log in the github issue

Pick one as the working copy, either works. My intention was purely to ensure that whatever is discussed gets captured for future reference.

Didn't mean to derail the discussion, please carry on

Sure, I'll copy the discussions to a google doc and point to it on the issue.

imo if the pruning job is done by filtering the input segments, we can't get a better solution than O(n) since some sort of looping or sorting need to be done with the input, so the time pruner has to keep the structure itself, even though the structure maybe larger than input segments.

Yeah, I think in a perfect world, you can only use this range index once. But it would use statistics to decide _which_ range filter on the table would eliminate the most segments. So, for example, you have a range index on timestamp and id. If the query is id = 1 AND timestamp between today and today - 1 day, it’d probably be better to use the id range index

Actually, why not have the list of segments passed to the pruner instead be a `Set`.

The first pruner should be a log(n) pruner. The `Set` passed in should be null, indicating this is the first pruner. It does `subSet` and returns a `Set` of the remaining segments. This (call it `firstPruneResults`) gets passed to the next pruner, which may also be a log(n) pruner. That prune does the `subSet` (`secondPruneResults`). You then do `firstPruneResults.retainAll(secondPruneResults)` which is O(n) where n is the number of items in `firstPruneResults`. As an optimization, could make the left hand side either first or second depending on which has fewer results.

The existing pruners can just iterate through the `Set` and return a new `HashSet`

I think using native `SortedSet` and `HashSet` make this a lot easier. As it’s reasonably easy to keep `SortedSet` in sync with the current set of segments coming from helix. Time complexity is still logarithmic in number of segments. `SortedSet` implementation can support anything that is sortable, which means all numeric columns (not just timestamps).

I think it’s a good idea for a generic numeric column pruner. Say if we have several numeric pruners. The result size of the pruners are m1, m2, … Then the total complexity would be O(logn + max(m1, m2, …)). (n is the # of all segments). If m is much smaller than n (depends on the query) this should work pretty well.

For time range pruning, this is kind of different, say I have 2 pruners for time columns, one for start time, the other for end time. A common query can be `"Select * from myTable where timeColumn &gt; startTime And timeColumn &lt; endTime"`. The result size of first pruner would be # of all segments which have timeColumn &gt; startTime, on average this should be half # of all segments. Same thing for the second pruner. Then the `retainAll()` will cost O(n). So for time range pruning this becomes an O(n) solution.

The interval search tree method is more optimized for this particular time range pruning. I think it's a good idea to keep prune() input and output as a set instead of list though. For a series of pruner, it's easier to get the intersection compared with list.

Ah. I see the issue here. The overlap on `SortedSet` either misses the first interval or the last interval. I.e. if you do the sortedSet on `minTime` , then an overlap query `BETWEEN startTime and endTime` only gives you the intervals who have a minTime in that range. This misses the very first interval, of which `startTime` is in the middle.

Perhaps instead we should use the <https://github.com/charcuterie/interval-tree/blob/master/src/datastructures/IntervalTree.java#L154|overlappers> method with the IntervalSet structure from <https://github.com/charcuterie|this library>. It’s not a very high traffic library, but would be very annoying to write something like this ourself.

Then the Iterator that returns can very easily be mapped back to a `Set`

I mean, either that or keep a `SortedSet` on `minTime` and a `SortedSet` on `maxTime`, then do a Set union on the `subSet` from both of them. Doubles the amount of time but it’s still logarithmic in input size. Maybe better than relying on a tiny lib.

<https://guava.dev/releases/21.0/api/docs/com/google/common/collect/RangeSet.html>

Here we go, guava has one.

So you could probably just subclass `Range` and have it store a segment on it.

Seems like the guava library only supports non-overlapping ranges.

I found this <https://algs4.cs.princeton.edu/93intersection/IntervalST.java.html> , which can fulfill our requirement.

I think it's from Princeton's algorithm class, and here's an introduction video: <https://youtu.be/q0QOYtSsTg4>

Ah. Neat. Yeah, I’d use that. Then use `Set` to get around multiple pruners in a row. And maybe let the user configure what order the pruners run

Cool. Maybe we can have the time range pruner be the first one as default for now, and create another issue for configuring the order of pruners.

Works for me. I think if you don’t provide any time filters, it’ll short-circuit the time filter and just pass a really large set to the next pruner.

Also when you’re implementing this, should override the `searchAll` function to use a `HashSet` instead of a `LinkedList` , that way you can just return a `Set` directly

Yes. The current implementation do not support duplicate time ranges, I can rewrite it to return `Set`  and add supports for duplicate ranges.

I think the solution should be grouping multiple physical segments into one logical segment, and only store ZK metadata for logical segment, as <@UDRJ7G85T> suggested

Yeah. May also be trying to make Pinot something it’s not. Pinot is very good at analyzing terrabytes of time series data. Might be square peg in a round hole trying to make it support petabytes. Perhaps traditional parquet files in s3 is better for 3+ month old data. Or something like that.

I still think the segment cold storage and the time based pruners are nice features to have just for the cost save. Probably most of our tables can fit into that paradigm.

My concern on the cold storage feature is that one query that hits the old data could invalid everything on the server cache. Just downloading all the old segments could take hours, and I don't think Pinot is designed for queries of such high latency.

Ideally, we should abstract the segment spi so that the query engine can directly work on parquet files stored in the deep storage without downloading the whole files

Yeah, I think 1) having limits on the number of segments you can query and 2) pruning aggressively helps.

I agree, the ideal would be having it work directly on parquet files. Though at what point are you better off just using Presto with a UNION ALL query with a `WHERE date &lt; 3 months` on one side and `WHERE data &gt; 3 months` on the other side.

This is not really terabyte vs petabytes, it’s more about metadata scale

If you use Presto, a simple file listing will have the same problem 

In the end, it’s a file list + filtering 

I think it’s both, really. The large amount of data itself becomes a problem because you can’t store it on normal hard discs. Needs to be in a distributed fs.

With that large of data, if your segments are 200-500 mb, the metatdata scale also becomes a problem.

We are really looking at 3600 segments for 10 years

So you can either do the segment group, or just merge the segments. But either way you do have a long download time.

Now, if you’re lucky the segment group itself causes a hit to a separate metadata API which narrows down the number of smaller segments you need to download.

Yeah, let’s get there to know what the bottle neck is

But again I keep asking myself if this isn’t trying to force Pinot into something it’s not.

Are you better off having a bespoke solution for long term historical that involves an aggressively indexed metadata store of files in s3. And a query engine that reads directly from s3 (like most parquet implementations)