You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by ka...@apache.org on 2026/07/05 15:26:58 UTC
(datafusion) branch final-aggr-with-lazily-materialize-poc-candidate1 updated: Use dense hashes for indexed final replay
This is an automated email from the ASF dual-hosted git repository.
Rachelint pushed a commit to branch final-aggr-with-lazily-materialize-poc-candidate1
in repository https://gitbox.apache.org/repos/asf/datafusion.git
The following commit(s) were added to refs/heads/final-aggr-with-lazily-materialize-poc-candidate1 by this push:
new d596cebd5f Use dense hashes for indexed final replay
d596cebd5f is described below
commit d596cebd5f7f3b70a8be62cc7b381679a28bb444
Author: kamille <ka...@apache.org>
AuthorDate: Sun Jul 5 23:26:46 2026 +0800
Use dense hashes for indexed final replay
---
datafusion/common/src/hash_utils.rs | 118 +++++++++------------
.../src/aggregates/group_values/mod.rs | 8 +-
.../aggregates/group_values/multi_group_by/mod.rs | 71 ++++++++++---
3 files changed, 117 insertions(+), 80 deletions(-)
diff --git a/datafusion/common/src/hash_utils.rs b/datafusion/common/src/hash_utils.rs
index 66eccc46e9..7b2a7e603e 100644
--- a/datafusion/common/src/hash_utils.rs
+++ b/datafusion/common/src/hash_utils.rs
@@ -311,40 +311,38 @@ fn hash_array_primitive_indices<T>(
{
assert_eq!(
hashes_buffer.len(),
- array.len(),
- "hashes_buffer and array should be of equal length"
+ indices.len(),
+ "hashes_buffer and indices should be of equal length"
);
if array.null_count() == 0 {
if rehash {
- for &row in indices {
+ for (hash, &row) in hashes_buffer.iter_mut().zip(indices) {
let value = unsafe { array.value_unchecked(row) };
- let mut hasher =
- random_state.seeded_state(hashes_buffer[row]).build_hasher();
+ let mut hasher = random_state.seeded_state(*hash).build_hasher();
value.hash_write(&mut hasher);
- hashes_buffer[row] = hasher.finish();
+ *hash = hasher.finish();
}
} else {
- for &row in indices {
+ for (hash, &row) in hashes_buffer.iter_mut().zip(indices) {
let value = unsafe { array.value_unchecked(row) };
- hashes_buffer[row] = value.hash_one(random_state);
+ *hash = value.hash_one(random_state);
}
}
} else if rehash {
- for &row in indices {
+ for (hash, &row) in hashes_buffer.iter_mut().zip(indices) {
if array.is_valid(row) {
let value = unsafe { array.value_unchecked(row) };
- let mut hasher =
- random_state.seeded_state(hashes_buffer[row]).build_hasher();
+ let mut hasher = random_state.seeded_state(*hash).build_hasher();
value.hash_write(&mut hasher);
- hashes_buffer[row] = hasher.finish();
+ *hash = hasher.finish();
}
}
} else {
- for &row in indices {
+ for (hash, &row) in hashes_buffer.iter_mut().zip(indices) {
if array.is_valid(row) {
let value = unsafe { array.value_unchecked(row) };
- hashes_buffer[row] = value.hash_one(random_state);
+ *hash = value.hash_one(random_state);
}
}
}
@@ -408,36 +406,34 @@ fn hash_array_indices<T>(
{
assert_eq!(
hashes_buffer.len(),
- array.len(),
- "hashes_buffer and array should be of equal length"
+ indices.len(),
+ "hashes_buffer and indices should be of equal length"
);
if array.null_count() == 0 {
if rehash {
- for &row in indices {
+ for (hash, &row) in hashes_buffer.iter_mut().zip(indices) {
let value = unsafe { array.value_unchecked(row) };
- hashes_buffer[row] =
- combine_hashes(value.hash_one(random_state), hashes_buffer[row]);
+ *hash = combine_hashes(value.hash_one(random_state), *hash);
}
} else {
- for &row in indices {
+ for (hash, &row) in hashes_buffer.iter_mut().zip(indices) {
let value = unsafe { array.value_unchecked(row) };
- hashes_buffer[row] = value.hash_one(random_state);
+ *hash = value.hash_one(random_state);
}
}
} else if rehash {
- for &row in indices {
+ for (hash, &row) in hashes_buffer.iter_mut().zip(indices) {
if array.is_valid(row) {
let value = unsafe { array.value_unchecked(row) };
- hashes_buffer[row] =
- combine_hashes(value.hash_one(random_state), hashes_buffer[row]);
+ *hash = combine_hashes(value.hash_one(random_state), *hash);
}
}
} else {
- for &row in indices {
+ for (hash, &row) in hashes_buffer.iter_mut().zip(indices) {
if array.is_valid(row) {
let value = unsafe { array.value_unchecked(row) };
- hashes_buffer[row] = value.hash_one(random_state);
+ *hash = value.hash_one(random_state);
}
}
}
@@ -581,8 +577,8 @@ fn hash_generic_byte_view_array_indices<T: ByteViewType>(
) {
assert_eq!(
hashes_buffer.len(),
- array.len(),
- "hashes_buffer and array should be of equal length"
+ indices.len(),
+ "hashes_buffer and indices should be of equal length"
);
let buffers = array.data_buffers();
@@ -597,7 +593,7 @@ fn hash_generic_byte_view_array_indices<T: ByteViewType>(
let has_nulls = array.null_count() != 0;
let has_buffers = !array.data_buffers().is_empty();
- for &row in indices {
+ for (hash, &row) in hashes_buffer.iter_mut().zip(indices) {
if has_nulls && array.is_null(row) {
continue;
}
@@ -606,23 +602,22 @@ fn hash_generic_byte_view_array_indices<T: ByteViewType>(
let view_len = view as u32;
if !has_buffers || view_len <= 12 {
if rehash {
- let mut hasher =
- random_state.seeded_state(hashes_buffer[row]).build_hasher();
+ let mut hasher = random_state.seeded_state(*hash).build_hasher();
view.hash_write(&mut hasher);
- hashes_buffer[row] = hasher.finish();
+ *hash = hasher.finish();
} else {
- hashes_buffer[row] = view.hash_one(random_state);
+ *hash = view.hash_one(random_state);
}
continue;
}
let value = view_bytes(view_len, view);
if rehash {
- let mut hasher = random_state.seeded_state(hashes_buffer[row]).build_hasher();
+ let mut hasher = random_state.seeded_state(*hash).build_hasher();
value.hash_write(&mut hasher);
- hashes_buffer[row] = hasher.finish();
+ *hash = hasher.finish();
} else {
- hashes_buffer[row] = value.hash_one(random_state);
+ *hash = value.hash_one(random_state);
}
}
}
@@ -1248,14 +1243,14 @@ fn hash_null_indices<S: HashState>(
hashes_buffer: &mut [u64],
rehash: bool,
) {
+ debug_assert_eq!(hashes_buffer.len(), indices.len());
if rehash {
- for &row in indices {
- hashes_buffer[row] =
- combine_hashes(random_state.hash_one(1), hashes_buffer[row]);
+ for hash in hashes_buffer.iter_mut() {
+ *hash = combine_hashes(random_state.hash_one(1), *hash);
}
} else {
- for &row in indices {
- hashes_buffer[row] = random_state.hash_one(1);
+ for hash in hashes_buffer.iter_mut() {
+ *hash = random_state.hash_one(1);
}
}
}
@@ -1271,16 +1266,10 @@ fn hash_single_array_indices_fallback(
let take_indices =
UInt64Array::from_iter_values(indices.iter().map(|&idx| idx as u64));
let array = take(array, &take_indices, None)?;
- let mut selected_hashes = if rehash {
- indices.iter().map(|&idx| hashes_buffer[idx]).collect()
- } else {
- vec![0; indices.len()]
- };
-
- hash_single_array(array.as_ref(), random_state, &mut selected_hashes, rehash)?;
- for (&row, hash) in indices.iter().zip(selected_hashes) {
- hashes_buffer[row] = hash;
+ if !rehash {
+ hashes_buffer.fill(0);
}
+ hash_single_array(array.as_ref(), random_state, hashes_buffer, rehash)?;
Ok(())
}
@@ -1333,9 +1322,8 @@ fn hash_single_array_indices(
hashes_buffer: &mut [u64],
_rehash: bool,
) -> Result<()> {
- for &row in indices {
- hashes_buffer[row] = 0;
- }
+ debug_assert_eq!(hashes_buffer.len(), indices.len());
+ hashes_buffer.fill(0);
Ok(())
}
@@ -1399,8 +1387,8 @@ where
/// Creates hash values for selected rows, based on the values in the columns.
///
-/// `hashes_buffer` must have the same length as the input arrays. Only rows in
-/// `indices` are updated. Values outside `indices` are left unchanged.
+/// `hashes_buffer` must have the same length as `indices`. Output hashes are
+/// dense: `hashes_buffer[pos]` contains the hash for row `indices[pos]`.
pub fn create_hashes_indices<'a, I, T>(
arrays: I,
random_state: &impl HashState,
@@ -1413,16 +1401,18 @@ where
{
for (col_idx, array) in arrays.into_iter().enumerate() {
let array = array.as_dyn_array();
+ debug_assert!(
+ indices.iter().all(|&idx| idx < array.len()),
+ "indices should be within array bounds"
+ );
assert_eq!(
hashes_buffer.len(),
- array.len(),
- "hashes_buffer and array should be of equal length"
+ indices.len(),
+ "hashes_buffer and indices should be of equal length"
);
let rehash = col_idx >= 1;
if !rehash {
- for &row in indices {
- hashes_buffer[row] = 0;
- }
+ hashes_buffer.fill(0);
}
hash_single_array_indices(array, random_state, indices, hashes_buffer, rehash)?;
}
@@ -1502,13 +1492,11 @@ mod tests {
let mut full_hashes = vec![0; arrays[0].len()];
create_hashes(&arrays, &random_state, &mut full_hashes)?;
- let mut selected_hashes = vec![u64::MAX; arrays[0].len()];
+ let mut selected_hashes = vec![u64::MAX; 2];
create_hashes_indices(&arrays, &random_state, &[1, 3], &mut selected_hashes)?;
- assert_eq!(selected_hashes[0], u64::MAX);
- assert_eq!(selected_hashes[1], full_hashes[1]);
- assert_eq!(selected_hashes[2], u64::MAX);
- assert_eq!(selected_hashes[3], full_hashes[3]);
+ assert_eq!(selected_hashes[0], full_hashes[1]);
+ assert_eq!(selected_hashes[1], full_hashes[3]);
Ok(())
}
diff --git a/datafusion/physical-plan/src/aggregates/group_values/mod.rs b/datafusion/physical-plan/src/aggregates/group_values/mod.rs
index 6c9bd663c7..75cbb34256 100644
--- a/datafusion/physical-plan/src/aggregates/group_values/mod.rs
+++ b/datafusion/physical-plan/src/aggregates/group_values/mod.rs
@@ -101,6 +101,9 @@ pub trait GroupValues: Send {
fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()>;
/// Calculates group ids for selected rows by row index.
+ ///
+ /// `hashes` is dense and aligned with `partition_indices`: `hashes[pos]`
+ /// contains the hash for row `partition_indices[pos]`.
fn intern_partitioned(
&mut self,
_cols: &[ArrayRef],
@@ -128,9 +131,8 @@ pub trait GroupValues: Send {
indices: &[usize],
hashes: &mut Vec<u64>,
) -> Result<()> {
- if hashes.len() != cols[0].len() {
- hashes.resize(cols[0].len(), 0);
- }
+ hashes.clear();
+ hashes.resize(indices.len(), 0);
create_hashes_indices(
cols,
&crate::aggregates::AGGREGATION_HASH_SEED,
diff --git a/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs b/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs
index e7b7ac985d..3d0279627c 100644
--- a/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs
+++ b/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs
@@ -237,6 +237,9 @@ struct VectorizedOperationBuffers {
/// The `vectorized_equal_to` group indices buffer
equal_to_group_indices: Vec<usize>,
+ /// The `vectorized_equal_to` hash buffer for partitioned intern.
+ equal_to_hashes: Vec<u64>,
+
/// The `vectorized_equal_to` result buffer (bitmask)
equal_to_results: BooleanBufferBuilder,
@@ -244,6 +247,9 @@ struct VectorizedOperationBuffers {
/// exist groups in `group_values` in `vectorized_equal_to`.
/// We will perform `scalarized_intern` for such rows.
remaining_row_indices: Vec<usize>,
+
+ /// The hash buffer for `remaining_row_indices` in partitioned intern.
+ remaining_hashes: Vec<u64>,
}
impl Default for VectorizedOperationBuffers {
@@ -252,8 +258,10 @@ impl Default for VectorizedOperationBuffers {
append_row_indices: Vec::new(),
equal_to_row_indices: Vec::new(),
equal_to_group_indices: Vec::new(),
+ equal_to_hashes: Vec::new(),
equal_to_results: BooleanBufferBuilder::new(0),
remaining_row_indices: Vec::new(),
+ remaining_hashes: Vec::new(),
}
}
}
@@ -263,7 +271,9 @@ impl VectorizedOperationBuffers {
self.append_row_indices.clear();
self.equal_to_row_indices.clear();
self.equal_to_group_indices.clear();
+ self.equal_to_hashes.clear();
self.remaining_row_indices.clear();
+ self.remaining_hashes.clear();
}
}
@@ -460,8 +470,8 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
groups.clear();
groups.resize(n_rows, usize::MAX);
- for &row in partition_indices {
- let target_hash = batch_hashes[row];
+ for (hash_idx, &row) in partition_indices.iter().enumerate() {
+ let target_hash = batch_hashes[hash_idx];
let entry = self
.map
.find_mut(target_hash, |(exist_hash, group_idx_view)| {
@@ -581,11 +591,11 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
self.vectorized_append(cols)?;
// 3. Perform `vectorized_equal_to`
- self.vectorized_equal_to(cols, groups);
+ self.vectorized_equal_to(cols, groups, false);
// 4. Perform scalarized inter for remaining rows
// (about remaining rows, can see comments for `remaining_row_indices`)
- self.scalarized_intern_remaining(cols, &batch_hashes, groups)?;
+ self.scalarized_intern_remaining(cols, &batch_hashes, groups, false)?;
self.hashes_buffer = batch_hashes;
@@ -610,8 +620,8 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
groups,
);
self.vectorized_append(cols)?;
- self.vectorized_equal_to(cols, groups);
- self.scalarized_intern_remaining(cols, batch_hashes, groups)?;
+ self.vectorized_equal_to(cols, groups, true);
+ self.scalarized_intern_remaining(cols, batch_hashes, groups, true)?;
Ok(())
}
@@ -642,6 +652,7 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
self.vectorized_operation_buffers
.equal_to_group_indices
.clear();
+ self.vectorized_operation_buffers.equal_to_hashes.clear();
for (row, &target_hash) in batch_hashes.iter().enumerate() {
if filter_array
@@ -721,9 +732,10 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
self.vectorized_operation_buffers
.equal_to_group_indices
.clear();
+ self.vectorized_operation_buffers.equal_to_hashes.clear();
- for &row in partition_indices {
- let target_hash = batch_hashes[row];
+ for (hash_idx, &row) in partition_indices.iter().enumerate() {
+ let target_hash = batch_hashes[hash_idx];
let entry = self
.map
.find(target_hash, |(exist_hash, _)| target_hash == *exist_hash);
@@ -758,6 +770,9 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
self.vectorized_operation_buffers
.equal_to_row_indices
.extend(std::iter::repeat_n(row, group_index_list.len()));
+ self.vectorized_operation_buffers
+ .equal_to_hashes
+ .extend(std::iter::repeat_n(target_hash, group_index_list.len()));
} else {
let group_index = group_index_view.value() as usize;
self.vectorized_operation_buffers
@@ -766,6 +781,9 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
self.vectorized_operation_buffers
.equal_to_group_indices
.push(group_index);
+ self.vectorized_operation_buffers
+ .equal_to_hashes
+ .push(target_hash);
}
}
}
@@ -807,17 +825,29 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
/// and perform `scalarized_intern` for them after.
/// Usually, such `rows` having same hash but different value with `exists rows`
/// are very few.
- fn vectorized_equal_to(&mut self, cols: &[ArrayRef], groups: &mut [usize]) {
+ fn vectorized_equal_to(
+ &mut self,
+ cols: &[ArrayRef],
+ groups: &mut [usize],
+ has_partitioned_hashes: bool,
+ ) {
assert_eq!(
self.vectorized_operation_buffers
.equal_to_group_indices
.len(),
self.vectorized_operation_buffers.equal_to_row_indices.len()
);
+ if has_partitioned_hashes {
+ assert_eq!(
+ self.vectorized_operation_buffers.equal_to_hashes.len(),
+ self.vectorized_operation_buffers.equal_to_row_indices.len()
+ );
+ }
self.vectorized_operation_buffers
.remaining_row_indices
.clear();
+ self.vectorized_operation_buffers.remaining_hashes.clear();
if self
.vectorized_operation_buffers
@@ -882,6 +912,11 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
self.vectorized_operation_buffers
.remaining_row_indices
.push(row);
+ if has_partitioned_hashes {
+ self.vectorized_operation_buffers
+ .remaining_hashes
+ .push(self.vectorized_operation_buffers.equal_to_hashes[idx]);
+ }
}
// Init the total result for checking next row
@@ -932,6 +967,7 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
cols: &[ArrayRef],
batch_hashes: &[u64],
groups: &mut [usize],
+ has_partitioned_hashes: bool,
) -> Result<()> {
if self
.vectorized_operation_buffers
@@ -943,8 +979,17 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
let mut map = mem::take(&mut self.map);
- for &row in &self.vectorized_operation_buffers.remaining_row_indices {
- let target_hash = batch_hashes[row];
+ for (remaining_idx, &row) in self
+ .vectorized_operation_buffers
+ .remaining_row_indices
+ .iter()
+ .enumerate()
+ {
+ let target_hash = if has_partitioned_hashes {
+ self.vectorized_operation_buffers.remaining_hashes[remaining_idx]
+ } else {
+ batch_hashes[row]
+ };
let entry = map.find_mut(target_hash, |(exist_hash, _)| {
// Somewhat surprisingly, this closure can be called even if the
// hash doesn't match, so check the hash first with an integer
@@ -1581,7 +1626,9 @@ mod tests {
let mut groups = Vec::new();
let mut hashes = Vec::new();
- group_values.create_hashes(&cols, &mut hashes).unwrap();
+ group_values
+ .create_hashes_indices(&cols, &partition_indices, &mut hashes)
+ .unwrap();
group_values
.intern_partitioned(&cols, &hashes, &mut groups, &partition_indices)
.unwrap();
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org