thinkharderdev commented on issue #13433: URL: https://github.com/apache/datafusion/issues/13433#issuecomment-2529946997
> TBH the last two batches are rather hard: > > ## `hashbrown` 0.14 & allocation size > `hashbrown` 0.14 doesn't expose the allocation size for `HashTable` which we would need here: > > https://github.com/apache/datafusion/blob/47569b21c50eab42771ca62fd237f429362e8a62/datafusion/physical-plan/src/joins/stream_join_utils.rs#L152-L158 > > `hashbrown` 0.15 [offers that](https://docs.rs/hashbrown/latest/hashbrown/struct.HashTable.html#method.allocation_size), but then we have to roll the `RawTable`->`HashTable` change together with the upgrade, not as separate steps. > > ## `ArrowHashTable` > This is a bit of a wild interface and I dunno if it's worth the 15% uplift TBH: > > https://github.com/apache/datafusion/blob/47569b21c50eab42771ca62fd237f429362e8a62/datafusion/physical-plan/src/aggregates/topk/hash_table.rs#L63-L86 > > The issue here is that `HashTable` doesn't offer an unsafe "directly address the bucket via index" kind of interface because it is fundamentally rather risky. I wonder if we should somewhat redesign this part. As far as I understand, this uses the following concepts: > > 1. **data heap:** a "heap" (which I guess is just a vector) to store the actual payload data > 2. **mutable slot:** a slot that stores a mutable index to the _data heap_. I guess this is used to update the data pointer whenever a new/better value was found. The slots are referenced by a simple `usize` index. > 3. **key lookup:** A way to lookup of key->_mutable slot_. > > The current solution fuses 2 & 3 into a single `RawTable` w/ a LOT of unsafe. I think we could deconstruct that into a `HashTable` (for 3) + `Vec` (for 2). This can be done BEFORE the `hashbrown` 0.15 update. The basic idea is just a hash map where the values are sorted so you can use as a combo aggregation by key + topk heap. @avantgardnerio and I went through a couple iterations on the design and landed on this because it doesn't regress performance when the grouping key is low cardinality. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
