You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "Dandandan (via GitHub)" <gi...@apache.org> on 2023/03/03 18:39:15 UTC
[GitHub] [arrow-datafusion] Dandandan opened a new issue, #5472: Speed up `DistinctCountAccumulator`
Dandandan opened a new issue, #5472:
URL: https://github.com/apache/arrow-datafusion/issues/5472
**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
Currently the code uses a `HashSet<ScalarValue>` to track unique keys, which is slow and uses more memory than needed.
**Describe the solution you'd like**
Use a typed array for storing the entries & keep a hashmap.
We can use the same approach as present in the dictionary builders (`PrimitiveDictionaryBuilder`) or parquet `Interner` contributed by @tustvold.
**Describe alternatives you've considered**
A clear and concise description of any alternative solutions or features you've considered.
**Additional context**
Add any other context or screenshots about the feature request here.
--
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] Dandandan commented on issue #5472: Speed up `DistinctCountAccumulator`
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #5472:
URL: https://github.com/apache/arrow-datafusion/issues/5472#issuecomment-1646970253
I tried to prototype a solution.
I think we need more than just storing a `HashSet` as the distinct count needs to be distinct *per group index* not just overall number of distinct values (that's why the original has to use a `HashMap` per accumulator). It needs to keep track of the unique values per group index and produce them (as list) to compute the the final count per group index.
I think an efficient way to store the data for primitives could be the following:
```
PrimitiveDistinctCountGroupsAccumulator<T: ArrowPrimitiveType> {
// stores unique group index + index of value in `values` for this group index
uniques: RawTable<(usize, usize)>,
/// stores the unique values
values: Vec<T::Native>,
/// Stores the index (+1) of the first value for index (0 is end of list)
/// The value is stored in`values`, the next (possible) index in `next`
/// First item for group index is stored at group index
first: Vec<usize>,
/// Stores the location (+1) of the next value (0 is end of list)
next: Vec<usize>,
/// Track nulls in the input / filters
null_state: NullState,
/// stores number of groups (to produce state)
total_num_groups: usize,
/// random state
random_state: RandomState
}
```
`uniques` stores the group id + index to the value.
We can use a similar datastructure as in the hash join to store the data in a chained list datastructure in a single `Vec`.
This makes it possible to produce a list array for each group index.
--
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] comphead commented on issue #5472: Speed up `DistinctCountAccumulator`
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on issue #5472:
URL: https://github.com/apache/arrow-datafusion/issues/5472#issuecomment-1458516562
Hi @Dandandan I was crawling through the dictionary builder implementation.
It has 3-in-1 : keys array, values array and a hashmap, won't be that causing an overhead?
Please elaborate if we can try a simple `HashSet<ArrowPrimitiveType>` as an alternative?
--
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 #5472: Speed up `DistinctCountAccumulator`
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #5472:
URL: https://github.com/apache/arrow-datafusion/issues/5472#issuecomment-1638071930
I think we could make COUNT DISTINCT go much faster if implemented via `HashSet<ArrowPrimitiveType>`. If that was implemented as a `GroupsAccumuluator` I suspect COUNT DISTINCT would be relatively screaming
--
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 #5472: Speed up `DistinctCountAccumulator`
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #5472:
URL: https://github.com/apache/arrow-datafusion/issues/5472#issuecomment-1638263130
I wonder how a `GroupsAccumulator` implementation could look like.
Make something like a `HashSet<(u64, OwnedRow>)` (index + row content) or `HashSet<(u64, ArrowPrimitiveType>)` for single rows / primitive type.
A way to make it even faster is to use `create_hashes` + memoize hashes (i.e. also store hash in table) and use the `RawTable` API.
Also there are probably more opportunities to rewrite queries (i.e. rewrite `select distinct` + `join` on the group by keys might work faster in some cases).
--
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 #5472: Speed up `DistinctCountAccumulator`
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #5472:
URL: https://github.com/apache/arrow-datafusion/issues/5472#issuecomment-1648467687
Storing chained values seems like a neat idea -- if you plan to use it for the Join maybe we could make it its own data structure and reuse in both places. 🤔
--
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 #5472: Speed up `DistinctCountAccumulator`
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #5472:
URL: https://github.com/apache/arrow-datafusion/issues/5472#issuecomment-1638619181
I was thinking something like the following (templated on primitive type):
```rust
struct CountDistinctGroupsAccumulator<T: ArrowPrimitiveType> {
values: HashSet<T>,
}
```
Then use `DataType::List` as we do today to pass intermediate state
> Also there are probably more opportunities to rewrite queries (i.e. rewrite select distinct + join on the group by keys might work faster in some cases).
that is also quite interesting
--
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] Speed up `DistinctCountAccumulator` [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #5472:
URL: https://github.com/apache/arrow-datafusion/issues/5472#issuecomment-1919603567
FWIW we made great progress in https://github.com/apache/arrow-datafusion/pull/8849 and https://github.com/apache/arrow-datafusion/pull/8721
The remaining types that might be important are Binary/LargeBinary but I would be inclined to close this ticket as complete now that we have fast count distinct for integers and strings
--
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 #5472: Speed up `DistinctCountAccumulator`
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #5472:
URL: https://github.com/apache/arrow-datafusion/issues/5472#issuecomment-1454123133
FYI @comphead For dictionary implementation see e.g. https://docs.rs/arrow-array/34.0.0/src/arrow_array/builder/primitive_dictionary_builder.rs.html#82
--
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] Speed up `DistinctCountAccumulator` [arrow-datafusion]
Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen closed issue #5472: Speed up `DistinctCountAccumulator`
URL: https://github.com/apache/arrow-datafusion/issues/5472
--
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] Speed up `DistinctCountAccumulator` [arrow-datafusion]
Posted by "yjshen (via GitHub)" <gi...@apache.org>.
yjshen commented on issue #5472:
URL: https://github.com/apache/arrow-datafusion/issues/5472#issuecomment-1971875367
Since #8827 has been merged(including the support for both Binary/LargeBinary), I think it's okay to close this one.
--
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 #5472: Speed up `DistinctCountAccumulator`
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #5472:
URL: https://github.com/apache/arrow-datafusion/issues/5472#issuecomment-1454019526
I'm not intimately familiar with this operator, but if it needs to support tuples or nested types the row format might be an option. You can implement the operator using rows and convert to OwnedRow to store in a HashSet
--
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