Extensions
 hll 2.10.0
 HyperLogLog data type and algorithm
README
Contents
Overview
This Postgres module introduces a new data type hll
which is a HyperLogLog data structure. HyperLogLog is a fixedsize, setlike structure used for distinct value counting with tunable precision. For example, in 1280 bytes hll
can estimate the count of tens of billions of distinct values with only a few percent error.
In addition to the algorithm proposed in the original paper, this implementation is augmented to improve its accuracy and memory use without sacrificing much speed. See below for more details.
Algorithms
A hll
is a combination of different set/distinctvaluecounting algorithms that can be thought of as a hierarchy, along with rules for moving up that hierarchy. In order to distinguish between said algorithms, we have given them names:
EMPTY
A constant value that denotes the empty set.
EXPLICIT
An explicit, unique, sorted list of integers in the set, which is maintained up to a fixed cardinality.
SPARSE
A 'lazy', mapbased implementation of HyperLogLog, a probabilistic set data structure. Only stores the indices and values of nonzero registers in a map, until the number of nonzero registers exceeds a fixed cardinality.
FULL
A fullymaterialized, listbased implementation of HyperLogLog. Explicitly stores the value of every register in a list ordered by register index.
Motivation
Our motivation for augmenting the original HLL algorithm went something like this:
 Naively, a HLL takes
