Repository navigation
Commit b23e6b6
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
- src
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
15 | 15 | | |
16 | 16 | | |
17 | 17 | | |
| 18 | + | |
18 | 19 | | |
19 | 20 | | |
20 | 21 | | |
| |||
24 | 25 | | |
25 | 26 | | |
26 | 27 | | |
27 | | - | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
28 | 31 | | |
| 32 | + | |
| 33 | + | |
29 | 34 | | |
30 | 35 | | |
31 | 36 | | |
| |||
34 | 39 | | |
35 | 40 | | |
36 | 41 | | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
37 | 47 | | |
38 | 48 | | |
39 | 49 | | |
| |||
216 | 226 | | |
217 | 227 | | |
218 | 228 | | |
219 | | - | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
| 255 | + | |
| 256 | + | |
| 257 | + | |
| 258 | + | |
| 259 | + | |
| 260 | + | |
| 261 | + | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
| 266 | + | |
| 267 | + | |
| 268 | + | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
| 280 | + | |
| 281 | + | |
| 282 | + | |
| 283 | + | |
| 284 | + | |
| 285 | + | |
| 286 | + | |
| 287 | + | |
| 288 | + | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
| 292 | + | |
| 293 | + | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
| 298 | + | |
| 299 | + | |
| 300 | + | |
| 301 | + | |
| 302 | + | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
| 309 | + | |
| 310 | + | |
| 311 | + | |
| 312 | + | |
| 313 | + | |
| 314 | + | |
| 315 | + | |
| 316 | + | |
| 317 | + | |
| 318 | + | |
| 319 | + | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
| 324 | + | |
| 325 | + | |
| 326 | + | |
| 327 | + | |
| 328 | + | |
| 329 | + | |
| 330 | + | |
220 | 331 | | |
0 commit comments