Skip to content

Commit 201099b

Browse files
mrhard9090Moltrax8claudejayzhan211alamb
authored
fix: evaluate sort-merge join filters that reference no columns (apache#26010)
## Which issue does this PR close? - Closes apache#26002. ## Rationale for this change `SortMergeJoinExec` only evaluated its join filter when the filter read at least one column. A filter that reads none (a bound parameter such as `$1 > 5`, or a volatile function such as `random() > 2`) was skipped, so every key match was kept. For `FULL JOIN` that returns matched pairs the filter rejects, where hash join null-pads both sides. ## What changes are included in this PR? - `freeze_streamed_matched` (`sort_merge_join/materializing_stream.rs`) now evaluates the filter whenever the join has one. The filter batch is built with `RecordBatchOptions::with_row_count(total_matched_rows)`, because a batch with no columns cannot infer its row count. - Two queries in `sort_merge_join.slt`: `FULL JOIN ... AND random() > 2` (every row null-padded) and `AND random() < 2` (all key matches kept). - `bitwise_stream.rs` (semi/anti/mark joins) built its filter batch the same way and failed with `must either specify a row count or at least one column` for a column-free filter. It now passes the row count too, with `join_semi_anti_mark_column_free_filter` covering all six join types. SQL cannot reach that path because the planner pushes such a predicate into an input; a `SortMergeJoinExec` built directly can. ## What is the testing strategy for this PR? `cargo test -p datafusion-sqllogictest --test sqllogictests -- sort_merge_join`: all 4 files pass. With the `materializing_stream.rs` change reverted, `sort_merge_join.slt` fails; with the `bitwise_stream.rs` change reverted, the new unit test fails with the error above. `cargo test -p datafusion-physical-plan --lib sort_merge_join`: 250 passed. `cargo fmt` and `cargo clippy -p datafusion-physical-plan --all-targets -- -D warnings` pass. ## Are there any user-facing changes? `FULL JOIN` (and other join types run by sort-merge join) with a column-free `ON` condition now returns the same rows as hash join. No API change. AI assistance: written with Claude Code; I reproduced the bug, reviewed the diff and ran the tests above. Co-authored-by: mrhard9090 <[email protected]> Co-authored-by: Claude Sonnet 5.5 <[email protected]> Co-authored-by: Jay Zhan <[email protected]> Co-authored-by: Andrew Lamb <[email protected]>
1 parent b93ef03 commit 201099b

4 files changed

Lines changed: 147 additions & 62 deletions

File tree

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

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -130,7 +130,9 @@ use crate::metrics::{
130130
use crate::spill::in_progress_spill_file::InProgressSpillFile;
131131
use crate::spill::spill_manager::SpillManager;
132132
use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
133-
use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBufferBuilder, RecordBatch};
133+
use arrow::array::{
134+
Array, ArrayRef, BooleanArray, BooleanBufferBuilder, RecordBatch, RecordBatchOptions,
135+
};
134136
use arrow::compute::{BatchCoalescer, SortOptions, filter_record_batch, not};
135137
use arrow::datatypes::SchemaRef;
136138
use arrow::util::bit_chunk_iterator::UnalignedBitChunk;
@@ -1306,7 +1308,11 @@ fn evaluate_filter_for_inner_row(
13061308
}
13071309
}
13081310

1309-
let filter_batch = RecordBatch::try_new(Arc::clone(filter.schema()), columns)?;
1311+
let filter_batch = RecordBatch::try_new_with_options(
1312+
Arc::clone(filter.schema()),
1313+
columns,
1314+
&RecordBatchOptions::new().with_row_count(Some(num_outer_rows)),
1315+
)?;
13101316
let result = filter
13111317
.expression()
13121318
.evaluate(&filter_batch)?

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

