comphead commented on code in PR #27530:
URL: https://github.com/apache/datafusion/pull/27530#discussion_r4631869088
##########
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:
The `MidChain` branch repeats the loop body for a single row. If the resume
position goes into the loop instead, there is one call site and the `expect`
goes away. `emit_grouped_rows` could then be inlined into the loop:
```rust
let (first_row, mut resume_pos) = match offset {
AtRow { row } => (row, None),
MidChain { row, next } => (row, Some(next as usize)),
};
for row in first_row..num_rows {
let pos = resume_pos.take();
let Some((start, end)) = rows_of(row) else {
continue;
};
if let Some(next_offset) = emit_grouped_rows(
&rows[..end],
pos.unwrap_or(start),
row,
&mut remaining,
input_indices,
match_indices,
row == num_rows - 1,
) {
return Some(next_offset);
}
}
None
```
##########
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:
This arm, and the `Chain` arm above it, are identical in the
`JoinHashMapU64` impl. A generic free function that takes `&HashTable<(u64,
T)>` and `&KeyRows<T>` and does the `match` itself, next to
`get_matched_indices_with_limit_offset`, would turn both impls into one call
and keep the `rows_of` closure in one place.
##########
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:
`ArrayMap::try_new` leaves `build_mem_used` to the caller
(`metrics.build_mem_used.add(array_map.size())`). Following that here would
keep metrics out of `join_hash_map.rs`. `group_rows` would take only the
reservation, and `build_in_memory` would update the gauge from
`map_reservation.size()` before and after. That drops the `Gauge` import, the
unused `_mem_used` in the default method, the gauge half of the `reserved` test
helper, and the `mem_used` assertions that repeat `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:
`PeakRecordingPool` in `datafusion_execution::memory_pool` already records
the high-water mark.
`PeakRecordingPool::new(Arc::new(UnboundedMemoryPool::default()))` with
`peak_reserved()` replaces this pool and its `Display` impl. The aggregate
tests in `aggregates/mod.rs` use it the same way.
##########
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:
This makes a full pass over `next` for every build with a repeated key,
including the ones that stay chained. On main that costs nothing, and here it
runs serially in `CollectLeft` (I haven't measured it). `update_from_iter`
already sees each chained insert. If it returned the number of chained rows
instead of `bool` (the symmetric hash join ignores the result),
`KeyRows::Chain` could hold `chained_rows: usize`. Then `!chained` becomes
`chained_rows == 0` and this pass goes away.
--
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]