Skip to content

Commit 597b29e

Browse files
committed
fix -0.0 comparison bug found by extending fuzz testing
1 parent 66bcb67 commit 597b29e

3 files changed

Lines changed: 126 additions & 42 deletions

File tree

‎datafusion/core/tests/fuzz_cases/join_fuzz.rs‎

Lines changed: 91 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -20,9 +20,9 @@ use std::time::SystemTime;
2020

2121
use crate::fuzz_cases::join_fuzz::JoinTestType::{HjSmj, NljHj};
2222

23-
use arrow::array::{Array, ArrayRef, BinaryArray, Int32Array};
23+
use arrow::array::{Array, ArrayRef, BinaryArray, Float64Array, Int32Array};
2424
use arrow::compute::SortOptions;
25-
use arrow::datatypes::Schema;
25+
use arrow::datatypes::{DataType, Schema};
2626
use arrow::record_batch::RecordBatch;
2727
use arrow::util::pretty::pretty_format_batches;
2828
use datafusion::common::JoinSide;
@@ -1381,29 +1381,79 @@ fn make_staggered_batches_binary(
13811381
// extreme on a separate task and those are then combined, and only randomization varies which
13821382
// partition holds the deciding key, or holds none at all.
13831383

1384-
fn pwmj_kv_schema() -> Arc<Schema> {
1384+
/// A key type the differential fuzz test can generate and array-ify. `i32` covers the plain
1385+
/// ordering/duplicate/NULL dimensions; `f64` adds `-0.0` and `NaN`, whose comparison semantics
1386+
/// arrow's `cmp` kernels and its `min`/`max` accumulators must agree on for
1387+
/// `PiecewiseMergeJoinExec`'s buffered-side reduction to be sound (see `right_existence_join`'s
1388+
/// module doc).
1389+
trait PwmjFuzzKey: Copy + 'static {
1390+
fn data_type() -> DataType;
1391+
fn to_array(values: &[Option<Self>]) -> ArrayRef;
1392+
/// Draws a value for the narrow `[0, key_range)` range the rest of the test relies on to
1393+
/// force duplicates and equal-boundary cases, plus (for floats) the values a uniform draw
1394+
/// over that range would never produce on its own.
1395+
fn gen_value(key_range: i32, rng: &mut StdRng) -> Self;
1396+
}
1397+
1398+
impl PwmjFuzzKey for i32 {
1399+
fn data_type() -> DataType {
1400+
DataType::Int32
1401+
}
1402+
1403+
fn to_array(values: &[Option<Self>]) -> ArrayRef {
1404+
Arc::new(Int32Array::from(values.to_vec()))
1405+
}
1406+
1407+
fn gen_value(key_range: i32, rng: &mut StdRng) -> Self {
1408+
rng.random_range(0..key_range)
1409+
}
1410+
}
1411+
1412+
impl PwmjFuzzKey for f64 {
1413+
fn data_type() -> DataType {
1414+
DataType::Float64
1415+
}
1416+
1417+
fn to_array(values: &[Option<Self>]) -> ArrayRef {
1418+
Arc::new(Float64Array::from(values.to_vec()))
1419+
}
1420+
1421+
fn gen_value(key_range: i32, rng: &mut StdRng) -> Self {
1422+
// One in 8 draws hits `-0.0` or `NaN` instead of the uniform range: both must compare
1423+
// consistently between the `cmp` kernel used to filter the streamed side and the
1424+
// `min`/`max` accumulators used to reduce the buffered side, and a plain uniform draw
1425+
// over `[0, key_range)` would essentially never produce either on its own.
1426+
match rng.random_range(0..8u32) {
1427+
0 => -0.0,
1428+
1 => f64::NAN,
1429+
_ => f64::from(rng.random_range(0..key_range)),
1430+
}
1431+
}
1432+
}
1433+
1434+
fn pwmj_kv_schema<K: PwmjFuzzKey>() -> Arc<Schema> {
13851435
Arc::new(Schema::new(vec![
1386-
arrow::datatypes::Field::new("id", arrow::datatypes::DataType::Int32, false),
1387-
arrow::datatypes::Field::new("k", arrow::datatypes::DataType::Int32, true),
1436+
arrow::datatypes::Field::new("id", DataType::Int32, false),
1437+
arrow::datatypes::Field::new("k", K::data_type(), true),
13881438
]))
13891439
}
13901440

1391-
fn pwmj_kv_batch(ids: &[i32], keys: &[Option<i32>]) -> RecordBatch {
1441+
fn pwmj_kv_batch<K: PwmjFuzzKey>(ids: &[i32], keys: &[Option<K>]) -> RecordBatch {
13921442
RecordBatch::try_new(
1393-
pwmj_kv_schema(),
1394-
vec![
1395-
Arc::new(Int32Array::from(ids.to_vec())),
1396-
Arc::new(Int32Array::from(keys.to_vec())),
1397-
],
1443+
pwmj_kv_schema::<K>(),
1444+
vec![Arc::new(Int32Array::from(ids.to_vec())), K::to_array(keys)],
13981445
)
13991446
.unwrap()
14001447
}
14011448

14021449
/// Single-partition, single-batch input: the buffered side, and the oracle's probe side.
1403-
fn pwmj_single_exec(ids: &[i32], keys: &[Option<i32>]) -> Arc<dyn ExecutionPlan> {
1450+
fn pwmj_single_exec<K: PwmjFuzzKey>(
1451+
ids: &[i32],
1452+
keys: &[Option<K>],
1453+
) -> Arc<dyn ExecutionPlan> {
14041454
MemorySourceConfig::try_new_exec(
14051455
&[vec![pwmj_kv_batch(ids, keys)]],
1406-
pwmj_kv_schema(),
1456+
pwmj_kv_schema::<K>(),
14071457
None,
14081458
)
14091459
.unwrap()
@@ -1413,9 +1463,9 @@ fn pwmj_single_exec(ids: &[i32], keys: &[Option<i32>]) -> Arc<dyn ExecutionPlan>
14131463
/// that draws no row left holding a single empty batch. Used for the streamed side throughout,
14141464
/// and for the buffered side of the right existence joins, which place no single-partition
14151465
/// requirement on it.
1416-
fn pwmj_parts_exec(
1466+
fn pwmj_parts_exec<K: PwmjFuzzKey>(
14171467
ids: &[i32],
1418-
keys: &[Option<i32>],
1468+
keys: &[Option<K>],
14191469
nparts: usize,
14201470
) -> Arc<dyn ExecutionPlan> {
14211471
let nparts = nparts.max(1);
@@ -1425,10 +1475,10 @@ fn pwmj_parts_exec(
14251475
}
14261476
for p in partitions.iter_mut() {
14271477
if p.is_empty() {
1428-
p.push(pwmj_kv_batch(&[], &[]));
1478+
p.push(pwmj_kv_batch::<K>(&[], &[]));
14291479
}
14301480
}
1431-
MemorySourceConfig::try_new_exec(&partitions, pwmj_kv_schema(), None).unwrap()
1481+
MemorySourceConfig::try_new_exec(&partitions, pwmj_kv_schema::<K>(), None).unwrap()
14321482
}
14331483

14341484
fn pwmj_plan(
@@ -1466,15 +1516,15 @@ fn pwmj_plan(
14661516
)
14671517
}
14681518

1469-
fn pwmj_nlj_oracle_plan(
1519+
fn pwmj_nlj_oracle_plan<K: PwmjFuzzKey>(
14701520
left: Arc<dyn ExecutionPlan>,
14711521
right: Arc<dyn ExecutionPlan>,
14721522
op: Operator,
14731523
join_type: JoinType,
14741524
) -> Arc<dyn ExecutionPlan> {
14751525
let intermediate_schema = Schema::new(vec![
1476-
arrow::datatypes::Field::new("k", arrow::datatypes::DataType::Int32, true),
1477-
arrow::datatypes::Field::new("k", arrow::datatypes::DataType::Int32, true),
1526+
arrow::datatypes::Field::new("k", K::data_type(), true),
1527+
arrow::datatypes::Field::new("k", K::data_type(), true),
14781528
]);
14791529
let expr = Arc::new(BinaryExpr::new(
14801530
Arc::new(Column::new("k", 0)),
@@ -1551,15 +1601,17 @@ async fn pwmj_collect_id_pairs(
15511601
}
15521602

15531603
/// Differential test for every join type `PiecewiseMergeJoin` supports, against a
1554-
/// `NestedLoopJoin` oracle.
1604+
/// `NestedLoopJoin` oracle, run once over `i32` keys and once over `f64` keys via
1605+
/// [`run_pwmj_fuzz`].
15551606
///
15561607
/// `Left`/`Full` are the ones with teeth: their unmatched buffered rows are derived from the
15571608
/// shared `min_marked` watermark rather than materialized per row, and that encoding is only
15581609
/// valid because every match marks a *suffix* of the buffered side. The dimensions the
15591610
/// cheaper tests do not reach are the ones that matter here -- `pwmj.slt` and the unit tests
15601611
/// both run the streamed side at a single partition and the default batch size, so neither
15611612
/// covers several partitions racing to run the final pass, nor the mid-scan resume path a
1562-
/// small batch size forces.
1613+
/// small batch size forces. The `f64` pass adds `-0.0` and `NaN`, which `pwmj.slt` only
1614+
/// exercises via a handful of fixed rows.
15631615
#[tokio::test(flavor = "multi_thread")]
15641616
async fn fuzz_pwmj_matches_nested_loop() {
15651617
// A small batch size splits output across several coalesced batches even for these tiny
@@ -1568,6 +1620,13 @@ async fn fuzz_pwmj_matches_nested_loop() {
15681620
TaskContext::default()
15691621
.with_session_config(SessionConfig::new().with_batch_size(3)),
15701622
);
1623+
// `f64` keys run every dimension below a second time with `-0.0` and `NaN` mixed in, on
1624+
// top of what `i32` already covers with plain duplicates and NULLs.
1625+
run_pwmj_fuzz::<i32>(&task_ctx).await;
1626+
run_pwmj_fuzz::<f64>(&task_ctx).await;
1627+
}
1628+
1629+
async fn run_pwmj_fuzz<K: PwmjFuzzKey + std::fmt::Debug>(task_ctx: &Arc<TaskContext>) {
15711630
let ops = [Operator::Lt, Operator::LtEq, Operator::Gt, Operator::GtEq];
15721631
let join_types = [
15731632
JoinType::Inner,
@@ -1592,9 +1651,9 @@ async fn fuzz_pwmj_matches_nested_loop() {
15921651
// the others require the buffered side coalesced and globally sorted.
15931652
let buffered_nparts = rng.random_range(1..4usize);
15941653

1595-
let gen_keys = |n: usize, rng: &mut StdRng| -> Vec<Option<i32>> {
1654+
let gen_keys = |n: usize, rng: &mut StdRng| -> Vec<Option<K>> {
15961655
(0..n)
1597-
.map(|_| (!rng.random_bool(0.2)).then(|| rng.random_range(0..key_range)))
1656+
.map(|_| (!rng.random_bool(0.2)).then(|| K::gen_value(key_range, rng)))
15981657
.collect()
15991658
};
16001659

@@ -1621,25 +1680,27 @@ async fn fuzz_pwmj_matches_nested_loop() {
16211680
op,
16221681
join_type,
16231682
),
1624-
Arc::clone(&task_ctx),
1683+
Arc::clone(task_ctx),
16251684
)
16261685
.await;
16271686
let want = pwmj_collect_id_pairs(
1628-
pwmj_nlj_oracle_plan(
1687+
pwmj_nlj_oracle_plan::<K>(
16291688
pwmj_single_exec(&left_ids, &left_keys),
16301689
pwmj_single_exec(&right_ids, &right_keys),
16311690
op,
16321691
join_type,
16331692
),
1634-
Arc::clone(&task_ctx),
1693+
Arc::clone(task_ctx),
16351694
)
16361695
.await;
16371696

16381697
assert_eq!(
1639-
got, want,
1640-
"mismatch seed={seed} op={op:?} join_type={join_type:?} \
1698+
got,
1699+
want,
1700+
"mismatch key_type={} seed={seed} op={op:?} join_type={join_type:?} \
16411701
nparts={nparts} buffered_nparts={buffered_nparts} \
1642-
left_keys={left_keys:?} right_keys={right_keys:?}"
1702+
left_keys={left_keys:?} right_keys={right_keys:?}",
1703+
std::any::type_name::<K>(),
16431704
);
16441705
}
16451706
}

‎datafusion/physical-plan/src/joins/piecewise_merge_join/exec.rs‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -472,7 +472,10 @@ impl PiecewiseMergeJoinExec {
472472
// `RightMark` is excluded: it adds a `mark` column, so its orderings would not
473473
// map across unchanged.
474474
JoinType::RightSemi | JoinType::RightAnti => vec![false, true],
475-
// The existence side is expected to come in sorted
475+
// Unlike the right existence joins above, output here is gated on a watermark
476+
// shared across every streamed partition (see `ExistencePWMJStream`) and emitted
477+
// only from whichever partition finishes last, so no streamed partition's output
478+
// order tracks its input order.
476479
JoinType::LeftSemi | JoinType::LeftAnti | JoinType::LeftMark => {
477480
vec![false, false]
478481
}

‎datafusion/physical-plan/src/joins/piecewise_merge_join/right_existence_join.rs‎

Lines changed: 31 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -68,10 +68,20 @@
6868
//! makes its comparison NULL rather than false, which is "no match" — dropped by `RightSemi`,
6969
//! kept by `RightAnti`.
7070
//!
71-
//! Picking the extreme and comparing against it must agree on ordering, and they do: arrow's
72-
//! `cmp` kernels and its `min`/`max` accumulators both order floats by `total_cmp`
71+
//! Picking the extreme and comparing against it must agree on ordering. `min_batch`/`max_batch`
72+
//! and arrow's `lt`/`lt_eq`/`gt`/`gt_eq` kernels both order floats by `total_cmp`
7373
//! (`arrow-arith`'s `MinAccumulator` compares with `ArrowNativeTypeOp::is_lt`, seeded from
74-
//! `MAX_TOTAL_ORDER`), so `-0.0` and NaN are treated identically on both sides.
74+
//! `MAX_TOTAL_ORDER`), which puts `-0.0` strictly below `+0.0` -- but SQL comparisons treat
75+
//! them as equal, and that is what a real `k < r` predicate actually evaluates to: any
76+
//! `BinaryExpr` comparison, including the one the `NestedLoopJoinExec` oracle in the
77+
//! differential fuzz test builds its filter from, normalizes `-0.0` to `+0.0` first (see
78+
//! `apply_cmp` in `datafusion-physical-expr-common`). Both the extreme and the streamed key
79+
//! array are normalized with [`normalize_float_zero`] before comparing,
80+
//! after the reduction: normalizing first would not change which value the reduction picks
81+
//! (`-0.0` and `+0.0` are numerically equal either way), and normalizing only where the
82+
//! comparison happens keeps the reduction itself agreeing with the unnormalized `min`/`max`
83+
//! semantics its docs above describe. `NaN` needs no such fix-up: every kernel involved orders
84+
//! it as the maximum, so it is treated identically on both sides already.
7585
//!
7686
//! # Cost
7787
//!
@@ -94,6 +104,7 @@ use arrow::compute::filter_record_batch;
94104
use arrow::compute::kernels::boolean::not;
95105
use arrow::compute::kernels::cmp::{gt, gt_eq, lt, lt_eq};
96106
use arrow_schema::SchemaRef;
107+
use datafusion_common::utils::normalize_float_zero;
97108
use datafusion_common::{Result, internal_err};
98109
use datafusion_execution::{RecordBatchStream, SendableRecordBatchStream};
99110
use datafusion_expr::{JoinType, Operator};
@@ -189,9 +200,16 @@ impl RightExistencePWMJStream {
189200

190201
// Null exactly when no buffered key is non-null, and NULLs match nothing. Cloned out by
191202
// value -- it is one row -- so the shared state is not kept alive by this stream.
192-
let extreme = buffered_extreme.extreme();
193-
self.buffered_extreme =
194-
(extreme.null_count() == 0).then(|| Scalar::new(Arc::clone(extreme)));
203+
//
204+
// Normalized because the `lt`/`lt_eq`/`gt`/`gt_eq` kernels called in
205+
// `filter_streamed_batch` order `-0.0` strictly below `+0.0`, but SQL comparisons --
206+
// including `apply_cmp`, which every other `k < r` predicate in the plan goes through
207+
// -- treat them as equal. The streamed key array is normalized the same way, right
208+
// before that comparison. `min`/`max_batch`, which reduced this extreme, order `-0.0`
209+
// below `+0.0` too, so normalizing after the reduction rather than before leaves the
210+
// reduction itself agreeing with the unnormalized ordering its own docs describe.
211+
let extreme = normalize_float_zero(buffered_extreme.extreme());
212+
self.buffered_extreme = (extreme.null_count() == 0).then(|| Scalar::new(extreme));
195213

196214
// With no non-null buffered key nothing matches, so `RightSemi` outputs nothing
197215
// and does not need to read a single streamed batch. `RightAnti` still has to,
@@ -240,10 +258,12 @@ impl RightExistencePWMJStream {
240258
// the streamed side.
241259
None => batch.columns().to_vec(),
242260
Some(extreme) => {
243-
let stream_values = self
244-
.on_streamed
245-
.evaluate(batch)?
246-
.into_array(batch.num_rows())?;
261+
let stream_values = normalize_float_zero(
262+
&self
263+
.on_streamed
264+
.evaluate(batch)?
265+
.into_array(batch.num_rows())?,
266+
);
247267

248268
// `extreme` is the buffered key, so it goes on the left of the operator,
249269
// matching the `buffered OP streamed` orientation of the predicate.
@@ -322,7 +342,7 @@ mod tests {
322342

323343
// Coverage for right existence joins also lives in `pwmj.slt` (both correlation
324344
// orientations, all four operators, NULLs, key types) and in the differential fuzz test
325-
// `fuzz_pwmj_existence_matches_nested_loop`, which checks them against
345+
// `fuzz_pwmj_matches_nested_loop`, which checks them against
326346
// `NestedLoopJoinExec` over randomized inputs. The tests here pin the parts SQL cannot
327347
// observe: which streamed batches were read, and which partition emitted them.
328348

0 commit comments

Comments
 (0)