jayzhan211 opened a new pull request, #25218:
URL: https://github.com/apache/datafusion/pull/25218
## Which issue does this PR close?
- No existing issue. Found while running the extended CI
`force_hash_collisions`
job against unrelated work; happy to file one first if you prefer.
## Rationale for this change
`ArrowBytesMap` keeps a value's bytes inline in an entry's `offset_or_inline`
field when the value is at most `SHORT_VALUE_LEN` (8) bytes, and keeps an
offset
into the value buffer there otherwise. The lookup for a **long** value
checked
only that the hashes matched, then built `header.range()` from that field and
read the buffer with `get_unchecked`:
```rust
let entry = self.map.find_mut(hash, |header| {
if header.hash != hash {
return false;
}
// SAFETY: buffer is only appended to, and we correctly inserted values
and offsets
let existing_value = unsafe { self.buffer.get_unchecked(header.range())
};
value == existing_value
});
```
When that hash matches a **short** entry, `offset_or_inline` holds inlined
bytes
rather than an offset, so the range is nonsense and the read goes outside the
buffer. The lookup for a short value does not have this problem, because it
already compares `header.len` first, which is precisely what keeps it sound.
This is reachable whenever a value of at most 8 bytes and a value longer
than 8
bytes collide on the full 64-bit hash inside one map. Two things make that
worth
fixing rather than dismissing:
- DataFusion hashes with `foldhash::fast::FixedState::default()`, a fixed
compile-time seed, so a colliding pair is reproducible across runs and
machines and can be found offline once.
- The expected number of such pairs grows with the product of the short and
long
distinct counts, so the exposure rises with cardinality rather than staying
constant.
The map backs grouped aggregation on a single string or binary column
(`GroupValuesBytes`) and `count(DISTINCT …)` over those types
(`ArrowBytesSet`), so this is on the path of ordinary `GROUP BY` and
`COUNT(DISTINCT)` queries.
What happens on a collision depends on the inlined bytes read as an offset.
If
they happen to land inside the buffer, the comparison sees unrelated bytes,
reports inequality, and the query is correct by luck. Otherwise the read is
out
of bounds, which is undefined behaviour: with UB checks enabled it aborts,
and
in a release build it reads unmapped or unrelated memory.
The extended CI job builds the workspace with `force_hash_collisions`, where
every value hashes to `0` so every short/long pair collides. Today
`dataframe::test_grouping_with_alias` aborts there:
```
unsafe precondition(s) violated: slice::get_unchecked requires that the range
is within the slice
thread caused non-unwinding panic. aborting.
```
## What changes are included in this PR?
- Compare `header.len` on the long-value path, exactly as the short-value
path
already does. That rules out short entries, so `offset_or_inline` is only
ever
treated as an offset when it is one, and it doubles as a cheap early-out.
It
cannot reject a real match, since two equal long values have equal lengths.
- Rewrite the `SAFETY` comment to state the invariant that actually holds.
- Give `datafusion-physical-expr-common` the `force_hash_collisions`
passthrough
feature that `datafusion-common`, `datafusion-core`,
`datafusion-physical-plan`
and the two aggregate crates already have, so the path can be reached
deterministically from a unit test.
## What is the testing strategy for this PR?
`short_and_long_values_with_colliding_hashes` in `binary_map.rs`, gated on
`force_hash_collisions`, inserts a 2-byte and a 30-byte value and then
repeats
both, asserting each distinct value is offered to the payload function
exactly
once. Mutation-checked in both directions: with the length check removed the
test aborts on the precondition violation, and with it the test passes.
With the fix, the whole `core_integration` suite passes under
`--features force_hash_collisions` (1144 tests) where it previously aborted.
Without the feature, `datafusion-physical-expr-common`,
`datafusion-functions-aggregate` and the `dataframe` integration tests all
pass,
and clippy is clean in both feature configurations.
## Are there any user-facing changes?
--
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]
