citusdata / citusdata/postgresql-hll
Cardinality is coming off by 2 percent (o_log2m=17, o_regwidth=5, o_expthresh=-1,o_sparseon=1)
- Dominant language
- C
- Stars
- 1.2k
- Forks
- 115
- PR merge metrics
- No merged PRs in 30d
Description
We are using HLL for calculating unique users in our system, for a day or date range depending on requirement. It worked fine with error percentage of 0.025 to 0.9% (acceptable for our use case), but last week's data is going off by 2%.
Following are the details:
Parameters: o_log2m=17, o_regwidth=5, o_expthresh=-1,o_sparseon=1
Data: User Ids of UUID type, generated by backend written in Golang
Unique count: 328428
Cardinality by HLL: 335881
For one particular day its coming off by 7000(approx)

As you can see from graph, for particular day (14 Sept) unique user for day are going more than total users of the day.
I am attaching CSV file which has list of unique user_ids and total count from our DB table, and we are able to recreate this issue in table(user_debug(id serial, user_id varchar, count int)) created from this CSV.
Query: select count(distinct(user_id)) as user from user_debug;
O/p: 328428
Query: select hll_cardinality(hll_add_agg(hll_hash_text(user_id))) from user_debug;
O/p: 335881
We tried to calculate cardinality per distinct 100000 user_ids in table and results is off by 150-400 by HLL, same goes with range of 150000 distict user_ids.
So we tried to run on different subset of rows and recreated issue with below query:
with a as ((select distinct(user_id) as user from user_debug limit 160000 offset 0) UNION (select distinct(user_id) as user from user_debug limit 160000 offset 168248 ))
select hll_cardinality(hll_add_agg(hll_hash_text(a.user))) from a;
This should have returned close to 320000 as count, but its returning 328345.
We couldn't debug any further, can you check?
CSV is attached.
[user_id.csv.zip](https://github.com/citusdata/postgresql-hll/files/2392915/user_id.csv.zip)
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.