Dandandan commented on code in PR #26447:
URL: https://github.com/apache/datafusion/pull/26447#discussion_r4625166595


##########
datafusion/physical-plan/src/joins/array_map.rs:
##########
@@ -136,8 +159,11 @@ impl ArrayMap {
         if range >= usize::MAX as u64 {
             return usize::MAX;
         }
-        let size = (range + 1) as usize;
-        size.saturating_mul(size_of::<u32>())
+        // One slot more than the key range, for the end of the last key's rows
+        // when they are sorted
+        let slots = (range + 2) as usize;

Review Comment:
   [P2] The guard above admits `range == usize::MAX - 1`. At that boundary 
`range + 2` overflows on a 64-bit target, panicking with overflow checks or 
wrapping to zero in release. A minimum key density of zero lets this range 
reach the estimator. Please use `(range as usize).saturating_add(2)` so the 
estimate saturates to `usize::MAX`. This boundary can be tested directly 
without allocating a map.



##########
datafusion/physical-plan/src/joins/array_map.rs:
##########
@@ -289,87 +499,145 @@ impl ArrayMap {
 
         let have_null = arr.null_count() > 0;
 
-        if self.next.is_empty() {
-            debug_assert!(
-                matches!(current_offset, AtRow { .. }),
-                "since the next offset is empty, mid-chain is not possible"
-            );
-            let rows = match current_offset {
-                AtRow { row } => row,
-                MidChain { row, .. } => row,
-            };
-            for prob_idx in rows..arr.len() {
-                if build_indices.len() == limit {
-                    return Ok(Some(AtRow { row: prob_idx }));
-                }
+        match &self.rows {
+            KeyRows::Unique { data } => {
+                debug_assert!(
+                    matches!(current_offset, AtRow { .. }),
+                    "unique keys cannot have mid-chain"
+                );
+                let rows = match current_offset {
+                    AtRow { row } => row,
+                    MidChain { row, .. } => row,
+                };
+                for prob_idx in rows..arr.len() {
+                    if build_indices.len() == limit {
+                        return Ok(Some(AtRow { row: prob_idx }));
+                    }
 
-                // short circuit
-                if have_null && arr.is_null(prob_idx) {
-                    continue;
+                    // short circuit
+                    if have_null && arr.is_null(prob_idx) {
+                        continue;
+                    }
+                    // SAFETY: prob_idx is guaranteed to be within bounds by 
the loop range.
+                    let prob_val: u64 = unsafe { arr.value_unchecked(prob_idx) 
}.as_();
+                    let Some(slot) =
+                        Self::key_to_index(prob_val, self.offset, data.len())
+                    else {
+                        continue;
+                    };
+                    let build_value = data[slot];
+                    if build_value == 0 {
+                        continue;
+                    }
+                    build_indices.push((build_value - 1) as u64);
+                    probe_indices.push(prob_idx as u32);
                 }
-                // SAFETY: prob_idx is guaranteed to be within bounds by the 
loop range.
-                let prob_val: u64 = unsafe { arr.value_unchecked(prob_idx) 
}.as_();
-                let Some(build_value) = self.get_value(prob_val) else {
-                    continue;
-                };
-                build_indices.push((build_value - 1) as u64);
-                probe_indices.push(prob_idx as u32);
             }
-        } else {
-            let mut remaining_output = limit;
-            let to_skip = match current_offset {
-                // `AtRow` indicates that `idx` processing hasn't been started
-                AtRow { row: idx } => idx,
-                // Otherwise, process remaining `idx` matches by traversing 
`next_chain`,
-                // to start with the next index
-                MidChain {
-                    row: idx,
-                    next: next_idx,
-                } => {
-                    let is_last = idx == arr.len() - 1;
-                    if let Some(next_offset) = traverse_chain(
-                        &self.next,
-                        idx,
-                        next_idx as u32,
+            KeyRows::Chain { data, next } => {
+                let mut remaining_output = limit;
+                let to_skip = match current_offset {
+                    // `AtRow` indicates that `idx` processing hasn't been 
started
+                    AtRow { row: idx } => idx,
+                    // Otherwise, process remaining `idx` matches by 
traversing `next_chain`,
+                    // to start with the next index
+                    MidChain {
+                        row: idx,
+                        next: next_idx,
+                    } => {
+                        let is_last = idx == arr.len() - 1;
+                        if let Some(next_offset) = traverse_chain(
+                            next,
+                            idx,
+                            next_idx as u32,
+                            &mut remaining_output,
+                            probe_indices,
+                            build_indices,
+                            is_last,
+                        ) {
+                            return Ok(Some(next_offset));
+                        }
+                        idx + 1
+                    }
+                };
+
+                for prob_side_idx in to_skip..arr.len() {
+                    if remaining_output == 0 {
+                        return Ok(Some(AtRow { row: prob_side_idx }));
+                    }
+
+                    if have_null && arr.is_null(prob_side_idx) {
+                        continue;
+                    }
+
+                    let is_last = prob_side_idx == arr.len() - 1;
+
+                    // SAFETY: prob_idx is guaranteed to be within bounds by 
the loop range.
+                    let prob_val: u64 =
+                        unsafe { arr.value_unchecked(prob_side_idx) }.as_();
+                    let Some(slot) =
+                        Self::key_to_index(prob_val, self.offset, data.len())
+                    else {
+                        continue;
+                    };
+                    let build_idx = data[slot];
+                    if build_idx == 0 {
+                        continue;
+                    }
+
+                    if let Some(offset) = traverse_chain(
+                        next,
+                        prob_side_idx,
+                        build_idx,
                         &mut remaining_output,
                         probe_indices,
                         build_indices,
                         is_last,
                     ) {
-                        return Ok(Some(next_offset));
+                        return Ok(Some(offset));
                     }
-                    idx + 1
-                }
-            };
-
-            for prob_side_idx in to_skip..arr.len() {
-                if remaining_output == 0 {
-                    return Ok(Some(AtRow { row: prob_side_idx }));
                 }
-
-                if have_null && arr.is_null(prob_side_idx) {
-                    continue;
-                }
-
-                let is_last = prob_side_idx == arr.len() - 1;
-
-                // SAFETY: prob_idx is guaranteed to be within bounds by the 
loop range.
-                let prob_val: u64 = unsafe { 
arr.value_unchecked(prob_side_idx) }.as_();
-                let Some(build_idx) = self.get_value(prob_val) else {
-                    continue;
-                };
-
-                if let Some(offset) = traverse_chain(
-                    &self.next,
-                    prob_side_idx,
-                    build_idx,
-                    &mut remaining_output,
+            }
+            KeyRows::Sorted { starts, rows } => {
+                let slots = starts.len() - 1;
+                return Ok(grouped_matched_indices(
+                    rows,
+                    arr.len(),
+                    |row| {
+                        if have_null && arr.is_null(row) {
+                            return None;
+                        }
+                        // SAFETY: `row` is within bounds, below `arr.len()`.
+                        let prob_val: u64 = unsafe { arr.value_unchecked(row) 
}.as_();

Review Comment:
   [P1] Please validate `row < num_rows` in the `MidChain` resume branch before 
calling `rows_of(row)`. The main loop guarantees that bound, but the resume 
branch gets `row` from the supplied `ProbeOffset`. If an offset is reused with 
a shorter, null-free batch, both the `Sorted` and `Grouped` closures can reach 
`value_unchecked` with an out-of-bounds index. Checking once on resume keeps 
the main loop unchanged.



##########
datafusion/physical-plan/src/joins/array_map.rs:
##########
@@ -223,13 +265,191 @@ impl ArrayMap {
         Ok(())
     }
 
+    /// Builds an [`ArrayMap`] with the rows sorted by key with a counting
+    /// sort, see [`KeyRows::Sorted`].
+    fn sort_rows<T: ArrowNumericType>(
+        array: &ArrayRef,
+        offset: u64,
+        size: usize,
+    ) -> Result<Self>
+    where
+        T::Native: AsPrimitive<u64>,
+    {
+        let arr = array.as_primitive::<T>();
+        let nulls = arr.nulls();
+        let is_null = |i| nulls.is_some_and(|nulls| nulls.is_null(i));
+        // First count each key's rows, with one more slot for the end of the
+        // last key's rows...
+        let mut starts: Vec<u32> = vec![0; size + 1];
+        let mut num_of_distinct_key = 0;
+        for (i, &val) in arr.values().iter().enumerate() {
+            if is_null(i) {
+                continue;
+            }
+            let Some(idx) = Self::key_to_index(val.as_(), offset, size) else {
+                return internal_err!("failed build Array idx >= data.len()");
+            };
+            if starts[idx] == 0 {
+                num_of_distinct_key += 1;
+            }
+            starts[idx] += 1;
+        }
+        // ...then turn the counts into the end of each key's rows...
+        let mut end = 0;
+        for count in &mut starts[..size] {
+            end += *count;
+            *count = end;
+        }
+        starts[size] = end;
+        // ...and place the rows from the last to the first, which moves the
+        // end of each key's rows back to their start and keeps them in order.
+        let mut rows = vec![0; end as usize];
+        for (i, &val) in arr.values().iter().enumerate().rev() {
+            if is_null(i) {
+                continue;
+            }
+            // In range: every key was checked when it was counted.
+            let idx = val.as_().wrapping_sub(offset) as usize;
+            starts[idx] -= 1;
+            rows[starts[idx] as usize] = i as u32;
+        }
+
+        Ok(Self {
+            rows: KeyRows::Sorted { starts, rows },
+            offset,
+            num_of_distinct_key,
+        })
+    }
+
     pub fn num_of_distinct_key(&self) -> usize {
         self.num_of_distinct_key
     }
 
+    /// Stores the build rows of each key next to each other, under the same
+    /// conditions as [`JoinHashMapType::group_rows`] does for a hash map, and
+    /// in the same layout. `keys` are the build keys the map was created from.
+    /// Returns whether the rows were grouped.
+    ///
+    /// [`JoinHashMapType::group_rows`]: 
crate::joins::join_hash_map::JoinHashMapType::group_rows
+    pub(crate) fn group_rows(
+        &mut self,
+        keys: &ArrayRef,
+        reservation: &MemoryReservation,
+        mem_used: &Gauge,
+    ) -> Result<bool> {
+        let KeyRows::Chain { .. } = &self.rows else {
+            return Ok(false);
+        };
+        // Every row with a key is in the chain. The groups hold the number of
+        // rows of each key and the rows, after the unused position `0`.
+        let rows = keys.len() - keys.null_count();
+        let len = 1 + self.num_of_distinct_key + rows;
+        if rows < self.num_of_distinct_key * 2 || u32::try_from(len).is_err() {
+            return Ok(false);
+        }
+        // The groups, and the slots of the keys while they are placed
+        let size = (len + self.num_of_distinct_key) * size_of::<u32>();

Review Comment:
   [P2] `present` is a `Vec<usize>` because `slot` is a `usize`. This charges 
four bytes per distinct key for scratch space, while the vector needs eight on 
64-bit targets. A pool near its limit can therefore admit grouping without 
enough room for the peak. Please calculate the scratch bytes with 
`size_of::<usize>()` and use that same amount when releasing the reservation. A 
pool limit between the two peak estimates would exercise the fallback.



-- 
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