Lines changed: 64 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -47,6 +47,7 @@ use arrow::compute::{
4747
take_arrays,
4848
};
4949
use arrow::datatypes::{Schema, SchemaRef};
50+
use arrow::record_batch::RecordBatchOptions;
5051
use datafusion_common::cast::as_uint64_array;
5152
use datafusion_common::instant::Instant;
5253
use datafusion_common::{
@@ -1704,73 +1705,76 @@ impl MaterializingSortMergeJoinStream {
17041705
};
17051706
let output_batch = RecordBatch::try_new(Arc::clone(&self.schema), columns)?;
17061707

1707-
if !filter_columns.is_empty() {
1708-
if let Some(f) = &self.filter {
1709-
let schema = self.filter_schema.as_ref().unwrap_or_else(|| f.schema());
1710-
let filter_batch =
1711-
RecordBatch::try_new(Arc::clone(schema), filter_columns)?;
1712-
let filter_result = f
1713-
.expression()
1714-
.evaluate(&filter_batch)?
1715-
.into_array(filter_batch.num_rows())?;
1716-
1717-
let filter_result_mask =
1718-
datafusion_common::cast::as_boolean_array(&filter_result)?;
1719-
1720-
// Convert NULL filter results to false — NULL means "not satisfied"
1721-
// per SQL semantics, same as Left/Right outer joins.
1722-
let mask = if filter_result_mask.null_count() > 0 {
1723-
compute::prep_null_mask_filter(filter_result_mask)
1724-
} else {
1725-
filter_result_mask.clone()
1726-
};
1708+
// A filter that reads no columns (e.g. a bound parameter or a volatile
1709+
// function) still has to be evaluated, so key on the filter itself.
1710+
if let Some(f) = &self.filter {
1711+
let schema = self.filter_schema.as_ref().unwrap_or_else(|| f.schema());
1712+
let filter_batch = RecordBatch::try_new_with_options(
1713+
Arc::clone(schema),
1714+
filter_columns,
1715+
&RecordBatchOptions::new().with_row_count(Some(total_matched_rows)),
1716+
)?;
1717+
let filter_result = f
1718+
.expression()
1719+
.evaluate(&filter_batch)?
1720+
.into_array(filter_batch.num_rows())?;
1721+
1722+
let filter_result_mask =
1723+
datafusion_common::cast::as_boolean_array(&filter_result)?;
1724+
1725+
// Convert NULL filter results to false — NULL means "not satisfied"
1726+
// per SQL semantics, same as Left/Right outer joins.
1727+
let mask = if filter_result_mask.null_count() > 0 {
1728+
compute::prep_null_mask_filter(filter_result_mask)
1729+
} else {
1730+
filter_result_mask.clone()
1731+
};
17271732

1728-
if self.deferred_filtering {
1729-
self.joined_record_batches.push_batch_with_filter_metadata(
1730-
output_batch,
1731-
&combined_left_indices,
1732-
&mask,
1733-
self.streamed_batch_counter,
1734-
self.join_type,
1735-
);
1736-
} else {
1737-
let filtered_batch = filter_record_batch(&output_batch, &mask)?;
1738-
self.joined_record_batches
1739-
.push_batch_without_metadata(filtered_batch);
1740-
}
1733+
if self.deferred_filtering {
1734+
self.joined_record_batches.push_batch_with_filter_metadata(
1735+
output_batch,
1736+
&combined_left_indices,
1737+
&mask,
1738+
self.streamed_batch_counter,
1739+
self.join_type,
1740+
);
1741+
} else {
1742+
let filtered_batch = filter_record_batch(&output_batch, &mask)?;
1743+
self.joined_record_batches
1744+
.push_batch_without_metadata(filtered_batch);
1745+
}
17411746

1742-
// Track which buffered rows had all filter matches fail,
1743-
// so full join can emit them as null-joined later.
1744-
if self.join_type == JoinType::Full {
1745-
let mut offset = 0usize;
1746-
for (batch_idx, _left, right) in matched_chunks {
1747-
let chunk_len = right.len();
1748-
let buffered_batch = &mut self.buffered_data.batches[*batch_idx];
1749-
1750-
for i in 0..chunk_len {
1751-
if right.is_null(i) {
1752-
continue;
1747+
// Track which buffered rows had all filter matches fail,
1748+
// so full join can emit them as null-joined later.
1749+
if self.join_type == JoinType::Full {
1750+
let mut offset = 0usize;
1751+
for (batch_idx, _left, right) in matched_chunks {
1752+
let chunk_len = right.len();
1753+
let buffered_batch = &mut self.buffered_data.batches[*batch_idx];
1754+
1755+
for i in 0..chunk_len {
1756+
if right.is_null(i) {
1757+
continue;
1758+
}
1759+
let idx = right.value(i) as usize;
1760+
match buffered_batch.join_filter_status[idx] {
1761+
FilterState::SomePassed => {}
1762+
_ if mask.value(offset + i) => {
1763+
buffered_batch.join_filter_status[idx] =
1764+
FilterState::SomePassed;
17531765
}
1754-
let idx = right.value(i) as usize;
1755-
match buffered_batch.join_filter_status[idx] {
1756-
FilterState::SomePassed => {}
1757-
_ if mask.value(offset + i) => {
1758-
buffered_batch.join_filter_status[idx] =
1759-
FilterState::SomePassed;
1760-
}
1761-
_ => {
1762-
buffered_batch.join_filter_status[idx] =
1763-
FilterState::AllFailed;
1764-
}
1766+
_ => {
1767+
buffered_batch.join_filter_status[idx] =
1768+
FilterState::AllFailed;
17651769
}
17661770
}
1767-
offset += chunk_len;
17681771
}
1769-
debug_assert_eq!(
1770-
offset, total_matched_rows,
1771-
"offset must advance through every chunk exactly once"
1772-
);
1772+
offset += chunk_len;
17731773
}
1774+
debug_assert_eq!(
1775+
offset, total_matched_rows,
1776+
"offset must advance through every chunk exactly once"
1777+
);
17741778
}
17751779
} else {
17761780
self.joined_record_batches

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

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1615,6 +1615,43 @@ async fn join_left_mark_different_columns_count_with_filter() -> Result<()> {
16151615
Ok(())
16161616
}
16171617

1618+
#[tokio::test]
1619+
async fn join_semi_anti_mark_column_free_filter() -> Result<()> {
1620+
for join_type in [
1621+
LeftSemi, LeftAnti, LeftMark, RightSemi, RightAnti, RightMark,
1622+
] {
1623+
let left = build_table(
1624+
("a1", &vec![1, 2, 3]),
1625+
("b1", &vec![4, 5, 7]),
1626+
("c1", &vec![7, 8, 9]),
1627+
);
1628+
let right = build_table(
1629+
("a2", &vec![10, 20, 30]),
1630+
("b1", &vec![4, 5, 6]),
1631+
("c2", &vec![70, 80, 90]),
1632+
);
1633+
let on = vec![(
1634+
Arc::new(Column::new_with_schema("b1", &left.schema())?) as _,
1635+
Arc::new(Column::new_with_schema("b1", &right.schema())?) as _,
1636+
)];
1637+
// A filter that reads no columns and rejects every pair.
1638+
let filter = JoinFilter::new(
1639+
Arc::new(Literal::new(ScalarValue::Boolean(Some(false)))),
1640+
vec![],
1641+
Arc::new(Schema::empty()),
1642+
);
1643+
let (_, batches) =
1644+
join_collect_with_filter(left, right, on, filter, join_type).await?;
1645+
let rows: usize = batches.iter().map(|b| b.num_rows()).sum();
1646+
let expected = match join_type {
1647+
LeftSemi | RightSemi => 0,
1648+
_ => 3,
1649+
};
1650+
assert_eq!(rows, expected, "{join_type:?}");
1651+
}
1652+
Ok(())
1653+
}
1654+
16181655
#[tokio::test]
16191656
async fn join_right_mark_different_columns_count_with_filter() -> Result<()> {
16201657
// select *

‎datafusion/sqllogictest/test_files/sort_merge_join.slt‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1029,6 +1029,44 @@ DROP TABLE c;
10291029
statement ok
10301030
set datafusion.execution.target_partitions = 4;
10311031

1032+
# Join filter that reads no columns: it must still be evaluated for every
1033+
# candidate pair (hash join already does), so FULL JOIN null-pads both sides.
1034+
statement ok
1035+
CREATE TABLE smj_nocol_a AS SELECT * FROM (VALUES (1, 10), (2, 20), (3, 30)) t(k, v);
1036+
1037+
statement ok
1038+
CREATE TABLE smj_nocol_b AS SELECT * FROM (VALUES (1, 100), (2, 200), (4, 400)) t(k, w);
1039+
1040+
statement ok
1041+
set datafusion.execution.target_partitions = 2;
1042+
1043+
query IIII
1044+
SELECT * FROM smj_nocol_a a FULL JOIN smj_nocol_b b ON a.k = b.k AND random() > 2 ORDER BY a.k, b.k;
1045+
----
1046+
1 10 NULL NULL
1047+
2 20 NULL NULL
1048+
3 30 NULL NULL
1049+
NULL NULL 1 100
1050+
NULL NULL 2 200
1051+
NULL NULL 4 400
1052+
1053+
query IIII
1054+
SELECT * FROM smj_nocol_a a FULL JOIN smj_nocol_b b ON a.k = b.k AND random() < 2 ORDER BY a.k, b.k;
1055+
----
1056+
1 10 1 100
1057+
2 20 2 200
1058+
3 30 NULL NULL
1059+
NULL NULL 4 400
1060+
1061+
statement ok
1062+
set datafusion.execution.target_partitions = 4;
1063+
1064+
statement ok
1065+
DROP TABLE smj_nocol_a;
1066+
1067+
statement ok
1068+
DROP TABLE smj_nocol_b;
1069+
10321070
# Config reset
10331071
statement ok
10341072
RESET datafusion.optimizer.prefer_hash_join;

0 commit comments

Comments
 (0)