Skip to content

Commit 287d0a0

Browse files
committed
test: fuzz sort-merge joins with low-cardinality keys
Most key groups in the join fuzz inputs hold one row, so a sort-merge join almost never pairs a streamed row with a run of more than one buffered row there, and never cuts such a run at the output batch. Add Inner, Left, Right and Full cases, unfiltered and filtered, whose keys take 25 values, so that each streamed row matches about 40 buffered rows and runs end both at buffered batch boundaries and where the output batch fills.
1 parent 2a112e7 commit 287d0a0

1 file changed

Lines changed: 132 additions & 1 deletion

File tree

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

Lines changed: 132 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -662,6 +662,124 @@ async fn test_right_mark_join_1k_binary_filtered() {
662662
}
663663
}
664664

665+
// In the tests above, most key groups hold one row: the i32 tests draw the join keys
666+
// `(a, b)` from 10,000 values for 1000 rows, and the binary ones from random bytes.
667+
// The tests below draw them from 25 values, so each streamed row matches about 40
668+
// buffered rows. Sort-merge join pairs a streamed row with its matches in runs, which
669+
// end where a buffered batch ends or where the output batch fills.
670+
671+
#[tokio::test]
672+
async fn test_inner_join_1k_low_cardinality() {
673+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
674+
JoinFuzzTestCase::new(
675+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
676+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
677+
JoinType::Inner,
678+
None,
679+
)
680+
.run_test(&[HjSmj, NljHj], false)
681+
.await
682+
}
683+
}
684+
685+
#[tokio::test]
686+
async fn test_inner_join_1k_low_cardinality_filtered() {
687+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
688+
JoinFuzzTestCase::new(
689+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
690+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
691+
JoinType::Inner,
692+
Some(Box::new(col_lt_col_filter)),
693+
)
694+
.run_test(&[HjSmj, NljHj], false)
695+
.await
696+
}
697+
}
698+
699+
#[tokio::test]
700+
async fn test_left_join_1k_low_cardinality() {
701+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
702+
JoinFuzzTestCase::new(
703+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
704+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
705+
JoinType::Left,
706+
None,
707+
)
708+
.run_test(&[HjSmj, NljHj], false)
709+
.await
710+
}
711+
}
712+
713+
#[tokio::test]
714+
async fn test_left_join_1k_low_cardinality_filtered() {
715+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
716+
JoinFuzzTestCase::new(
717+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
718+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
719+
JoinType::Left,
720+
Some(Box::new(col_lt_col_filter)),
721+
)
722+
.run_test(&[HjSmj, NljHj], false)
723+
.await
724+
}
725+
}
726+
727+
#[tokio::test]
728+
async fn test_right_join_1k_low_cardinality() {
729+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
730+
JoinFuzzTestCase::new(
731+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
732+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
733+
JoinType::Right,
734+
None,
735+
)
736+
.run_test(&[HjSmj, NljHj], false)
737+
.await
738+
}
739+
}
740+
741+
#[tokio::test]
742+
async fn test_right_join_1k_low_cardinality_filtered() {
743+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
744+
JoinFuzzTestCase::new(
745+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
746+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
747+
JoinType::Right,
748+
Some(Box::new(col_lt_col_filter)),
749+
)
750+
.run_test(&[HjSmj, NljHj], false)
751+
.await
752+
}
753+
}
754+
755+
#[tokio::test]
756+
async fn test_full_join_1k_low_cardinality() {
757+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
758+
JoinFuzzTestCase::new(
759+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
760+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
761+
JoinType::Full,
762+
None,
763+
)
764+
.run_test(&[HjSmj, NljHj], false)
765+
.await
766+
}
767+
}
768+
769+
#[tokio::test]
770+
async fn test_full_join_1k_low_cardinality_filtered() {
771+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
772+
JoinFuzzTestCase::new(
773+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
774+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
775+
JoinType::Full,
776+
Some(Box::new(col_lt_col_filter)),
777+
)
778+
.run_test(&[HjSmj, NljHj], false)
779+
.await
780+
}
781+
}
782+
665783
type JoinFilterBuilder = Box<dyn Fn(Arc<Schema>, Arc<Schema>) -> JoinFilter>;
666784

667785
struct JoinFuzzTestCase {
@@ -1392,12 +1510,25 @@ async fn test_nested_loop_join_spill_fuzz() {
13921510
/// two sorted int32 columns 'a', 'b' ranged from 0..99 as join columns
13931511
/// two random int32 columns 'x', 'y' as other columns
13941512
fn make_staggered_batches_i32(len: usize, with_extra_column: bool) -> Vec<RecordBatch> {
1513+
make_staggered_batches_i32_with_key_range(len, 100, with_extra_column)
1514+
}
1515+
1516+
/// Like [`make_staggered_batches_i32`], but with 'a' and 'b' drawn from
1517+
/// `0..key_range`, so that a small `key_range` makes few, large key groups
1518+
fn make_staggered_batches_i32_with_key_range(
1519+
len: usize,
1520+
key_range: i32,
1521+
with_extra_column: bool,
1522+
) -> Vec<RecordBatch> {
13951523
let mut rng = rand::rng();
13961524
let mut input12: Vec<(i32, i32)> = vec![(0, 0); len];
13971525
let mut input3: Vec<i32> = vec![0; len];
13981526
let mut input4: Vec<i32> = vec![0; len];
13991527
for v in &mut input12 {
1400-
*v = (rng.random_range(0..100), rng.random_range(0..100));
1528+
*v = (
1529+
rng.random_range(0..key_range),
1530+
rng.random_range(0..key_range),
1531+
);
14011532
}
14021533
rng.fill(&mut input3[..]);
14031534
rng.fill(&mut input4[..]);

0 commit comments

Comments
 (0)