You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2023/01/18 15:05:31 UTC

[GitHub] [arrow-datafusion] alamb opened a new issue, #4973: Consolidate and improve the performance of Aggregators

alamb opened a new issue, #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973

   Note this was broken out of https://github.com/apache/arrow-datafusion/issues/2723 and is based on the wonderful writeup from @crepererum and @tustvold   on https://github.com/apache/arrow-datafusion/issues/2723#issuecomment-1324876060
   
   # Background
   
   ## Prior Art
   After https://github.com/apache/arrow-datafusion/pull/4924 we have a single GroupByHash implementation that uses the Arrow row format for group keys (good!)
   
   However, the aggregator (e.g. the thing storing partial sums, counts, etc) is non ideal. Depending on the type of aggregate, it is either:
   
   1.  `Box<dyn RowAccumulator>` per 
   2. `Box<dyn Accumulator>`
   
   The GroupByHash operator  manages the mapping from group key to state and passes a `RowAccessor` to the `RowAccumulator` if needed.
   
   Groups are calculated once per batch, then a `take` kernel reshuffles everything and slices are passed to the `RowAccumulator`.
   
   
   ### Row Formats
   See #4179 -- Tl;Dr;: we have 3 row formats in our stack and we should focus on one.
   
   ## Proposal
   Ditch the *word-aligned* row format for the state management and change the aggregator to:
   
   ```rust
   trait Aggregator: MemoryConsumer {
       /// Update aggregator state for given groups.
       fn update_batch(&mut self, keys: Rows, batch: &RecordBatch)) -> Result<()>;
       ...
   }
   ```
   
   Hence the aggregator will be dyn-dispatched ONCE per record batch and will keep its own internal state. This moves the key->state map from the `[row_]hash.rs` to the aggregators. We will provide tooling (macros or generics) to simplify the implementation and to avoid boilerplate code as much as possible.
   
   Note that this also removes the `take` kernel since we think that it doesn't provide any performance improvements over iterating over the hashable rows and perform the aggregation row-by-row. We may bring the `take` handling back (as a "perform `take` if at least one aggregator wants that) if we can proof (via benchmarks) that this is desirable for certain aggregators, but we leave this out for now.
   
   This also moves the memory consumer handling into the aggregator since the aggregator knows best how to split states and spill data.
   
   ### Implementation Plan
   TBD


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] yjshen commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1454369204

   I'm curious about the proposed new Aggregator API. Do you know if it needs a hash table in each aggregator? I'm wondering because I'm a bit concerned about memory usage, especially for high cardinality aggregations. 
   
   Suppose keys are duplicated `n` times during execution (where `n` is the number of aggregators in the query). In that case, this could potentially lead to a significant increase in memory consumption, which might not be acceptable. What do you think about this?


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] yjshen commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1458236821

   Thank you @tustvold and @crepererum for your patient and detailed explanation.
   
   > aggregated values can be stored inline within the hash table
   
   I understand your main idea now and look forward to learning more about it.
   
   I agree that JIT is complex, and we should definitely try low-hanging fruits first.
   
   > we can support multiple approaches so long as they provide benefits to certain workloads.
   
   I agree to add this proposal as an alternative code path for aggregation. It would be great to have performance data in the future.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] crepererum commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "crepererum (via GitHub)" <gi...@apache.org>.
crepererum commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1456221104

   > So there will also be n times hash probe, and rehash, besides n memory overhead. Won't this hinder performance? 
   
   These are good questions.
   
   Hashing an `u128` ID should be very cheap since we don't need all this secure stuff anymore. So it's probably close to `upper_word(id) ^ lower_word(id)`. The random access pattern could be a problem, but I think this will be hard to avoid in general, at least if you wanna have a maintainable, safe solution (in contrast to the untyped aligned row format that is currently used).
   
   > How is the prototype benchmarked?
   
   There is no prototype yet, but a PR must run the groupby benchmarks.
   
   ---
   
   That said, I am open to other suggestions. The issue is that the current system needs a redesign:
   
   - It should be easy to add types and aggregations
   - It should ideally use a single aggregator type
   - It should work w/ memory accounting
   - Data accesses should be properly typed (in contrast to the aligned row format)
   - The solution should consider variable-length types. These cannot be added as an afterthought.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] tustvold commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1460970538

   > the Rows in arrow-rs incurs extra costs because it is designed for sort and requires order preserving
   
   Have you confirmed this, in my benchmarks I've found it to be significantly faster to encode than the DF row format? The order preserving part is basically free for most types, it is just a couple of bit twiddles.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] mingmwang commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "mingmwang (via GitHub)" <gi...@apache.org>.
