DevShiba opened a new pull request, #25020: URL: https://github.com/apache/datafusion/pull/25020
## Which issue does this PR close? - Closes #25011. ## Rationale for this change The `cargo test hash collisions (amd64)` CI job hangs for hours (sometimes hitting the 360-minute job limit and getting cancelled) in two tests in `datafusion/functions-aggregate-common/src/aggregate/count_distinct/bytes.rs`: ``` aggregate::count_distinct::bytes::tests::ungrouped_utf8_accumulator_is_never_worse_than_a_pre_allocated_set aggregate::count_distinct::bytes::tests::ungrouped_utf8_view_accumulator_is_never_worse_than_a_pre_allocated_set ``` Root cause: both tests insert up to 500,000 distinct values into `ArrowBytesSet`/`ArrowBytesViewSet`, twice per cardinality in `CARDINALITIES` (once into a lazily-constructed set, once into a pre-allocated one), to compare their reported `.size()`. Under normal hashing this is O(n) per insert. Under `force_hash_collisions` ([`datafusion/common/src/hash_utils.rs#L1184-L1195`](https://github.com/apache/datafusion/blob/main/datafusion/common/src/hash_utils.rs#L1184-L1195)) every value hashes to the same bucket, so the underlying hash table degrades to a linear scan per insert - O(n^2) overall for a set built up to n elements. I confirmed this is quadratic, not just slow, with a throwaway local timing probe over the same insert pattern under `--features datafusion-common/force_hash_collisions` (removed before this PR, shown here for reference): | n | time | |---|---| | 100 | 297us | | 500 | 3.7ms | | 1,000 | 14ms | | 2,000 | 54ms | | 5,000 | 347ms | Each 2x step in n is roughly a 4x step in time, consistent with O(n^2), and consistent with the multi-hour runtimes reported in #25011 for n up to 500,000. On the question raised in #25011 ("what behavior or regression boundaries are the 100,000 and 500,000 cardinalities intended to protect, and what approach would preserve that coverage?"): the assertions in `assert_lazy_is_not_worse` compare allocator sizes reported by a real hash-table implementation against a pre-allocated one, at cardinalities chosen to span both sides of the warm-up capacity (`PER_GROUP_SCALE`) and the point where the two constructors converge (`UNGROUPED_SCALE`). None of that is about hash *collision* behavior - forcing every key into one bucket doesn't exercise a code path these tests are meant to protect, it just makes every insert scan the one bucket's full contents, which is why the cost goes quadratic without adding coverage. This is the same situation the `force_hash_collisions` feature already has an established answer for: `count_distinct_spill` in `datafusion/core/tests/memory_limit/mod.rs` (added in #24918) is gated with `#[cfg(not(feature = "force_hash_collisions"))]` because its assertions depend on a real hash distribution across partitions and don't mean anything under forced collisions. This PR applies the identical pattern here, rather than reducing cardinality or otherwise changing what real-hashing runs cover. ## What changes are included in this PR? - `datafusion/functions-aggregate-common/Cargo.toml`: add a `[features]` section declaring `force_hash_collisions = ["datafusion-common/force_hash_collisions"]`, forwarding to `datafusion-common`'s feature of the same name. This crate previously declared no features of its own. Cargo does not propagate a dependency's active feature into a consuming crate's own `cfg(feature = ...)` checks, so without this forwarding declaration, a `#[cfg(feature = "force_hash_collisions")]` inside this crate would never see the workspace-level `--features force_hash_collisions` flag the affected CI job passes (`cargo test --workspace --features=force_hash_collisions,avro`). This mirrors the exact forwarding pattern already used in `datafusion/core/Cargo.toml` for the same feature name. - `datafusion/functions-aggregate-common/src/aggregate/count_distinct/bytes.rs`: gate the whole `mod tests` block (it contains only these two tests and their shared helpers - nothing else needs to stay compiled either way) with `#[cfg(all(test, not(feature = "force_hash_collisions")))]`, with a doc comment explaining the O(n^2) mechanism and linking back to this issue. No production code changes. No reduction in cardinality or coverage for the normal (non-collision-forced) test run - both tests still run exactly as before, across all 7 cardinalities up to 500,000, whenever `force_hash_collisions` is off. ## What is the testing strategy for this PR? This is a test-only change, verified by running the tests both ways: - Without the feature: `cargo test -p datafusion-functions-aggregate-common --lib -- count_distinct::bytes` still runs and passes both tests in ~0.8s. - With the feature: `cargo test -p datafusion-functions-aggregate-common --lib --features force_hash_collisions -- count_distinct::bytes` runs 0 tests with a clean compile - confirming the gate compiles out cleanly rather than silently failing to match. - Against the exact affected CI job command (`cd datafusion && cargo test --profile ci --exclude datafusion-examples --exclude datafusion-benchmarks --exclude datafusion-sqllogictest --exclude datafusion-cli --workspace --lib --tests --features=force_hash_collisions,avro`): the `datafusion-functions-aggregate-common` test binary reports 47 tests (49 minus the 2 gated ones) all passing, with neither `ungrouped_utf8_accumulator_is_never_worse_than_a_pre_allocated_set` nor its `Utf8View` counterpart appearing anywhere in the run - confirming the workspace-level feature flag correctly reaches the new local feature via Cargo's feature unification, not just the crate-local invocation. - `cargo fmt --check` and the exact CI clippy invocation (`ci/scripts/rust_clippy.sh`, i.e. `cargo clippy --all-targets --workspace --features avro,integration-tests,extended_tests -- -D warnings`) both pass clean across the whole workspace. ## Are there any user-facing changes? None. This only changes which tests compile under a testing-only feature flag; there is no change to any public API or runtime behavior. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
