citusdata / citusdata/postgresql-hll

Cardinality is coming off by 2 percent (o_log2m=17, o_regwidth=5, o_expthresh=-1,o_sparseon=1)

Open
#60 0 comments 0 reactions 0 assignees View on GitHub
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)
![user count issue](https://user-images.githubusercontent.com/23697630/45690846-ee18c000-bb74-11e8-81f7-b06e71fc1e3f.png)

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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.