apache / apache/datafusion

[Epic] Fuzz data generators never produce NULLs

Open
#24,243 3 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.