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


##########
datafusion/physical-plan/src/joins/join_hash_map.rs:
##########
@@ -324,24 +401,257 @@ impl JoinHashMapType for JoinHashMapU64 {
     fn len(&self) -> usize {
         self.map.len()
     }
+
+    fn group_rows(&mut self, reservation: &MemoryReservation) -> bool {
+        group_rows(&mut self.map, &mut self.rows, reservation)
+    }
 }
 
-use crate::joins::chain::traverse_chain;
+use crate::joins::chain::{grouped_matched_indices, traverse_chain};
 use crate::joins::join_hash_map::ProbeOffset::{AtRow, MidChain};
 
-/// Inserts the rows of `iter` into `map` and `next`. Returns `true` if any row
-/// was chained onto an existing hash value.
+/// See [`JoinHashMapType::get_matched_indices_with_limit_offset`].
+#[expect(clippy::too_many_arguments)]
+fn key_rows_matched_indices<T>(
+    map: &HashTable<(u64, T)>,
+    rows: &KeyRows<T>,
+    hash_values: &[u64],
+    valid_keys: Option<&NullBuffer>,
+    limit: usize,
+    offset: ProbeOffset,
+    input_indices: &mut Vec<u32>,
+    match_indices: &mut Vec<u64>,
+) -> Option<ProbeOffset>
+where
+    T: ArrowNativeType + TryFrom<usize> + PartialOrd + Into<u64> + Sub<Output 
= T>,
+    <T as TryFrom<usize>>::Error: Debug,
+{
+    match rows {
+        KeyRows::Chain { next, chained_rows } => 
get_matched_indices_with_limit_offset(
+            map,
+            next,
+            *chained_rows == 0,
+            hash_values,
+            valid_keys,
+            limit,
+            offset,
+            input_indices,
+            match_indices,
+        ),
+        KeyRows::Grouped { groups } => grouped_matched_indices(
+            groups,
+            hash_values.len(),
+            |row| {
+                // NULL keys cannot match any build row
+                if valid_keys.is_some_and(|valid| valid.is_null(row)) {
+                    return None;
+                }
+                let hash = hash_values[row];
+                let (_, pos) = map.find(hash, |(h, _)| hash == *h)?;
+                Some(group_rows_range(groups, pos.as_usize()))
+            },
+            limit,
+            offset,
+            input_indices,
+            match_indices,
+        ),
+    }
+}
+
+/// See [`JoinHashMapType::group_rows`].
+fn group_rows<T>(
+    map: &mut HashTable<(u64, T)>,
+    rows: &mut KeyRows<T>,
+    reservation: &MemoryReservation,
+) -> bool
+where
+    T: ArrowNativeType + Sub<Output = T> + PartialEq,
+{
+    let KeyRows::Chain { next, chained_rows } = rows else {
+        return false;
+    };
+    if *chained_rows == 0 {
+        return false;
+    }
+    let Some(len) = grouped_rows_len::<T>(map.len(), *chained_rows) else {
+        return false;
+    };
+    let size = len * size_of::<T>();
+    if reservation.try_grow(size).is_err() {
+        return false;
+    }
+    let groups = group_chains(map, next, len);
+    let freed = next.capacity() * size_of::<T>();
+    *rows = KeyRows::Grouped { groups };
+    reservation.shrink(freed);
+    true
+}
+
+/// Returns the range in `groups` of the rows of the group at `pos`, which
+/// starts with their number.
+#[inline]
+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, with
+/// `chained_rows` rows inserted after the first of their hash value, 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`. Rows left out of the map, such
+/// as NULL keys, count towards neither.
+fn grouped_rows_len<T: ArrowNativeType>(
+    map_len: usize,
+    chained_rows: usize,
+) -> Option<usize> {
+    if chained_rows < map_len {

Review Comment:
   @andygrove thanks for splitting this out. This threshold groups two kinds of 
build where grouping loses. With 16M build rows and exactly 2 rows per key, the 
join is 1.7x slower when the build rows of each key are stored together (in 
both `Partitioned` and `CollectLeft`). With shuffled keys at 2–4 rows per key 
it is 1.2–1.6x slower in `CollectLeft`. In the first case the groups are in 
hash-table order, so a probe that arrives in key order loses the locality the 
chain had (probe 0.72 → 1.3 s). In the second, the grouping pass adds about 270 
ms and the probe gets no faster.
   
   Could grouping skip both? I prototyped counting only the chained rows whose 
next row isn't the next row number, with a configurable threshold. It brings 
the stored-together case back to 1.02–1.06x of main, but with shuffled keys in 
`CollectLeft` grouping only breaks even at about 16 rows per key. Which 
threshold to pick is your call; the numbers are below.
   
   <details><summary>Benchmark (16M build rows, head/main, median of 5 warm 
runs × 2 rounds, M-series laptop)</summary>
   
   | Build rows per key | CollectLeft | Partitioned |
   |---|---|---|
   | shuffled, 2 | 1.46–1.58x | 1.01–1.18x |
   | shuffled, 4 | 1.23–1.28x | 0.82–0.85x |
   | shuffled, 8 | 1.07x | 0.72x |
   | shuffled, 16 | 0.91–0.96x | 0.51–0.63x |
   | shuffled, 100 | 0.56–0.62x | 0.30–0.37x |
   | stored together, 2 | 1.68–1.70x | 1.69–1.71x |
   | stored together, 100 | 1.17–1.23x | 1.05x |
   
   ```sql
   SET datafusion.optimizer.join_reordering = false;
   -- shuffled, 2 rows per key
   CREATE TABLE br2 AS SELECT ((value * 7919) % 16000000) % 8000000 * 1000003 
AS k, value AS v FROM range(16000000);
   CREATE TABLE pr2 AS SELECT ((value * 104729) % 16000000) % 8000000 * 1000003 
AS k FROM range(16000000);
   -- stored together, 2 rows per key
   CREATE TABLE bs2 AS SELECT (value / 2) * 1000003 AS k, value AS v FROM 
range(16000000);
   CREATE TABLE ps2 AS SELECT (value % 8000000) * 1000003 AS k FROM 
range(16000000);
   SELECT sum(b.v) FROM bs2 b JOIN ps2 p ON b.k = p.k;
   -- CollectLeft: also SET 
datafusion.optimizer.hash_join_single_partition_threshold(_rows) = 100000000000
   ```
   
   `EXPLAIN ANALYZE`, `CollectLeft`, stored together: build_time 0.26 → 0.43 s, 
join_time 0.72 → 1.3 s. Shuffled: build_time 0.35 → 0.61 s, join_time unchanged.
   </details>
   
   <details><summary>Counting the rows that jump (the comparison I 
prototyped)</summary>
   
   ```rs
   Occupied(mut occupied_entry) => {
       let (_, index) = occupied_entry.get_mut();
       let prev_index = *index;
       *index = T::try_from(row + 1).unwrap();
       next[row - deleted_offset] = prev_index;
       chained_rows += 1;
       // Rows are inserted last to first, so a key whose rows are stored
       // together chains each row to the one after it, which the chain
       // already reads in order.
       if prev_index != T::try_from(row + 2).unwrap() {
           scattered_rows += 1;
       }
   }
   ```
   
   `group_rows` then compares `scattered_rows` with `map.len() * 
(min_rows_per_key - 1)`, while `chained_rows` keeps deciding the unique-key 
fast path. In `test_which_build_rows_are_grouped`, `[10, 20, 10, 10]` then 
stays chained.
   </details>



##########
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##########
@@ -3500,6 +3508,24 @@ fn build_in_memory(
         })
         .transpose()?;
 
+    // Grouping the rows of repeated keys is optional: it keeps the chain if
+    // the memory for the groups is not available. Doing it after every
+    // reservation the build needs keeps it from making one of them fail.
+    let ungrouped_size = map_reservation.size();
+    let grouped = match &mut join_hash_map {
+        Map::HashMap(hashmap) => hashmap.group_rows(&map_reservation),
+        Map::ArrayMap(_) => false,
+    };
+    if grouped {
+        grouped_map_count.add(1);
+        let grouped_size = map_reservation.size();
+        if grouped_size >= ungrouped_size {
+            metrics.build_mem_used.add(grouped_size - ungrouped_size);
+        } else {
+            metrics.build_mem_used.sub(ungrouped_size - grouped_size);
+        }
+    }

Review Comment:
   Optional cleanup: the gauge already includes `ungrouped_size`, so 
subtracting it and adding the new size can't underflow, and the branch goes 
away.
   
   ```suggestion
       if grouped {
           grouped_map_count.add(1);
           metrics.build_mem_used.sub(ungrouped_size);
           metrics.build_mem_used.add(map_reservation.size());
       }
   ```



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