Skip to content

Commit 2abf69d

Browse files
authored
fix(smj): handle floating-point keys across batch boundaries (apache#25134)
## Which issue does this PR close? Closes apache#25133. ## Rationale for this change Sort-merge mark, semi, and anti joins can fail when floating-point key groups cross input batches. Float32/Float64 keys containing NaN can panic, and Float16 keys can return an unsupported-type error, even though the main merge scan supports these keys. ## What changes are included in this PR? Use the existing `JoinKeyComparator` for batch-boundary comparisons involving floating-point keys, matching the main merge scan's equality semantics. Slice the right-hand keys to one row before constructing the comparator; the left-hand keys are already single-row slices. This bounds signed-zero normalization to the rows being compared. Integer-only comparisons keep the existing scalar path. There are no memory-accounting, buffering, configuration, dependency, or public-API changes. ## What is the testing strategy for this PR? `join_float_key_batch_boundaries` in `datafusion/physical-plan/src/joins/sort_merge_join/tests.rs` exercises actual one- and two-row input batches. Its 144 cases cover Float16/32/64, left/right mark/semi/anti joins, both null-equality modes, and ascending/descending order. Inputs include nulls, infinities, signed zero, unmatched keys, and NaN groups spanning batches. Assertions check exact output row IDs/order, key types, and mark values. A physical-plan test is used because the reproducer needs precise input batch boundaries, independent of SQL optimizer choices. On unpatched Apache main (`40488988ad596c9b093ad60e1453430d803ce33c`) plus only the new tests, all 144 cases fail: 96 NaN panics and 48 Float16 unsupported-type errors. Local validation of `9ea2dea17b53b8ed2f8ea877df3d95604b87f450`: - Physical-plan library: **2,096 passed**, including all 144 new regression cases. - Full extended workspace command below: **11,454 Rust tests passed, 0 failed, 8 ignored**; the SQL logic harness also completed **513/513 files** successfully. - CLI: **107 reported passed, 0 failed**. Six environment-gated cases did not exercise external storage. - `cargo fmt --all -- --check`, `git diff --check`, `cargo clippy --locked --all-targets --all-features -- -D warnings`, and the complete `./dev/rust_lint.sh` suite, including documentation: **passed**. The lint suite used the CI-pinned Hawkeye 7.0.0. ```sh ulimit -n 4096 RUST_BACKTRACE=1 cargo test --locked --profile ci --no-fail-fast \ --exclude datafusion-examples --exclude datafusion-benchmarks --exclude datafusion-cli \ --workspace --lib --tests --bins \ --features avro,json,backtrace,extended_tests,recursive_protection,parquet_encryption cargo test --locked --profile ci -p datafusion-cli ``` The initial workspace attempt failed four sort-only RSS runners (`sort_no_mem_limit_runner` and `sort_with_mem_limit_{1,2,3}_runner`) with a zero baseline RSS. All four passed an isolated serial rerun, and the subsequent full workspace rerun passed without source/test changes. The cause of the initial intermittent failures has not been established. Supplemental standalone validation, not committed to this PR: an independent row-by-row oracle passed 2,592 cases covering asymmetric/empty input batches, filters, composite keys, both null placements and the float/join options above. An allocation probe confirmed the single-row slicing bounds comparator allocation independently of the full input batch size (32 through 1,048,576 rows). These checks supplement, rather than replace, the committed regression tests. The existing eight-case `sort_merge_join` release benchmark completed on the exact upstream base and PR, with an identical harness, compiler and lockfile. Runs were ordered base→PR and PR→base, using 30 samples, one-second warmup and a three-second requested measurement time. Short-run differences were mixed; the left-semi delta reversed from +3.5% to -2.6%. Inner 1-to-1 was initially slower (+9.9% and +3.7%), so it was repeated in three longer, alternating-order pairs (50 samples, eight-second requested measurement time). The PR/base point-estimate differences were -0.17%, +0.26% and -0.84%; Criterion reported change within its noise threshold or no change. The initial slowdown did not reproduce. These are integer-key control workloads on a development machine, not a floating-point speedup benchmark; no speedup or general performance-neutrality claim is made. Upstream test workflows currently require maintainer approval (`action_required`); local results above are not a claim that GitHub CI or coverage checks have passed. ## Are there any user-facing changes? Affected sort-merge joins can complete instead of failing at floating-point batch boundaries. No public API changes. AI-assisted contribution (OpenAI Codex).
1 parent 935748d commit 2abf69d

2 files changed

Lines changed: 129 additions & 0 deletions

File tree

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

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1193,6 +1193,21 @@ fn keys_match(
11931193
null_equality: NullEquality,
11941194
) -> Result<bool> {
11951195
debug_assert!(left_arrays.iter().all(|a| a.len() == 1));
1196+
if left_arrays
1197+
.iter()
1198+
.any(|array| array.data_type().is_floating())
1199+
{
1200+
// The scalar comparator's partial_cmp panics on NaN. Match the merge
1201+
// scan's floating-point equality, including its signed-zero handling.
1202+
let right_keys = slice_keys(right_arrays, 0);
1203+
return Ok(JoinKeyComparator::new(
1204+
left_arrays,
1205+
&right_keys,
1206+
sort_options,
1207+
null_equality,
1208+
)?
1209+
.is_equal(0, 0));
1210+
}
11961211
let cmp = compare_join_arrays(
11971212
left_arrays,
11981213
0,

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

Lines changed: 114 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4353,6 +4353,120 @@ fn columns(schema: &Schema) -> Vec<String> {
43534353
schema.fields().iter().map(|f| f.name().clone()).collect()
43544354
}
43554355

4356+
// Floating-point key groups must compare consistently within and across batches.
4357+
#[rstest::rstest]
4358+
#[tokio::test]
4359+
async fn join_float_key_batch_boundaries(
4360+
#[values(DataType::Float16, DataType::Float32, DataType::Float64)] key_type: DataType,
4361+
#[values(LeftMark, RightMark, LeftSemi, RightSemi, LeftAnti, RightAnti)]
4362+
join_type: JoinType,
4363+
#[values(NullEquality::NullEqualsNothing, NullEquality::NullEqualsNull)]
4364+
null_equality: NullEquality,
4365+
#[values(false, true)] descending: bool,
4366+
#[values(1, 2)] input_batch_size: usize,
4367+
) -> Result<()> {
4368+
let input = |unmatched_key| -> Result<Arc<dyn ExecutionPlan>> {
4369+
let mut keys = vec![
4370+
None,
4371+
Some(f64::NEG_INFINITY),
4372+
Some(-0.0),
4373+
Some(0.0),
4374+
Some(unmatched_key),
4375+
Some(f64::INFINITY),
4376+
Some(f64::NAN),
4377+
Some(f64::NAN),
4378+
Some(f64::NAN),
4379+
];
4380+
let mut ids: Vec<i32> = (0..keys.len() as i32).collect();
4381+
if descending {
4382+
keys.reverse();
4383+
ids.reverse();
4384+
}
4385+
let batch = RecordBatch::try_from_iter(vec![
4386+
(
4387+
"id",
4388+
Arc::new(Int32Array::from(ids)) as arrow::array::ArrayRef,
4389+
),
4390+
(
4391+
"key",
4392+
arrow::compute::cast(&arrow::array::Float64Array::from(keys), &key_type)?,
4393+
),
4394+
])?;
4395+
Ok(build_table_from_batches(
4396+
(0..batch.num_rows())
4397+
.step_by(input_batch_size)
4398+
.map(|offset| {
4399+
batch.slice(offset, input_batch_size.min(batch.num_rows() - offset))
4400+
})
4401+
.collect(),
4402+
))
4403+
};
4404+
let on: JoinOn = vec![(
4405+
Arc::new(Column::new("key", 1)),
4406+
Arc::new(Column::new("key", 1)),
4407+
)];
4408+
let (_, output) = join_collect_with_options(
4409+
input(1.0)?,
4410+
input(2.0)?,
4411+
on,
4412+
join_type,
4413+
vec![SortOptions {
4414+
descending,
4415+
nulls_first: !descending,
4416+
}],
4417+
null_equality,
4418+
)
4419+
.await?;
4420+
4421+
let is_mark = matches!(join_type, LeftMark | RightMark);
4422+
let is_anti = matches!(join_type, LeftAnti | RightAnti);
4423+
let mut expected: Vec<_> = (0..9)
4424+
.map(|id| {
4425+
let matched =
4426+
id != 4 && (id != 0 || null_equality == NullEquality::NullEqualsNull);
4427+
(id, matched)
4428+
})
4429+
.filter(|(_, matched)| is_mark || *matched != is_anti)
4430+
.collect();
4431+
if descending {
4432+
expected.reverse();
4433+
}
4434+
let mut ids = vec![];
4435+
let mut marks = vec![];
4436+
for batch in output {
4437+
assert_eq!(batch.schema().field(1).data_type(), &key_type);
4438+
ids.extend_from_slice(
4439+
batch
4440+
.column(0)
4441+
.as_any()
4442+
.downcast_ref::<Int32Array>()
4443+
.unwrap()
4444+
.values(),
4445+
);
4446+
if is_mark {
4447+
marks.extend(
4448+
batch
4449+
.column(2)
4450+
.as_any()
4451+
.downcast_ref::<BooleanArray>()
4452+
.unwrap()
4453+
.iter(),
4454+
);
4455+
}
4456+
}
4457+
assert_eq!(ids, expected.iter().map(|(id, _)| *id).collect::<Vec<_>>());
4458+
if is_mark {
4459+
assert_eq!(
4460+
marks,
4461+
expected
4462+
.iter()
4463+
.map(|(_, matched)| Some(*matched))
4464+
.collect::<Vec<_>>()
4465+
);
4466+
}
4467+
Ok(())
4468+
}
4469+
43564470
// ==================== BitwiseSortMergeJoinStream direct tests ====================
43574471
//
43584472
// These tests construct a BitwiseSortMergeJoinStream directly (bypassing exec)

0 commit comments

Comments
 (0)