Skip to content

Commit d3cec13

Browse files
committed
Adds fuzz test
1 parent 2b73c41 commit d3cec13

1 file changed

Lines changed: 222 additions & 1 deletion

File tree

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

Lines changed: 222 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -34,18 +34,24 @@ use datafusion::physical_plan::collect;
3434
use datafusion::physical_plan::expressions::Column;
3535
use datafusion::physical_plan::joins::utils::{ColumnIndex, JoinFilter};
3636
use datafusion::physical_plan::joins::{
37-
HashJoinExec, NestedLoopJoinExec, PartitionMode, SortMergeJoinExec,
37+
HashJoinExec, NestedLoopJoinExec, PartitionMode, PiecewiseMergeJoinExec,
38+
SortMergeJoinExec,
3839
};
40+
use datafusion::physical_plan::sorts::sort::SortExec;
41+
use datafusion::physical_plan::{ExecutionPlan, ExecutionPlanProperties, common};
3942
use datafusion::prelude::{SessionConfig, SessionContext};
4043
use datafusion_common::{NullEquality, ScalarValue};
44+
use datafusion_common_runtime::SpawnedTask;
4145
use datafusion_execution::TaskContext;
4246
use datafusion_execution::disk_manager::{DiskManagerBuilder, DiskManagerMode};
4347
use datafusion_execution::runtime_env::RuntimeEnvBuilder;
4448
use datafusion_physical_expr::PhysicalExprRef;
4549
use datafusion_physical_expr::expressions::Literal;
50+
use datafusion_physical_expr_common::sort_expr::{LexOrdering, PhysicalSortExpr};
4651

4752
use itertools::Itertools;
4853
use rand::Rng;
54+
use rand::{SeedableRng, rngs::StdRng};
4955
use test_utils::stagger_batch_with_seed;
5056

