Skip to content

Commit 45e61d5

Browse files
fix: approx_distinct over-counts for utf8view (apache#22815)
## Which issue does this PR close? - Closes apache#22796 ## Rationale for this change `approx_distinct` over-counted distinct values for `Utf8View` columns when the same short string appeared across batches with different layouts. Arrow stores strings ≤ 12 bytes inline in the 128-bit view integer. The fast path (no data buffers) hashed these as raw `u128`. But when a batch also had a long string, it fell into a different branch that hashed **all** strings as `&str` — including the short inline ones. The same string hashed differently in different batches, so HyperLogLog counted it twice. ## What changes are included in this PR? - **`StringViewHLLAccumulator::update_batch`** and **`Utf8ViewHasher`**: in mixed batches (data buffers present), short strings (≤ 12 bytes) are still hashed as the raw `u128` view; only long strings hash as `&str`. This keeps hashing consistent regardless of batch layout. - **Two regression tests**: - `utf8view_acc_split_batches_match_single_mixed_batch` — scalar accumulator - `utf8view_groups_short_string_hashed_consistently_across_batches` — group accumulator ## Are these changes tested? Yes, two new regression tests cover the exact failure mode. ## Are there any user-facing changes? Yes. `approx_distinct` on `Utf8View` / `VARCHAR VIEW` columns now returns correct (lower) counts. Results may differ from the previously incorrect values. --------- Co-authored-by: Yongting You <[email protected]> (cherry picked from commit 84dcc0b)
1 parent f38bd26 commit 45e61d5

1 file changed

Lines changed: 93 additions & 9 deletions

File tree

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

Lines changed: 93 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -250,16 +250,29 @@ impl Accumulator for StringViewHLLAccumulator {
250250
fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
251251
let array: &StringViewArray = downcast_value!(values[0], StringViewArray);
252252

253-
// When all strings are stored inline in the StringView (≤ 12 bytes),
254-
// hash the raw u128 view directly instead of materializing a &str.
255253
if array.data_buffers().is_empty() {
254+
// Fast path: with no data buffers every value is inline, so they all
255+
// take the u128 path — no need to check the length per row.
256256
for (i, &view) in array.views().iter().enumerate() {
257257
if !array.is_null(i) {
258258
self.hll.add_hashed(HLL_HASH_STATE.hash_one(view));
259259
}
260260
}
261261
} else {
262-
self.hll.extend(array.iter().flatten());
262+
// Mixed batch: decide per row by length. Short strings still use the
263+
// u128 path so they match how they'd be hashed in an all-inline
264+
// batch; only the genuinely out-of-line strings materialize a &str.
265+
for (i, &view) in array.views().iter().enumerate() {
266+
if array.is_null(i) {
267+
continue;
268+
}
269+
// The low 32 bits of the u128 view encode the string length.
270+
if (view as u32) <= 12 {
271+
self.hll.add_hashed(HLL_HASH_STATE.hash_one(view));
272+
} else {
273+
self.hll.add(array.value(i));
274+
}
275+
}
263276
}
264277

265278
Ok(())
@@ -566,9 +579,17 @@ impl HllValueHasher for Utf8ViewHasher {
566579
}
567580
}
568581
} else {
582+
// Mixed batch: short strings (≤ 12 bytes) are still inline and must
583+
// be hashed as the raw u128 view to match the all-inline fast path.
584+
let views = array.views();
569585
for i in 0..array.len() {
570586
if nulls.is_none_or(|n| n.is_valid(i)) {
571-
f(i, HLL_HASH_STATE.hash_one(array.value(i)));
587+
let view = views[i];
588+
if (view as u32) <= 12 {
589+
f(i, HLL_HASH_STATE.hash_one(view));
590+
} else {
591+
f(i, HLL_HASH_STATE.hash_one(array.value(i)));
592+
}
572593
}
573594
}
574595
}
@@ -1016,10 +1037,14 @@ fn is_hll_groups_type(data_type: &DataType) -> bool {
10161037
}
10171038

