A low-privilege implementation of hyperloglog for django and postgres
Project description
django_pg_simple_hll
Postgres-only HyperLogLog cardinality aggregation for the Django ORM.
Instead of counting the number of distinct users,
%%time
Session.objects.aggregate(unique_users=Count("user_uuid", distinct=True))
CPU times: user 864 µs, sys: 2.46 ms, total: 3.32 ms
Wall time: 461 ms
{'unique_users': 140000}
you can approximate it,
%%time
Session.objects.aggregate(approx_unique_users=HLLCardinality("user_uuid"))
CPU times: user 480 µs, sys: 1.54 ms, total: 2.02 ms
Wall time: 845 ms
{'approx_unique_users': 144594}
Or, instead of counting the number of distinct users per day,
%%time
list(
Session.objects
.annotate(date_of_session=TruncDate("created"))
.values("date_of_session")
.annotate(unique_users=Count("user_uuid", distinct=True))
.values("unique_users", "date_of_session")
.order_by("date_of_session")
)
CPU times: user 1.47 ms, sys: 3.16 ms, total: 4.64 ms
Wall time: 758 ms
[{'date_of_session': datetime.date(2023, 4, 28), 'unique_users': 20000},
{'date_of_session': datetime.date(2023, 4, 29), 'unique_users': 40000},
{'date_of_session': datetime.date(2023, 4, 30), 'unique_users': 60000},
{'date_of_session': datetime.date(2023, 5, 1), 'unique_users': 80000},
{'date_of_session': datetime.date(2023, 5, 2), 'unique_users': 100000},
{'date_of_session': datetime.date(2023, 5, 3), 'unique_users': 120000},
{'date_of_session': datetime.date(2023, 5, 4), 'unique_users': 140000}]
you can approximate it,
%%time
list(
Session.objects
.annotate(date_of_session=TruncDate("created"))
.values("date_of_session")
.annotate(approx_unique_users=HLLCardinality("user_uuid"))
.values("approx_unique_users", "date_of_session")
.order_by("date_of_session")
)
CPU times: user 1.53 ms, sys: 3.57 ms, total: 5.1 ms
Wall time: 838 ms
[{'date_of_session': datetime.date(2023, 4, 28), 'approx_unique_users': 19322},
{'date_of_session': datetime.date(2023, 4, 29), 'approx_unique_users': 39356},
{'date_of_session': datetime.date(2023, 4, 30), 'approx_unique_users': 61202},
{'date_of_session': datetime.date(2023, 5, 1), 'approx_unique_users': 80917},
{'date_of_session': datetime.date(2023, 5, 2), 'approx_unique_users': 102914},
{'date_of_session': datetime.date(2023, 5, 3), 'approx_unique_users': 125637},
{'date_of_session': datetime.date(2023, 5, 4), 'approx_unique_users': 144594}]
The approximation is sometimes faster and uses less memory, particularly when faceting by other variables.
By default, it uses a precision of 9, which tends to have an error of about 5%. You can set a higher precision (up to 26) through a second parameter:
%%time
list(
Session.objects
.annotate(date_of_session=TruncDate("created"))
.values("date_of_session")
.annotate(approx_unique_users=HLLCardinality("user_uuid", 11))
.values("approx_unique_users", "date_of_session")
.order_by("date_of_session")
)
CPU times: user 1.71 ms, sys: 3.82 ms, total: 5.53 ms
Wall time: 1.98 s
[{'date_of_session': datetime.date(2023, 4, 28), 'approx_unique_users': 20013},
{'date_of_session': datetime.date(2023, 4, 29), 'approx_unique_users': 39616},
{'date_of_session': datetime.date(2023, 4, 30), 'approx_unique_users': 59312},
{'date_of_session': datetime.date(2023, 5, 1), 'approx_unique_users': 81278},
{'date_of_session': datetime.date(2023, 5, 2), 'approx_unique_users': 101880},
{'date_of_session': datetime.date(2023, 5, 3), 'approx_unique_users': 122343},
{'date_of_session': datetime.date(2023, 5, 4), 'approx_unique_users': 141375}]
You can also set a lower precision (down to 4) for a faster, less accurate estimate.
%%time
list(
Session.objects
.annotate(date_of_session=TruncDate("created"))
.values("date_of_session")
.annotate(approx_unique_users=HLLCardinality("user_uuid", 7))
.values("approx_unique_users", "date_of_session")
.order_by("date_of_session")
)
CPU times: user 1.3 ms, sys: 2.85 ms, total: 4.15 ms
Wall time: 547 ms
[{'date_of_session': datetime.date(2023, 4, 28), 'approx_unique_users': 19363},
{'date_of_session': datetime.date(2023, 4, 29), 'approx_unique_users': 40627},
{'date_of_session': datetime.date(2023, 4, 30), 'approx_unique_users': 63159},
{'date_of_session': datetime.date(2023, 5, 1), 'approx_unique_users': 83371},
{'date_of_session': datetime.date(2023, 5, 2), 'approx_unique_users': 96185},
{'date_of_session': datetime.date(2023, 5, 3), 'approx_unique_users': 116565},
{'date_of_session': datetime.date(2023, 5, 4), 'approx_unique_users': 143588}]
HLL works by hashing each value it considers. For some reason, the aggregation is sometimes faster when that hashing is performed outside of the aggregation. So, it is also available in two separate steps:
%%time
list(
Session.objects
.annotate(date_of_session=TruncDate("created"))
.values("date_of_session")
.annotate(approx_unique_users=HLLCardinalityFromHash(HLLHash("user_uuid"), 9))
.values("approx_unique_users", "date_of_session")
.order_by("date_of_session")
)
CPU times: user 1.66 ms, sys: 1.23 ms, total: 2.89 ms
Wall time: 662 ms
[{'date_of_session': datetime.date(2023, 6, 2), 'approx_unique_users': 19322},
{'date_of_session': datetime.date(2023, 6, 3), 'approx_unique_users': 39356},
{'date_of_session': datetime.date(2023, 6, 4), 'approx_unique_users': 61202},
{'date_of_session': datetime.date(2023, 6, 5), 'approx_unique_users': 80917},
{'date_of_session': datetime.date(2023, 6, 6), 'approx_unique_users': 102914},
{'date_of_session': datetime.date(2023, 6, 7), 'approx_unique_users': 125637},
{'date_of_session': datetime.date(2023, 6, 8), 'approx_unique_users': 144594}]
The aggregation is also available in SQL for analytics:
select
date_trunc('day', created) as date_of_session,
hll_cardinality(user_uuid, 11) as approx_unique_users
from
testapp_session
group by
date_trunc('day', created)
order by date_of_session;
date_of_session | approx_unique_users
------------------------+---------------------
2023-04-28 00:00:00+00 | 20013
2023-04-29 00:00:00+00 | 39616
2023-04-30 00:00:00+00 | 59312
2023-05-01 00:00:00+00 | 81278
2023-05-02 00:00:00+00 | 101880
2023-05-03 00:00:00+00 | 122343
2023-05-04 00:00:00+00 | 141375
(7 rows)
Time: 2121.662 ms (00:02.122)
or
select
date_trunc('day', created) as date_of_session,
hll_cardinality_from_hash(hll_hash(user_uuid), 11) as approx_unique_users
from
testapp_session
group by
date_trunc('day', created)
order by date_of_session;
date_of_session | approx_unique_users
------------------------+---------------------
2023-06-02 00:00:00+00 | 20013
2023-06-03 00:00:00+00 | 39616
2023-06-04 00:00:00+00 | 59312
2023-06-05 00:00:00+00 | 81278
2023-06-06 00:00:00+00 | 101880
2023-06-07 00:00:00+00 | 122343
2023-06-08 00:00:00+00 | 141375
(7 rows)
Time: 1810.445 ms (00:01.810)
How to use
Install the package:
pip install django-pg-simple-hll
Add it to your Django INSTALLED_APPS
:
INSTALLED_APPS = [
...
"django_pg_simple_hll",
...
]
Run migrations
django-admin migrate django_pg_simple_hll
Should I use this?
If you can use an optimised version, you should use that. It will be faster - although I haven't done any benchmarks.
Use this if you can't install extensions on your database, such as on Amazon RDS.
SQL only
Don't care about the Django functions, and just want to be able to run the SQL? The entire implementation is in a single SQL file
Notes on SQL implementation
This is a low-privilege implementation of Hyperloglog approximate cardinality aggregation written in SQL and some PL/pgSQL. Read about it here,
Notes on Performance
This is not a scientific test, but here is an example of performance running on an M1 MacBook Pro, running Postgres 15 in Docker.
For a dataset of 560k rows and 140k unique values a precision of 8 matches the speed of COUNT(DISTINCT ...)
:
select count(user_uuid) from testapp_session;
count
--------
560000
(1 row)
Time: 227.959 ms
select count(distinct user_uuid) as unique_users from testapp_session;
unique_users
--------------
140000
(1 row)
Time: 476.819 ms
select hll_cardinality_from_hash(hll_hash(user_uuid), 8) as approx_unique_users from testapp_session;
approx_unique_users
---------------------
139309
(1 row)
Time: 402.569 ms
select hll_cardinality_from_hash(hll_hash(user_uuid), 11) as approx_unique_users from testapp_session;
approx_unique_users
---------------------
141375
(1 row)
Time: 1193.696 ms (00:01.194)
For a dataset of 5.6M rows and 1.4M unique values:
- with a precision of 7,
hll_aggregate
runs in about 0.81x the speed ofCOUNT(DISTINCT ...)
- with a precision of 8, it roughly matches (0.94x)
- with a precision of 11, it runs in about 2.4x
select count(user_uuid) from testapp_session;
count
---------
5600000
(1 row)
Time: 3798.774 ms (00:03.799)
select count(distinct user_uuid) as unique_users from testapp_session;
unique_users
--------------
1400000
(1 row)
Time: 4564.531 ms (00:04.565)
select hll_cardinality_from_hash(hll_hash(user_uuid), 7) as approx_unique_users from testapp_session;
approx_unique_users
---------------------
1308235
(1 row)
Time: 3710.460 ms (00:03.710)
select hll_cardinality_from_hash(hll_hash(user_uuid), 8) as approx_unique_users from testapp_session;
approx_unique_users
---------------------
1407331
(1 row)
Time: 4382.913 ms (00:04.383)
select hll_cardinality_from_hash(hll_hash(user_uuid), 11) as approx_unique_users from testapp_session;
approx_unique_users
---------------------
1390983
(1 row)
Time: 11027.942 ms (00:11.028)
For a dataset of 56M rows and 14M unique values:
- with a precision of 8,
hll_aggregate
runs in about 0.48x the speed ofCOUNT(DISTINCT ...)
- with a precision of 9, it runs in about 0.63x
- with a precision of 10, it runs in about 0.73x
- with a precision of 11, it runs in about 1.07x
select count(user_uuid) from testapp_session;
count
----------
56000000
(1 row)
Time: 45861.085 ms (00:45.861)
select count(distinct user_uuid) as unique_users from testapp_session;
unique_users
--------------
14000000
(1 row)
Time: 119551.361 ms (01:59.551)
select hll_cardinality_from_hash(hll_hash(user_uuid), 8) as approx_unique_users from testapp_session;
approx_unique_users
---------------------
13469591
(1 row)
Time: 58370.988 ms (00:58.371)
select hll_cardinality_from_hash(hll_hash(user_uuid), 9) as approx_unique_users from testapp_session;
approx_unique_users
---------------------
13028181
(1 row)
Time: 75231.592 ms (01:15.232)
select hll_cardinality_from_hash(hll_hash(user_uuid), 10) as approx_unique_users from testapp_session;
approx_unique_users
---------------------
13147406
(1 row)
Time: 87497.737 ms (01:27.498)
select hll_cardinality_from_hash(hll_hash(user_uuid), 11) as approx_unique_users from testapp_session;
approx_unique_users
---------------------
13363203
(1 row)
Time: 128338.223 ms (02:08.338)
The real advantage though is in combination with other properties:
E.g. this query runs 0.37x quicker if using hll_aggregate
than with COUNT(DISTINCT ...)
:
select
date_trunc('day', created) as date_of_session,
count(distinct user_uuid) as unique_users
from testapp_session
group by
date_trunc('day', created)
order by
date_of_session;
date_of_session | unique_users
------------------------+--------------
2023-06-02 00:00:00+00 | 2000000
2023-06-03 00:00:00+00 | 4000000
2023-06-04 00:00:00+00 | 6000000
2023-06-05 00:00:00+00 | 8000000
2023-06-06 00:00:00+00 | 10000000
2023-06-07 00:00:00+00 | 12000000
2023-06-08 00:00:00+00 | 14000000
(7 rows)
Time: 157028.067 ms (02:37.028)
select
date_trunc('day', created) as date_of_session,
hll_cardinality_from_hash(hll_hash(user_uuid), 9) as unique_users
from
testapp_session
group by
date_trunc('day', created)
order by
date_of_session;
date_of_session | unique_users
------------------------+--------------
2023-06-02 00:00:00+00 | 1963972
2023-06-03 00:00:00+00 | 4096876
2023-06-04 00:00:00+00 | 5869339
2023-06-05 00:00:00+00 | 7412843
2023-06-06 00:00:00+00 | 9401010
2023-06-07 00:00:00+00 | 11443836
2023-06-08 00:00:00+00 | 13028181
(7 rows)
Time: 58778.194 ms (00:58.778)
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for django_pg_simple_hll-0.3.0.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | c22177557167a4ede99b65cf586aa7989d5a605f756240cfa1488b7af860466d |
|
MD5 | dec069916d4f917dca4bc6775b1f3f4e |
|
BLAKE2b-256 | 496fd30dcbe04d4a1b37055be3cd5fd3137366de778f57001eac6429f96f1f8d |
Hashes for django_pg_simple_hll-0.3.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | eb8e81dc6528e053b7a7050dcb48b11672edc1e5b47df06daf7c13b55830bf26 |
|
MD5 | b0ffdb58bfe6c334d42f40558aa3c2d5 |
|
BLAKE2b-256 | 087367702a2ad86e407d20dbe114e7d903ac5494abffa8e67bf938da6c7829e0 |