Overview

This Postgres module introduces a new data type hll which is a HyperLogLog data structure. HyperLogLog is a fixed-size, set-like 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.

This postgresql-hll extension was originally developed by the Science team from Aggregate Knowledge, now a part of Neustar. Please see the acknowledgements section below for details about its contributors.

Algorithms

A hll is a combination of different set/distinct-value-counting 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', map-based implementation of HyperLogLog, a probabilistic set data structure. Only stores the indices and values of non-zero registers in a map, until the number of non-zero registers exceeds a fixed cardinality.

FULL

A fully-materialized, list-based 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 and regwidth = 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 64-bit 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 64-bit 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 non-zero values as a map from index to values. This map is stored as a list of index-value pairs that are bit-packed "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 map-based HyperLogLog structure. Finally, when there are enough registers, the map-based HLL will be converted to a bit-packed 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 >= '2012-01-02'::date AND date <= '2012-01-08'::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 >= '2012-01-01' AND
      date <  '2013-01-01'
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 pre-built aggregates or self-joins or generate_series trickery in a COUNT DISTINCT world.

Operators

We've added a few operators to make using hlls 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 absolutely 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 type-specific function, which makes it slower than the type-specific 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 hlls 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 hlls. Doing sliding window unique counting typically involves some generate_series trickery, but it's quite simple with the hlls you've already computed for your roll-ups.

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 log-base-2 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 regwidths and log2ms and the approximate maximum cardinality that can be estimated with those para