(datafusion) branch main updated: fix: skip count-distinct byte tests under force_hash_collisions (#25020)

[gi...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datafusion.git


The following commit(s) were added to refs/heads/main by this push:
     new 6ab4ce6606 fix: skip count-distinct byte tests under force_hash_collisions (#25020)
6ab4ce6606 is described below

commit 6ab4ce660623b16d3c17599e49fd72d92e63a3df
Author: DevShiba <11...@users.noreply.github.com>
AuthorDate: Mon Sep 7 14:36:53 2026 +0000

    fix: skip count-distinct byte tests under force_hash_collisions (#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.
---
 datafusion/functions-aggregate-common/Cargo.toml              |  4 ++++
 .../src/aggregate/count_distinct/bytes.rs                     | 11 ++++++++++-
 2 files changed, 14 insertions(+), 1 deletion(-)

diff --git a/datafusion/functions-aggregate-common/Cargo.toml b/datafusion/functions-aggregate-common/Cargo.toml
index 1714e1800a..0898e6b4c5 100644
--- a/datafusion/functions-aggregate-common/Cargo.toml
+++ b/datafusion/functions-aggregate-common/Cargo.toml
@@ -40,6 +40,10 @@ workspace = true
 [lib]
 name = "datafusion_functions_aggregate_common"
 
+[features]
+# Used for testing ONLY: causes all values to hash to the same value (test for collisions)
+force_hash_collisions = ["datafusion-common/force_hash_collisions"]
+
 [dependencies]
 arrow = { workspace = true }
 datafusion-common = { workspace = true }
diff --git a/datafusion/functions-aggregate-common/src/aggregate/count_distinct/bytes.rs b/datafusion/functions-aggregate-common/src/aggregate/count_distinct/bytes.rs
index d955d343ad..c230a27c02 100644
--- a/datafusion/functions-aggregate-common/src/aggregate/count_distinct/bytes.rs
+++ b/datafusion/functions-aggregate-common/src/aggregate/count_distinct/bytes.rs
@@ -166,7 +166,16 @@ impl Accumulator for BytesViewDistinctCountAccumulator {
     }
 }
 
-#[cfg(test)]
+/// With `force_hash_collisions` every distinct value collides into the same
+/// hash bucket, so both `ArrowBytesSet`/`ArrowBytesViewSet` degrade to a
+/// linear scan per insert. These tests insert up to 500,000 distinct values
+/// per accumulator (twice, once lazily constructed and once pre-allocated),
+/// which is O(n) under a real hash and O(n^2) under a forced collision,
+/// turning a sub-second run into a multi-hour one and hanging CI (see
+/// apache/datafusion#25011). Skipped under that feature, matching the
+/// `count_distinct_spill` precedent in
+/// `datafusion/core/tests/memory_limit/mod.rs`.
+#[cfg(all(test, not(feature = "force_hash_collisions")))]
 mod tests {
     use super::*;
     use arrow::array::{StringArray, StringViewArray};


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org