You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "rluvaton (via GitHub)" <gi...@apache.org> on 2025/01/19 20:42:59 UTC

[I] exposing vectorized hash table that work with `Array`s [arrow-rs]

rluvaton opened a new issue, #6996:
URL: https://github.com/apache/arrow-rs/issues/6996

   I just read the [Photon](https://cs.stanford.edu/~matei/papers/2022/sigmod_photon.pdf) paper from 2022 and saw their vectorized implementation for hash table, I also noticed that someone opened an issue in DataFusion https://github.com/apache/datafusion/issues/7095 for implementing it for group aggregate
   
   **Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
   I would like to have `HashSet`/`HashMap` that would support all Hash table functionality but with Arrays as input.
   
   Problem:
   DataFusion has `array_agg` with distinct support, if you look at the implementation it just keep adding to `HashSet`
   https://github.com/apache/datafusion/blob/6c9355d5be8b6045865fed67cb6d028b2dfc2e06/datafusion/functions-aggregate/src/array_agg.rs#L268-L281
   
   this works but can be improved with computing all the hashes first, and then do probing in a tight loop
   
   **Describe the solution you'd like**
   It would be helpful to use there and in other places a HashSet/HashMap that can
   1. Insert all values from an array
   2. Check all values in array exists and return a BooleanArray for the result
   3. Get all the values that match each key in the array
   
   **Describe alternatives you've considered**
   Implement it everywhere that need HashMap/HashSet or create external crate
   
   **Additional context**
   The way I see it there will be couple of implementation
   1. Primitive/boolean
   2. Bytes
   3. Generic that will use `arrow-row`
   
   
   I'm willing to create a PR for that. I see it as using internally the hashbrown raw API to implement 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.apache.org

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


Re: [I] Expose vectorized hash table that work with `Array`s [arrow-rs]

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

   Did you mean to file this in the datafusion repository? Hashtable implementations will necessarily be very tightly coupled with how a given query engine chooses to handle dataflow, I'm not sure a generic approach makes a whole lot of sense


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


Re: [I] Expose vectorized hash table that work with `Array`s [arrow-rs]

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

   I think it is a very good observation that there are several structures in DataFusion that basically look like hash sets / hash maps on arrays. 
   
   ```rust
   let hash_table = HashMap::new(key_array.data_type(), value_array.data_type());
   // returns a BooleanArray that 
   let inserted = hash_table.insert(key_array, value
   ```
   
   And there are similar things for Set. I am thinking specifically about code like 
   
   https://github.com/apache/datafusion/blob/274e5356ceb4c559ab4105478e75817a302d2f13/datafusion/functions-aggregate-common/src/aggregate/count_distinct/native.rs#L44-L51
   
   and 
   
   https://github.com/apache/datafusion/blob/274e5356ceb4c559ab4105478e75817a302d2f13/datafusion/functions-aggregate-common/src/aggregate/count_distinct/bytes.rs#L30-L46
   
   In my opinon  such a primitive makes a lot of sense to consider moving upstream in arrow. The open question in my mind is exactly what the API would look like
   
   Perhaps to begin with, we could begin in DataFusion refactoring the various maps / sets into an `ArrowSet` / `ArrowMap`. Once we have figured out what the API is then would be an excellent time to consider proposing upstreaming it into arrow.
   


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


Re: [I] Expose vectorized hash table that work with `Array`s [arrow-rs]

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

   > The open question in my mind is exactly what the API would look like
   
   This is the key thing IMO, I suspect either you will end up with something maximally flexible like `RawTable` but which is not very ergonomic, or something closer that's very coupled to the operation being performed, e.g. count distinct, but which isn't applicable to aggregates in general, or can't handle multiple columns, etc...
   
   I think seeing if there is a way to reduce duplication within DF would be a good first step to identify if there is a common API that can be extracted.


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