You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "sandeshkr419 (via GitHub)" <gi...@apache.org> on 2026/07/22 19:25:04 UTC
[PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
sandeshkr419 opened a new pull request, #23816:
URL: https://github.com/apache/datafusion/pull/23816
## Which issue does this PR close?
Resolves https://github.com/apache/datafusion/issues/23815
## Rationale for this change
Adds runtime-configurable HLL precision to approx_distinct. Previously the register count was a compile-time constant (p=14, 16 KiB per sketch); now any precision between 4 to 18 is supported.
## What changes are included in this PR?
- HyperLogLog::with_precision(p): constructs a sketch at the requested precision; new() still defaults to p=14.
- HyperLogLog::from_registers(vec): replaces new_with_registers([u8; 16384]); infers p from the slice length.
- ApproxDistinct::with_hll_precision(p): forwards p through every HLL accumulator path (HLLAccumulator, NumericHLLAccumulator, HllGroupsAccumulator). Has no effect for types that use exact bitmap counting (Boolean, Int8, UInt8, Int16, UInt16) — those paths are unaffected regardless of the value passed.
## Are these changes tested?
9 new tests cover: construction at non-default precisions, accuracy within expected error bounds at p=10 and p=12, roundtrip serialization at p=10/12/14, cross-precision merge panic (programming error guard), and boundary validation.
## Are there any user-facing changes?
None for existing callers. Old ApproxDistinct::new() and HyperLogLog::new() continue to use p=14.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3725664891
##########
datafusion/functions-aggregate/src/approx_distinct.rs:
##########
@@ -654,14 +707,35 @@ impl Default for ApproxDistinct {
#[derive(PartialEq, Eq, Hash)]
pub struct ApproxDistinct {
signature: Signature,
+ /// HLL register precision. Only used for types that take the HLL code path
+ /// (i.e. not Boolean / small-int types, which use exact bitmap counting).
+ hll_precision: usize,
}
impl ApproxDistinct {
pub fn new() -> Self {
Self {
signature: Signature::any(1, Volatility::Immutable),
+ hll_precision: DEFAULT_HLL_P,
}
}
+
+ /// Creates an `ApproxDistinct` that uses HLL sketches with `2^p` registers.
+ ///
+ /// This only has effect for types that use the HLL accumulator path. Small
+ /// integer and boolean types use exact bitmap counting regardless of this
+ /// value. Valid range: `HLL_P_MIN..=HLL_P_MAX` (4..=18).
+ pub fn with_hll_precision(p: usize) -> Result<Self> {
Review Comment:
Non-blocking suggestion:
It's the only API to use this configuration now, however mostly users are using higher level SQL/Dataframe API.
So it would be better to be able to set it from global configurations. After that we can add some end-to-end tests.
I remember there are no existing configurations targeting individual functions, so perhaps some refactor would be needed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5273610199
Thanks @kosiew for running the benchmarks again!
The `decimal128/256` regression should now go away with my the latest commit.
In the latest commit, I extracted `DEFAULT_Q` and `DEFAULT_MASK` as module-level constants (single declaration), and funnelled all pre-hashed loops through a `for_each_hash` method that checks `p == DEFAULT_HLL_P` once before entering the loop. The `Extend` impls still have an explicit and **intentional** `if self.p == DEFAULT_HLL_P` branch inline because Rust's compiler needs to see the const values at the call site to emit them as instruction immediates.
A helper function boundary blocks that optimization (measured it: +10% regression when abstracted through map()).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3779045152
##########
datafusion/functions-aggregate/src/hyperloglog.rs:
##########
@@ -70,107 +99,182 @@ impl<T> HyperLogLog<T>
where
T: Hash + ?Sized,
{
- /// Creates a new, empty HyperLogLog.
+ /// Creates a new, empty HyperLogLog with the default precision (14).
pub fn new() -> Self {
- let registers = [0; NUM_REGISTERS];
- Self::new_with_registers(registers)
+ Self::with_precision(DEFAULT_HLL_P)
}
- /// Creates a HyperLogLog from already populated registers
- /// note that this method should not be invoked in untrusted environment
- /// because the internal structure of registers are not examined.
- pub(crate) fn new_with_registers(registers: [u8; NUM_REGISTERS]) -> Self {
+ /// Creates a new, empty HyperLogLog with the given precision `p`.
+ ///
+ /// The number of registers is `2^p`. Supported range: `HLL_P_MIN..=DEFAULT_HLL_P`.
+ #[inline(always)]
+ pub fn with_precision(p: usize) -> Self {
+ assert!(
+ (HLL_P_MIN..=DEFAULT_HLL_P).contains(&p),
+ "HLL precision must be in {HLL_P_MIN}..={DEFAULT_HLL_P}, got {p}",
+ );
+ let q = 64 - p;
+ let p_mask = ((1_usize << p) as u64) - 1;
Self {
- registers,
+ p,
+ q,
+ p_mask,
phantom: PhantomData,
+ registers: [0u8; 1 << DEFAULT_HLL_P],
}
}
- /// The HLL hash state is shared through `datafusion_common::hash_utils`
- /// so sketches remain compatible across accumulators.
+ /// Creates a HyperLogLog from already populated registers.
+ ///
+ /// The precision is inferred from the register slice length, which must be
+ /// a power of two in the range `2^HLL_P_MIN..=2^DEFAULT_HLL_P`.
+ ///
+ /// Note that this method should not be invoked in an untrusted environment
+ /// because the internal structure of registers is not examined.
+ pub(crate) fn from_registers(v: &[u8]) -> Self {
+ let len = v.len();
+ assert!(
+ len.is_power_of_two(),
+ "register slice length must be a power of two, got {len}",
+ );
+ let p = len.ilog2() as usize;
+ assert!(
+ (HLL_P_MIN..=DEFAULT_HLL_P).contains(&p),
+ "inferred precision {p} is outside {HLL_P_MIN}..={DEFAULT_HLL_P}",
+ );
+ let q = 64 - p;
+ let p_mask = (len as u64) - 1;
+ let mut registers = [0u8; 1 << DEFAULT_HLL_P];
+ registers[..len].copy_from_slice(v);
+ Self {
+ p,
+ q,
+ p_mask,
+ phantom: PhantomData,
+ registers,
+ }
+ }
+
+ /// The precision of this sketch.
#[inline]
- fn hash_value(&self, obj: &T) -> u64 {
- HLL_HASH_STATE.hash_one(obj)
+ pub(crate) fn precision(&self) -> usize {
+ self.p
+ }
+
+ /// Heap bytes used by the register buffer (not captured by `size_of_val`).
+ /// Always 0 — registers are stored inline in the struct.
+ pub(crate) fn register_heap_size(&self) -> usize {
+ 0
}
/// Adds an element to the HyperLogLog.
+ #[cfg(test)]
pub fn add(&mut self, obj: &T) {
- let hash = self.hash_value(obj);
+ let hash = HLL_HASH_STATE.hash_one(obj);
self.add_hashed(hash);
}
/// Adds a pre-computed hash value directly to the HyperLogLog.
///
/// The hash should be computed using [`HLL_HASH_STATE`], the same hasher used
/// by [`Self::add`].
- #[inline]
+ #[inline(always)]
pub(crate) fn add_hashed(&mut self, hash: u64) {
- let index = (hash & HLL_P_MASK) as usize;
- let p = ((hash >> HLL_P) | (1_u64 << HLL_Q)).trailing_zeros() + 1;
- self.registers[index] = self.registers[index].max(p as u8);
+ self.for_each_hash(std::iter::once(hash));
Review Comment:
Done, please check now.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3772133887
##########
datafusion/functions-aggregate/src/approx_distinct.rs:
##########
@@ -654,14 +707,35 @@ impl Default for ApproxDistinct {
#[derive(PartialEq, Eq, Hash)]
pub struct ApproxDistinct {
signature: Signature,
+ /// HLL register precision. Only used for types that take the HLL code path
+ /// (i.e. not Boolean / small-int types, which use exact bitmap counting).
+ hll_precision: usize,
}
impl ApproxDistinct {
pub fn new() -> Self {
Self {
signature: Signature::any(1, Volatility::Immutable),
+ hll_precision: DEFAULT_HLL_P,
}
}
+
+ /// Creates an `ApproxDistinct` that uses HLL sketches with `2^p` registers.
+ ///
+ /// This only has effect for types that use the HLL accumulator path. Small
+ /// integer and boolean types use exact bitmap counting regardless of this
+ /// value. Valid range: `HLL_P_MIN..=HLL_P_MAX` (4..=18).
+ pub fn with_hll_precision(p: usize) -> Result<Self> {
Review Comment:
Yes, that would be great.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-6506518595
closing as AI spam. Again, sorry for wasting your time @kosiew
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5060408637
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/23816?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `91.98473%` with `21 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 80.71%. Comparing base ([`c118002`](https://app.codecov.io/gh/apache/datafusion/commit/c1180022e63f48a3af175d8d73dc21cca9379c65?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`5188279`](https://app.codecov.io/gh/apache/datafusion/commit/51882797097e21430296ba0691a3b18e07ec637a?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 13 commits behind head on main.
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/23816?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...afusion/functions-aggregate/src/approx\_distinct.rs](https://app.codecov.io/gh/apache/datafusion/pull/23816?src=pr&el=tree&filepath=datafusion%2Ffunctions-aggregate%2Fsrc%2Fapprox_distinct.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9mdW5jdGlvbnMtYWdncmVnYXRlL3NyYy9hcHByb3hfZGlzdGluY3QucnM=) | 85.41% | [20 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23816?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #23816 +/- ##
==========================================
- Coverage 80.72% 80.71% -0.01%
==========================================
Files 1089 1089
Lines 368911 369040 +129
Branches 368911 369040 +129
==========================================
+ Hits 297785 297884 +99
- Misses 53374 53395 +21
- Partials 17752 17761 +9
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/23816?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5265468179
🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/23816#issuecomment-5265441170)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c5265441170-1567-xfg92 6.12.85+ #1 SMP Wed Jun 17 20:31:55 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing hll-precision-param (8ab9e49f61480c270875f0d17f9a834581db107e) to 30ca39b (merge-base) [diff](https://github.com/apache/datafusion/compare/30ca39bef9ea2e746e143727f9de48b1608edc2a..8ab9e49f61480c270875f0d17f9a834581db107e)
<details><summary>Run configuration</summary>
```yaml
run benchmark approx_distinct
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5199989098
🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/23816#issuecomment-5199972189)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c5199972189-1465-r72j2 6.12.85+ #1 SMP Wed Jun 17 20:31:55 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing hll-precision-param (6a374a1ea63c246c5ba524c3def3c46d91aeb5f1) to 882d906 (merge-base) [diff](https://github.com/apache/datafusion/compare/882d90658a9334c3205c7994ac15b7c25163864c..6a374a1ea63c246c5ba524c3def3c46d91aeb5f1)
<details><summary>Run configuration</summary>
```yaml
run benchmark approx_distinct
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5259358458
Thanks @2010YOUY01 for the review and sharing benchmark data. I was able to reproduce the regression on my end and find the issue and add new benhcmarks.
**On the regression:** Root cause was `changing registers from [u8; 16384] to Vec<u8>` (double allocation per accumulator) and `p/q/p_mask` becoming struct fields loaded on every add_hashed call instead of compile-time constants.
Fixed in a follow-up commit: registers are back to an inline array (single allocation as before), and a `hll_update!` macro uses compile-time constants for the `p=14` path. Valid range is also tightened to `HLL_P_MIN..=DEFAULT_HLL_P (4..=14)` since p>14 was outside the feature intent of memory consumption and performance improvement.
Special handling of p=14 is to avoid performance hit on default case.
**On benchmarks**: Added two new groups: `approx_distinct_precision` and `approx_distinct_grouped_precision`, running across p ∈ {8, 10, 12, 14} for i64, utf8, and Decimal128. Confirms the expected ordering: p=12 is ~40% faster than p=14, p=8 ~50% faster, primarily from count() scanning 4× and 64× fewer registers respectively.
Please help review the changes and re-trigger benchmarks for another round of validation!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed pull request #23816: feat(functions-aggregate): make approx_distinct HLL precision configurable
URL: https://github.com/apache/datafusion/pull/23816
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5265441170
run benchmark approx_distinct
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5122765708
Thanks for the thorough review @kosiew!
Addressed the comments. Please take another look when you get a chance!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3677571483
##########
datafusion/functions-aggregate/src/approx_distinct.rs:
##########
@@ -654,12 +701,29 @@ impl Default for ApproxDistinct {
#[derive(PartialEq, Eq, Hash)]
pub struct ApproxDistinct {
signature: Signature,
+ /// HLL register precision. Only used for types that take the HLL code path
+ /// (i.e. not Boolean / small-int types, which use exact bitmap counting).
+ hll_precision: usize,
}
impl ApproxDistinct {
pub fn new() -> Self {
+ Self::with_hll_precision(DEFAULT_HLL_P)
+ }
+
+ /// Creates an `ApproxDistinct` that uses HLL sketches with `2^p` registers.
+ ///
+ /// This only has effect for types that use the HLL accumulator path. Small
+ /// integer and boolean types use exact bitmap counting regardless of this
+ /// value. Valid range: `HLL_P_MIN..=HLL_P_MAX` (4..=18).
+ pub fn with_hll_precision(p: usize) -> Self {
Review Comment:
Replaced the `assert!` with `plan_err!` so invalid precision surfaces as a clean DataFusion error rather than a panic.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5200081329
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/23816#issuecomment-5199972189)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing hll-precision-param (6a374a1ea63c246c5ba524c3def3c46d91aeb5f1) to 882d906 (merge-base) [diff](https://github.com/apache/datafusion/compare/882d90658a9334c3205c7994ac15b7c25163864c..6a374a1ea63c246c5ba524c3def3c46d91aeb5f1)
<details><summary>Run configuration</summary>
```yaml
run benchmark approx_distinct
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
group HEAD hll-precision-param
----- ---- -------------------
approx_distinct decimal128 1.00 14.5±0.02µs ? ?/sec 1.12 16.3±0.01µs ? ?/sec
approx_distinct decimal256 1.00 18.1±0.03µs ? ?/sec 1.23 22.3±0.02µs ? ?/sec
approx_distinct decimal32 1.00 12.9±0.01µs ? ?/sec 1.08 14.0±0.01µs ? ?/sec
approx_distinct decimal64 1.00 12.9±0.01µs ? ?/sec 1.09 14.1±0.02µs ? ?/sec
approx_distinct i16 bitmap 1.23 8.7±0.01µs ? ?/sec 1.00 7.1±0.44µs ? ?/sec
approx_distinct i64 80% distinct 1.00 12.8±0.01µs ? ?/sec 1.10 14.0±0.02µs ? ?/sec
approx_distinct i64 99% distinct 1.00 12.9±0.01µs ? ?/sec 1.09 14.1±0.02µs ? ?/sec
approx_distinct i8 bitmap 1.00 4.3±0.04µs ? ?/sec 1.01 4.4±0.01µs ? ?/sec
approx_distinct interval day_time 80% distinct 1.00 13.0±0.03µs ? ?/sec 1.08 14.1±0.03µs ? ?/sec
approx_distinct interval day_time 99% distinct 1.00 12.9±0.03µs ? ?/sec 1.09 14.1±0.01µs ? ?/sec
approx_distinct interval month_day_nano 80% distinct 1.00 13.9±0.01µs ? ?/sec 1.20 16.6±0.01µs ? ?/sec
approx_distinct interval month_day_nano 99% distinct 1.00 13.9±0.01µs ? ?/sec 1.20 16.7±0.03µs ? ?/sec
approx_distinct interval year_month 80% distinct 1.00 12.9±0.03µs ? ?/sec 1.09 14.0±0.01µs ? ?/sec
approx_distinct interval year_month 99% distinct 1.00 12.8±0.01µs ? ?/sec 1.09 14.0±0.03µs ? ?/sec
approx_distinct u16 bitmap 1.00 5.9±0.00µs ? ?/sec 1.46 8.6±0.01µs ? ?/sec
approx_distinct u8 bitmap 1.00 4.4±0.01µs ? ?/sec 1.01 4.4±0.01µs ? ?/sec
approx_distinct utf8 long 80% distinct 1.00 33.7±0.02µs ? ?/sec 1.00 33.7±0.07µs ? ?/sec
approx_distinct utf8 long 99% distinct 1.00 33.7±0.02µs ? ?/sec 1.00 33.5±0.04µs ? ?/sec
approx_distinct utf8 short 80% distinct 1.00 24.0±0.01µs ? ?/sec 1.02 24.4±0.02µs ? ?/sec
approx_distinct utf8 short 99% distinct 1.00 23.9±0.13µs ? ?/sec 1.02 24.3±0.01µs ? ?/sec
approx_distinct utf8view long 80% distinct 1.00 40.5±0.02µs ? ?/sec 1.00 40.7±0.03µs ? ?/sec
approx_distinct utf8view long 99% distinct 1.00 40.6±0.02µs ? ?/sec 1.00 40.6±0.03µs ? ?/sec
approx_distinct utf8view short 80% distinct 1.00 16.2±0.03µs ? ?/sec 1.02 16.6±0.03µs ? ?/sec
approx_distinct utf8view short 99% distinct 1.00 16.6±0.01µs ? ?/sec 1.00 16.6±0.04µs ? ?/sec
approx_distinct_grouped/Decimal128(10, 2) 50000 groups 1.00 30.3±0.41ms ? ?/sec 1.00 30.4±0.38ms ? ?/sec
approx_distinct_grouped/Decimal256(40, 2) 50000 groups 1.00 30.6±0.53ms ? ?/sec 1.03 31.5±0.43ms ? ?/sec
approx_distinct_grouped/Decimal32(9, 2) 50000 groups 1.00 28.9±0.34ms ? ?/sec 1.05 30.3±0.34ms ? ?/sec
approx_distinct_grouped/Decimal64(18, 2) 50000 groups 1.00 29.3±0.25ms ? ?/sec 1.03 30.2±0.34ms ? ?/sec
approx_distinct_grouped/Int64 50000 groups 1.00 29.2±0.28ms ? ?/sec 1.05 30.5±0.35ms ? ?/sec
approx_distinct_grouped/Interval(DayTime) 50000 groups 1.00 28.9±1.05ms ? ?/sec 1.06 30.5±0.88ms ? ?/sec
approx_distinct_grouped/Interval(MonthDayNano) 50000 groups 1.00 29.8±0.36ms ? ?/sec 1.04 31.0±0.39ms ? ?/sec
approx_distinct_grouped/Interval(YearMonth) 50000 groups 1.00 29.9±0.49ms ? ?/sec 1.00 29.9±0.49ms ? ?/sec
approx_distinct_grouped/Utf8 50000 groups 1.00 29.3±0.29ms ? ?/sec 1.06 31.0±0.40ms ? ?/sec
approx_distinct_grouped/Utf8View 50000 groups 1.00 29.4±0.40ms ? ?/sec 1.05 30.8±0.40ms ? ?/sec
```
</p>
</details>
<details><summary>Resource Usage</summary>
**approx_distinct — base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 495.1s |
| Peak memory | 56.1 MiB |
| Avg memory | 23.5 MiB |
| CPU user | 405.5s |
| CPU sys | 0.4s |
| Peak spill | 0 B |
**approx_distinct — branch**
| Metric | Value |
|--------|-------|
| Wall time | 490.1s |
| Peak memory | 58.9 MiB |
| Avg memory | 25.3 MiB |
| CPU user | 409.0s |
| CPU sys | 0.4s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3772221474
##########
datafusion/functions-aggregate/src/hyperloglog.rs:
##########
@@ -70,107 +99,182 @@ impl<T> HyperLogLog<T>
where
T: Hash + ?Sized,
{
- /// Creates a new, empty HyperLogLog.
+ /// Creates a new, empty HyperLogLog with the default precision (14).
pub fn new() -> Self {
- let registers = [0; NUM_REGISTERS];
- Self::new_with_registers(registers)
+ Self::with_precision(DEFAULT_HLL_P)
}
- /// Creates a HyperLogLog from already populated registers
- /// note that this method should not be invoked in untrusted environment
- /// because the internal structure of registers are not examined.
- pub(crate) fn new_with_registers(registers: [u8; NUM_REGISTERS]) -> Self {
+ /// Creates a new, empty HyperLogLog with the given precision `p`.
+ ///
+ /// The number of registers is `2^p`. Supported range: `HLL_P_MIN..=DEFAULT_HLL_P`.
+ #[inline(always)]
+ pub fn with_precision(p: usize) -> Self {
+ assert!(
+ (HLL_P_MIN..=DEFAULT_HLL_P).contains(&p),
+ "HLL precision must be in {HLL_P_MIN}..={DEFAULT_HLL_P}, got {p}",
+ );
+ let q = 64 - p;
+ let p_mask = ((1_usize << p) as u64) - 1;
Self {
- registers,
+ p,
+ q,
+ p_mask,
phantom: PhantomData,
+ registers: [0u8; 1 << DEFAULT_HLL_P],
}
}
- /// The HLL hash state is shared through `datafusion_common::hash_utils`
- /// so sketches remain compatible across accumulators.
+ /// Creates a HyperLogLog from already populated registers.
+ ///
+ /// The precision is inferred from the register slice length, which must be
+ /// a power of two in the range `2^HLL_P_MIN..=2^DEFAULT_HLL_P`.
+ ///
+ /// Note that this method should not be invoked in an untrusted environment
+ /// because the internal structure of registers is not examined.
+ pub(crate) fn from_registers(v: &[u8]) -> Self {
+ let len = v.len();
+ assert!(
+ len.is_power_of_two(),
+ "register slice length must be a power of two, got {len}",
+ );
+ let p = len.ilog2() as usize;
+ assert!(
+ (HLL_P_MIN..=DEFAULT_HLL_P).contains(&p),
+ "inferred precision {p} is outside {HLL_P_MIN}..={DEFAULT_HLL_P}",
+ );
+ let q = 64 - p;
+ let p_mask = (len as u64) - 1;
+ let mut registers = [0u8; 1 << DEFAULT_HLL_P];
+ registers[..len].copy_from_slice(v);
+ Self {
+ p,
+ q,
+ p_mask,
+ phantom: PhantomData,
+ registers,
+ }
+ }
+
+ /// The precision of this sketch.
#[inline]
- fn hash_value(&self, obj: &T) -> u64 {
- HLL_HASH_STATE.hash_one(obj)
+ pub(crate) fn precision(&self) -> usize {
+ self.p
+ }
+
+ /// Heap bytes used by the register buffer (not captured by `size_of_val`).
+ /// Always 0 — registers are stored inline in the struct.
+ pub(crate) fn register_heap_size(&self) -> usize {
+ 0
}
/// Adds an element to the HyperLogLog.
+ #[cfg(test)]
pub fn add(&mut self, obj: &T) {
- let hash = self.hash_value(obj);
+ let hash = HLL_HASH_STATE.hash_one(obj);
self.add_hashed(hash);
}
/// Adds a pre-computed hash value directly to the HyperLogLog.
///
/// The hash should be computed using [`HLL_HASH_STATE`], the same hasher used
/// by [`Self::add`].
- #[inline]
+ #[inline(always)]
pub(crate) fn add_hashed(&mut self, hash: u64) {
- let index = (hash & HLL_P_MASK) as usize;
- let p = ((hash >> HLL_P) | (1_u64 << HLL_Q)).trailing_zeros() + 1;
- self.registers[index] = self.registers[index].max(p as u8);
+ self.for_each_hash(std::iter::once(hash));
Review Comment:
Creating multiple utilities to implement this function seem unnecessary, could we inline all the logic like the previous implementation
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3761999571
##########
datafusion/functions-aggregate/src/approx_distinct.rs:
##########
@@ -654,14 +707,35 @@ impl Default for ApproxDistinct {
#[derive(PartialEq, Eq, Hash)]
pub struct ApproxDistinct {
signature: Signature,
+ /// HLL register precision. Only used for types that take the HLL code path
+ /// (i.e. not Boolean / small-int types, which use exact bitmap counting).
+ hll_precision: usize,
}
impl ApproxDistinct {
pub fn new() -> Self {
Self {
signature: Signature::any(1, Volatility::Immutable),
+ hll_precision: DEFAULT_HLL_P,
}
}
+
+ /// Creates an `ApproxDistinct` that uses HLL sketches with `2^p` registers.
+ ///
+ /// This only has effect for types that use the HLL accumulator path. Small
+ /// integer and boolean types use exact bitmap counting regardless of this
+ /// value. Valid range: `HLL_P_MIN..=HLL_P_MAX` (4..=18).
+ pub fn with_hll_precision(p: usize) -> Result<Self> {
Review Comment:
Makes sense, we can carve out a new issue to address this as a follow-up just to keep this PR contained. Hope that's okay?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5591757473
Marking as draft as I think this PR is no longer waiting on feedback and I am trying to make it easier to find PRs in need of review. Please mark it as ready for review when it is ready for another look
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5183417865
Thanks @kosiew for helping with review and approval. Workflow is all green ready to be merged.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5265683376
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/23816#issuecomment-5265441170)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing hll-precision-param (8ab9e49f61480c270875f0d17f9a834581db107e) to 30ca39b (merge-base) [diff](https://github.com/apache/datafusion/compare/30ca39bef9ea2e746e143727f9de48b1608edc2a..8ab9e49f61480c270875f0d17f9a834581db107e)
<details><summary>Run configuration</summary>
```yaml
run benchmark approx_distinct
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
group HEAD hll-precision-param
----- ---- -------------------
approx_distinct decimal128 1.00 14.5±0.01µs ? ?/sec 1.09 15.9±0.04µs ? ?/sec
approx_distinct decimal256 1.00 18.1±0.01µs ? ?/sec 1.27 23.0±0.02µs ? ?/sec
approx_distinct decimal32 1.00 12.9±0.01µs ? ?/sec 1.00 12.9±0.01µs ? ?/sec
approx_distinct decimal64 1.00 12.9±0.01µs ? ?/sec 1.00 12.9±0.01µs ? ?/sec
approx_distinct i16 bitmap 1.50 8.9±0.28µs ? ?/sec 1.00 5.9±0.01µs ? ?/sec
approx_distinct i64 80% distinct 1.00 12.8±0.05µs ? ?/sec 1.01 13.0±0.01µs ? ?/sec
approx_distinct i64 99% distinct 1.01 13.0±0.01µs ? ?/sec 1.00 12.9±0.01µs ? ?/sec
approx_distinct i8 bitmap 1.00 4.4±0.01µs ? ?/sec 1.00 4.4±0.01µs ? ?/sec
approx_distinct interval day_time 80% distinct 1.00 12.8±0.01µs ? ?/sec 1.02 13.1±0.05µs ? ?/sec
approx_distinct interval day_time 99% distinct 1.00 12.9±0.01µs ? ?/sec 1.01 13.1±0.01µs ? ?/sec
approx_distinct interval month_day_nano 80% distinct 1.00 13.9±0.01µs ? ?/sec 1.01 14.1±0.02µs ? ?/sec
approx_distinct interval month_day_nano 99% distinct 1.00 13.9±0.01µs ? ?/sec 1.01 14.1±0.01µs ? ?/sec
approx_distinct interval year_month 80% distinct 1.00 12.9±0.03µs ? ?/sec 1.01 13.1±0.05µs ? ?/sec
approx_distinct interval year_month 99% distinct 1.00 12.9±0.06µs ? ?/sec 1.01 13.0±0.01µs ? ?/sec
approx_distinct u16 bitmap 1.00 5.9±0.01µs ? ?/sec 1.01 6.0±0.02µs ? ?/sec
approx_distinct u8 bitmap 1.01 4.4±0.01µs ? ?/sec 1.00 4.4±0.01µs ? ?/sec
approx_distinct utf8 long 80% distinct 1.01 33.7±0.02µs ? ?/sec 1.00 33.5±0.01µs ? ?/sec
approx_distinct utf8 long 99% distinct 1.00 33.6±0.08µs ? ?/sec 1.00 33.7±0.01µs ? ?/sec
approx_distinct utf8 short 80% distinct 1.01 24.3±0.01µs ? ?/sec 1.00 24.0±0.02µs ? ?/sec
approx_distinct utf8 short 99% distinct 1.00 24.0±0.02µs ? ?/sec 1.00 24.0±0.07µs ? ?/sec
approx_distinct utf8view long 80% distinct 1.00 40.1±0.02µs ? ?/sec 1.01 40.6±0.02µs ? ?/sec
approx_distinct utf8view long 99% distinct 1.00 40.4±0.17µs ? ?/sec 1.00 40.2±0.01µs ? ?/sec
approx_distinct utf8view short 80% distinct 1.00 16.6±0.01µs ? ?/sec 1.00 16.5±0.01µs ? ?/sec
approx_distinct utf8view short 99% distinct 1.00 16.4±0.18µs ? ?/sec 1.01 16.6±0.01µs ? ?/sec
approx_distinct_grouped/Decimal128(10, 2) 50000 groups 1.00 22.8±0.02ms ? ?/sec 1.05 24.0±0.05ms ? ?/sec
approx_distinct_grouped/Decimal256(40, 2) 50000 groups 1.00 22.8±0.02ms ? ?/sec 1.07 24.3±0.04ms ? ?/sec
approx_distinct_grouped/Decimal32(9, 2) 50000 groups 1.00 22.6±0.02ms ? ?/sec 1.06 23.9±0.04ms ? ?/sec
approx_distinct_grouped/Decimal64(18, 2) 50000 groups 1.00 22.3±0.01ms ? ?/sec 1.07 24.0±0.03ms ? ?/sec
approx_distinct_grouped/Int64 50000 groups 1.00 22.3±0.02ms ? ?/sec 1.07 23.8±0.02ms ? ?/sec
approx_distinct_grouped/Interval(DayTime) 50000 groups 1.00 22.3±0.03ms ? ?/sec 1.08 24.0±0.11ms ? ?/sec
approx_distinct_grouped/Interval(MonthDayNano) 50000 groups 1.00 22.5±0.04ms ? ?/sec 1.07 24.0±0.07ms ? ?/sec
approx_distinct_grouped/Interval(YearMonth) 50000 groups 1.00 22.3±0.03ms ? ?/sec 1.06 23.8±0.02ms ? ?/sec
approx_distinct_grouped/Utf8 50000 groups 1.00 22.7±0.01ms ? ?/sec 1.06 24.2±0.04ms ? ?/sec
approx_distinct_grouped/Utf8View 50000 groups 1.00 22.5±0.07ms ? ?/sec 1.07 24.1±0.07ms ? ?/sec
approx_distinct_grouped_precision/p=10 Int64 50000 groups 1.00 24.5±0.02ms ? ?/sec
approx_distinct_grouped_precision/p=10 Utf8 50000 groups 1.00 24.0±0.04ms ? ?/sec
approx_distinct_grouped_precision/p=12 Int64 50000 groups 1.00 24.6±0.10ms ? ?/sec
approx_distinct_grouped_precision/p=12 Utf8 50000 groups 1.00 24.9±0.06ms ? ?/sec
approx_distinct_grouped_precision/p=14 Int64 50000 groups 1.00 24.4±0.03ms ? ?/sec
approx_distinct_grouped_precision/p=14 Utf8 50000 groups 1.00 24.7±0.02ms ? ?/sec
approx_distinct_grouped_precision/p=8 Int64 50000 groups 1.00 24.8±0.07ms ? ?/sec
approx_distinct_grouped_precision/p=8 Utf8 50000 groups 1.00 24.2±0.06ms ? ?/sec
approx_distinct_precision/p=10 decimal128 200 distinct 1.00 19.7±0.06µs ? ?/sec
approx_distinct_precision/p=10 i64 99% distinct 1.00 17.0±0.08µs ? ?/sec
approx_distinct_precision/p=10 utf8 short 99% distinct 1.00 26.5±0.06µs ? ?/sec
approx_distinct_precision/p=12 decimal128 200 distinct 1.00 25.8±0.02µs ? ?/sec
approx_distinct_precision/p=12 i64 99% distinct 1.00 18.9±0.01µs ? ?/sec
approx_distinct_precision/p=12 utf8 short 99% distinct 1.00 28.3±0.02µs ? ?/sec
approx_distinct_precision/p=14 decimal128 200 distinct 1.00 48.6±0.01µs ? ?/sec
approx_distinct_precision/p=14 i64 99% distinct 1.00 37.0±0.02µs ? ?/sec
approx_distinct_precision/p=14 utf8 short 99% distinct 1.00 48.4±0.01µs ? ?/sec
approx_distinct_precision/p=8 decimal128 200 distinct 1.00 18.2±0.04µs ? ?/sec
approx_distinct_precision/p=8 i64 99% distinct 1.00 16.7±0.01µs ? ?/sec
approx_distinct_precision/p=8 utf8 short 99% distinct 1.00 26.0±0.01µs ? ?/sec
```
</p>
</details>
<details><summary>Resource Usage</summary>
**approx_distinct — base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 655.1s |
| Peak memory | 55.3 MiB |
| Avg memory | 18.3 MiB |
| CPU user | 422.0s |
| CPU sys | 0.4s |
| Peak spill | 0 B |
**approx_distinct — branch**
| Metric | Value |
|--------|-------|
| Wall time | 640.1s |
| Peak memory | 55.5 MiB |
| Avg memory | 31.1 MiB |
| CPU user | 622.1s |
| CPU sys | 0.6s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3677571483
##########
datafusion/functions-aggregate/src/approx_distinct.rs:
##########
@@ -654,12 +701,29 @@ impl Default for ApproxDistinct {
#[derive(PartialEq, Eq, Hash)]
pub struct ApproxDistinct {
signature: Signature,
+ /// HLL register precision. Only used for types that take the HLL code path
+ /// (i.e. not Boolean / small-int types, which use exact bitmap counting).
+ hll_precision: usize,
}
impl ApproxDistinct {
pub fn new() -> Self {
+ Self::with_hll_precision(DEFAULT_HLL_P)
+ }
+
+ /// Creates an `ApproxDistinct` that uses HLL sketches with `2^p` registers.
+ ///
+ /// This only has effect for types that use the HLL accumulator path. Small
+ /// integer and boolean types use exact bitmap counting regardless of this
+ /// value. Valid range: `HLL_P_MIN..=HLL_P_MAX` (4..=18).
+ pub fn with_hll_precision(p: usize) -> Self {
Review Comment:
Good call, replaced the `assert!` with `plan_err!` so invalid precision surfaces as a clean DataFusion error rather than a panic.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3677591122
##########
datafusion/functions-aggregate/src/approx_distinct.rs:
##########
Review Comment:
Added `HyperLogLog::register_heap_size()` and included it in both `HLLAccumulator::size()` and `NumericHLLAccumulator::size()`; `HllGroupsAccumulator` was already correct; added regression tests asserting `size() >= 1 << p`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3664383259
##########
datafusion/functions-aggregate/src/approx_distinct.rs:
##########
@@ -336,13 +367,14 @@ impl GroupHll {
/// Merge a serialized state (produced by [`Self::serialize`] or by the
/// per-group [`Accumulator`]) into this sketch.
- fn merge_serialized(&mut self, bytes: &[u8]) -> Result<isize> {
+ fn merge_serialized(&mut self, bytes: &[u8], p: usize) -> Result<isize> {
if bytes.is_empty() {
return Ok(0);
}
- if bytes.len() == NUM_REGISTERS {
+ let num_registers = 1_usize << p;
+ if bytes.len() == num_registers {
Review Comment:
I think there is a correctness issue with the grouped state encoding at lower precisions.
`merge_serialized` treats any state whose length is `1 << p` as a dense sketch, but `serialize` writes sparse state as raw `u64` hashes. For `p <= 11`, those encodings can have the same length. For example, at `p = 4`, two hashes serialize to `2 * 8 == 16 == 1 << p`, and at `p = 10`, 128 hashes serialize to `1024 == 1 << p`.
In those cases, the final aggregation interprets sparse hashes as register bytes, which produces incorrect cardinality estimates.
Could we make the encoding unambiguous by adding a dense/sparse tag, or alternatively force sparse state to be serialized as dense whenever its serialized length could match a dense sketch? It would also be good to add a round trip test for at least one `p <= 11` case.
##########
datafusion/functions-aggregate/src/approx_distinct.rs:
##########
Review Comment:
I think the memory accounting regressed when `HyperLogLog` changed from an inline `[u8; NUM_REGISTERS]` to a `Vec<u8>`.
`size_of_val(self)` now only includes the `Vec` header, so both `HLLAccumulator::size` here and `NumericHLLAccumulator::size` around line 280 no longer account for the register buffer itself. That under reports each sketch by `1 << p` bytes, which can be as much as 256 KiB per accumulator at `p = 18`.
This could allow memory limited aggregations to exceed their configured limits. Could we include the register buffer in `size()`, perhaps via a `HyperLogLog::size()` helper, and add a regression test for the reported size?
##########
datafusion/functions-aggregate/src/approx_distinct.rs:
##########
@@ -654,12 +701,29 @@ impl Default for ApproxDistinct {
#[derive(PartialEq, Eq, Hash)]
pub struct ApproxDistinct {
signature: Signature,
+ /// HLL register precision. Only used for types that take the HLL code path
+ /// (i.e. not Boolean / small-int types, which use exact bitmap counting).
+ hll_precision: usize,
}
impl ApproxDistinct {
pub fn new() -> Self {
+ Self::with_hll_precision(DEFAULT_HLL_P)
+ }
+
+ /// Creates an `ApproxDistinct` that uses HLL sketches with `2^p` registers.
+ ///
+ /// This only has effect for types that use the HLL accumulator path. Small
+ /// integer and boolean types use exact bitmap counting regardless of this
+ /// value. Valid range: `HLL_P_MIN..=HLL_P_MAX` (4..=18).
+ pub fn with_hll_precision(p: usize) -> Self {
Review Comment:
`with_hll_precision` currently panics for invalid input. Since this is a public Rust API, would it make sense to provide a fallible constructor instead? That would let callers return a normal DataFusion error instead of panicking. If the panic is intentional, it would be helpful to document that callers are expected to validate the precision first.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5172585563
Fixed clippy/fmt issues. Thanks @kosiew. Workflow run is currently blocked for a maintainer approval - please initiate it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3780810351
##########
datafusion/functions-aggregate/src/hyperloglog.rs:
##########
@@ -70,107 +80,174 @@ impl<T> HyperLogLog<T>
where
T: Hash + ?Sized,
{
- /// Creates a new, empty HyperLogLog.
+ /// Creates a new, empty HyperLogLog with the default precision (14).
pub fn new() -> Self {
- let registers = [0; NUM_REGISTERS];
- Self::new_with_registers(registers)
+ Self::with_precision(DEFAULT_HLL_P)
}
- /// Creates a HyperLogLog from already populated registers
- /// note that this method should not be invoked in untrusted environment
- /// because the internal structure of registers are not examined.
- pub(crate) fn new_with_registers(registers: [u8; NUM_REGISTERS]) -> Self {
+ /// Creates a new, empty HyperLogLog with the given precision `p`.
+ ///
+ /// The number of registers is `2^p`. Supported range: `HLL_P_MIN..=DEFAULT_HLL_P`.
+ #[inline(always)]
+ pub fn with_precision(p: usize) -> Self {
+ assert!(
+ (HLL_P_MIN..=DEFAULT_HLL_P).contains(&p),
+ "HLL precision must be in {HLL_P_MIN}..={DEFAULT_HLL_P}, got {p}",
+ );
+ let q = 64 - p;
+ let p_mask = ((1_usize << p) as u64) - 1;
Self {
- registers,
+ p,
+ q,
+ p_mask,
+ phantom: PhantomData,
+ registers: [0u8; 1 << DEFAULT_HLL_P],
+ }
+ }
+
+ /// Creates a HyperLogLog from already populated registers.
+ ///
+ /// The precision is inferred from the register slice length, which must be
+ /// a power of two in the range `2^HLL_P_MIN..=2^DEFAULT_HLL_P`.
+ ///
+ /// Note that this method should not be invoked in an untrusted environment
+ /// because the internal structure of registers is not examined.
+ pub(crate) fn from_registers(v: &[u8]) -> Self {
+ let len = v.len();
+ assert!(
+ len.is_power_of_two(),
+ "register slice length must be a power of two, got {len}",
+ );
+ let p = len.ilog2() as usize;
+ assert!(
+ (HLL_P_MIN..=DEFAULT_HLL_P).contains(&p),
+ "inferred precision {p} is outside {HLL_P_MIN}..={DEFAULT_HLL_P}",
+ );
+ let q = 64 - p;
+ let p_mask = (len as u64) - 1;
+ let mut registers = [0u8; 1 << DEFAULT_HLL_P];
+ registers[..len].copy_from_slice(v);
+ Self {
+ p,
+ q,
+ p_mask,
phantom: PhantomData,
+ registers,
}
}
- /// The HLL hash state is shared through `datafusion_common::hash_utils`
- /// so sketches remain compatible across accumulators.
+ /// The precision of this sketch.
#[inline]
- fn hash_value(&self, obj: &T) -> u64 {
- HLL_HASH_STATE.hash_one(obj)
+ pub(crate) fn precision(&self) -> usize {
+ self.p
+ }
+
+ /// Heap bytes used by the register buffer (not captured by `size_of_val`).
+ /// Always 0 — registers are stored inline in the struct.
+ pub(crate) fn register_heap_size(&self) -> usize {
+ 0
}
/// Adds an element to the HyperLogLog.
+ #[cfg(test)]
pub fn add(&mut self, obj: &T) {
- let hash = self.hash_value(obj);
+ let hash = HLL_HASH_STATE.hash_one(obj);
self.add_hashed(hash);
}
- /// Adds a pre-computed hash value directly to the HyperLogLog.
- ///
- /// The hash should be computed using [`HLL_HASH_STATE`], the same hasher used
- /// by [`Self::add`].
- #[inline]
+ /// Adds a pre-computed hash. Hash must be produced by [`HLL_HASH_STATE`].
+ #[inline(always)]
pub(crate) fn add_hashed(&mut self, hash: u64) {
- let index = (hash & HLL_P_MASK) as usize;
- let p = ((hash >> HLL_P) | (1_u64 << HLL_Q)).trailing_zeros() + 1;
- self.registers[index] = self.registers[index].max(p as u8);
+ let index = (hash & self.p_mask) as usize;
+ let rho = ((hash >> self.p) | (1_u64 << self.q)).trailing_zeros() + 1;
+ self.registers[index] = self.registers[index].max(rho as u8);
+ }
+
+ /// Adds a slice of pre-computed hashes. Hashes must use [`HLL_HASH_STATE`].
+ pub(crate) fn add_hashed_slice(&mut self, hashes: &[u64]) {
+ // Default precision: use module-level constants so LLVM emits immediates.
+ // Other precisions: hoist struct fields outside the loop.
+ if self.p == DEFAULT_HLL_P {
+ for &hash in hashes {
+ let index = (hash & DEFAULT_MASK) as usize;
+ let rho =
+ ((hash >> DEFAULT_HLL_P) | (1_u64 << DEFAULT_Q)).trailing_zeros() + 1;
+ self.registers[index] = self.registers[index].max(rho as u8);
+ }
+ } else {
+ let (p, q, p_mask) = (self.p, self.q, self.p_mask);
+ for &hash in hashes {
+ let index = (hash & p_mask) as usize;
+ let rho = ((hash >> p) | (1_u64 << q)).trailing_zeros() + 1;
+ self.registers[index] = self.registers[index].max(rho as u8);
+ }
+ }
}
- /// Get the register histogram (each value in register index into
- /// the histogram; u32 is enough because we only have 2**14=16384 registers
#[inline]
- fn get_histogram(&self) -> [u32; HLL_Q + 2] {
- let mut histogram = [0; HLL_Q + 2];
- // hopefully this can be unrolled
- for r in self.registers {
- histogram[r as usize] += 1;
+ fn get_histogram(&self) -> [u32; 64 - HLL_P_MIN + 2] {
+ let mut histogram = [0u32; 64 - HLL_P_MIN + 2];
+ for r in &self.registers[..1 << self.p] {
+ histogram[*r as usize] += 1;
}
histogram
}
- /// Merge the other [`HyperLogLog`] into this one
+ /// Merge the other [`HyperLogLog`] into this one.
pub fn merge(&mut self, other: &HyperLogLog<T>) {
- assert!(
- self.registers.len() == other.registers.len(),
- "unexpected got unequal register size, expect {}, got {}",
- self.registers.len(),
- other.registers.len()
+ assert_eq!(
+ self.p, other.p,
+ "cannot merge HLL sketches with different precisions ({} vs {})",
+ self.p, other.p
);
- for i in 0..self.registers.len() {
+ let n = 1 << self.p;
+ for i in 0..n {
self.registers[i] = self.registers[i].max(other.registers[i]);
}
}
/// Guess the number of unique elements seen by the HyperLogLog.
pub fn count(&self) -> usize {
- count_from_histogram(&self.get_histogram())
+ count_from_histogram(&self.get_histogram()[..self.q + 2], self.p)
}
}
-/// Compute `index` and `rho` (register value) for a precomputed hash, exactly as
-/// [`HyperLogLog::add_hashed`] does.
+/// Compute `index` and `rho` (register value) for a precomputed hash at a given
+/// precision, exactly as [`HyperLogLog::add_hashed`] does.
#[inline]
-pub(crate) fn register_for_hash(hash: u64) -> (usize, u8) {
- let index = (hash & HLL_P_MASK) as usize;
- let rho = (((hash >> HLL_P) | (1_u64 << HLL_Q)).trailing_zeros() + 1) as u8;
+pub(crate) fn register_for_hash(hash: u64, p: usize) -> (usize, u8) {
+ let q = 64 - p;
+ let p_mask: u64 = ((1_usize << p) as u64) - 1;
+ let index = (hash & p_mask) as usize;
+ let rho = (((hash >> p) | (1_u64 << q)).trailing_zeros() + 1) as u8;
(index, rho)
}
/// Estimate the cardinality of a set of precomputed hashes without
-/// materializing a full [`NUM_REGISTERS`]-byte register array.
+/// materializing a full register array.
///
/// This is equivalent to adding every hash to a fresh [`HyperLogLog`] via
/// [`HyperLogLog::add_hashed`] and calling [`HyperLogLog::count`], but only does
/// work proportional to the number of hashes. It is used to cheaply estimate the
/// many small groups produced by a high-cardinality `GROUP BY`, where allocating
-/// and scanning a 16 KiB sketch per group would dominate the runtime.
+/// and scanning a sketch per group would dominate the runtime.
///
/// `hashes` may contain duplicates (duplicate hashes are idempotent).
-pub(crate) fn count_from_hashes(hashes: &[u64]) -> usize {
+pub(crate) fn count_from_hashes(hashes: &[u64], p: usize) -> usize {
Review Comment:
leaking precision to all internal APIs seem not necessary
probably we can do something like
```
enum GroupHllBuffer {
/// Distinct hashes seen so far. May contain duplicates between compactions.
Sparse(Vec<u64>),
Dense(Box<HyperLogLog<u8>>),
}
struct GroupHLL {
hll_buffer: GroupHLLBuffer,
p: usize,
}
```
and move all the implementation to the new struct
##########
datafusion/functions-aggregate/src/hyperloglog.rs:
##########
@@ -70,107 +80,174 @@ impl<T> HyperLogLog<T>
where
T: Hash + ?Sized,
{
- /// Creates a new, empty HyperLogLog.
+ /// Creates a new, empty HyperLogLog with the default precision (14).
pub fn new() -> Self {
- let registers = [0; NUM_REGISTERS];
- Self::new_with_registers(registers)
+ Self::with_precision(DEFAULT_HLL_P)
}
- /// Creates a HyperLogLog from already populated registers
- /// note that this method should not be invoked in untrusted environment
- /// because the internal structure of registers are not examined.
- pub(crate) fn new_with_registers(registers: [u8; NUM_REGISTERS]) -> Self {
+ /// Creates a new, empty HyperLogLog with the given precision `p`.
+ ///
+ /// The number of registers is `2^p`. Supported range: `HLL_P_MIN..=DEFAULT_HLL_P`.
+ #[inline(always)]
+ pub fn with_precision(p: usize) -> Self {
+ assert!(
+ (HLL_P_MIN..=DEFAULT_HLL_P).contains(&p),
+ "HLL precision must be in {HLL_P_MIN}..={DEFAULT_HLL_P}, got {p}",
+ );
+ let q = 64 - p;
+ let p_mask = ((1_usize << p) as u64) - 1;
Self {
- registers,
+ p,
+ q,
+ p_mask,
+ phantom: PhantomData,
+ registers: [0u8; 1 << DEFAULT_HLL_P],
+ }
+ }
+
+ /// Creates a HyperLogLog from already populated registers.
+ ///
+ /// The precision is inferred from the register slice length, which must be
+ /// a power of two in the range `2^HLL_P_MIN..=2^DEFAULT_HLL_P`.
+ ///
+ /// Note that this method should not be invoked in an untrusted environment
+ /// because the internal structure of registers is not examined.
+ pub(crate) fn from_registers(v: &[u8]) -> Self {
+ let len = v.len();
+ assert!(
+ len.is_power_of_two(),
+ "register slice length must be a power of two, got {len}",
+ );
+ let p = len.ilog2() as usize;
+ assert!(
+ (HLL_P_MIN..=DEFAULT_HLL_P).contains(&p),
+ "inferred precision {p} is outside {HLL_P_MIN}..={DEFAULT_HLL_P}",
+ );
+ let q = 64 - p;
+ let p_mask = (len as u64) - 1;
+ let mut registers = [0u8; 1 << DEFAULT_HLL_P];
+ registers[..len].copy_from_slice(v);
+ Self {
+ p,
+ q,
+ p_mask,
phantom: PhantomData,
+ registers,
}
}
- /// The HLL hash state is shared through `datafusion_common::hash_utils`
- /// so sketches remain compatible across accumulators.
+ /// The precision of this sketch.
#[inline]
- fn hash_value(&self, obj: &T) -> u64 {
- HLL_HASH_STATE.hash_one(obj)
+ pub(crate) fn precision(&self) -> usize {
+ self.p
+ }
+
+ /// Heap bytes used by the register buffer (not captured by `size_of_val`).
+ /// Always 0 — registers are stored inline in the struct.
+ pub(crate) fn register_heap_size(&self) -> usize {
+ 0
}
/// Adds an element to the HyperLogLog.
+ #[cfg(test)]
pub fn add(&mut self, obj: &T) {
- let hash = self.hash_value(obj);
+ let hash = HLL_HASH_STATE.hash_one(obj);
self.add_hashed(hash);
}
- /// Adds a pre-computed hash value directly to the HyperLogLog.
- ///
- /// The hash should be computed using [`HLL_HASH_STATE`], the same hasher used
- /// by [`Self::add`].
- #[inline]
+ /// Adds a pre-computed hash. Hash must be produced by [`HLL_HASH_STATE`].
+ #[inline(always)]
pub(crate) fn add_hashed(&mut self, hash: u64) {
- let index = (hash & HLL_P_MASK) as usize;
- let p = ((hash >> HLL_P) | (1_u64 << HLL_Q)).trailing_zeros() + 1;
- self.registers[index] = self.registers[index].max(p as u8);
+ let index = (hash & self.p_mask) as usize;
+ let rho = ((hash >> self.p) | (1_u64 << self.q)).trailing_zeros() + 1;
+ self.registers[index] = self.registers[index].max(rho as u8);
+ }
+
+ /// Adds a slice of pre-computed hashes. Hashes must use [`HLL_HASH_STATE`].
+ pub(crate) fn add_hashed_slice(&mut self, hashes: &[u64]) {
Review Comment:
I think small micro-bench regression is acceptable if we want additional feature, this performance hack is unnecessary, could we remove that to make the implementation simpler?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3761999571
##########
datafusion/functions-aggregate/src/approx_distinct.rs:
##########
@@ -654,14 +707,35 @@ impl Default for ApproxDistinct {
#[derive(PartialEq, Eq, Hash)]
pub struct ApproxDistinct {
signature: Signature,
+ /// HLL register precision. Only used for types that take the HLL code path
+ /// (i.e. not Boolean / small-int types, which use exact bitmap counting).
+ hll_precision: usize,
}
impl ApproxDistinct {
pub fn new() -> Self {
Self {
signature: Signature::any(1, Volatility::Immutable),
+ hll_precision: DEFAULT_HLL_P,
}
}
+
+ /// Creates an `ApproxDistinct` that uses HLL sketches with `2^p` registers.
+ ///
+ /// This only has effect for types that use the HLL accumulator path. Small
+ /// integer and boolean types use exact bitmap counting regardless of this
+ /// value. Valid range: `HLL_P_MIN..=HLL_P_MAX` (4..=18).
+ pub fn with_hll_precision(p: usize) -> Result<Self> {
Review Comment:
Makes sense, we can carve out a new issue to address this as a follow-up just to keep this PR contained. Is that okay?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "sandeshkr419 (via GitHub)" <gi...@apache.org>.
sandeshkr419 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3677586866
##########
datafusion/functions-aggregate/src/approx_distinct.rs:
##########
@@ -336,13 +367,14 @@ impl GroupHll {
/// Merge a serialized state (produced by [`Self::serialize`] or by the
/// per-group [`Accumulator`]) into this sketch.
- fn merge_serialized(&mut self, bytes: &[u8]) -> Result<isize> {
+ fn merge_serialized(&mut self, bytes: &[u8], p: usize) -> Result<isize> {
if bytes.is_empty() {
return Ok(0);
}
- if bytes.len() == NUM_REGISTERS {
+ let num_registers = 1_usize << p;
+ if bytes.len() == num_registers {
Review Comment:
Fixed now, serialize now promotes to dense whenever the sparse byte length would equal `1 << p`, avoiding the ambiguity; added roundtrip regression tests at both collision points (p=4 with 2 hashes, p=10 with 128 hashes).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5130172551
@sandeshkr419
Please correct the clippy, fmt errors.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5200111213
> ```
> group HEAD hll-precision-param
> ----- ---- -------------------
> approx_distinct decimal128 1.00 14.5±0.02µs ? ?/sec 1.12 16.3±0.01µs ? ?/sec
> approx_distinct decimal256 1.00 18.1±0.03µs ? ?/sec 1.23 22.3±0.02µs ? ?/sec
> approx_distinct decimal32 1.00 12.9±0.01µs ? ?/sec 1.08 14.0±0.01µs ? ?/sec
> approx_distinct decimal64 1.00 12.9±0.01µs ? ?/sec 1.09 14.1±0.02µs ? ?/sec
> approx_distinct i16 bitmap 1.23 8.7±0.01µs ? ?/sec 1.00 7.1±0.44µs ? ?/sec
> approx_distinct i64 80% distinct 1.00 12.8±0.01µs ? ?/sec 1.10 14.0±0.02µs ? ?/sec
> approx_distinct i64 99% distinct 1.00 12.9±0.01µs ? ?/sec 1.09 14.1±0.02µs ? ?/sec
> approx_distinct i8 bitmap 1.00 4.3±0.04µs ? ?/sec 1.01 4.4±0.01µs ? ?/sec
> approx_distinct interval day_time 80% distinct 1.00 13.0±0.03µs ? ?/sec 1.08 14.1±0.03µs ? ?/sec
> approx_distinct interval day_time 99% distinct 1.00 12.9±0.03µs ? ?/sec 1.09 14.1±0.01µs ? ?/sec
> approx_distinct interval month_day_nano 80% distinct 1.00 13.9±0.01µs ? ?/sec 1.20 16.6±0.01µs ? ?/sec
> approx_distinct interval month_day_nano 99% distinct 1.00 13.9±0.01µs ? ?/sec 1.20 16.7±0.03µs ? ?/sec
> approx_distinct interval year_month 80% distinct 1.00 12.9±0.03µs ? ?/sec 1.09 14.0±0.01µs ? ?/sec
> approx_distinct interval year_month 99% distinct 1.00 12.8±0.01µs ? ?/sec 1.09 14.0±0.03µs ? ?/sec
> approx_distinct u16 bitmap 1.00 5.9±0.00µs ? ?/sec 1.46 8.6±0.01µs ? ?/sec
> approx_distinct u8 bitmap 1.00 4.4±0.01µs ? ?/sec 1.01 4.4±0.01µs ? ?/sec
> approx_distinct utf8 long 80% distinct 1.00 33.7±0.02µs ? ?/sec 1.00 33.7±0.07µs ? ?/sec
> approx_distinct utf8 long 99% distinct 1.00 33.7±0.02µs ? ?/sec 1.00 33.5±0.04µs ? ?/sec
> approx_distinct utf8 short 80% distinct 1.00 24.0±0.01µs ? ?/sec 1.02 24.4±0.02µs ? ?/sec
> approx_distinct utf8 short 99% distinct 1.00 23.9±0.13µs ? ?/sec 1.02 24.3±0.01µs ? ?/sec
> approx_distinct utf8view long 80% distinct 1.00 40.5±0.02µs ? ?/sec 1.00 40.7±0.03µs ? ?/sec
> approx_distinct utf8view long 99% distinct 1.00 40.6±0.02µs ? ?/sec 1.00 40.6±0.03µs ? ?/sec
> approx_distinct utf8view short 80% distinct 1.00 16.2±0.03µs ? ?/sec 1.02 16.6±0.03µs ? ?/sec
> approx_distinct utf8view short 99% distinct 1.00 16.6±0.01µs ? ?/sec 1.00 16.6±0.04µs ? ?/sec
> approx_distinct_grouped/Decimal128(10, 2) 50000 groups 1.00 30.3±0.41ms ? ?/sec 1.00 30.4±0.38ms ? ?/sec
> approx_distinct_grouped/Decimal256(40, 2) 50000 groups 1.00 30.6±0.53ms ? ?/sec 1.03 31.5±0.43ms ? ?/sec
> approx_distinct_grouped/Decimal32(9, 2) 50000 groups 1.00 28.9±0.34ms ? ?/sec 1.05 30.3±0.34ms ? ?/sec
> approx_distinct_grouped/Decimal64(18, 2) 50000 groups 1.00 29.3±0.25ms ? ?/sec 1.03 30.2±0.34ms ? ?/sec
> approx_distinct_grouped/Int64 50000 groups 1.00 29.2±0.28ms ? ?/sec 1.05 30.5±0.35ms ? ?/sec
> approx_distinct_grouped/Interval(DayTime) 50000 groups 1.00 28.9±1.05ms ? ?/sec 1.06 30.5±0.88ms ? ?/sec
> approx_distinct_grouped/Interval(MonthDayNano) 50000 groups 1.00 29.8±0.36ms ? ?/sec 1.04 31.0±0.39ms ? ?/sec
> approx_distinct_grouped/Interval(YearMonth) 50000 groups 1.00 29.9±0.49ms ? ?/sec 1.00 29.9±0.49ms ? ?/sec
> approx_distinct_grouped/Utf8 50000 groups 1.00 29.3±0.29ms ? ?/sec 1.06 31.0±0.40ms ? ?/sec
> approx_distinct_grouped/Utf8View 50000 groups 1.00 29.4±0.40ms ? ?/sec 1.05 30.8±0.40ms ? ?/sec
> ```
Some workloads are getting slower 🤔 It would be great to figure out the reason, and see if we can avoid that.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(functions-aggregate): make approx_distinct HLL precision configurable [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#issuecomment-5199972189
run benchmark approx_distinct
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org