Skip to content

Commit b23e6b6

Browse files
authored
perf: improve approx_distinct performance 100x when there are fewer distinct values with many groups (apache#22768)
## Which issue does this PR close? - Closes apache#22767 ## Rationale for this change `approx_distinct` is very slow with `GROUP BY` on high-cardinality keys. On a dataset (~3.9M rows, ~512K groups), one file from the dataset describe in apache#22767 ```sql SELECT client_ip, approx_distinct(trace_id) AS cnt FROM '*.parquet' GROUP BY client_ip ORDER BY cnt DESC LIMIT 10; ``` - DataFusion: **~32.6s** - DuckDB (`approx_count_distinct`): **~0.1s** The reason is that `approx_distinct` only implemented `Accumulator`, not `GroupsAccumulator`. So grouped queries fell back to `GroupsAccumulatorAdapter`, which allocates a full 16 KiB HyperLogLog per group (~8 GB for 512K groups) and re-slices the input per group on every batch — even though most groups only see a few distinct values. ## What changes are included in this PR? - Add a dedicated `GroupsAccumulator` for `approx_distinct` that processes each batch in a single pass (no per-group slicing or dynamic dispatch). - Use an adaptive per-group sketch: keep a small list of hashes (sparse) and only switch to a dense 16 KiB HyperLogLog after 256 distinct values. This cuts memory and keeps the partial state small. The dense format stays compatible with the existing scalar accumulator. - Add `count_from_hashes` so small groups are estimated directly from their stored hashes, avoiding a 16 KiB alloc + scan per group at output time. - Hashing matches the existing per-type scalar accumulators, so results are unchanged. Boolean / small-int / `Null` keep using the old path. Result on the query above: **~32.6s → ~0.12s** (~270x, on par with DuckDB), with identical output. ## Are these changes tested? Yes. - New unit tests for the per-group sketch (sparse/dense, promotion, serialize/merge round-trip, merging groups, empty groups), checked against a dense-fold reference. - New `aggregate.slt` cases: grouped `approx_distinct` over `Utf8`, `Utf8View`, and `Int32` (small groups are exact), null-only groups (= 0), and a sparse→dense case (2000 distinct/group, within HyperLogLog error). - Existing `aggregate.slt` and `aggregate_skip_partial.slt` still pass; clippy and fmt are clean. ## Are there any user-facing changes? No API or result changes — only a large speedup for `approx_distinct` with `GROUP BY` on high-cardinality keys.
1 parent d0d993d commit b23e6b6

4 files changed

Lines changed: 972 additions & 14 deletions

File tree

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

Lines changed: 113 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18+
use std::hint::black_box;
1819
use std::sync::Arc;
1920

2021
use arrow::array::{
@@ -24,8 +25,12 @@ use arrow::array::{
2425
use arrow::datatypes::{DataType, Field, Schema};
2526
use criterion::{Criterion, criterion_group, criterion_main};
2627
use datafusion_expr::function::AccumulatorArgs;
27-
use datafusion_expr::{Accumulator, AggregateUDFImpl};
28+
use datafusion_expr::{
29+
Accumulator, AggregateUDF, AggregateUDFImpl, EmitTo, GroupsAccumulator,
30+
};
2831
use datafusion_functions_aggregate::approx_distinct::ApproxDistinct;
32+
use datafusion_physical_expr::GroupsAccumulatorAdapter;
33+
use datafusion_physical_expr::aggregate::AggregateExprBuilder;
2934
use datafusion_physical_expr::expressions::col;
3035
use rand::rngs::StdRng;
3136
use rand::{Rng, SeedableRng};
@@ -34,6 +39,11 @@ const BATCH_SIZE: usize = 8192;
3439
const SHORT_STRING_LENGTH: usize = 8;
3540
const LONG_STRING_LENGTH: usize = 20;
3641

42+
// Grouped (high-cardinality `GROUP BY`) benchmark parameters.
43+
const N_GROUPS: usize = 50_000;
44+
const AVG_ROWS_PER_GROUP: usize = 8;
45+
const STRING_POOL_SIZE: usize = 100_000;
46+
3747
fn prepare_accumulator(data_type: DataType) -> Box<dyn Accumulator> {
3848
let schema = Arc::new(Schema::new(vec![Field::new("f", data_type, true)]));
3949
let expr = col("f", &schema).unwrap();
@@ -216,5 +226,106 @@ fn approx_distinct_benchmark(c: &mut Criterion) {
216226
});
217227
}
218228

219-
criterion_group!(benches, approx_distinct_benchmark);
229+
/// Build a `GroupsAccumulator` the same way the aggregate operator does: use the
230+
/// specialized one if the function supports it, otherwise fall back to wrapping
231+
/// the per-group `Accumulator` in a `GroupsAccumulatorAdapter`.
232+
fn prepare_groups_accumulator(data_type: DataType) -> Box<dyn GroupsAccumulator> {
233+
let schema = Arc::new(Schema::new(vec![Field::new("f", data_type, true)]));
234+
let expr = col("f", &schema).unwrap();
235+
let udf = Arc::new(AggregateUDF::from(ApproxDistinct::new()));
236+
let agg = Arc::new(
237+
AggregateExprBuilder::new(udf, vec![expr])
238+
.schema(schema)
239+
.alias("approx_distinct(f)")
240+
.build()
241+
.unwrap(),
242+
);
243+
244+
if agg.groups_accumulator_supported() {
245+
agg.create_groups_accumulator().unwrap()
246+
} else {
247+
let agg = Arc::clone(&agg);
248+
let factory = move || agg.create_accumulator();
249+
Box::new(GroupsAccumulatorAdapter::new(factory))
250+
}
251+
}
252+
253+
fn grouped_total_rows() -> usize {
254+
N_GROUPS * AVG_ROWS_PER_GROUP
255+
}
256+
257+
/// A random group index in `0..N_GROUPS` for each row of a batch.
258+
fn make_group_indices(rng: &mut StdRng) -> Vec<usize> {
259+
(0..BATCH_SIZE)
260+
.map(|_| rng.random_range(0..N_GROUPS))
261+
.collect()
262+
}
263+
264+
/// Pre-build all input batches `(values, group_indices)` for the grouped run, so
265+
/// the measured loop only times the accumulator, not data generation.
266+
fn build_grouped_batches(data_type: &DataType) -> Vec<(ArrayRef, Vec<usize>)> {
267+
let n_batches = grouped_total_rows().div_ceil(BATCH_SIZE);
268+
let mut rng = StdRng::seed_from_u64(7);
269+
let pool = create_string_pool(STRING_POOL_SIZE, SHORT_STRING_LENGTH);
270+
271+
(0..n_batches)
272+
.map(|_| {
273+
let group_indices = make_group_indices(&mut rng);
274+
let values: ArrayRef = match data_type {
275+
DataType::Int64 => Arc::new(
276+
(0..BATCH_SIZE)
277+
.map(|_| Some(rng.random::<i64>()))
278+
.collect::<Int64Array>(),
279+
),
280+
DataType::Utf8 => Arc::new(
281+
(0..BATCH_SIZE)
282+
.map(|_| Some(pool[rng.random_range(0..pool.len())].as_str()))
283+
.collect::<StringArray>(),
284+
),
285+
DataType::Utf8View => Arc::new(
286+
(0..BATCH_SIZE)
287+
.map(|_| Some(pool[rng.random_range(0..pool.len())].as_str()))
288+
.collect::<StringViewArray>(),
289+
),
290+
other => panic!("unsupported grouped bench type: {other}"),
291+
};
292+
(values, group_indices)
293+
})
294+
.collect()
295+
}
296+
297+
/// Benchmark grouped `approx_distinct` over many groups. Each iteration feeds all batches into a
298+
/// fresh accumulator and emits the result for every group.
299+
fn approx_distinct_grouped_benchmark(c: &mut Criterion) {
300+
let mut group = c.benchmark_group("approx_distinct_grouped");
301+
group.sample_size(10);
302+
303+
for data_type in [DataType::Int64, DataType::Utf8, DataType::Utf8View] {
304+
let batches = build_grouped_batches(&data_type);
305+
let label = format!("{data_type:?} {N_GROUPS} groups");
306+
group.bench_function(&label, |b| {
307+
b.iter(|| {
308+
let mut acc = prepare_groups_accumulator(data_type.clone());
309+
for (values, group_indices) in &batches {
310+
acc.update_batch(
311+
std::slice::from_ref(values),
312+
group_indices,
313+
None,
314+
N_GROUPS,
315+
)
316+
.unwrap();
317+
}
318+
black_box(acc.evaluate(EmitTo::All).unwrap());
319+
})
320+
});
321+
}
322+
323+
group.finish();
324+
}
325+
326+
criterion_group!(
327+
benches,
328+
approx_distinct_benchmark,
329+
approx_distinct_grouped_benchmark
330+
);
220331
criterion_main!(benches);

0 commit comments

Comments
 (0)