Skip to content

Commit 84dcc0b

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]>
1 parent 9b81ff8 commit 84dcc0b

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
@@ -251,16 +251,29 @@ impl Accumulator for StringViewHLLAccumulator {
251251
fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
252252
let array: &StringViewArray = downcast_value!(values[0], StringViewArray);
253253

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

266279
Ok(())
@@ -567,9 +580,17 @@ impl HllValueHasher for Utf8ViewHasher {
567580
}
568581
}
569582
} else {
583+
// Mixed batch: short strings (≤ 12 bytes) are still inline and must
584+
// be hashed as the raw u128 view to match the all-inline fast path.
585+
let views = array.views();
570586
for i in 0..array.len() {
571587
if nulls.is_none_or(|n| n.is_valid(i)) {
572-
f(i, HLL_HASH_STATE.hash_one(array.value(i)));
588+
let view = views[i];
589+
if (view as u32) <= 12 {
590+
f(i, HLL_HASH_STATE.hash_one(view));
591+
} else {
592+
f(i, HLL_HASH_STATE.hash_one(array.value(i)));
593+
}
573594
}
574595
}
575596
}
@@ -1037,10 +1058,14 @@ fn is_hll_groups_type(data_type: &DataType) -> bool {
10371058
}
10381059

10391060
#[cfg(test)]
1040-
mod groups_tests {
1061+
mod tests {
10411062
use super::*;
1063+
use arrow::array::{AsArray, Int64Array, StringViewArray};
1064+
use std::sync::Arc;
1065+
1066+
// A string longer than the 12-byte inline limit
1067+
const LONG: &str = "this string is definitely longer than twelve bytes";
10421068

1043-
/// Hash a value the same way the accumulators do.
10441069
fn h(v: u64) -> u64 {
10451070
HLL_HASH_STATE.hash_one(v)
10461071
}
@@ -1061,6 +1086,13 @@ mod groups_tests {
10611086
buf
10621087
}
10631088

1089+
fn distinct_count(acc: &mut StringViewHLLAccumulator) -> u64 {
1090+
match acc.evaluate().unwrap() {
1091+
ScalarValue::UInt64(Some(v)) => v,
1092+
other => panic!("unexpected evaluate result: {other:?}"),
1093+
}
1094+
}
1095+
10641096
#[test]
10651097
fn sparse_stays_sparse_for_small_groups() {
10661098
let mut g = GroupHll::default();
@@ -1183,9 +1215,6 @@ mod groups_tests {
11831215
/// must not be counted (null filter is treated the same as false).
11841216
#[test]
11851217
fn update_batch_nullable_filter_excludes_null_filter_rows() {
1186-
use arrow::array::Int64Array;
1187-
use std::sync::Arc;
1188-
11891218
let values: ArrayRef = Arc::new(Int64Array::from(vec![1i64, 2, 3, 4, 5]));
11901219
// row 0: filter=true, row 1: filter=NULL, row 2: filter=false,
11911220
// row 3: filter=NULL, row 4: filter=true
@@ -1205,4 +1234,59 @@ mod groups_tests {
12051234
let expected = reference_count(&[h(1), h(5)]);
12061235
assert_eq!(counts.value(0), expected);
12071236
}
1237+
1238+
/// Regression: a short (≤ 12-byte) Utf8View string must hash identically
1239+
/// in an all-inline batch and in a mixed batch that also contains a long
1240+
/// string (which forces a data buffer).
1241+
#[test]
1242+
fn utf8view_groups_short_string_hashed_consistently_across_batches() {
1243+
// Batch 1: all-inline (no data buffers) — "aaa" is hashed as u128 view.
1244+
let batch1: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", "bbb"]));
1245+
assert!(batch1.as_string_view().data_buffers().is_empty());
1246+
1247+
// Batch 2: mixed — LONG forces a data buffer; "aaa" must still be
1248+
// hashed as u128 view so it matches its appearance in batch 1.
1249+
let batch2: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", LONG]));
1250+
assert!(!batch2.as_string_view().data_buffers().is_empty());
1251+
1252+
let group_indices = vec![0usize, 0];
1253+
let mut acc = HllGroupsAccumulator::<Utf8ViewHasher>::new();
1254+
acc.update_batch(&[batch1], &group_indices, None, 1)
1255+
.unwrap();
1256+
acc.update_batch(&[batch2], &group_indices, None, 1)
1257+
.unwrap();
1258+
1259+
// True distinct values: {"aaa", "bbb", LONG} == 3.
1260+
let result = acc.evaluate(EmitTo::All).unwrap();
1261+
let counts = result.as_any().downcast_ref::<UInt64Array>().unwrap();
1262+
assert_eq!(counts.value(0), 3);
1263+
}
1264+
1265+
/// Regression: a short (≤ 12-byte) Utf8View string must hash identically
1266+
/// regardless of which batch it appears in — all-inline or mixed.
1267+
#[test]
1268+
fn utf8view_acc_split_batches_match_single_mixed_batch() {
1269+
// Multiset: {"aaa" x2, "bbb", LONG}, so 3 distinct values.
1270+
let mixed: ArrayRef =
1271+
Arc::new(StringViewArray::from(vec!["aaa", "bbb", LONG, "aaa"]));
1272+
let mut acc_single = StringViewHLLAccumulator::new();
1273+
acc_single.update_batch(&[mixed]).unwrap();
1274+
1275+
// Same multiset, but split so "aaa" lands in both an all-inline batch
1276+
// and a batch with a data buffer (forced by LONG).
1277+
let inline_only: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", "bbb"]));
1278+
let with_buffer: ArrayRef = Arc::new(StringViewArray::from(vec!["aaa", LONG]));
1279+
assert!(inline_only.as_string_view().data_buffers().is_empty());
1280+
assert!(!with_buffer.as_string_view().data_buffers().is_empty());
1281+
1282+
let mut acc_split = StringViewHLLAccumulator::new();
1283+
acc_split.update_batch(&[inline_only]).unwrap();
1284+
acc_split.update_batch(&[with_buffer]).unwrap();
1285+
1286+
assert_eq!(
1287+
distinct_count(&mut acc_single),
1288+
distinct_count(&mut acc_split)
1289+
);
1290+
assert_eq!(distinct_count(&mut acc_single), 3);
1291+
}
12081292
}

0 commit comments

Comments
 (0)