Skip to content

Commit f71c600

Browse files
committed
refactor: reuse materialize_left_columns for streamed filter columns
- Gather the filter's streamed columns through `materialize_left_columns` on a projection, like the buffered ones, so that the range check runs once per freeze, and drop `take_column`. - Drop the `c1 < c2` case from the hash join comparison, which the interleaved `c2 > c1` filter already covers. - Replace the Inner spill test with `Inner` in `spill_with_filter_multi_batch`, since spilled batches are read back before any freeze.
1 parent 8012102 commit f71c600

2 files changed

Lines changed: 27 additions & 91 deletions

File tree

‎datafusion/physical-plan/src/joins/sort_merge_join/materializing_stream.rs‎

Lines changed: 25 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -388,8 +388,9 @@ pub(super) struct MaterializingSortMergeJoinStream {
388388
pub early_filtering: bool,
389389
/// The indices of every buffered column, for materializing all of them
390390
pub buffered_columns: Vec<usize>,
391-
/// The buffered columns that the join filter reads, in the filter's order.
392-
/// Empty unless `early_filtering`.
391+
/// The streamed and buffered columns that the join filter reads, each in the
392+
/// filter's order. Empty unless `early_filtering`.
393+
pub streamed_filter_columns: Vec<usize>,
393394
pub buffered_filter_columns: Vec<usize>,
394395
/// How many pairs the Inner join's filter has evaluated at freeze so far
395396
/// (see [`Self::filter_first_pays`])
@@ -660,15 +661,17 @@ impl MaterializingSortMergeJoinStream {
660661
let deferred_filtering = needs_deferred_filtering(filter.as_ref(), join_type);
661662
let early_filtering = join_type == JoinType::Inner && filter.is_some();
662663
let buffered_columns = (0..buffered_schema.fields().len()).collect();
663-
let buffered_filter_columns = match &filter {
664+
let filter_columns = |side| match &filter {
664665
Some(f) if early_filtering => f
665666
.column_indices()
666667
.iter()
667-
.filter(|c| c.side == JoinSide::Right)
668+
.filter(|c| c.side == side)
668669
.map(|c| c.index)
669670
.collect(),
670671
_ => vec![],
671672
};
673+
let streamed_filter_columns = filter_columns(JoinSide::Left);
674+
let buffered_filter_columns = filter_columns(JoinSide::Right);
672675
let filter_schema = if deferred_filtering && let Some(f) = &filter {
673676
let mut fields = Vec::with_capacity(f.schema().fields().len());
674677
for (column_index, field) in
@@ -706,6 +709,7 @@ impl MaterializingSortMergeJoinStream {
706709
filter_schema,
707710
early_filtering,
708711
buffered_columns,
712+
streamed_filter_columns,
709713
buffered_filter_columns,
710714
freeze_filter_evaluated: 0,
711715
freeze_filter_passed: 0,
@@ -1809,14 +1813,12 @@ impl MaterializingSortMergeJoinStream {
18091813
}
18101814

18111815
/// Freezes the matched pairs of an Inner join with a filter. The filter runs
1812-
/// on just the columns it reads, and only the pairs that pass have their
1813-
/// output columns materialized. A selective filter over a many-to-many join
1814-
/// rejects most pairs, so materializing every column of every pair before
1815-
/// filtering would spend most of the freeze on rows that are then dropped.
1816-
/// When the pairs' indices form ranges on both sides, as in a 1:1 join, the
1817-
/// columns materialize as slices and filtering first cannot save anything.
1818-
/// Then, or when [`Self::filter_first_pays`] says earlier freezes kept too
1819-
/// many of their pairs, the batch is materialized whole and then filtered.
1816+
/// on just the columns it reads, and only the pairs that pass are
1817+
/// materialized, which saves most of the freeze when the filter rejects most
1818+
/// pairs of a many-to-many join. When both sides' indices span ranges, as in
1819+
/// a 1:1 join, the columns materialize as slices and filtering first saves
1820+
/// nothing. Then, or when [`Self::filter_first_pays`] says so, the batch is
1821+
/// materialized whole and then filtered.
18201822
fn freeze_inner_filtered(
18211823
&mut self,
18221824
matched_chunks: &[MatchedChunk],
@@ -1849,6 +1851,14 @@ impl MaterializingSortMergeJoinStream {
18491851
);
18501852
}
18511853

1854+
let mut streamed_arrays = materialize_left_columns(
1855+
&self
1856+
.streamed_batch
1857+
.batch
1858+
.project(&self.streamed_filter_columns)?,
1859+
&streamed_indices,
1860+
)?
1861+
.into_iter();
18521862
let mut buffered_arrays = self
18531863
.materialize_right_columns(
18541864
matched_chunks,
@@ -1860,10 +1870,9 @@ impl MaterializingSortMergeJoinStream {
18601870
.column_indices()
18611871
.iter()
18621872
.map(|column_index| match column_index.side {
1863-
JoinSide::Left => take_column(
1864-
self.streamed_batch.batch.column(column_index.index),
1865-
&streamed_indices,
1866-
),
1873+
JoinSide::Left => streamed_arrays.next().ok_or_else(|| {
1874+
internal_datafusion_err!("missing streamed filter column")
1875+
}),
18671876
JoinSide::Right => buffered_arrays.next().ok_or_else(|| {
18681877
internal_datafusion_err!("missing buffered filter column")
18691878
}),
@@ -2394,15 +2403,6 @@ fn concat_indices<'a>(
23942403
}
23952404
}
23962405

2397-
/// The rows of `array` at `indices`, sliced when the indices form a range.
2398-
fn take_column(array: &ArrayRef, indices: &UInt64Array) -> Result<ArrayRef> {
2399-
if let Some(range) = is_contiguous_range(indices) {
2400-
Ok(array.slice(range.start, range.len()))
2401-
} else {
2402-
Ok(compute::take(array.as_ref(), indices, None)?)
2403-
}
2404-
}
2405-
24062406
/// Evaluates `filter` over `num_rows` pairs whose `columns` follow the filter's
24072407
/// intermediate `schema`, and returns which pairs pass. A NULL result does not
24082408
/// pass, as in SQL.

‎datafusion/physical-plan/src/joins/sort_merge_join/tests.rs‎

Lines changed: 2 additions & 66 deletions
Original file line numberDiff line numberDiff line change
@@ -4249,7 +4249,7 @@ async fn spill_with_filter_multi_batch() -> Result<()> {
42494249

42504250
let filter = build_c1_lt_c2_filter(&left.schema(), &right.schema());
42514251

4252-
let join_types = [Left, Right, Full];
4252+
let join_types = [Inner, Left, Right, Full];
42534253

42544254
let runtime = RuntimeEnvBuilder::new()
42554255
.with_memory_limit(500, 1.0)
@@ -8606,7 +8606,7 @@ fn assert_streamed_order(batches: &[RecordBatch]) {
86068606
/// An Inner join with a filter filters the pairs of each freeze before it
86078607
/// materializes them. It must keep the same pairs as a hash join whatever the
86088608
/// batch size, which decides where a freeze cuts a group, and whatever the order
8609-
/// of the filter's columns. The pseudo-random values pass `c1 < c2` for about
8609+
/// of the filter's columns. The pseudo-random values pass `c2 > c1` for about
86108610
/// half of the pairs, and their NULLs pass for none. Freezes that materialize
86118611
/// whole batches are covered by the high-pass filter and by the single pairs of
86128612
/// `batch_size` 1, whose indices form ranges. A filter that reads no columns must
@@ -8618,7 +8618,6 @@ async fn join_inner_early_filtering_matches_hash_join() -> Result<()> {
86188618
let on = early_filtering_on(&left_schema, &right_schema)?;
86198619
// Each filter with whether it keeps any pair of these inputs.
86208620
let filters = [
8621-
(build_c1_lt_c2_filter(&left_schema, &right_schema), true),
86228621
(interleaved_early_filter(&left_schema, &right_schema), true),
86238622
(high_pass_early_filter(&left_schema, &right_schema), true),
86248623
(column_free_early_filter(true), true),
@@ -8657,66 +8656,3 @@ async fn join_inner_early_filtering_matches_hash_join() -> Result<()> {
86578656
}
86588657
Ok(())
86598658
}
8660-
8661-
/// The freeze filters pairs from spilled buffered batches once they are read back.
8662-
#[tokio::test]
8663-
async fn join_inner_early_filtering_with_spilled_buffered_batches() -> Result<()> {
8664-
let ((left_batches, left_schema), (right_batches, right_schema)) =
8665-
early_filtering_inputs();
8666-
let on = early_filtering_on(&left_schema, &right_schema)?;
8667-
let filter = build_c1_lt_c2_filter(&left_schema, &right_schema);
8668-
let memory_exec = |batches: &Vec<RecordBatch>, schema: &SchemaRef| {
8669-
TestMemoryExec::try_new_exec(
8670-
std::slice::from_ref(batches),
8671-
Arc::clone(schema),
8672-
None,
8673-
)
8674-
};
8675-
let runtime = RuntimeEnvBuilder::new()
8676-
.with_memory_limit(100, 1.0)
8677-
.with_disk_manager_builder(
8678-
DiskManagerBuilder::default().with_mode(DiskManagerMode::OsTmpDirectory),
8679-
)
8680-
.build_arc()?;
8681-
let session_config = SessionConfig::default().with_batch_size(8192);
8682-
let sort_options = vec![SortOptions::default(); on.len()];
8683-
8684-
let join = join_with_filter(
8685-
memory_exec(&left_batches, &left_schema)?,
8686-
memory_exec(&right_batches, &right_schema)?,
8687-
on.clone(),
8688-
filter.clone(),
8689-
Inner,
8690-
sort_options.clone(),
8691-
NullEquality::NullEqualsNothing,
8692-
)?;
8693-
let task_ctx = Arc::new(
8694-
TaskContext::default()
8695-
.with_session_config(session_config.clone())
8696-
.with_runtime(runtime),
8697-
);
8698-
let spilled = common::collect(join.execute(0, task_ctx)?).await?;
8699-
assert!(
8700-
join.metrics().unwrap().spill_count().unwrap() > 0,
8701-
"expected the buffered batches to spill"
8702-
);
8703-
8704-
let join_no_spill = join_with_filter(
8705-
memory_exec(&left_batches, &left_schema)?,
8706-
memory_exec(&right_batches, &right_schema)?,
8707-
on,
8708-
filter,
8709-
Inner,
8710-
sort_options,
8711-
NullEquality::NullEqualsNothing,
8712-
)?;
8713-
let task_ctx = Arc::new(TaskContext::default().with_session_config(session_config));
8714-
let no_spill = common::collect(join_no_spill.execute(0, task_ctx)?).await?;
8715-
8716-
assert_streamed_order(&spilled);
8717-
assert_eq!(
8718-
batches_to_sort_string(&spilled),
8719-
batches_to_sort_string(&no_spill)
8720-
);
8721-
Ok(())
8722-
}

0 commit comments

Comments
 (0)