asdf2014 opened a new pull request, #19678:
URL: https://github.com/apache/druid/pull/19678
Fixes #19649.
### Description
`HyperLogLogCollector.estimateSparse()` could return a cardinality estimate
of `0` even after the collector had received data. In Hadoop-based ingestion
this surfaces as `DetermineHashedPartitionsJob` reporting `Found approximately
[0] rows in data` and the job failing with `No buckets?? seems there is no data
to index.`, even though the input records were read correctly.
#### Root cause
When an element's `positionOf1` exceeds the 4-bit nibble range
(`registerOffset + RANGE`, i.e. 16 on a fresh collector), its value is kept
only in the global overflow register and no entry is written to the sparse
storage buffer. When that overflow register is the only information the
collector holds — the typical case for a single such element — the sparse
buffer is empty, so the scan in `estimateSparse()` never visits the overflow
register: `zeroCount` stays equal to `NUM_BUCKETS` and the linear-counting
correction evaluates `m * ln(m / m) = 0`.
The pre-existing in-loop handling for the overflow register (the `position
== overflowPosition` branch) only runs when the overflow bucket shares a byte
with a populated sparse entry, so it does not cover the empty-buffer case.
#### Fix
`estimateSparse()` now records whether the overflow register was already
folded into a visited entry. If a non-zero overflow register was not accounted
for during the scan, it is added explicitly: `zeroCount` is decremented by one
(the register is not empty) and `1 / 2^overflowValue` is added to the harmonic
sum, mirroring how the dense path and the in-loop sparse path already handle
the overflow register. Every other case — no overflow, an overflow register
folded into an entry, and the dense path — is unchanged.
#### Release note
Fixed a bug where a `hyperUnique`/HLL sketch built from a very small number
of values could estimate a cardinality of `0` when the only populated register
was the overflow register. This could also cause Hadoop-based ingestion to fail
with `No buckets?? seems there is no data to index.`
<hr>
##### Key changed/added classes in this PR
* `HyperLogLogCollector`
<hr>
This PR has:
- [x] been self-reviewed.
- [x] a release note entry in the PR description.
- [x] added comments explaining the "why" and the intent of the code
wherever would not be obvious for an unfamiliar reader.
- [x] added unit tests or modified existing tests to cover new code paths,
ensuring the threshold for code coverage is met.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
