@@ -34,18 +34,24 @@ use datafusion::physical_plan::collect;
3434use datafusion:: physical_plan:: expressions:: Column ;
3535use datafusion:: physical_plan:: joins:: utils:: { ColumnIndex , JoinFilter } ;
3636use 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} ;
3942use datafusion:: prelude:: { SessionConfig , SessionContext } ;
4043use datafusion_common:: { NullEquality , ScalarValue } ;
44+ use datafusion_common_runtime:: SpawnedTask ;
4145use datafusion_execution:: TaskContext ;
4246use datafusion_execution:: disk_manager:: { DiskManagerBuilder , DiskManagerMode } ;
4347use datafusion_execution:: runtime_env:: RuntimeEnvBuilder ;
4448use datafusion_physical_expr:: PhysicalExprRef ;
4549use datafusion_physical_expr:: expressions:: Literal ;
50+ use datafusion_physical_expr_common:: sort_expr:: { LexOrdering , PhysicalSortExpr } ;
4651
4752use itertools:: Itertools ;
4853use rand:: Rng ;
54+ use rand:: { SeedableRng , rngs:: StdRng } ;
4955use 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