andygrove commented on code in PR #27530:
URL: https://github.com/apache/datafusion/pull/27530#discussion_r4642938835


##########
datafusion/physical-plan/src/joins/chain.rs:
##########
@@ -62,3 +62,100 @@ where
         match_row_idx = next - one;
     }
 }
+
+/// Emits the build rows `rows[pos..]` of probe row `prob_idx`, at most
+/// `remaining` of them, for maps that store the build rows of each key next to
+/// each other instead of in a chain. Returns `Some(offset)` if the limit was
+/// reached and there are more results to process, as [`traverse_chain`] does.
+#[inline(always)]
+fn emit_grouped_rows<T>(
+    rows: &[T],
+    pos: usize,
+    prob_idx: usize,
+    remaining: &mut usize,
+    input_indices: &mut Vec<u32>,
+    match_indices: &mut Vec<u64>,
+    is_last_input: bool,
+) -> Option<ProbeOffset>
+where
+    T: Copy + Into<u64>,
+{
+    let end = rows.len();
+    let take = (end - pos).min(*remaining);
+    match_indices.extend(rows[pos..pos + take].iter().map(|&row| row.into()));
+    input_indices.extend(std::iter::repeat_n(prob_idx as u32, take));
+    *remaining -= take;
+    if *remaining > 0 {
+        return None;
+    }
+    if pos + take < end {
+        Some(MidChain {
+            row: prob_idx,
+            next: (pos + take) as u64,
+        })
+    } else if is_last_input {
+        None
+    } else {
+        Some(AtRow { row: prob_idx + 1 })
+    }
+}
+
+/// Emits the matches of the probe rows `0..num_rows` from `offset`, at most
+/// `limit` of them, for maps that store the build rows of each key next to
+/// each other, see `JoinHashMapType::group_rows`. `rows_of` returns the range
+/// in `rows` of a probe row's matches, or `None` if the probe row has none.
+/// Returns the offset to resume from, as [`traverse_chain`] does.
+pub(crate) fn grouped_matched_indices<T>(
+    rows: &[T],
+    num_rows: usize,
+    rows_of: impl Fn(usize) -> Option<(usize, usize)>,
+    limit: usize,
+    offset: ProbeOffset,
+    input_indices: &mut Vec<u32>,
+    match_indices: &mut Vec<u64>,
+) -> Option<ProbeOffset>
+where
+    T: Copy + Into<u64>,
+{
+    // Clear the buffer before producing new results
+    input_indices.clear();
+    match_indices.clear();
+    let mut remaining = limit;
+
+    let to_skip = match offset {
+        AtRow { row } => row,
+        // Resume at position `next` of the matches of probe row `row`
+        MidChain { row, next } => {

Review Comment:
   Done in dd8ecf487. The resume position goes into the loop, and the emit 
helper is inlined.



##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -214,17 +276,38 @@ impl JoinHashMapType for JoinHashMapU32 {
         input_indices: &mut Vec<u32>,
         match_indices: &mut Vec<u64>,
     ) -> Option<ProbeOffset> {
-        get_matched_indices_with_limit_offset::<u32>(
-            &self.map,
-            &self.next,
-            !self.chained,
-            hash_values,
-            valid_keys,
-            limit,
-            offset,
-            input_indices,
-            match_indices,
-        )
+        match &self.rows {
+            KeyRows::Chain { next, chained } => {
+                get_matched_indices_with_limit_offset::<u32>(
+                    &self.map,
+                    next,
+                    !chained,
+                    hash_values,
+                    valid_keys,
+                    limit,
+                    offset,
+                    input_indices,
+                    match_indices,
+                )
+            }
+            KeyRows::Grouped { groups } => grouped_matched_indices(

Review Comment:
   Done in dd8ecf487. Both impls call `key_rows_matched_indices`.



##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -324,11 +443,203 @@ impl JoinHashMapType for JoinHashMapU64 {
     fn len(&self) -> usize {
         self.map.len()
     }
+
+    fn group_rows(&mut self, reservation: &MemoryReservation, mem_used: 
&Gauge) -> bool {
+        group_rows(&mut self.map, &mut self.rows, reservation, mem_used)
+    }
 }
 
-use crate::joins::chain::traverse_chain;
+use crate::joins::chain::{grouped_matched_indices, traverse_chain};
 use crate::joins::join_hash_map::ProbeOffset::{AtRow, MidChain};
 
+/// See [`JoinHashMapType::group_rows`].
+fn group_rows<T>(
+    map: &mut HashTable<(u64, T)>,
+    rows: &mut KeyRows<T>,
+    reservation: &MemoryReservation,
+    mem_used: &Gauge,
+) -> bool
+where
+    T: ArrowNativeType + Sub<Output = T> + PartialEq,
+{
+    let KeyRows::Chain {
+        next,
+        chained: true,
+    } = rows
+    else {
+        return false;
+    };
+    let Some(len) = grouped_rows_len(map.len(), next) else {
+        return false;
+    };
+    let size = len * size_of::<T>();
+    if reservation.try_grow(size).is_err() {
+        return false;
+    }
+    mem_used.add(size);
+    let groups = group_chains(map, next, len);
+    let freed = next.capacity() * size_of::<T>();
+    *rows = KeyRows::Grouped { groups };
+    reservation.shrink(freed);
+    mem_used.sub(freed);
+    true
+}
+
+/// Returns the range in `groups` of the rows of the group at `pos`, which
+/// starts with their number.
+#[inline]
+pub(crate) fn group_rows_range<T: ArrowNativeType>(
+    groups: &[T],
+    pos: usize,
+) -> (usize, usize) {
+    (pos + 1, pos + 1 + groups[pos].as_usize())
+}
+
+/// Returns the length of the groups of the `map_len` hash values whose chains
+/// are in `next`, or `None` if the hash values have fewer than two rows each
+/// on average, or if a position in the groups would not fit in `T`.
+fn grouped_rows_len<T: ArrowNativeType>(map_len: usize, next: &[T]) -> 
Option<usize> {
+    // Each row inserted after the first of its hash value points at the row
+    // inserted before it, while the rows left out of the map, such as NULL
+    // keys, keep `0`.
+    let zero = T::usize_as(0);
+    let chained_rows = next.iter().filter(|&&index| index != zero).count();

Review Comment:
   Done in dd8ecf487. `update_from_iter` returns the number of chained rows, 
and `KeyRows::Chain` keeps `chained_rows`. The pass over `next` is gone.



##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -324,11 +443,203 @@ impl JoinHashMapType for JoinHashMapU64 {
     fn len(&self) -> usize {
         self.map.len()
     }
+
+    fn group_rows(&mut self, reservation: &MemoryReservation, mem_used: 
&Gauge) -> bool {
+        group_rows(&mut self.map, &mut self.rows, reservation, mem_used)
+    }
 }
 
-use crate::joins::chain::traverse_chain;
+use crate::joins::chain::{grouped_matched_indices, traverse_chain};
 use crate::joins::join_hash_map::ProbeOffset::{AtRow, MidChain};
 
+/// See [`JoinHashMapType::group_rows`].
+fn group_rows<T>(
+    map: &mut HashTable<(u64, T)>,
+    rows: &mut KeyRows<T>,
+    reservation: &MemoryReservation,
+    mem_used: &Gauge,

Review Comment:
   Done in dd8ecf487. `group_rows` takes only the reservation, and 
`build_in_memory` updates `build_mem_used` from the change in 
`map_reservation.size()`.



##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -3874,6 +3896,118 @@ mod tests {
         Ok(())
     }
 
+    /// Joins 10 build batches of 1,000 rows, whose keys are `key(row)`, with
+    /// three probe rows, in `pool`, and returns how many maps had their rows
+    /// grouped.
+    async fn grouped_build(
+        key: impl Fn(i64) -> i64,
+        pool: Arc<dyn MemoryPool>,
+    ) -> Result<usize> {
+        let schema = Arc::new(Schema::new(vec![Field::new("k", 
DataType::Int64, false)]));
+        let batch = |keys: Vec<i64>| {
+            let column = Arc::new(Int64Array::from(keys)) as ArrayRef;
+            RecordBatch::try_new(Arc::clone(&schema), vec![column])
+        };
+        let build_batches = (0..10)
+            .map(|b| batch((b * 1_000..(b + 1) * 1_000).map(&key).collect()))
+            .collect::<Result<Vec<_>, _>>()?;
+        let build =
+            TestMemoryExec::try_new_exec(&[build_batches], 
Arc::clone(&schema), None)?;
+        let probe = batch(vec![key(0), key(1), key(999)])?;
+        let probe =
+            TestMemoryExec::try_new_exec(&[vec![probe]], Arc::clone(&schema), 
None)?;
+        let on = vec![(
+            Arc::new(Column::new_with_schema("k", &schema)?) as _,
+            Arc::new(Column::new_with_schema("k", &schema)?) as _,
+        )];
+        let join = join(
+            build,
+            probe,
+            on,
+            &JoinType::Inner,
+            NullEquality::NullEqualsNothing,
+        )?;
+
+        let runtime = RuntimeEnvBuilder::new()
+            .with_memory_pool(pool)
+            .build_arc()?;
+        let task_ctx = Arc::new(TaskContext::default().with_runtime(runtime));
+        common::collect(join.execute(0, task_ctx)?).await?;
+        Ok(join
+            .metrics()
+            .unwrap()
+            .sum_by_name(GROUPED_MAP_COUNT_METRIC_NAME)
+            .unwrap()
+            .as_usize())
+    }
+
+    /// Grouping the rows of repeated keys comes after every reservation the
+    /// build needs, and is skipped without the memory for it, so a build that
+    /// fits without its groups never fails for them, and groups them once the
+    /// memory for the groups is available.
+    #[tokio::test]
+    async fn grouping_never_fails_the_build() -> Result<()> {
+        use std::fmt::{self, Display};
+        use std::sync::atomic::{AtomicUsize, Ordering};
+
+        /// An unbounded pool that remembers the most it had reserved at once
+        #[derive(Debug, Default)]
+        struct PeakPool {

Review Comment:
   Done in dd8ecf487. Switched to `PeakRecordingPool`.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to