Index merging without garbage

[leventov]

Current state

Currently the data in several partial (or just one - for transformations) indexes is transformed during merged in the following way:

0. Iterator < TimeAndDims + Object[] metrics (entry in IncrementalIndex) >
   --> sorting dimension value indexed, aka unsortedToSorted
1. Iterator < Rowboat (Object[] dims, Object[] metrics) >
   --> optionally, reordering dims
2. Iterator < Rowboat (Object[] dims, Object[] metrics) >
   // here array elements are the same objects as at the previous step, but Object[] arrays are new, if reordering or dims and/or metrics is actually required
   
   --> another one reindexing, based on merged dictionary
3. Iterator < Rowboat (Object[] dims, Object[] metrics) >
   --> final merge.

Here, Object[] elements are either int[] (DimensionSelector), Long, Double or Float (numeric ColumnValueSelectors, correspondingly).

So in the process of merge, each entry generates 2-3 extra Rowboat objects, 4-7 new Object[] arrays, and N (the number of string dimensions) * 2 new int[] arrays, and new boxed primitive objects, if merging is done with QueryableIndex as a source.

Garbage-free approach

Rowboat contains an array of ColumnValueSelector objects, representing the stream of dimensions, and another array of ColumnValueSelector objects, representing a stream of metrics, both "under cursor". When QueryableIndexis used as source for merging, the existing Cursor and ColumnValueSelectorFactory infrastructure is reused with minimal modifications.

0->1 and 2-3 conversions, as described above, implemented as ColumnValueSelector transformations, without creating new arrays, boxed primitives, etc. 1->2 transformation is essentially a no-op: create a Rowboat object with array of ColumnValueSelectors, ordered differently.

[gianm]

Thank you for summarizing the motivation.

Can you quantify the benefit from this series of patches?

Could you also please lay out what backwards-incompatible API changes (if any) are expected as part of this series of patches?

[leventov]

I don't know how much space and time it will save, because this series of patches is not finished yet, and not tested.

Aggregations in extensions, which are supposed to be used for indexing rollup, must implement AggregatorFactory.makeAggregateCombiner(): https://github.com/druid-io/druid/pull/4676/files#diff-90e2d51a725b4d59f09e2f8b740b7f37R70

[github-actions]

This issue has been marked as stale due to 280 days of inactivity.
It will be closed in 4 weeks if no further activity occurs. If this issue is still
relevant, please simply write any comment. Even if closed, you can still revive the
issue at any time or discuss it on the dev@druid.apache.org list.
Thank you for your contributions.

[github-actions]

This issue has been closed due to lack of activity. If you think that
is incorrect, or the issue requires additional review, you can revive the issue at
any time.