Repository navigation
Manage group values and states by blocks in aggregation #11931
Description
Activity
take
Is the plan to manage group values and states in two different kinds of blocks, or a unified block?
There are so many good optimizations in the aggregation code now, they make the implementation a bit hard to understand, I was thinking managing group values + states in a single block could also be a good cleanup
Is the plan to manage group values and states in two different kinds of blocks, or a unified block?
There are so many good optimizations in the aggregation code now, they make the implementation a bit hard to understand, I was thinking managing group values + states in a single block could also be a good cleanup
Plan to make them two kinds of blocks, because
group valuesis the inner struct inGroupValues, andstatesis the one in differentGroupAccumulator, seems hard to manage them in a same place.The design is similar as #7065 , but introduce it into
GroupValues, not onlyGroupAccumulators.The reason why doing it is according to the cpu flamegraph, the growing of the big single
group valuesinGroupValuesandstatesin respecitveGroupAccumulatorseems really cost cpu(due to copy caused by growing).Reacted by Yongting YouThe sketch's detailed design
1. When will the blocked method triggered?
- It should not be streaming aggregation, because steaming depends on the excact
Emit::First(n)mode, and it is too expansive to impl it in blocked method. - The blocked
GroupValueswill be triggered, if we found the usedGroupValuesimpl support it. - The blocked
GroupAccumulatorwill be only triggered, when all the usedGroupAccumulators support blocked, and the usedGroupValuessupports blocked too.
2. Introduce new emit modes used in blocked method
It can support emit multiple blocks in
GroupValuessandGroupAccumulatorsnow:/// Describes how many rows should be emitted during grouping. #[derive(Debug, Clone, Copy)] pub enum EmitTo { /// Emit all groups All, /// Emit only the first `n` groups and shift all existing group /// indexes down by `n`. /// /// For example, if `n=10`, group_index `0, 1, ... 9` are emitted /// and group indexes '`10, 11, 12, ...` become `0, 1, 2, ...`. First(usize), /// Emit all groups managed by blocks AllBlocks, /// Emit only the first `n` group blocks, /// similar as `First`, but used in blocked `GroupValues` and `GroupAccumulator`. /// /// For example, `n=3`, `block size=4`, finally 12 groups will be returned. FirstBlocks(usize), }For incrementally development for blocked method for so many detailed GroupValues and GroupAccumulator impls. This sketch pr did a lot of compatibility works, and combinations are allowed：
- Single GroupAccumulator + single GroupAccumulator
- Blocked GroupValues + single GroupAccumulator
- Blocked GroupValues + blocked GroupAccumulator
3. Introduce
GroupIndicesto do communication betweenGroupValuesandGroupAccumulatorOne of the problem is how to let
GroupAccumulatorknow the ifgroup indicesis flat orblocked?
I introduceGroupIndicesto make it, but it indeed leads to api change forGroupAccumulator.pub enum GroupIndices<'a> { Flat(&'a [u64]), Blocked(&'a [u64]), } #[derive(Debug, Clone, Copy, PartialEq, Eq)] pub enum GroupIndicesType { Flat, Blocked, } impl GroupIndicesType { pub fn typed_group_indices<'a>(&self, indices: &'a [u64]) -> GroupIndices<'a> { match self { GroupIndicesType::Flat => GroupIndices::Flat(indices), GroupIndicesType::Blocked => GroupIndices::Blocked(indices), } } }- It should not be streaming aggregation, because steaming depends on the excact
/// For example,
n= 10,block size=4,nwill be aligned to 12,
/// and finally 3 blocks will be returned.
FirstBlocks(usize)I think emitting with "n" blocks is much more straightforward. n = 3, block size = 4. emit 3 * 4 = 12 elements
/// For example,
n= 10,block size=4,nwill be aligned to 12,
/// and finally 3 blocks will be returned.
FirstBlocks(usize)I think emitting with "n" blocks is much more straightforward. n = 3, block size = 4. emit 3 * 4 = 12 elements
It seems indeed more clear! I have switched to this in codes.
@alamb
I have finished the draft framework for blocked aggregation intermediate management, and we can incrementally impl blocked method for differentGroupAccumulators andGroupValueson it. Minding have a quick look?The general design can see:
#11931 (comment)And the pr is here:
#11943Implementing this aggregation approach #20773 would also contribute to keeping the state small per aggregation in the partial aggregate (and hopefully improves performance). The approach could be repeated in final / final partitioned aggregation (not sure why it is not done in the paper (maybe it is not as "free" as it is in partial aggregation step).
While still a large feature to implement, I think implementing it might be more local to aggregation (no changes needed to groupvalues / accumulators, etc...)
This PR
#20964I think shows that we probably can do the block-based aggregation in a couple of smaller steps, something like:
- Change group accumulators to allocate fixed-size blocks
- Change group by values to allocate fixed-size blocks
- Integrate indices with new fixed-size block allocation
This PR #20964
I think shows that we probably can do the block-based aggregation in a couple of smaller steps, something like:
- Change group accumulators to allocate fixed-size blocks
- Change group by values to allocate fixed-size blocks
- Integrate indices with new fixed-size block allocation
Yes, I introduce the similar
Blocks<T>in #15591 , but only used in accumulator, it should indeed also used in group valuesReacted by Daniël HeresI filed a ticket / epic to track the idea of blocked state management here
Is your feature request related to a problem or challenge?
Now we manage the group values and the aggregation states by a single big vector growing constantly.
This solution is simple to impl, but really leads to some extra cpu cost according to the cpu profile.
Maybe we should manage them by blocks like duckdb.
Describe the solution you'd like
It may be a big work, I want to finish it through following steps:
GroupValuesRows.group valuesmanagement in otherGroupValuesimpls.statesmanagement in differentGroupAccumulatorimpls.The general design is similar as #7065 , but introduce it into GroupValues, not only GroupAccumulators.
Describe alternatives you've considered
No response
Additional context
The cpu cost flamegraph:
https://github.com/Rachelint/drawio-store/blob/main/cpucosts0811.png