regwidth * 2^log2m
bits to store.  In typical usage,
log2m = 11
andregwidth = 5
, it requires 10,240 bits or 1,280 bytes.  That's a lot of bytes!
The first addition to the original HLL algorithm came from realizing that 1,280 bytes is the size of 160 64bit integers. So, if we wanted more accuracy at low cardinalities, we could just keep an explicit set of the inputs as a sorted list of 64bit integers until we hit the 161st distinct value. This would give us the true representation of the distinct values in the stream while requiring the same amount of memory. (This is the EXPLICIT
algorithm.)
The second came from the realization that we didn't need to store registers whose value was zero. We could simply represent the set of registers that had nonzero values as a map from index to values. This is map is stored as a list of indexvalue pairs that are bitpacked "short words" of length log2m + regwidth
. (This is the SPARSE
algorithm.)
Combining these two augmentations, we get a "promotion hierarchy" that allows the algorithm to be tuned for better accuracy, memory, or performance.
Initializing and storing a new hll
object will simply allocate a small sentinel value symbolizing the empty set (EMPTY
). When you add the first few values, a sorted list of unique integers is stored in an EXPLICIT
set. When you wish to cease trading off accuracy for memory, the values in the sorted list are "promoted" to a SPARSE
mapbased HyperLogLog structure. Finally, when there are enough registers, the mapbased HLL will be converted to a bitpacked FULL
HLL structure.
Empirically, the insertion rate of EMPTY
, EXPLICIT
, and SPARSE
representations is measured in 200k/s  300k/s range, while the throughput of the FULL
representation is in the millions of inserts per second on relatively new hardware ('10 Xeon).
Naturally, the cardinality estimates of the EMPTY
and EXPLICIT
representations is exact, while the SPARSE
and FULL
representations' accuracies are governed by the guarantees provided by the original HLL algorithm.
Usage
"Hello World"
 Make a dummy table
CREATE TABLE helloworld (
id integer,
set hll
);
 Insert an empty HLL
INSERT INTO helloworld(id, set) VALUES (1, hll_empty());
 Add a hashed integer to the HLL
UPDATE helloworld SET set = hll_add(set, hll_hash_integer(12345)) WHERE id = 1;
 Or add a hashed string to the HLL
UPDATE helloworld SET set = hll_add(set, hll_hash_text('hello world')) WHERE id = 1;
 Get the cardinality of the HLL
SELECT hll_cardinality(set) FROM helloworld WHERE id = 1;
Now with the silly stuff out of the way, here's a more realistic use case.
Data Warehouse Use Case
Let's assume I've got a fact table that records users' visits to my site, what they did, and where they came from. It's got hundreds of millions of rows. Table scans take minutes (or at least lots and lots of seconds.)
CREATE TABLE facts (
date date,
user_id integer,
activity_type smallint,
referrer varchar(255)
);
I'd really like a quick (milliseconds) idea of how many unique users are visiting per day for my dashboard. No problem, let's set up an aggregate table:
 Create the destination table
CREATE TABLE daily_uniques (
date date UNIQUE,
users hll
);
 Fill it with the aggregated unique statistics
INSERT INTO daily_uniques(date, users)
SELECT date, hll_add_agg(hll_hash_integer(user_id))
FROM facts
GROUP BY 1;
We're first hashing the user_id
, then aggregating those hashed values into one hll
per day. Now we can ask for the cardinality of the hll
for each day:
SELECT date, hll_cardinality(users) FROM daily_uniques;
You're probably thinking, "But I could have done this with COUNT DISTINCT
!" And you're right, you could have. But then you only ever answer a single question: "How many unique users did I see each day?"
What if you wanted to this week's uniques?
SELECT hll_cardinality(hll_union_agg(users)) FROM daily_uniques WHERE date >= '20120102'::date AND date <= '20120108'::date;
Or the monthly uniques for this year?
SELECT EXTRACT(MONTH FROM date) AS month, hll_cardinality(hll_union_agg(users))
FROM daily_uniques
WHERE date >= '20120101' AND
date < '20130101'
GROUP BY 1;
Or how about a sliding window of uniques over the past 6 days?
SELECT date, #hll_union_agg(users) OVER seven_days
FROM daily_uniques
WINDOW seven_days AS (ORDER BY date ASC ROWS 6 PRECEDING);
Or the number of uniques you saw yesterday that you didn't see today?
SELECT date, (#hll_union_agg(users) OVER two_days)  #users AS lost_uniques
FROM daily_uniques
WINDOW two_days AS (ORDER BY date ASC ROWS 1 PRECEDING);
These are just a few examples of the types of queries that would return in milliseconds in an hll
world from a single aggregate, but would require either completely separate prebuilt aggregates or selfjoins or generate_series
trickery in a COUNT DISTINCT
world.
Operators
We've added a few operators to make using hll
s less cumbersome/verbose. They're simple aliases for the most commonly used functions.
Function  Operator  Example 

hll_add 
 
hll_add(users, hll_hash_integer(123)) or users  hll_hash_integer(123) or hll_hash_integer(123)  users

hll_cardinality 
# 
hll_cardinality(users) or #users

hll_union 
 
hll_union(male_users, female_users) or male_users  female_users or female_users  male_users

Hashing
You'll notice that all the calls to hll_add
or 
involve wrapping the input value in a hll_hash_[type]
call; it's aboslutely crucial that you hash your input values to hll
structures. For more on this, see the section below titled 'The Importance of Hashing'.
The hashing functions we've made available are listed below:
Function  Input  Example 

hll_hash_boolean 
boolean 
hll_hash_boolean(TRUE) or hll_hash_boolean(TRUE, 123/*hash seed*/)

hll_hash_smallint 
smallint 
hll_hash_smallint(4) or hll_hash_smallint(4, 123/*hash seed*/)

hll_hash_integer 
integer 
hll_hash_integer(21474836) or hll_hash_integer(21474836, 123/*hash seed*/)

hll_hash_bigint 
bigint 
hll_hash_bigint(223372036854775808) or hll_hash_bigint(223372036854775808, 123/*hash seed*/)

hll_hash_bytea 
bytea 
hll_hash_bytea(E'\\xDEADBEEF') or hll_hash_bytea(E'\\xDEADBEEF', 123/*hash seed*/)

hll_hash_text 
text 
hll_hash_text('foobar') or hll_hash_text('foobar', 123/*hash seed*/)

hll_hash_any 
any 
hll_hash_any(anyval) or hll_hash_any(anyval, 123/*hash seed*/)

NOTE: hll_hash_any
dynamically dispatches to the appropriate typespecific function, which makes it slower than the typespecific ones it wraps. Use it only when the input type is not known beforehand.
So what if you don't want to hash your input?
postgres=# select 1234  hll_empty();
ERROR: operator does not exist: integer  hll
LINE 1: select 1234  hll_empty();
^
HINT: No operator matches the given name and argument type(s). You might need to add explicit type casts.
Not pretty. Since hashing is such a crucial part of the accuracy of HyperLogLog, we decided to "enforce" this at a type level. You can only add hll_hashval
typed things to a hll
, which is what the hll_hash_[type]
functions return. You can simply cast integer values to hll_hashval
to add them without hashing, like so:
postgres=# select 1234::hll_hashval  hll_empty();
?column?

\x128c4900000000000004d2
(1 row)
Aggregate functions
If you want to create a hll
from a table or result set, use hll_add_agg
. The naming here isn't particularly creative: it's an aggregate function that adds the values to an empty hll
.
SELECT date, hll_add_agg(hll_hash_integer(user_id))
FROM facts
GROUP BY 1;
The above example will give you a hll
for each date that contains each day's users.
If you want to summarize a list of hll
s that you already have stored into a single hll
, use hll_union_agg
. Again: it's an aggregate function that unions the values into an empty hll
.
SELECT EXTRACT(MONTH FROM date), hll_cardinality(hll_union_agg(users))
FROM daily_uniques
GROUP BY 1;
Sliding windows are another prime example of the power of hll
s. Doing sliding window unique counting typically involves some generate_series
trickery, but it's quite simple with the hll
s you've already computed for your rollups.
SELECT date, #hll_union_agg(users) OVER seven_days
FROM daily_uniques
WINDOW seven_days AS (ORDER BY date ASC ROWS 6 PRECEDING);
Explanation of Parameters and Tuning
log2m
The logbase2 of the number of registers used in the HyperLogLog algorithm. Must be at least 4 and at most 31. This parameter tunes the accuracy of the HyperLogLog structure. The relative error is given by the expression ±1.04/√(2^{log2m}). Note that increasing log2m
by 1 doubles the required storage for the hll
.
regwidth
The number of bits used per register in the HyperLogLog algorithm. Must be at least 1 and at most 8. This parameter, in conjunction with log2m
, tunes the maximum cardinality of the set whose cardinality can be estimated. For clarity, we've provided a table of regwidth
s and log2m
s and the approximate maximum cardinality that can be estimated with those parameters. (The size of the resulting structure is provided as well.)
logm2  regwidth=1  regwidth=2  regwidth=3  regwidth=4  regwidth=5  regwidth=6 

10  7.4e+02 _{128B}  3.0e+03 _{256B}  4.7e+04 _{384B}  1.2e+07 _{512B}  7.9e+11 _{640B}  3.4e+21 _{768B} 
11  1.5e+03 _{256B}  5.9e+03 _{512B}  9.5e+04 _{768B}  2.4e+07 _{1.0KB}  1.6e+12 _{1.2KB}  6.8e+21 _{1.5KB} 
12  3.0e+03 _{512B}  1.2e+04 _{1.0KB}  1.9e+05 _{1.5KB}  4.8e+07 _{2.0KB}  3.2e+12 _{2.5KB}  1.4e+22 _{3KB} 
13  5.9e+03 _{1.0KB}  2.4e+04 _{2.0KB}  3.8e+05 _{3KB}  9.7e+07 _{4KB}  6.3e+12 _{5KB}  2.7e+22 _{6KB} 
14  1.2e+04 _{2.0KB}  4.7e+04 _{4KB}  7.6e+05 _{6KB}  1.9e+08 _{8KB}  1.3e+13 _{10KB}  5.4e+22 _{12KB} 
15  2.4e+04 _{4KB}  9.5e+04 _{8KB}  1.5e+06 _{12KB}  3.9e+08 _{16KB}  2.5e+13 _{20KB}  1.1e+23 _{24KB} 
16  4.7e+04 _{8KB}  1.9e+05 _{16KB}  3.0e+06 _{24KB}  7.7e+08 _{32KB}  5.1e+13 _{40KB}  2.2e+23 _{48KB} 
17  9.5e+04 _{16KB}  3.8e+05 _{32KB}  6.0e+06 _{48KB}  1.5e+09 _{64KB}  1.0e+14 _{80KB}  4.4e+23 _{96KB} 
expthresh
Tunes when the EXPLICIT
to SPARSE
promotion occurs, based on the set's cardinality. It is also possible to turn off the use of the EXPLICIT
representation entirely. If the EXPLICIT
representation is turned off, the EMPTY
set is promoted directly to SPARSE
. Must be 1, 0, or 118 inclusive.
expthresh value  Meaning 

1  Promote at whatever cutoff makes sense for optimal memory usage. ('auto' mode) 
0  Skip EXPLICIT representation in hierarchy. 
118  Promote at 2^{expthresh  1} cardinality 
You can choose the EXPLICIT
cutoff such that it will end up taking more memory than a FULL
hll
representation. This is allowed for those cases where perfect precision and accuracy are required up through some preset cardinality range, after which estimates of the cardinality are sufficient.
NOTE: The restriction of expthresh
to a maximum value of 18 (for the third case in the table above) is an implementation tradeoff between performance and general appeal. If you want access to higher expthresh
values, let us know in the Issues section and we'll see what we can do.
sparseon
Enables or disables the SPARSE
representation. If both the EXPLICIT
and SPARSE
representations are disabled, an EMPTY
set will be promoted directly to a FULL
set. If SPARSE
is enabled, the promotion from SPARSE
to FULL
will occur when the internal SPARSE
representation's memory footprint would exceed that of the FULL
version. Must be either either 0
(zero) or 1
(one). Zero means disabled, one is enabled.
Defaults
In all the examples above, the type hll
has been used without adornment. This is a shortcut. In reality, the type can have up to 4 arguments. The defaults are shown as well.
hll(log2m=11, regwidth=5, expthresh=1, sparseon=1)
You can provide any prefix of the full list of arguments. The named arguments are the same as those mentioned in the 'Explanation of Parameters' section, above. If you'd like to change these (they're hardcoded in the source) look in hll.c
for DEFAULT_LOG2M
and that should get you there pretty quickly.
Debugging
hll_print
is your friend! It will show you all the parameters of the hll
as well as nicelyformatted representation of the contents.
Compatibility
This module has been tested on:
 Centos 5/6 x86_64
 Postgres 9.0, 9.1, 9.2
 gcc 4.4.6
If you end up needing to change something to get this running on another system, send us the diff and we'll try to work it in!
Build
With rpmbuild
Specify versions:
export VER=2.10.0
export PGSHRT=91
Make sure Makefile
points to the correct pg_config
for the specified version, since rpmbuild
doesn't respect env variables:
PG_CONFIG = /usr/pgsql9.1/bin/pg_config
Create a tarball from the source tree:
tar cvfz postgresql${PGSHRT}hll${VER}.tar.gz postgresqlhll \
transform="s/postgresqlhll/postgresql${PGSHRT}hll/g"
Execute rpmbuild:
rpmbuild tb postgresql${PGSHRT}hll${VER}.tar.gz
Install RPM:
rpm Uv rpmbuild/RPMS/x86_64/postgresql91hll2.10.00.x86_64.rpm
And if you want the debugging build:
rpm Uv rpmbuild/RPMS/x86_64/postgresql91hlldebuginfo2.10.00.x86_64.rpm
From source
If you aren't using the pg_config
on your path (or don't have it on your path), specify the correct one to build against:
PG_CONFIG=/usr/pgsql9.1/bin/pg_config make
Or to build with what's on your path, just:
make
If you're building on OS X with clang
as the default C/C++ compiler, you'll need to specify gcc
as your compiler:
make CC=gcc CXX=gcc
Or for the debug build:
DEBUG=1 make
Then install:
sudo make install
Install
After you've built and installed the artifacts, fire up psql
:
postgres=# CREATE EXTENSION hll;
CREATE EXTENSION
And then just verify it's there:
postgres=# \dx
List of installed extensions
Name  Version  Schema  Description
+++
hll  1.0  public  type for storing hyperloglog data
plpgsql  1.0  pg_catalog  PL/pgSQL procedural language
(2 rows)
Tests
Create the regression database:
psql d postgres
CREATE DATABASE hll_regress;
Create the extension in the created database:
psql d hll_regress
CREATE EXTENSION hll;
Run the regression:
cd regress
make clean
make j5
The Importance of Hashing
In brief, it is absolutely crucial to hash inputs to the hll
. A close approximation of uniform randomness in the inputs ensures that the error guarantees laid out in the original paper hold. In fact, the canonical C++ implementation of MurmurHash 3 is provided in this module to facilitate this input requirement. We've empirically determined that MurmurHash 3 is an excellent and fast hash function to use in conjunction with the hll
module.
The seed to the hash call must remain constant for all inputs to a given hll
. Similarly, if you plan to compute the union of two hll
s, the input values must have been hashed using the same seed.
For a good overview of the importance of hashing and hash functions when using probabilistic algorithms as well as an analysis of MurmurHash 3, see these four blog posts:
 KMinimum Values: Sketching Error, Hash Functions, and You
 Choosing a Good Hash Function, Part 1
 Choosing a Good Hash Function, Part 2
 Choosing a Good Hash Function, Part 3
On Unions and Intersections
hll
s have the useful property that the union of any number of hll
s is equal to the hll
that would have been populated by playing back all inputs to those N hll
s into a single hll
. Colloquially, we say that hll
s have "lossless" unions because the same cardinality error guarantees that apply to a single hll
apply to a union of hll
s. This property combined with Postgres' aggregation functions (sliding window and so on) can power some pretty impressive analytics, like the number of unique visitors in a 30day sliding window over the course of a year. See the hll_union_agg
and hll_union
functions.
Using the inclusionexclusion principle and the union function, you can also estimate the intersection of sets represented by hll
s. Note, however, that error is proportional to the union of the two hll
s, while the result can be significantly smaller than the union, leading to disproportionately large error relative to the actual intersection cardinality. For instance, if one hll
has a cardinality of 1 billion, while the other has a cardinality of 10 million, with an overlap of 5 million, the intersection cardinality can easily be dwarfed by even a 1% error estimate in the larger hll
s cardinality.
For more information on hll
intersections, see this blog post.
Storage formats
hll
s are stored in the database as byte arrays, which are packed according to the storage specification, v1.0.0.
It is a pretty trivial task to export these to and from Postgres and other applications by implementing a serializer/deserializer. We have provided several packages that provide such tools: