You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "tustvold (via GitHub)" <gi...@apache.org> on 2023/07/20 18:25:25 UTC
[GitHub] [arrow-datafusion] tustvold opened a new pull request, #7043: Specialize primitive group values
tustvold opened a new pull request, #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043
# Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
Part of #6969
# Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
```
--------------------
Benchmark tpch_mem.json
--------------------
┏━━━━━━━━━━━━━━┳━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query ┃ main ┃ specialize-primitive-group-values ┃ Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1 │ 385.21ms │ 384.94ms │ no change │
│ QQuery 2 │ 102.04ms │ 91.22ms │ +1.12x faster │
│ QQuery 3 │ 104.50ms │ 108.36ms │ no change │
│ QQuery 4 │ 69.37ms │ 72.72ms │ no change │
│ QQuery 5 │ 234.38ms │ 248.42ms │ 1.06x slower │
│ QQuery 6 │ 28.62ms │ 28.20ms │ no change │
│ QQuery 7 │ 550.32ms │ 577.73ms │ no change │
│ QQuery 8 │ 160.42ms │ 153.16ms │ no change │
│ QQuery 9 │ 348.10ms │ 350.41ms │ no change │
│ QQuery 10 │ 201.04ms │ 205.85ms │ no change │
│ QQuery 11 │ 95.55ms │ 100.06ms │ no change │
│ QQuery 12 │ 112.20ms │ 112.50ms │ no change │
│ QQuery 13 │ 199.70ms │ 163.78ms │ +1.22x faster │
│ QQuery 14 │ 30.56ms │ 31.35ms │ no change │
│ QQuery 15 │ 34.63ms │ 30.74ms │ +1.13x faster │
│ QQuery 16 │ 104.27ms │ 107.38ms │ no change │
│ QQuery 17 │ 582.36ms │ 487.69ms │ +1.19x faster │
│ QQuery 18 │ 994.82ms │ 900.53ms │ +1.10x faster │
│ QQuery 19 │ 112.26ms │ 109.53ms │ no change │
│ QQuery 20 │ 204.93ms │ 212.06ms │ no change │
│ QQuery 21 │ 695.60ms │ 690.43ms │ no change │
│ QQuery 22 │ 55.44ms │ 55.59ms │ no change │
└──────────────┴──────────┴───────────────────────────────────┴───────────────┘
```
# What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
# Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
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 pull request #7043: Specialize single column primitive group values
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#issuecomment-1645484618
FYI @yahoNanJing -- I think this PR will make it even easier to evaluate the improvements that a fixed width arrow row format would provide (We can make a specialized GroupsValue under the correct circumstances)
--
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 merged pull request #7043: Specialize single column primitive group values
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold merged PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043
--
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 a diff in pull request #7043: Specialize primitive group values
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269820180
##########
datafusion/core/src/physical_plan/aggregates/row_hash.rs:
##########
@@ -59,181 +56,6 @@ pub(crate) enum ExecutionState {
use super::order::GroupOrdering;
use super::AggregateExec;
-/// An interning store for group keys
-trait GroupValues: Send {
- /// Calculates the `groups` for each input row of `cols`
- fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()>;
-
- /// Returns the number of bytes used by this [`GroupValues`]
- fn size(&self) -> usize;
-
- /// Returns true if this [`GroupValues`] is empty
- fn is_empty(&self) -> bool;
-
- /// The number of values stored in this [`GroupValues`]
- fn len(&self) -> usize;
-
- /// Emits the group values
- fn emit(&mut self, emit_to: EmitTo) -> Result<Vec<ArrayRef>>;
-}
-
-/// A [`GroupValues`] making use of [`Rows`]
-struct GroupValuesRows {
Review Comment:
This is moved into a new module
--
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 a diff in pull request #7043: Specialize primitive group values
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269928090
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
+ /// The group index of the null value if any
+ null_group: Option<usize>,
+ /// The values for each group index
+ values: Vec<T::Native>,
+ /// The random state used to generate hashes
+ random_state: RandomState,
+}
+
+impl<T: ArrowPrimitiveType> GroupValuesPrimitive<T> {
+ pub fn new(data_type: DataType) -> Self {
+ assert!(PrimitiveArray::<T>::is_compatible(&data_type));
+ Self {
+ data_type,
+ map: RawTable::with_capacity(128),
+ values: Vec::with_capacity(128),
+ null_group: None,
+ random_state: Default::default(),
+ }
+ }
+}
+
+impl<T: ArrowPrimitiveType> GroupValues for GroupValuesPrimitive<T>
+where
+ T::Native: HashValue,
+{
+ fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()> {
+ assert_eq!(cols.len(), 1);
+ groups.clear();
+
+ for v in cols[0].as_primitive::<T>() {
+ let group_id = match v {
+ None => *self.null_group.get_or_insert_with(|| {
+ let group_id = self.values.len();
+ self.values.push(Default::default());
+ group_id
+ }),
+ Some(key) => {
+ let state = &self.random_state;
+ let hash = key.hash(state);
+ let insert = self.map.find_or_find_insert_slot(
+ hash,
+ |g| unsafe { self.values.get_unchecked(*g).is_eq(key) },
+ |g| unsafe { self.values.get_unchecked(*g).hash(state) },
+ );
+
+ // SAFETY: No mutation occurred since find_or_find_insert_slot
+ unsafe {
+ match insert {
+ Ok(v) => *v.as_ref(),
+ Err(slot) => {
+ let g = self.values.len();
+ self.map.insert_in_slot(hash, slot, g);
Review Comment:
It is accounted in the size method
--
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 a diff in pull request #7043: Specialize single column primitive group values
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1270442893
##########
datafusion/core/src/physical_plan/aggregates/group_values/mod.rs:
##########
@@ -0,0 +1,65 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use arrow_array::{downcast_primitive, ArrayRef};
+use arrow_schema::SchemaRef;
+use datafusion_common::Result;
+use datafusion_physical_expr::EmitTo;
+
+mod primitive;
+use primitive::GroupValuesPrimitive;
+
+mod row;
+use row::GroupValuesRows;
+
+/// An interning store for group keys
+pub trait GroupValues: Send {
+ /// Calculates the `groups` for each input row of `cols`
+ fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()>;
+
+ /// Returns the number of bytes used by this [`GroupValues`]
+ fn size(&self) -> usize;
+
+ /// Returns true if this [`GroupValues`] is empty
+ fn is_empty(&self) -> bool;
+
+ /// The number of values stored in this [`GroupValues`]
+ fn len(&self) -> usize;
+
+ /// Emits the group values
+ fn emit(&mut self, emit_to: EmitTo) -> Result<Vec<ArrayRef>>;
+}
+
+pub fn new_group_values(schema: SchemaRef) -> Result<Box<dyn GroupValues>> {
+ if schema.fields.len() == 1 {
+ let d = schema.fields[0].data_type();
+
+ macro_rules! downcast_helper {
+ ($t:ty, $d:ident) => {
+ return Ok(Box::new(GroupValuesPrimitive::<$t>::new($d.clone())))
+ };
+ }
+
+ // TODO: More primitives
Review Comment:
Is this still relevant?
--
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 a diff in pull request #7043: Specialize single column primitive group values
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1270832361
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
+ /// The group index of the null value if any
+ null_group: Option<usize>,
+ /// The values for each group index
+ values: Vec<T::Native>,
+ /// The random state used to generate hashes
+ random_state: RandomState,
+}
+
+impl<T: ArrowPrimitiveType> GroupValuesPrimitive<T> {
+ pub fn new(data_type: DataType) -> Self {
+ assert!(PrimitiveArray::<T>::is_compatible(&data_type));
+ Self {
+ data_type,
+ map: RawTable::with_capacity(128),
+ values: Vec::with_capacity(128),
+ null_group: None,
+ random_state: Default::default(),
+ }
+ }
+}
+
+impl<T: ArrowPrimitiveType> GroupValues for GroupValuesPrimitive<T>
+where
+ T::Native: HashValue,
+{
+ fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()> {
+ assert_eq!(cols.len(), 1);
+ groups.clear();
+
+ for v in cols[0].as_primitive::<T>() {
+ let group_id = match v {
+ None => *self.null_group.get_or_insert_with(|| {
+ let group_id = self.values.len();
+ self.values.push(Default::default());
+ group_id
+ }),
+ Some(key) => {
+ let state = &self.random_state;
+ let hash = key.hash(state);
+ let insert = self.map.find_or_find_insert_slot(
+ hash,
+ |g| unsafe { self.values.get_unchecked(*g).is_eq(key) },
+ |g| unsafe { self.values.get_unchecked(*g).hash(state) },
+ );
+
+ // SAFETY: No mutation occurred since find_or_find_insert_slot
+ unsafe {
+ match insert {
+ Ok(v) => *v.as_ref(),
+ Err(slot) => {
+ let g = self.values.len();
+ self.map.insert_in_slot(hash, slot, g);
+ self.values.push(key);
+ g
+ }
+ }
+ }
+ }
+ };
+ groups.push(group_id)
+ }
+ Ok(())
+ }
+
+ fn size(&self) -> usize {
+ self.map.capacity() * std::mem::size_of::<usize>() + self.values.allocated_size()
+ }
+
+ fn is_empty(&self) -> bool {
+ self.values.is_empty()
+ }
+
+ fn len(&self) -> usize {
+ self.values.len()
+ }
+
+ fn emit(&mut self, emit_to: EmitTo) -> Result<Vec<ArrayRef>> {
+ fn build_primitive<T: ArrowPrimitiveType>(
+ values: Vec<T::Native>,
+ null_idx: Option<usize>,
+ ) -> PrimitiveArray<T> {
+ let nulls = null_idx.map(|null_idx| {
+ let mut buffer = BooleanBufferBuilder::new(values.len());
+ buffer.append_n(values.len(), true);
+ buffer.set_bit(null_idx, false);
+ unsafe { NullBuffer::new_unchecked(buffer.finish(), 1) }
+ });
+ PrimitiveArray::<T>::new(values.into(), nulls)
+ }
+
+ let array: PrimitiveArray<T> = match emit_to {
+ EmitTo::All => {
+ self.map.clear();
+ build_primitive(std::mem::take(&mut self.values), self.null_group.take())
+ }
+ EmitTo::First(n) => {
+ // SAFETY: self.map outlives iterator and is not modified concurrently
+ unsafe {
Review Comment:
There isn't an easy way to make this generic, as one stores tuples and one isn't... I at least can't see a way that doesn't just obfuscate the code
--
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 pull request #7043: Specialize single column primitive group values
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#issuecomment-1645751526
TLDR is I think this PR is good to go from a performance perspective. I don't see massive gains but I do see small improvements
--
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 a diff in pull request #7043: Specialize single column primitive group values
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1270440126
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
Review Comment:
I wonder if you tried `RawTable<(T::Native, usize)>` as well? Not sure if we could expect much benefit, maybe slightly better locality as we only have to follow one pointer.
--
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 a diff in pull request #7043: Specialize primitive group values
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269920404
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
Review Comment:
I wonder also if we can not store `T::Native` in the table now instead?
--
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 pull request #7043: Specialize primitive group values
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#issuecomment-1644664460
I just pushed a fix for the CI failure. I am now running benchmarks on this branch to confirm.
--
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 a diff in pull request #7043: Specialize primitive group values
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269874826
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
+ /// The group index of the null value if any
+ null_group: Option<usize>,
+ /// The values for each group index
+ values: Vec<T::Native>,
+ /// The random state used to generate hashes
+ random_state: RandomState,
+}
+
+impl<T: ArrowPrimitiveType> GroupValuesPrimitive<T> {
+ pub fn new(data_type: DataType) -> Self {
+ assert!(PrimitiveArray::<T>::is_compatible(&data_type));
+ Self {
+ data_type,
+ map: RawTable::with_capacity(128),
+ values: Vec::with_capacity(128),
+ null_group: None,
+ random_state: Default::default(),
+ }
+ }
+}
+
+impl<T: ArrowPrimitiveType> GroupValues for GroupValuesPrimitive<T>
+where
+ T::Native: HashValue,
+{
+ fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()> {
+ assert_eq!(cols.len(), 1);
+ groups.clear();
+
+ for v in cols[0].as_primitive::<T>() {
+ let group_id = match v {
+ None => *self.null_group.get_or_insert_with(|| {
+ let group_id = self.values.len();
+ self.values.push(Default::default());
+ group_id
+ }),
+ Some(key) => {
+ let state = &self.random_state;
+ let hash = key.hash(state);
+ let insert = self.map.find_or_find_insert_slot(
+ hash,
+ |g| unsafe { self.values.get_unchecked(*g).is_eq(key) },
Review Comment:
this is awesome 🚀
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
+ /// The group index of the null value if any
+ null_group: Option<usize>,
+ /// The values for each group index
+ values: Vec<T::Native>,
+ /// The random state used to generate hashes
+ random_state: RandomState,
+}
+
+impl<T: ArrowPrimitiveType> GroupValuesPrimitive<T> {
+ pub fn new(data_type: DataType) -> Self {
+ assert!(PrimitiveArray::<T>::is_compatible(&data_type));
+ Self {
+ data_type,
+ map: RawTable::with_capacity(128),
+ values: Vec::with_capacity(128),
+ null_group: None,
+ random_state: Default::default(),
+ }
+ }
+}
+
+impl<T: ArrowPrimitiveType> GroupValues for GroupValuesPrimitive<T>
+where
+ T::Native: HashValue,
+{
+ fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()> {
+ assert_eq!(cols.len(), 1);
+ groups.clear();
+
+ for v in cols[0].as_primitive::<T>() {
+ let group_id = match v {
+ None => *self.null_group.get_or_insert_with(|| {
+ let group_id = self.values.len();
+ self.values.push(Default::default());
+ group_id
+ }),
+ Some(key) => {
+ let state = &self.random_state;
+ let hash = key.hash(state);
+ let insert = self.map.find_or_find_insert_slot(
+ hash,
+ |g| unsafe { self.values.get_unchecked(*g).is_eq(key) },
Review Comment:
this is awesome 🚀
--
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 a diff in pull request #7043: Specialize primitive group values
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269873503
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
Review Comment:
This deviates a bit from `map: RawTable<(u64, usize)>` (i.e. storing the hash in the table as well). Previously, this was faster because of avoiding slower rehashing. I wonder how it compares now?
--
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 a diff in pull request #7043: Specialize primitive group values
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269937204
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
Review Comment:
Thanks :)
--
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 a diff in pull request #7043: Specialize primitive group values
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269929275
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
Review Comment:
This approach was faster for primitives, where computing the hashes is relatively inexpensive
--
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 a diff in pull request #7043: Specialize primitive group values
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269873503
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
Review Comment:
This deviates a bit from `map: RawTable<(u64, usize)>` (i.e. storing the hash in the table as well). Previously, this was faster because of avoiding slower rehashing (but it could be it is mostly re-hashing strings that is slow). I wonder how it compares now?
--
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 a diff in pull request #7043: Specialize single column primitive group values
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1270804057
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
Review Comment:
We can't use create_hashes as we are generating the hashes from the native values, not an array
--
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 pull request #7043: Specialize single column primitive group values
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#issuecomment-1645605424
I saw some strange results when running with this branch on my clickbench testing. Please standby
--
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 a diff in pull request #7043: Specialize primitive group values
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269874547
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
+ /// The group index of the null value if any
+ null_group: Option<usize>,
+ /// The values for each group index
+ values: Vec<T::Native>,
+ /// The random state used to generate hashes
+ random_state: RandomState,
+}
+
+impl<T: ArrowPrimitiveType> GroupValuesPrimitive<T> {
+ pub fn new(data_type: DataType) -> Self {
+ assert!(PrimitiveArray::<T>::is_compatible(&data_type));
+ Self {
+ data_type,
+ map: RawTable::with_capacity(128),
+ values: Vec::with_capacity(128),
+ null_group: None,
+ random_state: Default::default(),
+ }
+ }
+}
+
+impl<T: ArrowPrimitiveType> GroupValues for GroupValuesPrimitive<T>
+where
+ T::Native: HashValue,
+{
+ fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()> {
+ assert_eq!(cols.len(), 1);
+ groups.clear();
+
+ for v in cols[0].as_primitive::<T>() {
+ let group_id = match v {
+ None => *self.null_group.get_or_insert_with(|| {
+ let group_id = self.values.len();
+ self.values.push(Default::default());
+ group_id
+ }),
+ Some(key) => {
+ let state = &self.random_state;
+ let hash = key.hash(state);
+ let insert = self.map.find_or_find_insert_slot(
+ hash,
+ |g| unsafe { self.values.get_unchecked(*g).is_eq(key) },
+ |g| unsafe { self.values.get_unchecked(*g).hash(state) },
Review Comment:
🚀
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
+ /// The group index of the null value if any
+ null_group: Option<usize>,
+ /// The values for each group index
+ values: Vec<T::Native>,
+ /// The random state used to generate hashes
+ random_state: RandomState,
+}
+
+impl<T: ArrowPrimitiveType> GroupValuesPrimitive<T> {
+ pub fn new(data_type: DataType) -> Self {
+ assert!(PrimitiveArray::<T>::is_compatible(&data_type));
+ Self {
+ data_type,
+ map: RawTable::with_capacity(128),
+ values: Vec::with_capacity(128),
+ null_group: None,
+ random_state: Default::default(),
+ }
+ }
+}
+
+impl<T: ArrowPrimitiveType> GroupValues for GroupValuesPrimitive<T>
+where
+ T::Native: HashValue,
+{
+ fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()> {
+ assert_eq!(cols.len(), 1);
+ groups.clear();
+
+ for v in cols[0].as_primitive::<T>() {
+ let group_id = match v {
+ None => *self.null_group.get_or_insert_with(|| {
+ let group_id = self.values.len();
+ self.values.push(Default::default());
+ group_id
+ }),
+ Some(key) => {
+ let state = &self.random_state;
+ let hash = key.hash(state);
+ let insert = self.map.find_or_find_insert_slot(
+ hash,
+ |g| unsafe { self.values.get_unchecked(*g).is_eq(key) },
+ |g| unsafe { self.values.get_unchecked(*g).hash(state) },
Review Comment:
🚀
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
+ /// The group index of the null value if any
+ null_group: Option<usize>,
+ /// The values for each group index
+ values: Vec<T::Native>,
+ /// The random state used to generate hashes
+ random_state: RandomState,
+}
+
+impl<T: ArrowPrimitiveType> GroupValuesPrimitive<T> {
+ pub fn new(data_type: DataType) -> Self {
+ assert!(PrimitiveArray::<T>::is_compatible(&data_type));
+ Self {
+ data_type,
+ map: RawTable::with_capacity(128),
+ values: Vec::with_capacity(128),
+ null_group: None,
+ random_state: Default::default(),
+ }
+ }
+}
+
+impl<T: ArrowPrimitiveType> GroupValues for GroupValuesPrimitive<T>
+where
+ T::Native: HashValue,
+{
+ fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()> {
+ assert_eq!(cols.len(), 1);
+ groups.clear();
+
+ for v in cols[0].as_primitive::<T>() {
+ let group_id = match v {
+ None => *self.null_group.get_or_insert_with(|| {
+ let group_id = self.values.len();
+ self.values.push(Default::default());
+ group_id
+ }),
+ Some(key) => {
+ let state = &self.random_state;
+ let hash = key.hash(state);
+ let insert = self.map.find_or_find_insert_slot(
+ hash,
+ |g| unsafe { self.values.get_unchecked(*g).is_eq(key) },
+ |g| unsafe { self.values.get_unchecked(*g).hash(state) },
Review Comment:
🚀
--
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 pull request #7043: Specialize single column primitive group values
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#issuecomment-1644702457
My benchmark results are similar. I plan to review this PR carefully tomorrow morning
FYI @yahoNanJing
```
--------------------
Benchmark tpch_mem.json
--------------------
┏━━━━━━━━━━━━━━┳━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query ┃ main_base ┃ specialize-primitive-group-values ┃ Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1 │ 533.98ms │ 539.33ms │ no change │
│ QQuery 2 │ 144.79ms │ 128.73ms │ +1.12x faster │
│ QQuery 3 │ 154.18ms │ 151.19ms │ no change │
│ QQuery 4 │ 108.38ms │ 113.34ms │ no change │
│ QQuery 5 │ 339.26ms │ 345.13ms │ no change │
│ QQuery 6 │ 37.56ms │ 38.62ms │ no change │
│ QQuery 7 │ 810.72ms │ 762.61ms │ +1.06x faster │
│ QQuery 8 │ 222.49ms │ 233.41ms │ no change │
│ QQuery 9 │ 505.28ms │ 511.36ms │ no change │
│ QQuery 10 │ 306.53ms │ 291.01ms │ +1.05x faster │
│ QQuery 11 │ 149.93ms │ 146.22ms │ no change │
│ QQuery 12 │ 165.08ms │ 160.02ms │ no change │
│ QQuery 13 │ 284.97ms │ 241.23ms │ +1.18x faster │
│ QQuery 14 │ 44.42ms │ 43.16ms │ no change │
│ QQuery 15 │ 49.69ms │ 41.66ms │ +1.19x faster │
│ QQuery 16 │ 155.59ms │ 150.90ms │ no change │
│ QQuery 17 │ 752.18ms │ 723.37ms │ no change │
│ QQuery 18 │ 1420.88ms │ 1390.54ms │ no change │
│ QQuery 19 │ 161.97ms │ 163.11ms │ no change │
│ QQuery 20 │ 299.46ms │ 289.71ms │ no change │
│ QQuery 21 │ 1033.28ms │ 952.11ms │ +1.09x faster │
│ QQuery 22 │ 82.75ms │ 83.04ms │ no 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 a diff in pull request #7043: Specialize single column primitive group values
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1270518058
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
+ /// The group index of the null value if any
+ null_group: Option<usize>,
+ /// The values for each group index
+ values: Vec<T::Native>,
+ /// The random state used to generate hashes
+ random_state: RandomState,
+}
+
+impl<T: ArrowPrimitiveType> GroupValuesPrimitive<T> {
+ pub fn new(data_type: DataType) -> Self {
+ assert!(PrimitiveArray::<T>::is_compatible(&data_type));
+ Self {
+ data_type,
+ map: RawTable::with_capacity(128),
+ values: Vec::with_capacity(128),
+ null_group: None,
+ random_state: Default::default(),
+ }
+ }
+}
+
+impl<T: ArrowPrimitiveType> GroupValues for GroupValuesPrimitive<T>
+where
+ T::Native: HashValue,
+{
+ fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()> {
+ assert_eq!(cols.len(), 1);
+ groups.clear();
+
+ for v in cols[0].as_primitive::<T>() {
+ let group_id = match v {
+ None => *self.null_group.get_or_insert_with(|| {
+ let group_id = self.values.len();
+ self.values.push(Default::default());
+ group_id
+ }),
+ Some(key) => {
+ let state = &self.random_state;
+ let hash = key.hash(state);
+ let insert = self.map.find_or_find_insert_slot(
+ hash,
+ |g| unsafe { self.values.get_unchecked(*g).is_eq(key) },
+ |g| unsafe { self.values.get_unchecked(*g).hash(state) },
+ );
+
+ // SAFETY: No mutation occurred since find_or_find_insert_slot
+ unsafe {
+ match insert {
+ Ok(v) => *v.as_ref(),
+ Err(slot) => {
+ let g = self.values.len();
+ self.map.insert_in_slot(hash, slot, g);
+ self.values.push(key);
+ g
+ }
+ }
+ }
+ }
+ };
+ groups.push(group_id)
+ }
+ Ok(())
+ }
+
+ fn size(&self) -> usize {
+ self.map.capacity() * std::mem::size_of::<usize>() + self.values.allocated_size()
+ }
+
+ fn is_empty(&self) -> bool {
+ self.values.is_empty()
+ }
+
+ fn len(&self) -> usize {
+ self.values.len()
+ }
+
+ fn emit(&mut self, emit_to: EmitTo) -> Result<Vec<ArrayRef>> {
+ fn build_primitive<T: ArrowPrimitiveType>(
+ values: Vec<T::Native>,
+ null_idx: Option<usize>,
+ ) -> PrimitiveArray<T> {
+ let nulls = null_idx.map(|null_idx| {
+ let mut buffer = BooleanBufferBuilder::new(values.len());
+ buffer.append_n(values.len(), true);
+ buffer.set_bit(null_idx, false);
+ unsafe { NullBuffer::new_unchecked(buffer.finish(), 1) }
+ });
+ PrimitiveArray::<T>::new(values.into(), nulls)
+ }
+
+ let array: PrimitiveArray<T> = match emit_to {
+ EmitTo::All => {
+ self.map.clear();
+ build_primitive(std::mem::take(&mut self.values), self.null_group.take())
+ }
+ EmitTo::First(n) => {
+ // SAFETY: self.map outlives iterator and is not modified concurrently
+ unsafe {
Review Comment:
I think this code is largely replicated from the row version. I wonder if it could be refactored into a (templated) common function (with appropriate documentation)?
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
+ /// The group index of the null value if any
+ null_group: Option<usize>,
Review Comment:
👍
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
Review Comment:
I think this rationale (aka that not storing the hashes for primitives is because it is fast, etc) should be encoded as comments / docstrings to help future readers of this code
I of course, will be happy to add it as a follow on PR, but if you have to change this one now,
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
+ /// The group index of the null value if any
+ null_group: Option<usize>,
Review Comment:
👍
##########
datafusion/core/src/physical_plan/aggregates/group_values/row.rs:
##########
@@ -0,0 +1,184 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
Review Comment:
this code is just moved, right?
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
Review Comment:
```suggestion
/// A [`GroupValues`] storing a single column of raw primitive values
///
/// This specialization is significantly faster than using the more general
/// purpose `Row`s format
```
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
Review Comment:
Can you explain why this doesn't use `create_hash`es? And perhaps add comments in the code about the rationale?
If it is important not to use `create_hashes` I recommend
1. Move this code to `hash_utils.rs` so it is easier to find
2. Implement the `force_hash_collisions` version (that always hashes things to 0) to ensure appropriate coverage
Here is an example of `force_hash_collisions`
https://github.com/apache/arrow-datafusion/blob/368f6e606a3cfca8e04638b8d5ff0ff116a20b57/datafusion/physical-expr/src/hash_utils.rs#L214-L224
--
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 a diff in pull request #7043: Specialize primitive group values
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269929275
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
Review Comment:
This approach was faster for primitives, where computing the hashes is relatively inexpensive. I tried using `HashMap<T::Native, usize>` and it was 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] Dandandan commented on a diff in pull request #7043: Specialize primitive group values
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269886823
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
Review Comment:
It might be as well this was back when the aggregation was mostly `HashMap<Vec<ScalarValue>, Accumulator>`
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
Review Comment:
It might be as well this was back when the aggregation was mostly something like `HashMap<Vec<ScalarValue>, Accumulator>`
--
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 a diff in pull request #7043: Specialize primitive group values
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7043:
URL: https://github.com/apache/arrow-datafusion/pull/7043#discussion_r1269880848
##########
datafusion/core/src/physical_plan/aggregates/group_values/primitive.rs:
##########
@@ -0,0 +1,191 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::physical_plan::aggregates::group_values::GroupValues;
+use ahash::RandomState;
+use arrow::array::BooleanBufferBuilder;
+use arrow::buffer::NullBuffer;
+use arrow::datatypes::i256;
+use arrow_array::cast::AsArray;
+use arrow_array::{ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, PrimitiveArray};
+use arrow_schema::DataType;
+use datafusion_common::Result;
+use datafusion_execution::memory_pool::proxy::VecAllocExt;
+use datafusion_physical_expr::EmitTo;
+use half::f16;
+use hashbrown::raw::RawTable;
+use std::sync::Arc;
+
+/// A trait to allow hashing of floating point numbers
+trait HashValue {
+ fn hash(self, state: &RandomState) -> u64;
+}
+
+macro_rules! hash_integer {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self)
+ }
+ })+
+ };
+}
+hash_integer!(i8, i16, i32, i64, i128, i256);
+hash_integer!(u8, u16, u32, u64);
+
+macro_rules! hash_float {
+ ($($t:ty),+) => {
+ $(impl HashValue for $t {
+ fn hash(self, state: &RandomState) -> u64 {
+ state.hash_one(self.to_bits())
+ }
+ })+
+ };
+}
+
+hash_float!(f16, f32, f64);
+
+/// A [`GroupValues`] storing raw primitive values
+pub struct GroupValuesPrimitive<T: ArrowPrimitiveType> {
+ /// The data type of the output array
+ data_type: DataType,
+ /// Stores the group index based on the hash of its value
+ map: RawTable<usize>,
+ /// The group index of the null value if any
+ null_group: Option<usize>,
+ /// The values for each group index
+ values: Vec<T::Native>,
+ /// The random state used to generate hashes
+ random_state: RandomState,
+}
+
+impl<T: ArrowPrimitiveType> GroupValuesPrimitive<T> {
+ pub fn new(data_type: DataType) -> Self {
+ assert!(PrimitiveArray::<T>::is_compatible(&data_type));
+ Self {
+ data_type,
+ map: RawTable::with_capacity(128),
+ values: Vec::with_capacity(128),
+ null_group: None,
+ random_state: Default::default(),
+ }
+ }
+}
+
+impl<T: ArrowPrimitiveType> GroupValues for GroupValuesPrimitive<T>
+where
+ T::Native: HashValue,
+{
+ fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()> {
+ assert_eq!(cols.len(), 1);
+ groups.clear();
+
+ for v in cols[0].as_primitive::<T>() {
+ let group_id = match v {
+ None => *self.null_group.get_or_insert_with(|| {
+ let group_id = self.values.len();
+ self.values.push(Default::default());
+ group_id
+ }),
+ Some(key) => {
+ let state = &self.random_state;
+ let hash = key.hash(state);
+ let insert = self.map.find_or_find_insert_slot(
+ hash,
+ |g| unsafe { self.values.get_unchecked(*g).is_eq(key) },
+ |g| unsafe { self.values.get_unchecked(*g).hash(state) },
+ );
+
+ // SAFETY: No mutation occurred since find_or_find_insert_slot
+ unsafe {
+ match insert {
+ Ok(v) => *v.as_ref(),
+ Err(slot) => {
+ let g = self.values.len();
+ self.map.insert_in_slot(hash, slot, g);
Review Comment:
I think this should still track the allocated memory (like `insert_accounted` did?)
--
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