mingmwang commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1610843919

   Some finding when reading DuckDB source code:
   
   1)  DuckDB uses generics to manage the Accumulator state, it uses function pointers to do the dispatch, there is some C++ static cast.
   2) There is no magic to the HashMap, the PartitionableHashTable is not used in the single thread model. The two level hash tables' idea is the same as ClickHouse, when the total groups in the single hash table exceeds a threshold(10000), it turns to the partitioned version.
   
   ```c++
   // two level hash tables
   vector<unique_ptr<PartitionableHashTable>> intermediate_hts;
   vector<shared_ptr<GroupedAggregateHashTable>> finalized_hts;
   
   // radix_limit is hard coded to 10000
   if (llstate.total_groups >= radix_limit) {
   		gstate.partitioned = true;
   }
   
   ```
   3) DuckDB uses `Row Layout`, the Row Layout keeps both the group keys and agg stats together.
   
   ```c++
   class RowLayout {
   .......
   private:
   	//! The types of the data columns
   	vector<LogicalType> types;
   	//! The aggregate functions
   	Aggregates aggregates;
   	//! The width of the validity header
   	idx_t flag_width;
   	//! The width of the data portion
   	idx_t data_width;
   	//! The width of the aggregate state portion
   	idx_t aggr_width;
   	//! The width of the entire row
   	idx_t row_width;
   	//! The offsets to the columns and aggregate data in each row
   	vector<idx_t> offsets;
   	//! Whether all columns in this layout are constant size
   	bool all_constant;
   	//! Offset to the pointer to the heap for each row
   	idx_t heap_pointer_offset;
   };
   }
   ```
   
   4) Due to the RowLayout and the uses of generics, the memory size of the  group state in DuckDB is much smaller than DataFusion's, maybe more than `5 times `smaller than ours.  I guess this is the major reason why they are faster and have a more efficient memory access pattern.
   
   DuckDB test result for tpch-q17
   
   ```c++
   	std::cout << "layout column count:" << layout.ColumnCount() << std::endl;
   	for (auto it = layout.GetTypes().cbegin(); it != layout.GetTypes().cend() ; ++it) std::cout << (*it).ToString() << " ";
   	std::cout << "layout agg count:" << layout.AggregateCount() << std::endl;
   	std::cout << "layout DataWidth:" << layout.GetDataWidth() << std::endl;
   	std::cout << "layout RowWidth:" << layout.GetRowWidth() << std::endl;
   ```
   ```
   layout column count:2
   INTEGER UBIGINT 
   layout agg count:1
   layout DataWidth:15
   layout RowWidth:40
   ```
   
   DataFusion test result
   
   ```rust
       let acc = AvgAccumulator::try_new(
           &DataType::Decimal128(18, 0),
           &DataType::Decimal128(24, 0),
       )?;
   
       println!("AvgAccumulator size: {:?}", std::mem::size_of::<AvgAccumulator>());
   
       struct NormalAVGStruct {
           count: u64,
           sum: i128,
       }
   
       println!("NormalAVGStruct size: {:?}", std::mem::size_of::<NormalAVGStruct>());
       println!("GroupState size: {:?}", std::mem::size_of::<GroupState>());
       println!("Arrow OwnedRow size: {:?}", std::mem::size_of::<OwnedRow>());
       println!("Accumulator item vec size: {:?}", std::mem::size_of::<Vec<AccumulatorItem>>());
       println!("usize vec size: {:?}", std::mem::size_of::<Vec<usize>>());
       println!("boxed u8 size: {:?}", std::mem::size_of::<Box<[u8]>>());
   ```
   
   ```
   AvgAccumulator size: 112
   NormalAVGStruct size: 32
   GroupState size: 112
   Arrow OwnedRow size: 40
   Accumulator item vec size: 24
   usize vec size: 24
   boxed u8 size: 16
   ```
   
   Learn from me is that I think we should avoid using `Arc`, `Box`, `Vec`, `dyn Trait` in the  Group State,  those are all pointers, pointers will consume at least 8 bytes and pointers point to other memory address will lead to random access. 
   We should also avoid using `ScalarValue` in Accumulator , `ScalarValue` is the enum type and the memory size is padding to the most large member. That means we have to make the Accumulator generic.
   
   https://duckdb.org/2022/03/07/aggregate-hashtable.html


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] sunchao commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "sunchao (via GitHub)" <gi...@apache.org>.
sunchao commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1613496266

   > I did some further experiment in the bucketing to see if this is still the case today [branch](https://github.com/apache/arrow-datafusion/commits/bucketing).
   This is very close to the description in the above MonetDB paper and written about here https://www.cockroachlabs.com/blog/vectorized-hash-joiner/ but doesn't really improve join performance, even when creating buckets to avoid collisions
   
   @Dandandan does DF use SIMD in the hot paths of hash join? From my experiences LLVM auto-vectorization is pretty fragile and often times doesn't get triggered if the logic is a bit complex. I think even the `create_hashes` in aggregation doesn't use SIMD (I could be wrong there).


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] sunchao commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "sunchao (via GitHub)" <gi...@apache.org>.
sunchao commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1613758230

   @Dandandan thanks, I agree that calculating hashes itself is probably not so critical to performances comparing to other hash table operations. We are doing some experiments to switch to vectorized hash table and see if it can deliver better performance. So far, without SIMD it's roughly the same as `hashbrown` used by DF, and I'm really hoping by vectorizing each of the steps it can get us to the next level. Will share the result once I have some numbers.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] tustvold commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1608231439

   > like spilling to disk
   > or non-fixed size intermediates
   
   I think I must be missing something, we have an API to return the partial state as an ArrayRef? That is both trivially spillable and supports non-fixed size intermediates through constructions like `ListArray`, etc... 


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1613172054

   Filed https://github.com/apache/arrow-datafusion/issues/6798 to track removing the duplication between the different hash operators


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] mingmwang commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "mingmwang (via GitHub)" <gi...@apache.org>.
mingmwang commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1614228374

   Based on the test result,  I would like do another POC and implement a new Accumulator framework. The Accumulator framework will follow your suggestions in the new Accumulator API proposal and will combine the normal Accumulator
   and the RowAccumulator into a unified Accumulator framework.
   
   1)   Unify the Accumulator framework,  remove the current RowAccumulator API.
   2)  A new `RowLayout` to combine the grouping data and accumulator state together
   3)  Make the new Accumulator state `generic`.
   4)  There will be one NewAccumulator instance per aggregate in the query (NOT one per group)
   5)  NewAccumulator API has update_batch that is invoked once per input batch, per aggregate (NOT PER GROUP). 
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1618911907

   > I am adding this comment here instead of opening a new issue as it looks the above PRs may fix/improve but please let me know if you would like a new issue.
   
   @vincev -- thank you Yes, I expect DataFusion will get significantly faster with the new grouping. However, the overall performance of the median aggregator will still have room to improve (someone will need to write a specialized vectorized implementation of `median`)


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] jhorstmann commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "jhorstmann (via GitHub)" <gi...@apache.org>.
jhorstmann commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1617699726

   [Clickbench query Q32](https://benchmark.clickhouse.com/#eyJzeXN0ZW0iOnsiQXRoZW5hIChwYXJ0aXRpb25lZCkiOmZhbHNlLCJBdGhlbmEgKHNpbmdsZSkiOmZhbHNlLCJBdXJvcmEgZm9yIE15U1FMIjpmYWxzZSwiQXVyb3JhIGZvciBQb3N0Z3JlU1FMIjpmYWxzZSwiQnlDb25pdHkiOmZhbHNlLCJCeXRlSG91c2UiOmZhbHNlLCJjaERCIjpmYWxzZSwiQ2l0dXMiOmZhbHNlLCJDbGlja0hvdXNlIChkYXRhIGxha2UsIHBhcnRpdGlvbmVkKSI6ZmFsc2UsIkNsaWNrSG91c2UgKFBhcnF1ZXQsIHBhcnRpdGlvbmVkKSI6ZmFsc2UsIkNsaWNrSG91c2UgKFBhcnF1ZXQsIHNpbmdsZSkiOnRydWUsIkNsaWNrSG91c2UiOmZhbHNlLCJDbGlja0hvdXNlICh0dW5lZCkiOmZhbHNlLCJDbGlja0hvdXNlICh6c3RkKSI6ZmFsc2UsIkNsaWNrSG91c2UgQ2xvdWQiOmZhbHNlLCJDbGlja0hvdXNlIENsb3VkIChBV1MpIjpmYWxzZSwiQ2xpY2tIb3VzZSBDbG91ZCAoR0NQKSI6ZmFsc2UsIkNsaWNrSG91c2UgKHdlYikiOmZhbHNlLCJDcmF0ZURCIjpmYWxzZSwiRGF0YWJlbmQiOmZhbHNlLCJEYXRhRnVzaW9uIChzaW5nbGUgcGFycXVldCkiOnRydWUsIkFwYWNoZSBEb3JpcyI6ZmFsc2UsIkRydWlkIjpmYWxzZSwiRHVja0RCIChQYXJxdWV0LCBwYXJ0aXRpb25lZCkiOnRydWUsIkR1Y2tEQiI6ZmFsc2UsIkVsYXN0aWNzZWFyY2giOmZhbHNlLCJFbGFzdGljc2VhcmNoICh0dW5lZCkiOmZhbHNlLCJHcmVlbnBsdW
 0iOmZhbHNlLCJIZWF2eUFJIjpmYWxzZSwiSHlkcmEiOmZhbHNlLCJJbmZvYnJpZ2h0IjpmYWxzZSwiS2luZXRpY2EiOmZhbHNlLCJNYXJpYURCIENvbHVtblN0b3JlIjpmYWxzZSwiTWFyaWFEQiI6ZmFsc2UsIk1vbmV0REIiOmZhbHNlLCJNb25nb0RCIjpmYWxzZSwiTXlTUUwgKE15SVNBTSkiOmZhbHNlLCJNeVNRTCI6ZmFsc2UsIlBpbm90IjpmYWxzZSwiUG9zdGdyZVNRTCI6ZmFsc2UsIlBvc3RncmVTUUwgKHR1bmVkKSI6ZmFsc2UsIlF1ZXN0REIgKHBhcnRpdGlvbmVkKSI6ZmFsc2UsIlF1ZXN0REIiOmZhbHNlLCJSZWRzaGlmdCI6ZmFsc2UsIlNlbGVjdERCIjpmYWxzZSwiU2luZ2xlU3RvcmUiOmZhbHNlLCJTbm93Zmxha2UiOmZhbHNlLCJTUUxpdGUiOmZhbHNlLCJTdGFyUm9ja3MiOmZhbHNlLCJUaW1lc2NhbGVEQiAoY29tcHJlc3Npb24pIjpmYWxzZSwiVGltZXNjYWxlREIiOmZhbHNlfSwidHlwZSI6eyJzdGF0ZWxlc3MiOnRydWUsIm1hbmFnZWQiOnRydWUsIkphdmEiOnRydWUsImNvbHVtbi1vcmllbnRlZCI6dHJ1ZSwiQysrIjp0cnVlLCJNeVNRTCBjb21wYXRpYmxlIjp0cnVlLCJyb3ctb3JpZW50ZWQiOnRydWUsIkMiOnRydWUsIlBvc3RncmVTUUwgY29tcGF0aWJsZSI6dHJ1ZSwiQ2xpY2tIb3VzZSBkZXJpdmF0aXZlIjp0cnVlLCJlbWJlZGRlZCI6dHJ1ZSwiYXdzIjp0cnVlLCJnY3AiOnRydWUsInNlcnZlcmxlc3MiOnRydWUsIlJ1c3QiOnRydWUsInNlYXJjaCI6dHJ1ZSwiZG9jdW1lbnQiOnRydWU
 sInRpbWUtc2VyaWVzIjp0cnVlfSwibWFjaGluZSI6eyJzZXJ2ZXJsZXNzIjp0cnVlLCIxNmFjdSI6dHJ1ZSwiYzZhLjR4bGFyZ2UsIDUwMGdiIGdwMiAoZG9ja2VyKSI6dHJ1ZSwiTCI6dHJ1ZSwiTSI6dHJ1ZSwiUyI6dHJ1ZSwiWFMiOnRydWUsImM2YS40eGxhcmdlLCA1MDBnYiBncDIiOnRydWUsImM2YS5tZXRhbCwgNTAwZ2IgZ3AyIjp0cnVlLCJjNS40eGxhcmdlLCA1MDBnYiBncDIiOnRydWUsIjYwIHRocmVhZHMgKGlkZWFsKSI6dHJ1ZSwiNjAgdGhyZWFkcyAobG9jYWwpIjp0cnVlLCIxOTJHQiI6dHJ1ZSwiMjRHQiI6dHJ1ZSwiMzYwR0IiOnRydWUsIjQ4R0IiOnRydWUsIjcyMEdCIjp0cnVlLCI5NkdCIjp0cnVlLCI3MDhHQiI6dHJ1ZSwibTVkLjI0eGxhcmdlIjp0cnVlLCJtNmkuMzJ4bGFyZ2UiOnRydWUsImM1bi40eGxhcmdlLCA1MDBnYiBncDIiOnRydWUsImM2YS40eGxhcmdlLCAxNTAwZ2IgZ3AyIjp0cnVlLCJkYzIuOHhsYXJnZSI6dHJ1ZSwicmEzLjE2eGxhcmdlIjp0cnVlLCJyYTMuNHhsYXJnZSI6dHJ1ZSwicmEzLnhscGx1cyI6dHJ1ZSwiUzI0Ijp0cnVlLCJTMiI6dHJ1ZSwiMlhMIjp0cnVlLCIzWEwiOnRydWUsIjRYTCI6dHJ1ZSwiWEwiOnRydWV9LCJjbHVzdGVyX3NpemUiOnsiMSI6dHJ1ZSwiMiI6dHJ1ZSwiNCI6dHJ1ZSwiOCI6dHJ1ZSwiMTYiOnRydWUsIjMyIjp0cnVlLCI2NCI6dHJ1ZSwiMTI4Ijp0cnVlLCJzZXJ2ZXJsZXNzIjp0cnVlLCJ1bmRlZmluZWQiOnRydWV9LCJtZXRyaWMiOiJo
 b3QiLCJxdWVyaWVzIjpbZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsZmFsc2UsdHJ1ZSxmYWxzZSxmYWxzZSxmYWxzZSxmYWxzZSxmYWxzZSxmYWxzZSxmYWxzZSxmYWxzZSxmYWxzZSxmYWxzZV19) is also a very good benchmark of high cardinality grouping. It's also the only query that [did not finish successfully when the benchmark results were last updated](https://github.com/ClickHouse/ClickBench/tree/main/datafusion#to-solve).


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] sunchao commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "sunchao (via GitHub)" <gi...@apache.org>.
sunchao commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1461255058

   Yea, for the spilling case, I agree it's better to use Arrow format for the group keys, and have an option to "hydrate" dictionary arrays. We shouldn't need to use Arrow format for aggregate buffers though, although it may help to just keep a single row format in the project as you said. We need to find out whether there's any performance impact by switching to that.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] mingmwang commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "mingmwang (via GitHub)" <gi...@apache.org>.
