You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by mb...@apache.org on 2026/07/14 19:30:40 UTC
(datafusion) branch branch-54 updated: [branch-54] fix: `approx_distinct` over-counts for utf8view (backport #22815, adapted) (#23576)
This is an automated email from the ASF dual-hosted git repository.
mbutrovich pushed a commit to branch branch-54
in repository https://gitbox.apache.org/repos/asf/datafusion.git
The following commit(s) were added to refs/heads/branch-54 by this push:
new 70bdc95904 [branch-54] fix: `approx_distinct` over-counts for utf8view (backport #22815, adapted) (#23576)
70bdc95904 is described below
commit 70bdc959044f1867d184405b7478c43583503f07
Author: Matt Butrovich <mb...@users.noreply.github.com>
AuthorDate: Tue Jul 14 15:30:33 2026 -0400
[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
1cb4de41c).
## 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 <ha...@gmail.com>
Co-authored-by: Yongting You <20...@gmail.com>
---
.../functions-aggregate/src/approx_distinct.rs | 64 +++++++++++++++++++++-
1 file changed, 61 insertions(+), 3 deletions(-)
diff --git a/datafusion/functions-aggregate/src/approx_distinct.rs b/datafusion/functions-aggregate/src/approx_distinct.rs
index cc42b6c22b..c98ab4f696 100644
--- a/datafusion/functions-aggregate/src/approx_distinct.rs
+++ b/datafusion/functions-aggregate/src/approx_distinct.rs
@@ -245,16 +245,29 @@ impl Accumulator for StringViewHLLAccumulator {
fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
let array: &StringViewArray = downcast_value!(values[0], StringViewArray);
- // When all strings are stored inline in the StringView (≤ 12 bytes),
- // hash the raw u128 view directly instead of materializing a &str.
if array.data_buffers().is_empty() {
+ // Fast path: with no data buffers every value is inline, so they all
+ // take the u128 path — no need to check the length per row.
for (i, &view) in array.views().iter().enumerate() {
if !array.is_null(i) {
self.hll.add_hashed(HLL_HASH_STATE.hash_one(view));
}
}
} else {
- self.hll.extend(array.iter().flatten());
+ // Mixed batch: decide per row by length. Short strings still use the
+ // u128 path so they match how they'd be hashed in an all-inline
+ // batch; only the genuinely out-of-line strings materialize a &str.
+ for (i, &view) in array.views().iter().enumerate() {
+ if array.is_null(i) {
+ continue;
+ }
+ // The low 32 bits of the u128 view encode the string length.
+ if (view as u32) <= 12 {
+ self.hll.add_hashed(HLL_HASH_STATE.hash_one(view));
+ } else {
+ self.hll.add(array.value(i));
+ }
+ }
}
Ok(())
@@ -464,3 +477,48 @@ impl AggregateUDFImpl for ApproxDistinct {
self.doc()
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use arrow::array::AsArray;
+ use std::sync::Arc;
+
+ // A string longer than the 12-byte inline limit
+ const LONG: &str = "this string is definitely longer than twelve bytes";
+
+ fn distinct_count(acc: &mut StringViewHLLAccumulator) -> u64 {
+ match acc.evaluate().unwrap() {
+ ScalarValue::UInt64(Some(v)) => v,
+ other => panic!("unexpected evaluate result: {other:?}"),
+ }
+ }
+
+ /// Regression: a short (≤ 12-byte) Utf8View string must hash identically
+ /// regardless of which batch it appears in — all-inline or mixed.
+ #[test]
+ fn utf8view_acc_split_batches_match_single_mixed_batch() {
+ // Multiset: {"aaa" x2, "bbb", LONG}, so 3 distinct values.
+ let mixed: ArrayRef =
+ Arc::new(StringViewArray::from(vec!["aaa", "bbb", LONG, "aaa"]));
+ let mut acc_single = StringViewHLLAccumulator::new();
+ acc_single.update_batch(&[mixed]).unwrap();
+
+ // Same multiset, but split so "aaa" lands in both an all-inline batch
+ // and a batch with a data buffer (forced by LONG).
+ let inline_only: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", "bbb"]));
+ let with_buffer: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", LONG]));
+ assert!(inline_only.as_string_view().data_buffers().is_empty());
+ assert!(!with_buffer.as_string_view().data_buffers().is_empty());
+
+ let mut acc_split = StringViewHLLAccumulator::new();
+ acc_split.update_batch(&[inline_only]).unwrap();
+ acc_split.update_batch(&[with_buffer]).unwrap();
+
+ assert_eq!(
+ distinct_count(&mut acc_single),
+ distinct_count(&mut acc_split)
+ );
+ assert_eq!(distinct_count(&mut acc_single), 3);
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org