[Epic] Fuzz data generators never produce NULLs
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Context
#11596 and #24208 are both wrong-result bugs in `SortProperties` ordering propagation. Neither one crashes: the optimizer claims an ordering the data doesn't have, and a downstream sort gets elided. Both went unnoticed for a long time, and both need NULLs in the data to be observable at all.
We already have a [fuzzer](https://github.com/apache/datafusion/blob/main/datafusion/core/tests/fuzz_cases/equivalence/ordering.rs) aimed at exactly this code. The equivalence fuzz tests check `EquivalenceProperties::ordering_satisfy` against ground truth: `is_table_same_after_sort` re-sorts the generated table with arrow's `lexsort_to_indices` (which respects `nulls_first`) and compares row order. That oracle would have caught both bugs.
The problem is the input side. `generate_table_for_eq_properties` and `generate_table_for_orderings` (fuzz_cases/equivalence/utils.rs) build every column with `Float64Array::from_iter_values`, which takes an iterator of plain f64 (not `Option`). The generated arrays never contain a null and no null percentage to turn up.
### What I did
I surveyed the rest of the fuzz suite and found the same gap in most of it:
| Fuzzer | NULL coverage today | Oracle |
| ------------------------------------------------------------------------------- | -------------------------------------------------------------------------- | ---------------------------------- |
| `equivalence/utils.rs` generators (used by ordering/properties/projection fuzz) | none possible (`from_iter_values`) | ground truth (arrow lexsort) |
| `sort_preserving_repartition_fuzz.rs` (near-copy of the above generator) | none possible | ground truth |
| `limit_fuzz.rs` (TopK) | columns are `Vec>` but every variant says `// no nulls for now` | differential (TopK vs full sort) |
| `window_fuzz.rs` | PARTITION BY / ORDER BY columns never null | metamorphic (bounded vs unbounded) |
| `sort_fuzz.rs` | all three staggered generators non-null | reference sort (std sort) |
| `merge_fuzz.rs` | `(low..high).map(Some)`, always `Some` | differential |
| `join_fuzz.rs` | join key columns non-null (a payload filter column already has ~10% nulls) | differential (HJ vs SMJ vs NLJ) |
| `aggregate_fuzz.rs` (old `streaming_aggregate_test` path) | non-null | differential |
The newer infrastructure already handles this well: `RecordBatchGenerator` picks a null percentage per column from `[0.0, 0.01, 0.1, 0.5]`, and `sort_query_fuzz.rs` even generates `ORDER BY ... NULLS FIRST/LAST` queries. But that path never reaches the `EquivalenceProperties` code where these two bugs live.
### Describe the solution you'd like
This is a proposal and I'd appreciate feedback on it, especially on scope.
For each fuzzer above:
- If the component under test really does assume non-null input, keep the data non-null, but say so in the schema (`nullable: false`) or a comment. The absence of NULLs should be a decision.
- Otherwise, add NULLs with a randomized percentage. Reuse the existing null-aware generators (`test-utils/array_gen`, `RecordBatchGenerator`) rather than adding new one-off ones.
### Task list
This is a rough plan; items may change as earlier ones land and we see what the updated fuzzers turn up
- [ ] Make the `equivalence/utils.rs` generators null-aware, placing NULLs per the declared orderings. Verify it fails against the pre-fix code for #11596/#24208
- [ ] Fold `sort_preserving_repartition_fuzz.rs`'s copy of the generator into the fixed one.
- [ ] `limit_fuzz.rs`: remove `// no nulls for now`, inject randomized nulls
- [ ] `window_fuzz.rs`: nulls in PARTITION BY / ORDER BY columns
- [ ] `sort_fuzz.rs`: nulls in the staggered batch generators
- [ ] `merge_fuzz.rs`: nulls in the merged streams
- [ ] `join_fuzz.rs`: nulls in join key columns, to exercise null-equality semantics across the three join implementations
- [ ] `aggregate_fuzz.rs` old path: add nulls, or migrate the remaining tests to the null-aware `AggregationFuzzer` framework
Out of scope for now: `pruning.rs` uses a deliberately non-nullable schema, and NULL pruning semantics feel like a separate discussion.
Contributor guide
Research direction
Start with datafusion/core/tests/fuzz_cases/equivalence/utils.rs and the ordering fuzz case, then compare its generators with test-utils/array_gen and RecordBatchGenerator. Review the listed fuzzers, including sort_preserving_repartition_fuzz.rs and limit_fuzz.rs, to identify where NULLs are intentionally absent. Done means the applicable generators exercise randomized NULLs and the equivalence fuzzing can expose the cases from #11596 and #24208.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- testing
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100