Repository navigation
Commit 6ab4ce6
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
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
40 | 40 | | |
41 | 41 | | |
42 | 42 | | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
43 | 47 | | |
44 | 48 | | |
45 | 49 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
166 | 166 | | |
167 | 167 | | |
168 | 168 | | |
169 | | - | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
170 | 179 | | |
171 | 180 | | |
172 | 181 | | |
| |||
0 commit comments