Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Off-by-one bug in calculation of zeros in SparseHll::toDense #42

Closed
mbasmanova opened this issue Jun 9, 2021 · 2 comments
Closed

Off-by-one bug in calculation of zeros in SparseHll::toDense #42

mbasmanova opened this issue Jun 9, 2021 · 2 comments

Comments

@mbasmanova
Copy link

I noticed a bug in SparseHll::toDense while porting HLL algorithm to C++.

https://github.com/airlift/airlift/blob/master/stats/src/main/java/io/airlift/stats/cardinality/SparseHll.java#L175

Here, decodeBucketValue has the number of zeros + 1, hence, the +1 in listener.visit(bucket, zeros + 1); will add an extra one.

See airlift#926

CC: @arhimondr @rongrong @tdcmeehan @highker
@rongrong
Copy link

rongrong commented Jun 9, 2021

Do we understand the implications of this in correctness in production?

@jonhehir jonhehir mentioned this issue Jun 17, 2022
Open
jonhehir added a commit to jonhehir/airlift that referenced this issue Jun 24, 2022
@jonhehir
Add unit tests to clarify HLL behavior
6620234 
This commit makes no functional changes and only adds tests. Beyond merely improving test
coverage, this commit serves as partial documentation of one minor (but surprising) edge case
(issue to be filed) and as verification of behavior that was contested in prestodb#42.
@jonhehir jonhehir mentioned this issue Jun 24, 2022
Merged
jonhehir added a commit to jonhehir/airlift that referenced this issue Jun 24, 2022
@jonhehir
Add unit tests to clarify HLL behavior
e69eccd 
This commit makes no functional changes and only adds tests. Beyond merely improving test
coverage, this commit serves as partial documentation of one minor (but surprising) edge case
(prestodb#56) and as verification of behavior that was contested in prestodb#42.
@jonhehir
Copy link

Per the unit tests in #55, it seems the correct values are being recorded.

highker pushed a commit that referenced this issue Jun 26, 2022
@jonhehir @highker
Add unit tests to clarify HLL behavior
5adf282 
This commit makes no functional changes and only adds tests. Beyond merely improving test
coverage, this commit serves as partial documentation of one minor (but surprising) edge case
(#56) and as verification of behavior that was contested in #42.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@jonhehir @rongrong @mbasmanova