Skip to content

Commit 378d525

Browse files
committed
refactor: simplify sort-merge join early filtering
- Drop the `streamed_side` field: only an Inner join filters early, so the streamed side is always the left input. - Compute the buffered columns the filter reads once, not on every freeze. - Repeat the streamed row with `take` instead of a `ScalarValue` round trip. - Make `materialize_right_columns` generic over `Borrow<MatchedChunk>`, so callers pass chunks without collecting a `Vec<&MatchedChunk>` and kept chunks are borrowed rather than cloned. - Reuse `evaluate_join_filter` in the outer join path. - Build one `FilterPredicate` for both index arrays in `MatchedChunk::filter`. - Fold the column-free filter test into the hash join comparison test.
1 parent 58325af commit 378d525

2 files changed

Lines changed: 93 additions & 148 deletions

File tree

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

Lines changed: 83 additions & 102 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99
//! *streamed* side and the *buffered* side), compares join keys, and
1010
//! produces joined `RecordBatch`es.
1111
12+
use std::borrow::{Borrow, Cow};
1213
use std::cmp::Ordering;
1314
use std::collections::VecDeque;
1415
use std::fmt::Debug;
@@ -31,16 +32,16 @@ use crate::{PhysicalExpr, SendableRecordBatchStream};
3132
use arrow::array::{types::UInt64Type, *};
3233
use arrow::buffer::BooleanBuffer;
3334
use arrow::compute::{
34-
self, BatchCoalescer, SortOptions, concat_batches, filter_record_batch, interleave,
35-
take_arrays,
35+
self, BatchCoalescer, FilterBuilder, SortOptions, concat_batches,
36+
filter_record_batch, interleave, take_arrays,
3637
};
3738
use arrow::datatypes::{Schema, SchemaRef};
3839
use arrow::record_batch::RecordBatchOptions;
3940
use datafusion_common::cast::{as_boolean_array, as_uint64_array};
4041
use datafusion_common::instant::Instant;
4142
use datafusion_common::{
42-
DataFusionError, JoinSide, JoinType, NullEquality, Result, ScalarValue, exec_err,
43-
internal_err,
43+
DataFusionError, JoinSide, JoinType, NullEquality, Result, exec_err,
44+
internal_datafusion_err, internal_err,
4445
};
4546
use datafusion_execution::memory_pool::MemoryReservation;
4647
use datafusion_execution::runtime_env::RuntimeEnv;
@@ -81,18 +82,18 @@ impl MatchedChunk {
8182

8283
/// Keeps the pairs whose bit is set in `mask`.
8384
fn filter(&self, mask: &BooleanBuffer) -> Result<Self> {
84-
let mask = BooleanArray::new(mask.clone(), None);
85+
let predicate = FilterBuilder::new(&BooleanArray::new(mask.clone(), None))
86+
.optimize()
87+
.build();
8588
Ok(Self {
8689
buffered_batch_idx: self.buffered_batch_idx,
87-
streamed_indices: as_uint64_array(&compute::filter(
88-
&self.streamed_indices,
89-
&mask,
90-
)?)?
90+
streamed_indices: as_uint64_array(
91+
&predicate.filter(&self.streamed_indices)?,
92+
)?
9193
.clone(),
92-
buffered_indices: as_uint64_array(&compute::filter(
93-
&self.buffered_indices,
94-
&mask,
95-
)?)?
94+
buffered_indices: as_uint64_array(
95+
&predicate.filter(&self.buffered_indices)?,
96+
)?
9697
.clone(),
9798
filtered: self.filtered,
9899
})
@@ -487,12 +488,13 @@ pub(super) struct MaterializingSortMergeJoinStream {
487488
/// streamed row (see [`Self::pair_filtered_run`]), and at freeze for the
488489
/// remaining pairs (see [`Self::freeze_inner_filtered`]). Outer joins keep
489490
/// a rejected pair for the deferred pipeline, which may null-join its row.
491+
/// Only an Inner join filters early, so its streamed side is the left input.
490492
pub early_filtering: bool,
491-
/// The join input whose rows are streamed: the right one for a Right join,
492-
/// the left one otherwise. The join filter's column indices name join inputs.
493-
pub streamed_side: JoinSide,
494493
/// The indices of every buffered column, for materializing all of them
495494
pub buffered_columns: Vec<usize>,
495+
/// The buffered columns that the join filter reads, in the filter's order.
496+
/// Empty unless `early_filtering`.
497+
pub buffered_filter_columns: Vec<usize>,
496498
/// How many pairs the Inner join's filter has evaluated at freeze so far
497499
/// (see [`Self::filter_first_pays`])
498500
pub freeze_filter_evaluated: usize,
@@ -754,14 +756,23 @@ impl MaterializingSortMergeJoinStream {
754756
semi/anti/mark joins use BitwiseSortMergeJoinStream"
755757
);
756758
let join_time = join_metrics.join_time();
757-
let (streamed_side, buffered_side) = if join_type == JoinType::Right {
758-
(JoinSide::Right, JoinSide::Left)
759+
let buffered_side = if join_type == JoinType::Right {
760+
JoinSide::Left
759761
} else {
760-
(JoinSide::Left, JoinSide::Right)
762+
JoinSide::Right
761763
};
762764
let deferred_filtering = needs_deferred_filtering(filter.as_ref(), join_type);
763765
let early_filtering = join_type == JoinType::Inner && filter.is_some();
764766
let buffered_columns = (0..buffered_schema.fields().len()).collect();
767+
let buffered_filter_columns = match &filter {
768+
Some(f) if early_filtering => f
769+
.column_indices()
770+
.iter()
771+
.filter(|c| c.side == JoinSide::Right)
772+
.map(|c| c.index)
773+
.collect(),
774+
_ => vec![],
775+
};
765776
let filter_schema = if deferred_filtering && let Some(f) = &filter {
766777
let mut fields = Vec::with_capacity(f.schema().fields().len());
767778
for (column_index, field) in
@@ -798,8 +809,8 @@ impl MaterializingSortMergeJoinStream {
798809
deferred_filtering,
799810
filter_schema,
800811
early_filtering,
801-
streamed_side,
802812
buffered_columns,
813+
buffered_filter_columns,
803814
freeze_filter_evaluated: 0,
804815
freeze_filter_passed: 0,
805816
filter,
@@ -1016,20 +1027,20 @@ impl MaterializingSortMergeJoinStream {
10161027
return Ok(None);
10171028
};
10181029
let streamed = &self.streamed_batch.batch;
1019-
let streamed_idx = self.streamed_batch.idx;
1030+
let streamed_idx = UInt64Array::from_value(self.streamed_batch.idx as u64, len);
10201031
let columns = filter
10211032
.column_indices()
10221033
.iter()
10231034
.map(|column_index| match column_index.side {
1024-
JoinSide::None => internal_err!("Unexpected JoinSide::None in filter"),
1025-
side if side == self.streamed_side => ScalarValue::try_from_array(
1035+
JoinSide::Left => Ok(compute::take(
10261036
streamed.column(column_index.index),
1027-
streamed_idx,
1028-
)?
1029-
.to_array_of_size(len),
1030-
_ => Ok(buffered
1037+
&streamed_idx,
1038+
None,
1039+
)?),
1040+
JoinSide::Right => Ok(buffered
10311041
.column(column_index.index)
10321042
.slice(buffered_start, len)),
1043+
JoinSide::None => internal_err!("Unexpected JoinSide::None in filter"),
10331044
})
10341045
.collect::<Result<Vec<_>>>()?;
10351046
let passed = evaluate_join_filter(filter, filter.schema(), columns, len)?;
@@ -1913,9 +1924,8 @@ impl MaterializingSortMergeJoinStream {
19131924
let left_columns =
19141925
materialize_left_columns(&self.streamed_batch.batch, &combined_left_indices)?;
19151926

1916-
let chunk_refs: Vec<&MatchedChunk> = matched_chunks.iter().collect();
19171927
let right_columns = self.materialize_right_columns(
1918-
&chunk_refs,
1928+
matched_chunks,
19191929
total_matched_rows,
19201930
&self.buffered_columns,
19211931
)?;
@@ -1943,25 +1953,10 @@ impl MaterializingSortMergeJoinStream {
19431953
if let Some(f) = &self.filter {
19441954
debug_assert!(self.deferred_filtering);
19451955
let schema = self.filter_schema.as_ref().unwrap_or_else(|| f.schema());
1946-
let filter_batch = RecordBatch::try_new_with_options(
1947-
Arc::clone(schema),
1948-
filter_columns,
1949-
&RecordBatchOptions::new().with_row_count(Some(total_matched_rows)),
1950-
)?;
1951-
let filter_result = f
1952-
.expression()
1953-
.evaluate(&filter_batch)?
1954-
.into_array(filter_batch.num_rows())?;
1955-
1956-
let filter_result_mask = as_boolean_array(&filter_result)?;
1957-
1958-
// Convert NULL filter results to false — NULL means "not satisfied"
1959-
// per SQL semantics, same as Left/Right outer joins.
1960-
let mask = if filter_result_mask.null_count() > 0 {
1961-
compute::prep_null_mask_filter(filter_result_mask)
1962-
} else {
1963-
filter_result_mask.clone()
1964-
};
1956+
let mask = BooleanArray::new(
1957+
evaluate_join_filter(f, schema, filter_columns, total_matched_rows)?,
1958+
None,
1959+
);
19651960

19661961
self.joined_record_batches.push_batch_with_filter_metadata(
19671962
output_batch,
@@ -2048,46 +2043,40 @@ impl MaterializingSortMergeJoinStream {
20482043
let num_rows = unfiltered.iter().map(|c| c.len()).sum();
20492044
let streamed_indices =
20502045
concat_indices(unfiltered.iter().map(|c| &c.streamed_indices))?;
2051-
let buffered_filter_columns: Vec<usize> = filter
2052-
.column_indices()
2053-
.iter()
2054-
.filter(|c| c.side != self.streamed_side && c.side != JoinSide::None)
2055-
.map(|c| c.index)
2056-
.collect();
20572046
let mut buffered_arrays = self
20582047
.materialize_right_columns(
20592048
&unfiltered,
20602049
num_rows,
2061-
&buffered_filter_columns,
2050+
&self.buffered_filter_columns,
20622051
)?
20632052
.into_iter();
20642053
let columns = filter
20652054
.column_indices()
20662055
.iter()
20672056
.map(|column_index| match column_index.side {
2068-
JoinSide::None => {
2069-
internal_err!("Unexpected JoinSide::None in filter")
2070-
}
2071-
side if side == self.streamed_side => take_column(
2057+
JoinSide::Left => take_column(
20722058
self.streamed_batch.batch.column(column_index.index),
20732059
&streamed_indices,
20742060
),
2075-
_ => buffered_arrays.next().ok_or_else(|| {
2076-
DataFusionError::Internal(
2077-
"missing buffered filter column".to_string(),
2078-
)
2061+
JoinSide::Right => buffered_arrays.next().ok_or_else(|| {
2062+
internal_datafusion_err!("missing buffered filter column")
20792063
}),
2064+
JoinSide::None => {
2065+
internal_err!("Unexpected JoinSide::None in filter")
2066+
}
20802067
})
20812068
.collect::<Result<Vec<_>>>()?;
2082-
let passed =
2083-
evaluate_join_filter(filter, filter.schema(), columns, num_rows)?;
20842069
self.freeze_filter_evaluated += num_rows;
2085-
self.freeze_filter_passed += passed.count_set_bits();
2086-
Some(passed)
2070+
Some(evaluate_join_filter(
2071+
filter,
2072+
filter.schema(),
2073+
columns,
2074+
num_rows,
2075+
)?)
20872076
};
20882077

20892078
// Keep the pairs that passed, in order.
2090-
let mut kept: Vec<MatchedChunk> = Vec::with_capacity(matched_chunks.len());
2079+
let mut kept: Vec<Cow<MatchedChunk>> = Vec::with_capacity(matched_chunks.len());
20912080
let mut kept_rows = 0;
20922081
let mut offset = 0;
20932082
for chunk in matched_chunks {
@@ -2098,14 +2087,15 @@ impl MaterializingSortMergeJoinStream {
20982087
offset += len;
20992088
let count = mask.count_set_bits();
21002089
if count == len {
2101-
kept.push(chunk.clone());
2090+
kept.push(Cow::Borrowed(chunk));
21022091
} else if count > 0 {
2103-
kept.push(chunk.filter(&mask)?);
2092+
kept.push(Cow::Owned(chunk.filter(&mask)?));
21042093
}
2094+
self.freeze_filter_passed += count;
21052095
kept_rows += count;
21062096
}
21072097
_ => {
2108-
kept.push(chunk.clone());
2098+
kept.push(Cow::Borrowed(chunk));
21092099
kept_rows += len;
21102100
}
21112101
}
@@ -2117,12 +2107,8 @@ impl MaterializingSortMergeJoinStream {
21172107
let streamed_indices = concat_indices(kept.iter().map(|c| &c.streamed_indices))?;
21182108
let streamed_columns =
21192109
materialize_left_columns(&self.streamed_batch.batch, &streamed_indices)?;
2120-
let kept_refs: Vec<&MatchedChunk> = kept.iter().collect();
2121-
let buffered_columns = self.materialize_right_columns(
2122-
&kept_refs,
2123-
kept_rows,
2124-
&self.buffered_columns,
2125-
)?;
2110+
let buffered_columns =
2111+
self.materialize_right_columns(&kept, kept_rows, &self.buffered_columns)?;
21262112
let output_batch = RecordBatch::try_new(
21272113
Arc::clone(&self.schema),
21282114
[streamed_columns, buffered_columns].concat(),
@@ -2144,9 +2130,8 @@ impl MaterializingSortMergeJoinStream {
21442130
concat_indices(matched_chunks.iter().map(|c| &c.streamed_indices))?;
21452131
let streamed_columns =
21462132
materialize_left_columns(&self.streamed_batch.batch, &streamed_indices)?;
2147-
let chunk_refs: Vec<&MatchedChunk> = matched_chunks.iter().collect();
21482133
let buffered_columns = self.materialize_right_columns(
2149-
&chunk_refs,
2134+
matched_chunks,
21502135
total_matched_rows,
21512136
&self.buffered_columns,
21522137
)?;
@@ -2209,20 +2194,23 @@ impl MaterializingSortMergeJoinStream {
22092194
/// for a single fetch. When multiple batches are involved, `interleave`
22102195
/// gathers columns across sources. A null-row sentinel at source index 0
22112196
/// handles null right indices (unmatched streamed rows).
2212-
fn materialize_right_columns(
2197+
fn materialize_right_columns<C: Borrow<MatchedChunk>>(
22132198
&self,
2214-
matched_chunks: &[&MatchedChunk],
2199+
matched_chunks: &[C],
22152200
total_matched_rows: usize,
22162201
columns: &[usize],
22172202
) -> Result<Vec<ArrayRef>> {
2218-
let first_batch_idx = matched_chunks[0].buffered_batch_idx;
2219-
let single_source = matched_chunks
2220-
.iter()
2221-
.all(|c| c.buffered_batch_idx == first_batch_idx);
2203+
let chunks = || {
2204+
matched_chunks
2205+
.iter()
2206+
.map(|c| -> &MatchedChunk { c.borrow() })
2207+
};
2208+
let first_batch_idx = matched_chunks[0].borrow().buffered_batch_idx;
2209+
let single_source = chunks().all(|c| c.buffered_batch_idx == first_batch_idx);
22222210

22232211
if single_source {
22242212
let combined_right_indices =
2225-
concat_indices(matched_chunks.iter().map(|c| &c.buffered_indices))?;
2213+
concat_indices(chunks().map(|c| &c.buffered_indices))?;
22262214

22272215
return fetch_right_columns_by_idxs(
22282216
&self.buffered_data,
@@ -2239,9 +2227,7 @@ impl MaterializingSortMergeJoinStream {
22392227
// `interleave` walks a null buffer for *every* output row as soon as
22402228
// any input is nullable, so an always-present sentinel would tax the
22412229
// common all-matched case.
2242-
let needs_null_sentinel = matched_chunks
2243-
.iter()
2244-
.any(|c| c.buffered_indices.null_count() > 0);
2230+
let needs_null_sentinel = chunks().any(|c| c.buffered_indices.null_count() > 0);
22452231
let source_offset = usize::from(needs_null_sentinel);
22462232

22472233
// Map each distinct `buffered_batch_idx` to a contiguous source
@@ -2296,8 +2282,7 @@ impl MaterializingSortMergeJoinStream {
22962282
// (`source_data` is gathered from it), so the table is the only
22972283
// added state, and it is transient: sized to the span this freeze
22982284
// touches rather than held across freezes.
2299-
let (min_batch_idx, max_batch_idx) = matched_chunks
2300-
.iter()
2285+
let (min_batch_idx, max_batch_idx) = chunks()
23012286
.fold((usize::MAX, 0usize), |(lo, hi), c| {
23022287
(lo.min(c.buffered_batch_idx), hi.max(c.buffered_batch_idx))
23032288
});
@@ -2314,7 +2299,7 @@ impl MaterializingSortMergeJoinStream {
23142299
Vec::with_capacity(matched_chunks.len().min(source_of_batch.len()));
23152300
let mut interleave_indices: Vec<(usize, usize)> =
23162301
Vec::with_capacity(total_matched_rows);
2317-
for chunk in matched_chunks {
2302+
for chunk in chunks() {
23182303
let batch_idx = chunk.buffered_batch_idx;
23192304
let right = &chunk.buffered_indices;
23202305
let slot = &mut source_of_batch[batch_idx - min_batch_idx];
@@ -2570,17 +2555,13 @@ fn fetch_right_columns_from_batch_by_idxs(
25702555
) -> Result<Vec<ArrayRef>> {
25712556
match &buffered_batch.batch {
25722557
BufferedBatchState::InMemory(batch) => {
2573-
let arrays: Vec<ArrayRef> = columns
2574-
.iter()
2575-
.map(|&c| Arc::clone(batch.column(c)))
2576-
.collect();
2558+
let arrays = columns.iter().map(|&c| batch.column(c));
25772559
if let Some(range) = is_contiguous_range(buffered_indices) {
2578-
Ok(arrays
2579-
.iter()
2580-
.map(|a| a.slice(range.start, range.len()))
2581-
.collect())
2560+
Ok(arrays.map(|a| a.slice(range.start, range.len())).collect())
25822561
} else {
2583-
Ok(take_arrays(&arrays, buffered_indices, None)?)
2562+
arrays
2563+
.map(|a| Ok(compute::take(a.as_ref(), buffered_indices, None)?))
2564+
.collect()
25842565
}
25852566
}
25862567
BufferedBatchState::Spilled(_) => {
@@ -2593,7 +2574,7 @@ fn fetch_right_columns_from_batch_by_idxs(
25932574

25942575
/// Concatenates the index arrays of several chunks into one.
25952576
fn concat_indices<'a>(
2596-
indices: impl ExactSizeIterator<Item = &'a UInt64Array>,
2577+
indices: impl Iterator<Item = &'a UInt64Array>,
25972578
) -> Result<UInt64Array> {
25982579
let arrays: Vec<&dyn Array> = indices.map(|a| a as &dyn Array).collect();
25992580
match arrays.as_slice() {

0 commit comments

Comments
 (0)