Skip to content

Commit 6ab4ce6

Browse files
authored
fix: skip count-distinct byte tests under force_hash_collisions (apache#25020)
## Which issue does this PR close? - Closes apache#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 apache#25011 for n up to 500,000. On the question raised in apache#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 apache#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.
1 parent d682553 commit 6ab4ce6

2 files changed

Lines changed: 14 additions & 1 deletion

File tree

‎datafusion/functions-aggregate-common/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,10 @@ workspace = true
4040
[lib]
4141
name = "datafusion_functions_aggregate_common"
4242

43+
[features]
44+
# Used for testing ONLY: causes all values to hash to the same value (test for collisions)
45+
force_hash_collisions = ["datafusion-common/force_hash_collisions"]
46+
4347
[dependencies]
4448
arrow = { workspace = true }
4549
datafusion-common = { workspace = true }

‎datafusion/functions-aggregate-common/src/aggregate/count_distinct/bytes.rs‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -166,7 +166,16 @@ impl Accumulator for BytesViewDistinctCountAccumulator {
166166
}
167167
}
168168

169-
#[cfg(test)]
169+
/// With `force_hash_collisions` every distinct value collides into the same
170+
/// hash bucket, so both `ArrowBytesSet`/`ArrowBytesViewSet` degrade to a
171+
/// linear scan per insert. These tests insert up to 500,000 distinct values
172+
/// per accumulator (twice, once lazily constructed and once pre-allocated),
173+
/// which is O(n) under a real hash and O(n^2) under a forced collision,
174+
/// turning a sub-second run into a multi-hour one and hanging CI (see
175+
/// apache/datafusion#25011). Skipped under that feature, matching the
176+
/// `count_distinct_spill` precedent in
177+
/// `datafusion/core/tests/memory_limit/mod.rs`.
178+
#[cfg(all(test, not(feature = "force_hash_collisions")))]
170179
mod tests {
171180
use super::*;
172181
use arrow::array::{StringArray, StringViewArray};

0 commit comments

Comments
 (0)