mingmwang commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1621762170

   > @mingmwang @Dandandan and @tustvold (and everyone else following along) here is a POC #6800
   > 
   > It follows similar pattern as you describe in [#4973 (comment)](https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1614211204) and It also makes q17 go more than 2x faster (and has no `unsafe` code or row format)!
   > 
   > > This branch: Query 17 avg time: 766.31 ms
   > > main: Query 17 avg time: 1789.73 ms
   > 
   > I would love feedback and thoughts on the approach
   
   I like your approach !!. The POC result is very promising, and the performance is better than my best version.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1608068287

   @tustvold  and I had a large talk about this topic in the context of https://github.com/apache/arrow-datafusion/pull/6657 and how to improve the performance of both grouping in general and high cardinality groups in particular
   
   It is very similar in spirit to @Dandandan 's / @ic4y 's ticket https://github.com/apache/arrow-datafusion/issues/956 and the proposals from @crepererum above, 
   
   The high level idea is to change the state management of the Aggregate operators so that it
   1. Manages state for *all* groups rather than just one group
   3. There is still only a single hash table (that maps group values to group_ids)
   
   In ASCII art:
   
   ## How aggregation currently works
   
   ```
                                                                  ...                    
                                                                                         
                                            ┌───────────────────────────────────────────┐
                                            │┌────────────┐┌────────────┐┌────────────┐ │
       ┌─────┐                              ││accumulator ││accumulator ││accumulator │ │
       │  5  │               ┌─────────────▶││  0 state   ││  1 state   ││  2 state   │ │
       ├─────┤               │              │└────────────┘└────────────┘└────────────┘ │
       │  9  │──────────────┐│              └───────────────────────────────────────────┘
       ├─────┤              ││                                                           
       │     │              ││                                  ...                      
       ├─────┤              ││                                                           
       │  1  │ ─────────────┼┘              ┌───────────────────────────────────────────┐
       ├─────┤              │               │┌────────────┐┌────────────┐┌────────────┐ │
       │     │              │               ││accumulator ││accumulator ││accumulator │ │
       └─────┘              └──────────────▶││  0 state   ││  1 state   ││  2 state   │ │
                                            │└────────────┘└────────────┘└────────────┘ │
                                            └───────────────────────────────────────────┘
                                                                                         
       Hash Table                                               ...                      
                                                                                         
                                                                                         
                                               GroupState s                              
                                                                                         
                                                                                         
   stores "group indexes"                                                                
   which are indexes into                     stores the aggregation states for each     
   Vec<GroupState>                            aggregate (either as Vec<dyn Accumulator>  
                                              or Row Vec<u8>).                           
                                                                                         
                                              There is one GroupState PER GROUP          
                                                                                         
                                                                                         
   ```
   
   Currently the hash table stores an index into a `Vec` of [`GroupState`
   ](https://github.com/apache/arrow-datafusion/blob/1522e7a58e801b87a0f8f5c6187a2038453eba9d/datafusion/core/src/physical_plan/aggregates/utils.rs#L38) which hold state per group. 
   
   This design means that when grouping by high cardinality groups where each accumulator receives only a few rows per group per batch, the overhead is quite high
   
   ## Proposal
   
   ```
                                            ┌──────────────┐   ┌──────────────┐   ┌──────────────┐
                                            │┌────────────┐│   │┌────────────┐│   │┌────────────┐│
       ┌─────┐                              ││accumulator ││   ││accumulator ││   ││accumulator ││
       │  5  │                              ││     0      ││   ││     0      ││   ││     0      ││
       ├─────┤                              ││ ┌────────┐ ││   ││ ┌────────┐ ││   ││ ┌────────┐ ││
       │  9  │                              ││ │ state  │ ││   ││ │ state  │ ││   ││ │ state  │ ││
       ├─────┤                              ││ │        │ ││   ││ │        │ ││   ││ │        │ ││
       │     │                              ││ │        │ ││   ││ │        │ ││   ││ │        │ ││
       ├─────┤                              ││ │        │ ││   ││ │        │ ││   ││ │        │ ││
       │  1  │                              ││ │        │ ││   ││ │        │ ││   ││ │        │ ││
       ├─────┤                              ││ │        │ ││   ││ │        │ ││   ││ │        │ ││
       │     │                              ││ │        │ ││   ││ │        │ ││   ││ │        │ ││
       └─────┘                              ││ │        │ ││   ││ │        │ ││   ││ │        │ ││
                                            ││ │        │ ││   ││ │        │ ││   ││ │        │ ││
                                            ││ └────────┘ ││   ││ └────────┘ ││   ││ └────────┘ ││
                                            │└────────────┘│   │└────────────┘│   │└────────────┘│
       Hash Table                           └──────────────┘   └──────────────┘   └──────────────┘
                                                                                                  
                                             New NewAccumulator                                   
                                                                                                  
                                                                                                  
                                                                                                  
   stores "group indexes"                     There is one NewAccumulator per aggregate           
   which are indexes into                     (NOT PER GROUP). Internally, each                   
   Vec<GroupState>                            NewAccumulator manages the state for                
                                              multiple groups                                     
   ```
   
   In this design, the hash table still stores the group -> group index mapping. However, the state for all groups is handled internally by a (new) type of accumulator that stores the group state internally. 
   
   As today, the group by hash will calculate the group_id for each input row, after applying any filters and then make a **SINGLE** function call to the NewAccumulator to update all relevant group values for the ENTIRE BATCH.
   
   ## More details:
   
   
   Make a `NewAccumulator` trait so that it has:
   1. Manages the accumulated state for *all* groups. (remove `aggregation_buffer` from GroupState`)
   4. There will be one `NewAccumulator` instance per aggregate in the query (NOT one per group)
   2. `NewAccumulator` API has update_batch that is invoked once per input batch, per aggrgate (NOT PER GROUP). Something like:
   
   ```rust
       /// updates the accumulator's state from a vector of arrays.
       fn update_batch(
           &mut self,
           values: &[ArrayRef],
           // ( Which rows in `values` to be accumulated, group states)
           group_indicies: &[(Range<usize>, usize)],
       ) -> Result<()>;
   ```
   
   Other details:
   1.  Assumes that the group_indexes are contiguous (there aren't gaps, aka it is ok to use a `Vec<...>` internally to store the group states within the accumulator)
   2. The internal state (evaluate and state) for row accumulator will produce an `ArrayRef` (which can be done without copying using the newer zero copy arrow APIs that convert `Vec` to Array without any copy).  
   4. The `NewAccumulator` API has some way to get the size of the accumulated state size (`size()`)
   5. We would not change the existing (public) [`Accumulator`](https://docs.rs/datafusion/latest/datafusion/physical_plan/trait.Accumulator.html#) API, instead would implement a wrapper using `Vec<Box<dyn Accumulator>>>`
   
   ## Benefits of this design:
   1. No per-group overhead (the root cause why high cardinality grouping is slow)
   2. There is still only one hash table, mapping from group key to logical group number
   6. There is no copy of intermediate vales into a new array to call accumulator interface
   2. There are no `ScalarValue`s (outside of what is needed to adapt existing Accumulator API)
   3. Unified implementation rather than split between diffferent accumulator (e.g. `RowAccumulator` and `dyn Accumulator`)
   6. Could remove the fixed length row format
   7. Expected performance to be the similar for `Accumulator` based aggregates
   5. Expected performance much faster for other aggregates, especially for for high cardinality  groups
   
   
   High level implementation plan:
   1. Remove the copy/paste between row_hash.rs and bounded_aggregate_stream.rs 
   2. Sketch out the new API
   3. Migrate over
   
   cc @yjshen @mingmwang 
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1612269640

   > Learn from me is that I think we should avoid using Arc, Box, Vec, dyn Trait in the Group State, those are all pointers, pointers will consume at least 8 bytes and pointers point to other memory address will lead to random access.
   
   Agree -- I am hoping to have none of that overhead
   
   
   > We should also avoid using ScalarValue in Accumulator , ScalarValue is the enum type and the memory size is padding to the most large member. That means we have to make the Accumulator generic.
   
   100% agree that anything that uses ScalarValue sacrifices a lot of performance
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] crepererum commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "crepererum (via GitHub)" <gi...@apache.org>.
crepererum commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1455804758

   > Do you know if it needs a hash table in each aggregator? I'm wondering because I'm a bit concerned about memory usage, especially for high cardinality aggregations.
   
   Yes, see https://github.com/apache/arrow-datafusion/issues/2723#issuecomment-1324876060
   
   We're trading speed for slightly more memory usage here. We could probably avoid storing the actual key in the per-aggregator hash tables by either interning the key using another hash table (key -> ID) or by hashing the keys to a "wide enough" ID (like 128bit, also assuming that the hash function is actually proper).


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] yjshen commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1458077103

   > So technically NOTHING would change when this proposal is implemented
   
   I take it differently here; changing one single hash table to per-aggregator hash table is a fundamental change. After this change, we will theoretically:
   1. do more hash table operations (hash, matching, resize&rehash when the threshold is reached) 
   2. introduce much more random memory access state update (_no matter whether the state is the current word-aligned row or changed to using the unified row in arrow-rs_)
      - for a continuous row state in the current approach, we could load sequential words of it into cache lines, update all fields at once, and proceed with the next group by key. 
      - With the per-aggregator state, the cache line will always be filled with adjacent but irrelevant state data.
   
   If the current inefficiency comes from too much dyn dispatch, I would like to try JIT.
       


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] mingmwang commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "mingmwang (via GitHub)" <gi...@apache.org>.
mingmwang commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1590583787

   @alamb @ozankabak @yjshen @jiangzhx 
   
   For group by high cardinality columns, I will do some POC to support two levels of grouping state (PartitionedHashTable).
   The PartitionedHashTable approach was adopted by many other engines like ClickHouse, DuckDB and Databend. It is also mentioned in the "Morsel-Driven Parallelism" paper.  
   
   
   
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] mingmwang commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "mingmwang (via GitHub)" <gi...@apache.org>.
mingmwang commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1614211204

   @alamb @tustvold @Dandandan 
   
   I did another POC based on the changes in #6657. The basic idea is to reduce the memory size of `GroupState` and  avoid using `Arc, Box, Vec, dyn Trait`, etc.  And the result is very exciting !!!
   Compared to the main branch, there is about 50% improvement, and for the high cardinality aggregation itself,  the improvement is about 100%. 
   
   Test result:
   
   Q17
   
   ```
   Running benchmarks with the following options: DataFusionBenchmarkOpt { query: Some(17), debug: false, iterations: 10, partitions: 1, batch_size: 8192, path: "./parquet_data", file_format: "parquet", mem_table: false, output_path: None, disable_statistics: false }
   null_width 2
   values_width 24
   Query 17 iteration 0 took 818.2 ms and returned 1 rows
   null_width 2
   values_width 24
   Query 17 iteration 1 took 774.3 ms and returned 1 rows
   null_width 2
   values_width 24
   Query 17 iteration 2 took 765.0 ms and returned 1 rows
   null_width 2
   values_width 24
   Query 17 iteration 3 took 772.8 ms and returned 1 rows
   null_width 2
   values_width 24
   Query 17 iteration 4 took 770.9 ms and returned 1 rows
   null_width 2
   values_width 24
   Query 17 iteration 5 took 765.2 ms and returned 1 rows
   null_width 2
   values_width 24
   Query 17 iteration 6 took 765.9 ms and returned 1 rows
   null_width 2
   values_width 24
   Query 17 iteration 7 took 760.3 ms and returned 1 rows
   null_width 2
   values_width 24
   Query 17 iteration 8 took 758.3 ms and returned 1 rows
   null_width 2
   values_width 24
   Query 17 iteration 9 took 763.8 ms and returned 1 rows
   Query 17 avg time: 771.46 ms
   ```
   
   Q18
   
   ```
   Query 18 iteration 4 took 768.1 ms and returned 57 rows
   null_width 2
   values_width 24
   null_width 2
   values_width 24
   Query 18 iteration 5 took 776.4 ms and returned 57 rows
   null_width 2
   values_width 24
   null_width 2
   values_width 24
   Query 18 iteration 6 took 767.0 ms and returned 57 rows
   null_width 2
   values_width 24
   null_width 2
   values_width 24
   Query 18 iteration 7 took 775.9 ms and returned 57 rows
   null_width 2
   values_width 24
   null_width 2
   values_width 24
   Query 18 iteration 8 took 773.7 ms and returned 57 rows
   null_width 2
   values_width 24
   null_width 2
   values_width 24
   Query 18 iteration 9 took 771.2 ms and returned 57 rows
   Query 18 avg time: 778.98 ms
   ```
   
   ```rust
   
   pub(crate) struct NonFixedSizeGroupState {
       /// Group data
       pub group_data: Vec<u8>,
       /// Accumulator data
       pub acc_data: Vec<u8>,
   }
   
   impl NonFixedSizeGroupState {
       #[inline(always)]
       fn group_data(&self) -> &[u8] {
           &self.group_data
       }
   
       #[inline(always)]
       fn agg_data(&self) -> &[u8] {
           &self.acc_data
       }
   }
   
   pub(crate) struct FixedSizeGroupState {
       /// Group data and Accumulator state data, stored sequentially
       pub group_states: Vec<u8>,
   }
   
   impl FixedSizeGroupState {
       #[inline(always)]
       fn group_data(&self, data_width: usize) -> &[u8] {
           &self.group_states[0..data_width]
       }
   
       #[inline(always)]
       fn agg_data(&self, data_width: usize) -> &[u8] {
           &self.group_states[data_width..]
       }
   }
   
   
   fn update_one_accumulator_with_native_value<T1>(
           &mut self,
           groups_addresses: &[usize],
           agg_input_array: &T1,
           acc_idx: usize,
           filter_bool_array: &[Option<&BooleanArray>],
           row_layout: Arc<RowLayout>,
       ) -> Result<()>
       where
           T1: ArrowArrayReader,
       {
           let acc = &self.row_accumulators[acc_idx];
           let filter_array = &filter_bool_array[acc_idx];
           let mut state_accessor = RowAccessor::new_from_layout(row_layout);
           if filter_array.is_none() && agg_input_array.null_count() == 0 {
               for idx in 0..groups_addresses.len() {
                   unsafe {
                       let group_state_ptr = &mut *(&self.aggr_state.group_states
                           [groups_addresses[idx]]
                           as *const FixedSizeGroupState
                           as *mut FixedSizeGroupState);
                       state_accessor.point_to(
                           0,
                           group_state_ptr.group_states[self.data_part_width..].as_mut(),
                       );
                       acc.update_value::<T1::Item>(
                           Some(agg_input_array.value_at_unchecked(idx)),
                           &mut state_accessor,
                       );
                   }
               }
           } else {
               for idx in 0..groups_addresses.len() {
                   unsafe {
                       let group_state_ptr = &mut *(&self.aggr_state.group_states
                           [groups_addresses[idx]]
                           as *const FixedSizeGroupState
                           as *mut FixedSizeGroupState);
                       state_accessor.point_to(
                           0,
                           group_state_ptr.group_states[self.data_part_width..].as_mut(),
                       );
                       let value = col_to_value(agg_input_array, filter_array, idx);
                       acc.update_value::<T1::Item>(value, &mut state_accessor);
                   }
               }
           }
   
           Ok(())
       }
   ```


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] yjshen commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1457463675

   > I think it is important to highlight that the proposal in https://github.com/apache/arrow-datafusion/issues/2723#issuecomment-1324876060 is still a row hash approach, just using a different row encoding. Early benchmarks show it to be significantly faster.
   
   @tustvold There appears to be a discrepancy between your proposal and my current situation. Can you clarify how I should interpret this?
   
   > Hence the aggregator will be dyn-dispatched ONCE per record batch and will keep its own internal state. This moves the key->state map from the [row_]hash.rs to the aggregators.
   
   Do you know if it needs a hash table in each aggregator? What does the internal state mean? Can you elaborate
   
   If yes, what do you mean by "still a row hash approach"? Keys are rows, but aggregator states are not?
   If not, why @crepererum said: "We're trading speed for slightly more memory usage here....", and why "in the per-aggregator hash tables by either interning...."
   
   If the proposal is to remove all(word-aligned/compact) row formats inside DataFusion, use row-format from arrow-rs, and achieve a significant performance improvement, I completely vote for the change.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1614959711

   @mingmwang  @Dandandan  and @tustvold  (and everyone else following along) here is a POC https://github.com/apache/arrow-datafusion/pull/6800
    
   
   It follows similar pattern as you describe in https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1614211204  and It also makes q17  go more than 2x faster (and has no `unsafe` code or row format)!
   
   > This branch: Query 17 avg time: 766.31 ms
   > main: Query 17 avg time: 1789.73 ms
   
   I would feedback and thoughts on the approach
   
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1609200478

   I think we need to try it to really see -- I'll talk with @tustvold  and hopefully we can find some way to sketch out and implement the proposal as an RFC to prove / disprove the potential benefits
   
   >  With the Row Layout, the states of multiple Accumulators belong to the same group can be updated in the tight loop. I
   
   I think our proposal above also has this property (the accumulator has the states for all the groups and thus all the associated state for all groups can be updated in the same tight loop.
   
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1613162551

   Here is my POC plan:
   
   Implement enough of the new design to run TPCH q17 (the query that https://github.com/apache/arrow-datafusion/pull/6657 improved).
   
   I will test / profile using this command:
   
   ```shell
   $ cargo run --profile release-nonlto --bin tpch -- benchmark datafusion --iterations 5 -m --format parquet -q 17 --path /Users/alamb/Software/arrow-datafusion/benchmarks/data/
   ```
   
   As a reminder, here is the TPCH query:
   ```shell
   cat ./benchmarks/queries/q17.sql
   select
           sum(l_extendedprice) / 7.0 as avg_yearly
   from
       lineitem,
       part
   where
           p_partkey = l_partkey
     and p_brand = 'Brand#23'
     and p_container = 'MED BOX'
     and l_quantity < (
       select
               0.2 * avg(l_quantity)
       from
           lineitem
       where
               l_partkey = p_partkey
   
   ```
   
   If this POC shows promise, I'll then start moving the actual implementation over. 
   
   My basic plan is to make a copy/paste version of row_hash.rs and change the planner to use it when possible
   
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] mingmwang commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "mingmwang (via GitHub)" <gi...@apache.org>.
mingmwang commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1590592547

   **4.4 Grouping/Aggregation**
   
   The performance characteristics of the aggregation operator differs very much depending on the number of groups (distinct keys). If there are few groups, aggregation is very fast because all groups fit into cache. If, however, there are many groups, many cache misses happen. Contention from parallel accesses can be a problem in both cases (if the key distribution is skewed). To achieve good performance and scalability in all these cases, without relying on query optimizer estimates, we use an approach similar to IBM BLU’s aggregation [31].


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] sunchao commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "sunchao (via GitHub)" <gi...@apache.org>.
sunchao commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1611602305

   Another interesting aspect from DuckDB is that it uses a vectorized hash table, instead of a general one like DF. I think the former allows it to vectorize each step of the hash table operation, including hash comparison, equality check, as well as hash probing. This is the same approach that Photon has adopted, as mentioned in their [SIGMOD'22 paper](https://dl.acm.org/doi/10.1145/3514221.3526054).


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] Dandandan commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1613764389

   Cool @sunchao very interested about what comes out of those experiments :)


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] liurenjie1024 commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "liurenjie1024 (via GitHub)" <gi...@apache.org>.
liurenjie1024 commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1617772737

   We have implemented a hash key to further reduce allocation for fix sized group key/state, which is inspired by clickhouse:
   https://github.com/risingwavelabs/risingwave/blob/main/src/common/src/hash/key.rs
   
   cc @mingmwang 


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] yjshen commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1456117697

   So there will also be `n` times hash probe, and rehash, besides `n` memory overhead. Won't this hinder performance? How is the prototype benchmarked?


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] yjshen commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1456323067

   While I agree that we may need to revisit the current `Box<dyn Accumulator>` approach when creating a fallback or default strategy, I do not believe we should combine all hash aggregate methods into one universal approach. Given that we are constructing an essential operator for a database execution engine, it is important to consider specialized implementations that offer performance benefits for handling different use cases.
   
   I view row hash as a fast lane for certain queries rather than a dead end. By efficiently executing queries through row hash, we can avoid slower or more general approaches. Furthermore, I am open to exploring other specialized aggregate implementations that offer performance benefits to handle more use cases quickly.
   
   For example, Spark provides multiple hash aggregate implementations, including vectorized hash, hash, and object hash. Similarly, ClickHouse offers different implementation options for its hash table, based on key types. Utilizing these specialized implementations can optimize query performance without relying on a one-size-fits-all approach.
   
   
   > It should be easy to add types and aggregations
   
   Regarding the proposed criteria for a fallback strategy, I believe that while it should be easy to add types and aggregations, not all internal implementations should be treated equally, or else we risk the entire engine running at the speed of UDAFs.
   
   > It should work w/ memory accounting
   
   While it would be beneficial for the fallback strategy to work with memory accounting, it is not strictly necessary. Users can take risks when defining UDAFs, or we could even risk the less-used built-in functions.
   
   > Data accesses should be properly typed (in contrast to the aligned row format)
   
   I'm not convinced that data accesses need to be typed for aggregate implementations, which is entirely internal to database engines.
   
   > The solution should consider variable-length types. These cannot be added as an afterthought.
   
   I understand that you were referring to the aligned format, but it is possible to handle variable length fields using 'pointer swizzling.' Additionally, I don't believe that `median` is a performance-critical aggregate function that needs to be considered a first-class citizen for all aggregate strategies.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] Dandandan commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1613589972

   > > I did some further experiment in the bucketing to see if this is still the case today [branch](https://github.com/apache/arrow-datafusion/commits/bucketing).
   > > This is very close to the description in the above MonetDB paper and written about here https://www.cockroachlabs.com/blog/vectorized-hash-joiner/ but doesn't really improve join performance, even when creating buckets to avoid collisions
   > 
   > @Dandandan does DF use SIMD in the hot paths of hash join? From my experiences LLVM auto-vectorization is pretty fragile and often times doesn't get triggered if the logic is a bit complex. I think even the `create_hashes` in aggregation doesn't use SIMD (I could be wrong there).
   
   @sunchao TBH I am not sure about whether everything generates optimal SIMD instructions, however in the hash join vectorization of `create_hashes`, vectorized equality checking (using plain arrow kernels) was definitely a big performance improvement compared to the earlier scalar-based approaches, this would probably be the case even without much use of SIMD. There are probably some possible improvements here and there wrt. generated code. `create_hashes` uses ahash internally, which is one of the faster algorithms - the hashing itself is usually not very expensive by now compared to other operations, it used to be. It just does the hashing + rehashing column-wise like in other systems.
   
   The above experiment is only about the conversion from using a `RawTable<(u64, u64))` to storing buckets in a `Vec<u64>` and having collision checking handled at the probing phase as discussed in the MonetDB paper. Maybe I'm a bit wrong here in my implementation (and the Photon whitepaper doesn't include enough details unfortunately) or something else could be optimized in order for it to be faster. Or it turns out that keeping a plain hashtable for values only might not be so bad at all(?) At least with the current approach I'm getting mixed results.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1456836406

   I agree this should be benchmark results driven and the outcome should be as maintainable as possible. Given how performance critical this code is, I think performance is of higher priority than requiring strong typing (though of course it would be great if the resulting solution is strongly typed as well as high performance)
   
   If we can't handle memory accounting for some reason, providing the user a choice to use potentially unlimited memory or faster performance, seems acceptable. I would be surprised if we can't work a memory limit check in somehow and amortize its cost into the noise
   
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1458493210

   It is great to see the discussion on this ticket -- it is really nice to see


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] sunchao commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "sunchao (via GitHub)" <gi...@apache.org>.
sunchao commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1461017703

   I don't think DF format considers dictionary 😂 . In the POC for group-by columns we basically "unpack" the dictionary arrays into plain rows while doing the columnar to row conversion. For aggregate columns, we initialize the buffer (using DF format) based on the schema of the aggregates. If dictionary type shows up in any of the aggregates, we'll remove it and replace it with its value type.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] yjshen commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1608128995

   High cardinality always comes with great memory consumption; how will the new design deal with memory limit? 
   - Adaptive sizing(perhaps?): How would the hash table header and states in each accumulator initialize and grow their sizes afterward? 
   - Spill mechanism: Do we spill based on partitions, based on fixed-sized state buffers, or something else?
   - Merging for final aggregate? Perhaps sort-based agg?
   
   It would be great if we could have a design doc to capture all features we need and the decisions we make for different characteristics of the queries.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1593109590

   > For group by high cardinality columns, I will do some POC to support two levels of grouping state (PartitionedHashTable).
   
   I thought DataFusion already did two level partitioned hashing but I just checked and apparently not. 
   
   For example:
   
   ```sql
   ❯ explain select avg(system_load_average_1m) from '/tmp/example' group by uid;
   +---------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------+
   | plan_type     | plan                                                                                                                                                          |
   +---------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------+
   | logical_plan  | Projection: AVG(/tmp/example.system_load_average_1m)                                                                                                          |
   |               |   Aggregate: groupBy=[[/tmp/example.uid]], aggr=[[AVG(/tmp/example.system_load_average_1m)]]                                                                  |
   |               |     TableScan: /tmp/example projection=[system_load_average_1m, uid]                                                                                          |
   | physical_plan | ProjectionExec: expr=[AVG(/tmp/example.system_load_average_1m)@1 as AVG(/tmp/example.system_load_average_1m)]                                                 |
   |               |   AggregateExec: mode=FinalPartitioned, gby=[uid@0 as uid], aggr=[AVG(/tmp/example.system_load_average_1m)]                                                   |
   |               |     CoalesceBatchesExec: target_batch_size=8192                                                                                                               |
   |               |       RepartitionExec: partitioning=Hash([Column { name: "uid", index: 0 }], 16), input_partitions=16                                                         |
   |               |         RepartitionExec: partitioning=RoundRobinBatch(16), input_partitions=2                                                                                 |
   |               |           AggregateExec: mode=Partial, gby=[uid@1 as uid], aggr=[AVG(/tmp/example.system_load_average_1m)]                                                    |
   |               |             ParquetExec: file_groups={2 groups: [[private/tmp/example/1.parquet], [private/tmp/example/2.parquet]]}, projection=[system_load_average_1m, uid] |
   |               |                                                                                                                                                               |
   +---------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------+
   ```
   
   
   This plan partitions on the group key `uid` (`RepartitionExec: partitioning=Hash([Column { name: "uid", index: 0 }], 16)`) **after** the first `AggregateExec`.
   
   Repartioning **before** the first AggregateExec is what is needed (so that each of the first level hash tables has a distinct set of keys and the hash tables can be smaller and more efficient). So instead of 
   
   ```
   AggregateExec: mode=FinalPartitioned
     RepartitionExec: partitioning=Hash([Column { name: "uid", index: 0 }], 16)
       RepartitionExec: partitioning=RoundRobinBatch(16), 
         AggregateExec: mode=Partial, gby=[uid@1 as uid], 
          ParquetExec: file_groups=...
   ```
   
   The plan would look something like
   ```
   AggregateExec: mode=FinalPartitioned
     AggregateExec: mode=Partial, gby=[uid@1 as uid], 
       RepartitionExec: partitioning=Hash([Column { name: "uid", index: 0 }], 16) <-- this is done prior to aggregation
          ParquetExec: file_groups=...
   ```
   
   The potential downside is that the hash function needs to be computed on more rows and the repartitioning happens prior to the first level aggregation which would be a slow down for low cardinality
   
   The more sophisticated version I think would have *3* aggregates
   
   ```
   AggregateExec: mode=FinalPartitioned
     AggregateExec: mode=Partial, gby=[uid@1 as uid],
       RepartitionExec: partitioning=Hash([Column { name: "uid", index: 0 }], 16) 
         AggregateExec: mode=PartialSmall, gby=[uid@1 as uid], <-- this is done prior to aggregation to reduce low cardinality inputs. The idea would be that the operator would have a small hash table (a few MB?) and dump to the output when the table is full
            ParquetExec: file_groups=...
   ```
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] tustvold commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1608940763

   > The per-group type dispatching overhead is not the major bottleneck
   
   I agree 100%, the issue is the per-group dispatching and state-management overheads. This is what destroys performance for high-cardinality grouping and is what the proposal aims to address. The fact the proposal also eliminates the type-dispatching overheads is a happy accident.
   
   > If we let each Accumulator manages its own state, I guess there will be more random memory access.
   
   The output of the accumulators is a columnar representation per aggregator. The current approach uses a row format to store intermediate state, converting back to this columnar representation on flush. It is unclear to me why this would be advantageous, if anything it seems like it would lead to more random memory accesses.
   
   > The random memory access and mem stall should be the major bottleneck in the case of high cardinality grouping
   
   Assuming relatively cheap aggregators like count or max, I personally would expect the hash table logic to be the bottleneck, but perhaps that is what you are alluding to here. The cost of updating the aggregators once the groups have been identified should be a rounding error if done properly in a columnar fashion.
   
   I suspect rather than having discussions about theoretical performance characteristics, it is probably worth prototyping and collecting some empirical data. I can try to find some time in the coming weeks. Whilst I expect good things, even if the performance is only an incremental improvement, I think the proposal provides a huge improvement to code quality and maintainability which I personally think is extremely important.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1608219118

   > Am I missing something here as to why we would need to do something different?
   
   I think @yjshen  was wondering how the proposed design would handle additional functionality in the future (like spilling to disk, or non-fixed size intermediates). 


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] Dandandan commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1609329395

   And I'm quite positive this direction can yield some non-trivial speed up :)


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb closed issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed issue #4973: Improve the performance of `Aggregator`, grouping, aggregation
URL: https://github.com/apache/arrow-datafusion/issues/4973


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] Dandandan commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1611735883

   Thanks @sunchao 
   
   We use a vectorized approach already in the hash join (hashing/ probing). I'm interested in the benchmark results compared to duckdb / photon. We still use a default hashtable instead of the bucketing approach mentioned in the monetdb paper. I previously failed to achieve improved performance with the bucketing approach as e.g. used in the MonetDB paper https://dare.uva.nl/search?identifier=5ccbb60a-38b8-4eeb-858a-e7735dd37487, but this might be improved now that other steps are vectorized.
   
   As mentioned we're not fully using vectorization in hash aggregate: only the hashing step is now vectorized (`create_hashes`).


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] Dandandan commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1611941686

   I did some further experiment in the bucketing to see if this is still the case today [branch](https://github.com/apache/arrow-datafusion/commits/bucketing). 
   This is very close to the description in the above MonetDB paper and written about here https://www.cockroachlabs.com/blog/vectorized-hash-joiner/ but doesn't really improve join performance, even when creating buckets to avoid collisions:
   ```
   ┏━━━━━━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
   ┃ Query        ┃     main ┃ bucketing ┃        Change ┃
   ┡━━━━━━━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
   │ QQuery 1     │ 191.85ms │  190.28ms │     no change │
   │ QQuery 2     │  61.98ms │   64.53ms │     no change │
   │ QQuery 3     │  50.88ms │   56.76ms │  1.12x slower │
   │ QQuery 4     │  39.03ms │   35.95ms │ +1.09x faster │
   │ QQuery 5     │  99.29ms │   98.34ms │     no change │
   │ QQuery 6     │  10.39ms │   10.32ms │     no change │
   │ QQuery 7     │ 206.01ms │  219.09ms │  1.06x slower │
   │ QQuery 8     │  76.13ms │   70.68ms │ +1.08x faster │
   │ QQuery 9     │ 146.93ms │  151.70ms │     no change │
   │ QQuery 10    │ 105.55ms │   99.88ms │ +1.06x faster │
   │ QQuery 11    │  49.42ms │   50.23ms │     no change │
   │ QQuery 12    │  68.90ms │   69.53ms │     no change │
   │ QQuery 13    │ 187.72ms │  204.39ms │  1.09x slower │
   │ QQuery 14    │  13.09ms │   13.09ms │     no change │
   │ QQuery 15    │  23.09ms │   24.37ms │  1.06x slower │
   │ QQuery 16    │  51.90ms │   55.24ms │  1.06x slower │
   │ QQuery 17    │ 699.28ms │  687.04ms │     no change │
   │ QQuery 18    │ 535.28ms │  540.28ms │     no change │
   │ QQuery 19    │  57.93ms │   58.78ms │     no change │
   │ QQuery 20    │ 209.35ms │  205.46ms │     no change │
   │ QQuery 21    │ 269.83ms │  303.29ms │  1.12x slower │
   │ QQuery 22    │  28.59ms │   32.93ms │  1.15x slower │
   └──────────────┴──────────┴───────────┴───────────────┘
   ```


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] vincev commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "vincev (via GitHub)" <gi...@apache.org>.
vincev commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1619815087

   @alamb spent a bit of time looking at the median aggregator, I was able to reduce the time from ~22secs to ~2secs by reducing the number of allocations:
   
   ```
   $ time ./target/release/datafusion-median
   +--------------+--------------+----------+
   | payment_type | total_amount | n        |
   +--------------+--------------+----------+
   | 5            | 5.275        | 6        |
   | 3            | 7.7          | 194323   |
   | 4            | -6.8         | 244364   |
   | 0            | 23.0         | 1368303  |
   | 2            | 13.3         | 7763339  |
   | 1            | 16.56        | 30085763 |
   +--------------+--------------+----------+
   
   real    0m2.514s
   user    0m4.725s
   sys     0m1.765s
   ```
   
   I have created https://github.com/apache/arrow-datafusion/pull/6837.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] tustvold commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1456366407

   What do people think about implementing the strategy as described here - https://github.com/apache/arrow-datafusion/issues/2723#issuecomment-1324876060 and then revisiting the question of whether we keep additional fallback approaches based on empirical evidence as to their performance characteristics.
   
   If this proves to outperform all the existing implementations, there is no harm in removing the other approaches, if it does not we can keep them


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] sunchao commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "sunchao (via GitHub)" <gi...@apache.org>.
sunchao commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1460948372

   I'm actually working on some POC to improve the hash aggregation performance, following a very similar approach. The only difference is that I'm not using `Rows` in the `update_batch` API, but rather the row format defined in DF: it seems the `Rows` in `arrow-rs` incurs extra costs because it is designed for sort and requires order preserving, and the cost is especially high for dictionary encoded arrays.
   
   The approach requires quite a few API changes. I was able to see a big improvement for simple cases at least - haven't done comprehensive benchmarks.
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] tustvold commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1461004722

   > For dictionary array at least
   
   Aah, yeah dictionaries are expensive as it has to compute a combined dictionary. I'm curious what the DF format is doing here, is it just hydrating all the values?


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] mingmwang commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "mingmwang (via GitHub)" <gi...@apache.org>.
mingmwang commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1493939474

   https://github.com/apache/arrow-datafusion/pull/5837
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] tustvold commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1608203572

   > how will the new design deal with memory limit
   
   I would anticipate this working in much the same way as it currently does with the [`Accumulator`](https://docs.rs/datafusion/latest/datafusion/physical_plan/trait.Accumulator.html) interface which is also stateful. The only difference would be using `ScalarValue` instead of `ArrayRef`. Am I missing something here as to why we would need to do something different?


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1608258253

   I think that is an excellent answer 🎉 


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] Dandandan commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1609327645

   One earlier suggestion in the comment I found interesting by @tustvold is the ability to store the data inline (in the hashtable) vs storing it in a `Vec`-like container. In some cases (e.g. count/sum) this might have some benefit (perf/memory) over keeping only indices to external array.
   
   There is some overlap with hash join - In https://github.com/apache/arrow-datafusion/pull/6724 added the ability to vectorize the hash collision checks (using `eq`/`take`) .
   If we move away from converting to Row-format and this approach can be re-used here as well.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] mingmwang commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "mingmwang (via GitHub)" <gi...@apache.org>.
mingmwang commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1608796360

   @alamb @tustvold 
   
   If I understand correctly, in this new proposal, we will not use the `Row Layout` to manage the `Accumulator` states, right?
   I think the `Row Layout` is still useful in the case of high cardinality grouping along with multiple `Accumulators` (avg, min, max,..).   With the `Row Layout`, the states of multiple `Accumulators` belong to the same group can be updated in the tight loop. If we let each `Accumulator` manages its own state, I guess there will be more random memory access.
   
   And below is my observation:
   
   1).  The per-group type dispatching overhead is not the major bottleneck, that's also why the PR #6657 only get 10%~ 15%
   performance gain. 
   2).  The random memory access and mem stall should be the major bottleneck in the case of high cardinality grouping .
   
   And I checked DuckDB's source code, looks like they also use the  `Row Layout` to manage the aggregator states.
   They use C++ templates in the state update functions also. I'm going to take a closer look at the source code this week and next week.
   
   https://github.com/duckdb/duckdb/blob/e49cf8132dc07324e0bb165593c8160837fcef3a/src/include/duckdb/common/types/row/row_layout.hpp
   
   
   
   
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] vincev commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "vincev (via GitHub)" <gi...@apache.org>.
vincev commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1618619316

   I am adding this comment here instead of opening a new issue as it looks the above PRs may fix/improve but please let me know if you would like a new issue.
   
   I am experimenting with using datafusion instead of Polars as query engine for dply-rs and I have noticed that group by median is more than ~20x slower (I run these a few times the timing is consistent):
   
   The Polars version:
   
   ```
   $ time ./target/release/polars-median
   shape: (6, 3)
   ┌──────────────┬──────────────┬──────────┐
   │ payment_type ┆ total_amount ┆ n        │
   │ ---          ┆ ---          ┆ ---      │
   │ i64          ┆ f64          ┆ u32      │
   ╞══════════════╪══════════════╪══════════╡
   │ 5            ┆ 5.275        ┆ 6        │
   │ 3            ┆ 7.7          ┆ 194323   │
   │ 4            ┆ -6.8         ┆ 244364   │
   │ 0            ┆ 23.0         ┆ 1368303  │
   │ 2            ┆ 13.3         ┆ 7763339  │
   │ 1            ┆ 16.56        ┆ 30085763 │
   └──────────────┴──────────────┴──────────┘
   
   real    0m0.551s
   user    0m1.654s
   sys     0m0.253s
   ```
   datafusion version:
   
   ```
   $ time ./target/release/datafusion-median
   +--------------+--------------+----------+
   | payment_type | total_amount | n        |
   +--------------+--------------+----------+
   | 5            | 5.275        | 6        |
   | 3            | 7.7          | 194323   |
   | 4            | -6.8         | 244364   |
   | 0            | 23.0         | 1368303  |
   | 2            | 13.3         | 7763339  |
   | 1            | 16.56        | 30085763 |
   +--------------+--------------+----------+
   
   real    0m22.681s
   user    1m54.036s
   sys     0m3.001s
   ```
   
   This is using one year of data from the [nyctaxi](https://www.nyc.gov/site/tlc/about/tlc-trip-record-data.page) dataset.
   
   The Datafusion code:
   
   ```rust
   use anyhow::Result;
   use datafusion::prelude::*;
   
   #[tokio::main]
   async fn main() -> Result<()> {
       let ctx = SessionContext::new();
       let df = ctx
           .read_parquet("./data/*.parquet", Default::default())
           .await?;
       df.aggregate(
           vec![col("payment_type")],
           vec![
               median(col("total_amount")).alias("total_amount"),
               count(lit(1)).alias("n"),
           ],
       )?
       .sort(vec![col("n").sort(true, false)])?
       .show()
       .await?;
       Ok(())
   }
   ```
   
   The Polars code:
   
   ```rust
   use anyhow::Result;
   use polars::prelude::*;
   
   fn main() -> Result<()> {
       let lazy = LazyFrame::scan_parquet("./data/*.parquet", ScanArgsParquet::default())?;
       let df = lazy
           .groupby([col("payment_type")])
           .agg([col("total_amount").median(), col("total_amount").count().alias("n")])
           .sort("n", Default::default())
           .collect()?;
       println!("{}", df);
   
       Ok(())
   }
   ```
   
   
   
   
   
   
   
   
   
   
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] alamb commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregation

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1614658561

   > Based on the test result, I would like do another POC and implement a new Accumulator framework. The Accumulator framework will follow your suggestions in the new Accumulator API proposal and will combine the normal Accumulator
   
   Sounds like a great idea @mingmwang  ❤️  -- Note I also got super excited about this project and I am in the middle of implementing a POC for the proposed approach -- you can see the structure I have so far here https://github.com/apache/arrow-datafusion/pull/6800. I am hoping to have some numbers ready to report today 
   
   If you also do a POC that will be great and we can compare the results and pick the one that shows the greatest promise.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] tustvold commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1458099098

   > introduce much more random memory access state update
   
   The cache locality is actually likely better as the aggregated values can be stored inline within the hash table as they are known at compile time. Similarly the row format stores consecutive rows contiguously in memory, and so you have very good locality from that perspective as well.
   
   > I would like to try JIT
   
   I think if we can get competitive performance without having to reach for JIT I think that is a massive win to maintainability. I originally reached for a JIT when creating the row format, and came to the conclusion it is a huge additional complexity that needs to yield order of magnitude performance improvements to justify itself. In the case of the row format the JIT approach was actually slower, than a correctly vectorised version. That's not to say we couldn't use a JIT, just it should definitely not be the first thing we try.
   
   > is a fundamental change
   
   I see no reason to be fundamentalist here, we can support multiple approaches so long as they provide benefits to certain workloads. I suggest we move ahead with a POC and get some real performance data
   


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] sunchao commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "sunchao (via GitHub)" <gi...@apache.org>.
sunchao commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1460990408

   For dictionary array at least, it stands out in the profiling result:
   
   <img width="2059" alt="Screenshot 2023-03-08 at 2 39 13 PM" src="https://user-images.githubusercontent.com/506679/223867552-265deefd-6e30-4801-a91b-2e6f56bd0b22.png">
   
   I feel for aggregate buffers, it's just simpler to use the native format of the data types (with null bits separated). 


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] tustvold commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1461028917

   Hmm... Perhaps I could add an option to RowConverter to hydrate dictionaries to allow trading off space in this way 🤔
   
   The main reason advantage of the arrow format, aside from reducing the number of formats we need to maintain, is so that aggregators can easily spill sorted state, which can then be cheaply recombined.


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] ozankabak commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1461188543

   > The main advantage of the arrow format, aside from reducing the number of formats we need to maintain, is so that aggregators can easily spill sorted state, which can then be cheaply recombined.
   
   Agreed 👍 
   
   > Hmm... Perhaps I could add an option to RowConverter to hydrate dictionaries to allow trading off space in this way 🤔
   
   This sounds reasonable (at least at first thought)


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


[GitHub] [arrow-datafusion] crepererum commented on issue #4973: Improve the performance of `Aggregator`, grouping, aggregaton

Posted by "crepererum (via GitHub)" <gi...@apache.org>.
crepererum commented on issue #4973:
URL: https://github.com/apache/arrow-datafusion/issues/4973#issuecomment-1457962122

   To clarify the situation around the row format:
   
   @tustvold and I think:
   
   - **group key:** That it should be sufficient to use the arrow row format for the group key. This is already done and proofed to be a perf win)
   - **group state:** That the group state should be implemented by the aggregator (hence you get an internal hash table per aggregator) instead of using the compact DF row format. This is what we're discussing here, i.e. what keeps the state for a group (there are multiple groups and potentially multiple aggregators). 
   
   The current compact aggregation looks roughly as following:
   
   - you have two `dyn RowAccumulator` and the untyped `aggregation_buffer`
   - first you calculate the group key based on the arrow row format, then you reshuffle the input so that groups are put together (sort by group key)
   - then you feed every group record batch and a view into the untyped bufffer into `RowAccumulator::update_batch` (this is a dyn dispatch per group per accumulator)
   
   Our proposal would be:
   
   - calculate group key
   - feed input columns + group key cols into `Accumulator`. This is one dyn dispatch per accumulator
   
   Now in our proposal you CAN still use reshuffle + flat state buffer, but in many cases it might be cheaper to just iterate over the input and do the aggregation directly (reshuffle VS hash multiple times).
   
   So technically NOTHING would change when this proposal is implemented, just that the aggregator operator no longer needs to care about "is this a compact aggregator or a non-compact one" and that the buffers are owned by the aggregators instead of flying around. However the change provides a base to simplify aggregators or to make them even faster w/ more hacks (if we want).


-- 
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.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org