5157
// Determines what Fuzz tests needs to run
@@ -1347,3 +1353,218 @@ fn make_staggered_batches_binary(
13471353
// preserve your existing randomized partitioning
13481354
stagger_batch_with_seed(batch, 42)
13491355
}
1356+
1357+
// ---- Differential fuzz: PiecewiseMergeJoin existence joins vs NestedLoopJoin ----
1358+
//
1359+
// `PiecewiseMergeJoinExec` takes a range predicate and no equi keys, so it cannot be added to
1360+
// `JoinFuzzTestCase` above (that harness joins on `a` and `b` and folds the equality into the
1361+
// NestedLoopJoin filter). These tests use `NestedLoopJoinExec` with an equivalent filter as
1362+
// the oracle instead.
1363+
//
1364+
// What only randomization reaches: `LeftSemi`/`LeftAnti` record matches in a shared
1365+
// `AtomicUsize` watermark and emit once, from whichever streamed partition finishes last. The
1366+
// streamed side below is spread round-robin over several partitions as one-row batches, so
1367+
// batches arrive in an order no static test pins down, and the counter that gates the final
1368+
// pass is seeded from a partition count that deliberately disagrees with the `num_partitions`
1369+
// argument.
1370+
1371+
fn pwmj_kv_schema() -> Arc<Schema> {
1372+
Arc::new(Schema::new(vec![
1373+
arrow::datatypes::Field::new("id", arrow::datatypes::DataType::Int32, false),
1374+
arrow::datatypes::Field::new("k", arrow::datatypes::DataType::Int32, true),
1375+
]))
1376+
}
1377+
1378+
fn pwmj_kv_batch(ids: &[i32], keys: &[Option<i32>]) -> RecordBatch {
1379+
RecordBatch::try_new(
1380+
pwmj_kv_schema(),
1381+
vec![
1382+
Arc::new(Int32Array::from(ids.to_vec())),
1383+
Arc::new(Int32Array::from(keys.to_vec())),
1384+
],
1385+
)
1386+
.unwrap()
1387+
}
1388+
1389+
/// Single-partition, single-batch input: the buffered side, and the oracle's probe side.
1390+
fn pwmj_single_exec(ids: &[i32], keys: &[Option<i32>]) -> Arc<dyn ExecutionPlan> {
1391+
MemorySourceConfig::try_new_exec(
1392+
&[vec![pwmj_kv_batch(ids, keys)]],
1393+
pwmj_kv_schema(),
1394+
None,
1395+
)
1396+
.unwrap()
1397+
}
1398+
1399+
/// Streamed side spread round-robin across `nparts` partitions, one row per batch.
1400+
fn pwmj_parts_exec(
1401+
ids: &[i32],
1402+
keys: &[Option<i32>],
1403+
nparts: usize,
1404+
) -> Arc<dyn ExecutionPlan> {
1405+
let nparts = nparts.max(1);
1406+
let mut partitions: Vec<Vec<RecordBatch>> = vec![Vec::new(); nparts];
1407+
for (row, (&id, key)) in ids.iter().zip(keys.iter()).enumerate() {
1408+
partitions[row % nparts].push(pwmj_kv_batch(&[id], &[*key]));
1409+
}
1410+
for p in partitions.iter_mut() {
1411+
if p.is_empty() {
1412+
p.push(pwmj_kv_batch(&[], &[]));
1413+
}
1414+
}
1415+
MemorySourceConfig::try_new_exec(&partitions, pwmj_kv_schema(), None).unwrap()
1416+
}
1417+
1418+
fn pwmj_existence_plan(
1419+
left: Arc<dyn ExecutionPlan>,
1420+
right: Arc<dyn ExecutionPlan>,
1421+
op: Operator,
1422+
join_type: JoinType,
1423+
) -> Arc<dyn ExecutionPlan> {
1424+
// Matches `PiecewiseMergeJoinExec::required_input_ordering`: descending for `<`/`<=`,
1425+
// ascending for `>`/`>=`, NULLs first either way.
1426+
let sort_options = match op {
1427+
Operator::Lt | Operator::LtEq => SortOptions::new(true, true),
1428+
Operator::Gt | Operator::GtEq => SortOptions::new(false, true),
1429+
other => panic!("not a range operator: {other:?}"),
1430+
};
1431+
let ordering = LexOrdering::new(vec![PhysicalSortExpr::new(
1432+
Arc::new(Column::new("k", 1)),
1433+
sort_options,
1434+
)])
1435+
.unwrap();
1436+
let sorted_left = Arc::new(SortExec::new(ordering, left));
1437+
let on: (PhysicalExprRef, PhysicalExprRef) =
1438+
(Arc::new(Column::new("k", 1)), Arc::new(Column::new("k", 1)));
1439+
// `num_partitions` is 1 while the streamed side has up to 3: the final-pass counter must
1440+
// come from the streamed side's partition count, not from this argument.
1441+
Arc::new(
1442+
PiecewiseMergeJoinExec::try_new(sorted_left, right, on, op, join_type, 1)
1443+
.unwrap(),
1444+
)
1445+
}
1446+
1447+
fn pwmj_nlj_oracle_plan(
1448+
left: Arc<dyn ExecutionPlan>,
1449+
right: Arc<dyn ExecutionPlan>,
1450+
op: Operator,
1451+
join_type: JoinType,
1452+
) -> Arc<dyn ExecutionPlan> {
1453+
let intermediate_schema = Schema::new(vec![
1454+
arrow::datatypes::Field::new("k", arrow::datatypes::DataType::Int32, true),
1455+
arrow::datatypes::Field::new("k", arrow::datatypes::DataType::Int32, true),
1456+
]);
1457+
let expr = Arc::new(BinaryExpr::new(
1458+
Arc::new(Column::new("k", 0)),
1459+
op,
1460+
Arc::new(Column::new("k", 1)),
1461+
)) as PhysicalExprRef;
1462+
let column_indices = vec![
1463+
ColumnIndex {
1464+
index: 1,
1465+
side: JoinSide::Left,
1466+
},
1467+
ColumnIndex {
1468+
index: 1,
1469+
side: JoinSide::Right,
1470+
},
1471+
];
1472+
let filter = JoinFilter::new(expr, column_indices, Arc::new(intermediate_schema));
1473+
Arc::new(
1474+
NestedLoopJoinExec::try_new(left, right, Some(filter), &join_type, None).unwrap(),
1475+
)
1476+
}
1477+
1478+
/// Executes every output partition concurrently and returns the surviving left `id`s, sorted.
1479+
///
1480+
/// Concurrent rather than one partition at a time: the partitions share the watermark and race
1481+
/// to be the one that runs the final pass, which is the part a sequential drain cannot reach.
1482+
async fn pwmj_collect_ids(
1483+
plan: Arc<dyn ExecutionPlan>,
1484+
task_ctx: Arc<TaskContext>,
1485+
) -> Vec<i32> {
1486+
let streams = (0..plan.output_partitioning().partition_count())
1487+
.map(|partition| plan.execute(partition, Arc::clone(&task_ctx)).unwrap())
1488+
.collect::<Vec<_>>();
1489+
let per_partition =
1490+
futures::future::join_all(streams.into_iter().map(|stream| {
1491+
SpawnedTask::spawn(async move { common::collect(stream).await })
1492+
}))
1493+
.await;
1494+
1495+
let mut ids = Vec::new();
1496+
for batches in per_partition {
1497+
for batch in batches.unwrap().unwrap() {
1498+
let col = batch
1499+
.column(0)
1500+
.as_any()
1501+
.downcast_ref::<Int32Array>()
1502+
.unwrap();
1503+
ids.extend((0..col.len()).map(|i| col.value(i)));
1504+
}
1505+
}
1506+
ids.sort();
1507+
ids
1508+
}
1509+
1510+
#[tokio::test(flavor = "multi_thread")]
1511+
async fn fuzz_pwmj_existence_matches_nested_loop() {
1512+
// A small batch size splits the final-pass output across several coalesced batches even
1513+
// for these tiny inputs, covering that boundary too.
1514+
let task_ctx = Arc::new(
1515+
TaskContext::default()
1516+
.with_session_config(SessionConfig::new().with_batch_size(3)),
1517+
);
1518+
let ops = [Operator::Lt, Operator::LtEq, Operator::Gt, Operator::GtEq];
1519+
1520+
for seed in 0..60u64 {
1521+
let mut rng = StdRng::seed_from_u64(seed);
1522+
let left_len = rng.random_range(0..25usize);
1523+
let right_len = rng.random_range(0..25usize);
1524+
// A narrow key range forces duplicates and equal-boundary cases.
1525+
let key_range = rng.random_range(1..6i32);
1526+
let nparts = rng.random_range(1..4usize);
1527+
1528+
let gen_keys = |n: usize, rng: &mut StdRng| -> Vec<Option<i32>> {
1529+
(0..n)
1530+
.map(|_| (!rng.random_bool(0.2)).then(|| rng.random_range(0..key_range)))
1531+
.collect()
1532+
};
1533+
1534+
let left_ids: Vec<i32> = (0..left_len as i32).collect();
1535+
let left_keys = gen_keys(left_len, &mut rng);
1536+
let right_ids: Vec<i32> = (0..right_len as i32).collect();
1537+
let right_keys = gen_keys(right_len, &mut rng);
1538+
1539+
for op in ops {
1540+
for join_type in [JoinType::LeftSemi, JoinType::LeftAnti] {
1541+
let got = pwmj_collect_ids(
1542+
pwmj_existence_plan(
1543+
pwmj_single_exec(&left_ids, &left_keys),
1544+
pwmj_parts_exec(&right_ids, &right_keys, nparts),
1545+
op,
1546+
join_type,
1547+
),
1548+
Arc::clone(&task_ctx),
1549+
)
1550+
.await;
1551+
let want = pwmj_collect_ids(
1552+
pwmj_nlj_oracle_plan(
1553+
pwmj_single_exec(&left_ids, &left_keys),
1554+
pwmj_single_exec(&right_ids, &right_keys),
1555+
op,
1556+
join_type,
1557+
),
1558+
Arc::clone(&task_ctx),
1559+
)
1560+
.await;
1561+
1562+
assert_eq!(
1563+
got, want,
1564+
"mismatch seed={seed} op={op:?} join_type={join_type:?} \
1565+
nparts={nparts} left_keys={left_keys:?} right_keys={right_keys:?}"
1566+
);
1567+
}
1568+
}
1569+
}
1570+
}

0 commit comments

Comments
 (0)