andygrove commented on code in PR #27278:
URL: https://github.com/apache/datafusion/pull/27278#discussion_r4619460544
##########
datafusion/physical-plan/benches/sort_merge_join.rs:
##########
@@ -232,6 +276,103 @@ fn bench_smj(c: &mut Criterion) {
});
}
+ // 1:10 and 1:100 Inner Joins with a filter. `left.data < right.data` keeps
+ // about half of the pairs. A streamed row meets a run of 10 or 100
buffered
+ // rows, so its pairs are filtered at freeze.
+ for (n, key_mod, name) in [
+ (100_000, 10_000, "inner_1to10_filtered"),
+ (20_000, 200, "inner_1to100_filtered"),
+ ] {
+ let left_batches = build_sorted_batches(n, key_mod, &s);
+ let right_batches = build_sorted_batches(n, key_mod, &s);
+ group.bench_function(BenchmarkId::new(name, n), |b| {
+ b.iter(|| {
+ let left = make_exec(&left_batches, &s);
+ let right = make_exec(&right_batches, &s);
+ do_join_with_filter(
+ left,
+ right,
+ datafusion_common::JoinType::Inner,
+ Some(data_lt_filter()),
+ &rt,
+ )
+ })
+ });
+ }
+
+ // 1:10 Inner Joins with a filter that keeps most pairs — 100K left, 100K
right,
+ // 10K distinct keys. `left.data <> right.data` drops only the pair of a
row with
+ // itself, keeping 90% of the pairs. The narrow case joins just `key` and
`data`,
+ // so the filter reads half of the output columns.
+ {
+ let n = 100_000;
+ let key_mod = 10_000;
+ let left_batches = build_sorted_batches(n, key_mod, &s);
+ let right_batches = build_sorted_batches(n, key_mod, &s);
+ group.bench_function(
+ BenchmarkId::new("inner_1to10_high_pass_filtered", n),
+ |b| {
+ b.iter(|| {
+ let left = make_exec(&left_batches, &s);
+ let right = make_exec(&right_batches, &s);
+ do_join_with_filter(
+ left,
+ right,
+ datafusion_common::JoinType::Inner,
+ Some(data_filter(Operator::NotEq)),
+ &rt,
+ )
+ })
+ },
+ );
+ let narrow = narrow_schema();
+ let left_batches = build_narrow_sorted_batches(n, key_mod);
+ let right_batches = build_narrow_sorted_batches(n, key_mod);
+ group.bench_function(
+ BenchmarkId::new("inner_1to10_high_pass_filtered_narrow", n),
+ |b| {
+ b.iter(|| {
+ let left = make_exec(&left_batches, &narrow);
+ let right = make_exec(&right_batches, &narrow);
+ do_join_with_filter(
+ left,
+ right,
+ datafusion_common::JoinType::Inner,
+ Some(data_filter(Operator::NotEq)),
+ &rt,
+ )
+ })
+ },
+ );
+ }
+
+ // 1:1000 Inner Join with a selective filter — 2K left, 20K right, 20 keys
+ // Every streamed row meets a run of 1000 buffered rows, the shape of
TPC-DS
+ // q72's `catalog_sales` to `inventory` join. Each key's 100 streamed rows
take
+ // the smallest of its `data` values, so `left.data > right.data` keeps
about
+ // 5% of the 2M pairs. Such runs are filtered as they are paired.
Review Comment:
Filtering while pairing is gone, so this sentence no longer holds. The last
sentence of the 1:10/1:100 comment on line 281 (`so its pairs are filtered at
freeze`) was written to contrast with it, so it can go too.
```suggestion
// 5% of the 2M pairs.
```
##########
datafusion/physical-plan/src/joins/sort_merge_join/materializing_stream.rs:
##########
@@ -1771,33 +2008,215 @@ impl MaterializingSortMergeJoinStream {
Ok(())
}
- /// Materializes right-side columns across all matched chunks.
+ /// Freezes the matched pairs of an Inner join with a filter. The filter
runs
+ /// on just the columns it reads, for the pairs of the chunks that
+ /// [`Self::pair_filtered_run`] did not filter already, and only the pairs
that
+ /// pass have their output columns materialized. A selective filter over a
+ /// many-to-many join rejects most pairs, so materializing every column of
+ /// every pair before filtering would spend most of the freeze on rows that
+ /// are then dropped. When no chunk was filtered already and earlier
freezes
+ /// kept enough of their pairs, [`Self::filter_first_pays`] says the
opposite,
+ /// and the batch is materialized whole and then filtered.
+ fn freeze_inner_filtered(
+ &mut self,
+ matched_chunks: &[MatchedChunk],
+ total_matched_rows: usize,
+ ) -> Result<()> {
+ let Some(filter) = &self.filter else {
+ return internal_err!("early filtering requires a join filter");
+ };
+ debug_assert_eq!(
+ self.join_type,
+ JoinType::Inner,
+ "only an Inner join filters early, so the streamed side is the
left one"
+ );
+
+ // Evaluate the filter over the pairs of the chunks not filtered yet.
+ let unfiltered: Vec<&MatchedChunk> =
+ matched_chunks.iter().filter(|c| !c.filtered).collect();
+ if unfiltered.len() == matched_chunks.len() &&
!self.filter_first_pays(filter) {
+ return self.freeze_inner_filtered_whole(matched_chunks,
total_matched_rows);
+ }
+ let passed = if unfiltered.is_empty() {
+ None
+ } else {
+ let num_rows = unfiltered.iter().map(|c| c.len()).sum();
+ let streamed_indices =
+ concat_indices(unfiltered.iter().map(|c|
&c.streamed_indices))?;
+ let mut buffered_arrays = self
+ .materialize_right_columns(
+ &unfiltered,
+ num_rows,
+ &self.buffered_filter_columns,
+ )?
+ .into_iter();
+ let columns = filter
+ .column_indices()
+ .iter()
+ .map(|column_index| match column_index.side {
+ JoinSide::Left => take_column(
+ self.streamed_batch.batch.column(column_index.index),
+ &streamed_indices,
+ ),
+ JoinSide::Right => buffered_arrays.next().ok_or_else(|| {
+ internal_datafusion_err!("missing buffered filter
column")
+ }),
+ JoinSide::None => {
+ internal_err!("Unexpected JoinSide::None in filter")
+ }
+ })
+ .collect::<Result<Vec<_>>>()?;
+ self.freeze_filter_evaluated += num_rows;
+ Some(evaluate_join_filter(
+ filter,
+ filter.schema(),
+ columns,
+ num_rows,
+ )?)
+ };
+
+ // Keep the pairs that passed, in order.
+ let mut kept: Vec<Cow<MatchedChunk>> =
Vec::with_capacity(matched_chunks.len());
+ let mut kept_rows = 0;
+ let mut offset = 0;
+ for chunk in matched_chunks {
+ let len = chunk.len();
+ match (&passed, chunk.filtered) {
+ (Some(passed), false) => {
+ let mask = passed.slice(offset, len);
+ offset += len;
+ let count = mask.count_set_bits();
+ if count == len {
+ kept.push(Cow::Borrowed(chunk));
+ } else if count > 0 {
+ kept.push(Cow::Owned(chunk.filter(&mask)?));
+ }
+ self.freeze_filter_passed += count;
+ kept_rows += count;
+ }
+ _ => {
+ kept.push(Cow::Borrowed(chunk));
+ kept_rows += len;
+ }
+ }
+ }
+ if kept_rows == 0 {
+ return Ok(());
+ }
+
+ let streamed_indices = concat_indices(kept.iter().map(|c|
&c.streamed_indices))?;
+ let streamed_columns =
+ materialize_left_columns(&self.streamed_batch.batch,
&streamed_indices)?;
+ let buffered_columns =
+ self.materialize_right_columns(&kept, kept_rows,
&self.buffered_columns)?;
+ let output_batch = RecordBatch::try_new(
+ Arc::clone(&self.schema),
+ [streamed_columns, buffered_columns].concat(),
+ )?;
+ self.joined_record_batches
+ .push_batch_without_metadata(output_batch);
+ Ok(())
+ }
+
+ /// Freezes the matched pairs of an Inner join with a filter by
materializing
+ /// every column of every pair, evaluating the filter on the columns it
reads,
+ /// and filtering the batch. None of the pairs was filtered already.
+ fn freeze_inner_filtered_whole(
+ &mut self,
+ matched_chunks: &[MatchedChunk],
+ total_matched_rows: usize,
+ ) -> Result<()> {
+ let streamed_indices =
+ concat_indices(matched_chunks.iter().map(|c|
&c.streamed_indices))?;
+ let streamed_columns =
+ materialize_left_columns(&self.streamed_batch.batch,
&streamed_indices)?;
+ let buffered_columns = self.materialize_right_columns(
+ matched_chunks,
+ total_matched_rows,
+ &self.buffered_columns,
+ )?;
+ let Some(filter) = &self.filter else {
+ return internal_err!("early filtering requires a join filter");
+ };
+ let filter_columns =
+ get_filter_columns(Some(filter), &streamed_columns,
&buffered_columns)?;
+ let passed = evaluate_join_filter(
+ filter,
+ filter.schema(),
+ filter_columns,
+ total_matched_rows,
+ )?;
+ let kept_rows = passed.count_set_bits();
+ self.freeze_filter_evaluated += total_matched_rows;
+ self.freeze_filter_passed += kept_rows;
+ if kept_rows == 0 {
+ return Ok(());
+ }
+
+ let output_batch = RecordBatch::try_new(
+ Arc::clone(&self.schema),
+ [streamed_columns, buffered_columns].concat(),
+ )?;
+ let output_batch = if kept_rows == total_matched_rows {
+ output_batch
+ } else {
+ filter_record_batch(&output_batch, &BooleanArray::new(passed,
None))?
+ };
+ self.joined_record_batches
+ .push_batch_without_metadata(output_batch);
+ Ok(())
+ }
+
+ /// Whether filtering the pairs of a freeze before materializing them is
cheaper
+ /// than materializing every column of every pair and filtering the batch.
+ ///
+ /// Filtering first gathers the filter's `f` columns for every pair,
filters the
+ /// pairs' two index arrays, and gathers all `k` output columns for the
share
+ /// `p` of pairs that pass. The other way gathers the `k` columns for every
+ /// pair and copies the share `p` of them to filter the batch. Counting a
+ /// gathered value as 1 and a copied one as 1/2, filtering first is cheaper
+ /// while `f + 1 + k·p < k + k·p/2`, that is while `p < 2·(k - f - 1)/k`.
`p` is
+ /// the share that passed in the earlier freezes, or 0 before the first.
+ fn filter_first_pays(&self, filter: &JoinFilter) -> bool {
+ let k = self.schema.fields().len() as f64;
+ let f = filter.column_indices().len() as f64;
+ let p = if self.freeze_filter_evaluated == 0 {
+ 0.0
+ } else {
+ self.freeze_filter_passed as f64 / self.freeze_filter_evaluated as
f64
+ };
+ p < 2.0 * (k - f - 1.0) / k
Review Comment:
Following up on @viirya's note that the model counts columns rather than
bytes: it turns into a regression when the filter reads string columns and
keeps most pairs. With `k = 6` and `f = 2` the threshold is `2(6 - 2 - 1)/6 =
1.0`, so a 90% pass rate still filters first. Filtering first then gathers the
two strings for every pair, and gathers them again for the 90% that pass.
I ran `inner_1to10_high_pass_filtered`'s inputs with the filter
`left.payload <> right.payload`, which keeps the same 90% of pairs. Over 5
alternating rounds against 9d916ab47, this PR takes 1.14x as long as `main`
(14.91 to 16.99 ms), and 1.15x in a second run of 5 rounds. With `left.payload
< right.payload`, which keeps 45%, it's 0.94x, so this only shows up when most
pairs pass.
Reusing the filter's columns fixes it at the root. Filtering first already
holds them for every pair, so it can filter them by `passed`, as it does the
index arrays, instead of gathering them again. Only the other columns are then
gathered for the pairs that passed. Medians of that second run, as a ratio to
`main`:
| Case | This PR | Reusing the filter's columns |
|---|---:|---:|
| 1:10, `left.payload <> right.payload`, 90% kept | 1.15 | 0.93 |
| 1:10, `left.payload < right.payload`, 45% kept | 0.95 | 0.94 |
| `inner_1to10_filtered` | 0.56 | 0.53 |
| `inner_1to10_high_pass_filtered` | 0.80 | 0.76 |
| `inner_1to10_high_pass_filtered_narrow` | 1.04 | 1.02 |
| `inner_1to1000_selective_filtered` | 0.23 | 0.23 |
| 8-row buffered batches, 95% kept | 1.09 | 1.03 |
| 64-row buffered batches, 95% kept | 0.95 | 0.90 |
| 8-row buffered batches, 5% kept | 0.91 | 0.89 |
The unfiltered `inner_1to1` control read 1.01 and 1.02. The diff is below.
It passes the 498 SMJ tests, clippy, and the differential test from the review
summary. It keeps your threshold, which becomes a little cautious, because the
second step now costs `f·p/2 + (k - f)·p` rather than `k·p`. The doc comment
would need that change too. Weighting a variable-width column as four in
`filter_first_pays` also fixed the 90% case (0.94x) and left the 8-row case at
1.05x, if you'd rather keep the change in the model, but then the weight is a
guess.
<details><summary>Diff against f71c600f8</summary>
```diff
diff --git
a/datafusion/physical-plan/src/joins/sort_merge_join/materializing_stream.rs
b/datafusion/physical-plan/src/joins/sort_merge_join/materializing_stream.rs
index dbfaf8f69..ca90ccacd 100644
---
a/datafusion/physical-plan/src/joins/sort_merge_join/materializing_stream.rs
+++
b/datafusion/physical-plan/src/joins/sort_merge_join/materializing_stream.rs
@@ -1851,21 +1851,20 @@ impl MaterializingSortMergeJoinStream {
);
}
- let mut streamed_arrays = materialize_left_columns(
+ let streamed_filter_arrays = materialize_left_columns(
&self
.streamed_batch
.batch
.project(&self.streamed_filter_columns)?,
&streamed_indices,
- )?
- .into_iter();
- let mut buffered_arrays = self
- .materialize_right_columns(
- matched_chunks,
- total_matched_rows,
- &self.buffered_filter_columns,
- )?
- .into_iter();
+ )?;
+ let buffered_filter_arrays = self.materialize_right_columns(
+ matched_chunks,
+ total_matched_rows,
+ &self.buffered_filter_columns,
+ )?;
+ let mut streamed_arrays = streamed_filter_arrays.iter().cloned();
+ let mut buffered_arrays = buffered_filter_arrays.iter().cloned();
let columns = filter
.column_indices()
.iter()
@@ -1912,10 +1911,34 @@ impl MaterializingSortMergeJoinStream {
}
}
- let streamed_columns =
- materialize_left_columns(&self.streamed_batch.batch,
&kept_streamed)?;
- let buffered_columns =
- self.materialize_right_columns(&kept, kept_rows,
&self.buffered_columns)?;
+ // The filter's columns are already gathered for every pair, so
filter
+ // them rather than gathering them again for the pairs that passed.
+ let keep = |array: &ArrayRef| -> Result<ArrayRef> {
+ if kept_rows == total_matched_rows {
+ Ok(Arc::clone(array))
+ } else {
+ Ok(predicate.filter(array.as_ref())?)
+ }
+ };
+ let streamed_columns = output_columns(
+ self.streamed_schema.fields().len(),
+ &self.streamed_filter_columns,
+ &streamed_filter_arrays,
+ keep,
+ |others| {
+ materialize_left_columns(
+ &self.streamed_batch.batch.project(others)?,
+ &kept_streamed,
+ )
+ },
+ )?;
+ let buffered_columns = output_columns(
+ self.buffered_schema.fields().len(),
+ &self.buffered_filter_columns,
+ &buffered_filter_arrays,
+ keep,
+ |others| self.materialize_right_columns(&kept, kept_rows,
others),
+ )?;
let output_batch = RecordBatch::try_new(
Arc::clone(&self.schema),
[streamed_columns, buffered_columns].concat(),
@@ -2392,6 +2415,35 @@ fn fetch_right_columns_from_batch_by_idxs(
}
}
+/// The `num_columns` output columns of one side for the pairs that passed
the
+/// filter. A column the filter read comes from `keep` applied to its array
in
+/// `filter_arrays`, and `gather` materializes the others.
+fn output_columns(
+ num_columns: usize,
+ filter_columns: &[usize],
+ filter_arrays: &[ArrayRef],
+ keep: impl Fn(&ArrayRef) -> Result<ArrayRef>,
+ gather: impl FnOnce(&[usize]) -> Result<Vec<ArrayRef>>,
+) -> Result<Vec<ArrayRef>> {
+ let others: Vec<usize> = (0..num_columns)
+ .filter(|c| !filter_columns.contains(c))
+ .collect();
+ let mut gathered = if others.is_empty() {
+ vec![]
+ } else {
+ gather(&others)?
+ }
+ .into_iter();
+ (0..num_columns)
+ .map(|c| match filter_columns.iter().position(|&f| f == c) {
+ Some(position) => keep(&filter_arrays[position]),
+ None => gathered
+ .next()
+ .ok_or_else(|| internal_datafusion_err!("missing output
column")),
+ })
+ .collect()
+}
+
/// Concatenates the index arrays of several chunks into one.
fn concat_indices<'a>(
indices: impl Iterator<Item = &'a UInt64Array>,
```
</details>
--
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]