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