10181039
#[cfg(test)]
1019-
mod groups_tests {
1040+
mod tests {
10201041
use super::*;
1042+
use arrow::array::{AsArray, Int64Array, StringViewArray};
1043+
use std::sync::Arc;
1044+
1045+
// A string longer than the 12-byte inline limit
1046+
const LONG: &str = "this string is definitely longer than twelve bytes";
10211047

1022-
/// Hash a value the same way the accumulators do.
10231048
fn h(v: u64) -> u64 {
10241049
HLL_HASH_STATE.hash_one(v)
10251050
}
@@ -1040,6 +1065,13 @@ mod groups_tests {
10401065
buf
10411066
}
10421067

1068+
fn distinct_count(acc: &mut StringViewHLLAccumulator) -> u64 {
1069+
match acc.evaluate().unwrap() {
1070+
ScalarValue::UInt64(Some(v)) => v,
1071+
other => panic!("unexpected evaluate result: {other:?}"),
1072+
}
1073+
}
1074+
10431075
#[test]
10441076
fn sparse_stays_sparse_for_small_groups() {
10451077
let mut g = GroupHll::default();
@@ -1162,9 +1194,6 @@ mod groups_tests {
11621194
/// must not be counted (null filter is treated the same as false).
11631195
#[test]
11641196
fn update_batch_nullable_filter_excludes_null_filter_rows() {
1165-
use arrow::array::Int64Array;
1166-
use std::sync::Arc;
1167-
11681197
let values: ArrayRef = Arc::new(Int64Array::from(vec![1i64, 2, 3, 4, 5]));
11691198
// row 0: filter=true, row 1: filter=NULL, row 2: filter=false,
11701199
// row 3: filter=NULL, row 4: filter=true
@@ -1184,4 +1213,59 @@ mod groups_tests {
11841213
let expected = reference_count(&[h(1), h(5)]);
11851214
assert_eq!(counts.value(0), expected);
11861215
}
1216+
1217+
/// Regression: a short (≤ 12-byte) Utf8View string must hash identically
1218+
/// in an all-inline batch and in a mixed batch that also contains a long
1219+
/// string (which forces a data buffer).
1220+
#[test]
1221+
fn utf8view_groups_short_string_hashed_consistently_across_batches() {
1222+
// Batch 1: all-inline (no data buffers) — "aaa" is hashed as u128 view.
1223+
let batch1: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", "bbb"]));
1224+
assert!(batch1.as_string_view().data_buffers().is_empty());
1225+
1226+
// Batch 2: mixed — LONG forces a data buffer; "aaa" must still be
1227+
// hashed as u128 view so it matches its appearance in batch 1.
1228+
let batch2: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", LONG]));
1229+
assert!(!batch2.as_string_view().data_buffers().is_empty());
1230+
1231+
let group_indices = vec![0usize, 0];
1232+
let mut acc = HllGroupsAccumulator::<Utf8ViewHasher>::new();
1233+
acc.update_batch(&[batch1], &group_indices, None, 1)
1234+
.unwrap();
1235+
acc.update_batch(&[batch2], &group_indices, None, 1)
1236+
.unwrap();
1237+
1238+
// True distinct values: {"aaa", "bbb", LONG} == 3.
1239+
let result = acc.evaluate(EmitTo::All).unwrap();
1240+
let counts = result.as_any().downcast_ref::<UInt64Array>().unwrap();
1241+
assert_eq!(counts.value(0), 3);
1242+
}
1243+
1244+
/// Regression: a short (≤ 12-byte) Utf8View string must hash identically
1245+
/// regardless of which batch it appears in — all-inline or mixed.
1246+
#[test]
1247+
fn utf8view_acc_split_batches_match_single_mixed_batch() {
1248+
// Multiset: {"aaa" x2, "bbb", LONG}, so 3 distinct values.
1249+
let mixed: ArrayRef =
1250+
Arc::new(StringViewArray::from(vec!["aaa", "bbb", LONG, "aaa"]));
1251+
let mut acc_single = StringViewHLLAccumulator::new();
1252+
acc_single.update_batch(&[mixed]).unwrap();
1253+
1254+
// Same multiset, but split so "aaa" lands in both an all-inline batch
1255+
// and a batch with a data buffer (forced by LONG).
1256+
let inline_only: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", "bbb"]));
1257+
let with_buffer: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", LONG]));
1258+
assert!(inline_only.as_string_view().data_buffers().is_empty());
1259+
assert!(!with_buffer.as_string_view().data_buffers().is_empty());
1260+
1261+
let mut acc_split = StringViewHLLAccumulator::new();
1262+
acc_split.update_batch(&[inline_only]).unwrap();
1263+
acc_split.update_batch(&[with_buffer]).unwrap();
1264+
1265+
assert_eq!(
1266+
distinct_count(&mut acc_single),
1267+
distinct_count(&mut acc_split)
1268+
);
1269+
assert_eq!(distinct_count(&mut acc_single), 3);
1270+
}
11871271
}

0 commit comments

Comments
 (0)