You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@flink.apache.org by "Jim Hughes (Jira)" <ji...@apache.org> on 2026/04/03 17:46:00 UTC
[jira] [Created] (FLINK-39399) Integer overflow in HyperLogLogPlusPlus.query() causes APPROX_COUNT_DISTINCT undercount at high cardinality
Jim Hughes created FLINK-39399:
----------------------------------
Summary: Integer overflow in HyperLogLogPlusPlus.query() causes APPROX_COUNT_DISTINCT undercount at high cardinality
Key: FLINK-39399
URL: https://issues.apache.org/jira/browse/FLINK-39399
Project: Flink
Issue Type: Bug
Components: Table SQL / Runtime
Reporter: Jim Hughes
APPROX_COUNT_DISTINCT produce incorrect (undercounted) results when the true cardinality exceeds ~100 million distinct values.
The root cause is an integer overflow in HyperLogLogPlusPlus.query(). In HyperLogLogPlusPlus.java line 4950:
{code:java}
zInverse += 1.0 / (1 << mIdx);
{code}
mIdx is the per-register value representing the position of the leading 1-bit in a hash. At high cardinality, some registers accumulate values >= 32. Because 1 is an int, Java's << operator masks the shift count modulo 32, so 1 << 35 silently evaluates to 1 << 3 = 8 instead of the correct 34359738368. This corrupts the zInverse accumulator and produces a dramatically wrong cardinality estimate.
*Fix:*
Change 1 << mIdx to 1L << mIdx so the shift uses long arithmetic (modulo 64, which is sufficient since register values max out around 51 for a 64-bit hash).
{code:java}
zInverse += 1.0 / (1L << mIdx);
{code}
*How to reproduce:*
Construct an HLL buffer where every register holds a value >= 32 (e.g., 35) and call query(). With the bug, the estimate is ~95K. With the fix, the estimate correctly reflects the large register values (~4e14). Alternatively, run APPROX_COUNT_DISTINCT over ~120M+ distinct values and observe the estimate is orders of magnitude too low.
(Diagnosed and generated with Claude code.)
--
This message was sent by Atlassian Jira
(v8.20.10#820010)