Skip to content

Commit 70bdc95

Browse files
mbutrovichhaohuaijin2010YOUY01
authored
[branch-54] fix: approx_distinct over-counts for utf8view (backport #22815, adapted) (#23576)
## Which issue does this PR close? - Backport of #22815 to `branch-54` (for 54.1.0, tracked in #22547). - Fixes wrong results #22796 (regression introduced by the inline-u128 hashing fast path in #21064, which is present on `branch-54` as commit 1cb4de4). ## Rationale for this change `approx_distinct` over-counts `Utf8View` values when the same short (<= 12 byte) string appears across batches with different layouts: an all-inline batch hashes it as a raw `u128` view, while a mixed batch (with a data buffer) hashed it as a `&str`, so the same value is counted twice. ## What changes are included in this PR? This is an **adapted** backport, not a clean cherry-pick. `branch-54` only has the scalar `StringViewHLLAccumulator` path; the group `HllGroupsAccumulator` / `Utf8ViewHasher` code the upstream fix also touched comes from #22768, which is **not** on `branch-54`. - Applied verbatim from #22815: the scalar `StringViewHLLAccumulator::update_batch` mixed-batch fix (per-row length check) and its regression test `utf8view_acc_split_batches_match_single_mixed_batch`. - Omitted as not applicable: the `Utf8ViewHasher` group-accumulator hunk and its group test. - Added: a `#[cfg(test)] mod tests` scaffold and imports, since `branch-54`'s `approx_distinct.rs` had no test module. ## Are these changes tested? Yes. The scalar regression test passes with the fix and fails without it (over-count), confirming it exercises the regression. ## Are there any user-facing changes? `approx_distinct` on `Utf8View` / `VARCHAR VIEW` columns now returns correct (lower) counts. Results may differ from the previously incorrect values. No API changes. Co-authored-by: Huaijin <[email protected]> Co-authored-by: Yongting You <[email protected]>
1 parent 6c770b5 commit 70bdc95

1 file changed

Lines changed: 61 additions & 3 deletions

File tree

‎datafusion/functions-aggregate/src/approx_distinct.rs‎

Lines changed: 61 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -245,16 +245,29 @@ impl Accumulator for StringViewHLLAccumulator {
245245
fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
246246
let array: &StringViewArray = downcast_value!(values[0], StringViewArray);
247247

248-
// When all strings are stored inline in the StringView (≤ 12 bytes),
249-
// hash the raw u128 view directly instead of materializing a &str.
250248
if array.data_buffers().is_empty() {
249+
// Fast path: with no data buffers every value is inline, so they all
250+
// take the u128 path — no need to check the length per row.
251251
for (i, &view) in array.views().iter().enumerate() {
252252
if !array.is_null(i) {
253253
self.hll.add_hashed(HLL_HASH_STATE.hash_one(view));
254254
}
255255
}
256256
} else {
257-
self.hll.extend(array.iter().flatten());
257+
// Mixed batch: decide per row by length. Short strings still use the
258+
// u128 path so they match how they'd be hashed in an all-inline
259+
// batch; only the genuinely out-of-line strings materialize a &str.
260+
for (i, &view) in array.views().iter().enumerate() {
261+
if array.is_null(i) {
262+
continue;
263+
}
264+
// The low 32 bits of the u128 view encode the string length.
265+
if (view as u32) <= 12 {
266+
self.hll.add_hashed(HLL_HASH_STATE.hash_one(view));
267+
} else {
268+
self.hll.add(array.value(i));
269+
}
270+
}
258271
}
259272

260273
Ok(())
@@ -464,3 +477,48 @@ impl AggregateUDFImpl for ApproxDistinct {
464477
self.doc()
465478
}
466479
}
480+
481+
#[cfg(test)]
482+
mod tests {
483+
use super::*;
484+
use arrow::array::AsArray;
485+
use std::sync::Arc;
486+
487+
// A string longer than the 12-byte inline limit
488+
const LONG: &str = "this string is definitely longer than twelve bytes";
489+
490+
fn distinct_count(acc: &mut StringViewHLLAccumulator) -> u64 {
491+
match acc.evaluate().unwrap() {
492+
ScalarValue::UInt64(Some(v)) => v,
493+
other => panic!("unexpected evaluate result: {other:?}"),
494+
}
495+
}
496+
497+
/// Regression: a short (≤ 12-byte) Utf8View string must hash identically
498+
/// regardless of which batch it appears in — all-inline or mixed.
499+
#[test]
500+
fn utf8view_acc_split_batches_match_single_mixed_batch() {
501+
// Multiset: {"aaa" x2, "bbb", LONG}, so 3 distinct values.
502+
let mixed: ArrayRef =
503+
Arc::new(StringViewArray::from(vec!["aaa", "bbb", LONG, "aaa"]));
504+
let mut acc_single = StringViewHLLAccumulator::new();
505+
acc_single.update_batch(&[mixed]).unwrap();
506+
507+
// Same multiset, but split so "aaa" lands in both an all-inline batch
508+
// and a batch with a data buffer (forced by LONG).
509+
let inline_only: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", "bbb"]));
510+
let with_buffer: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", LONG]));
511+
assert!(inline_only.as_string_view().data_buffers().is_empty());
512+
assert!(!with_buffer.as_string_view().data_buffers().is_empty());
513+
514+
let mut acc_split = StringViewHLLAccumulator::new();
515+
acc_split.update_batch(&[inline_only]).unwrap();
516+
acc_split.update_batch(&[with_buffer]).unwrap();
517+
518+
assert_eq!(
519+
distinct_count(&mut acc_single),
520+
distinct_count(&mut acc_split)
521+
);
522+
assert_eq!(distinct_count(&mut acc_single), 3);
523+
}
524+
}

0 commit comments

Comments
 (0)