postgresql-hll

The hll module provides powerful probabilistic set operations:

Unions

hlls support "lossless" unions. The union of any number of hlls is mathematically equivalent to a single hll populated by all original inputs. This allows for efficient large-scale analytics, such as calculating unique visitors in a sliding window using Postgres aggregation functions like hll_union_agg and hll_union.

Intersections

You can estimate the intersection of sets using the inclusion-exclusion principle combined with the union function.

Warning on Error Rates: The error in an intersection estimate is proportional to the union of the two hlls. If one hll is significantly larger than the other (e.g., one has 1 billion elements and the other has 10 million), the error margin of the larger hll can easily overwhelm the actual intersection cardinality, leading to disproportionately large relative errors.

To create and install an RPM package, follow these steps:

1. Set versions (e.g., for version 2.21 and PostgreSQL 11):

   export VER=2.21
   export PGSHRT=11

2. Configure Makefile: Ensure the Makefile points to the correct pg_config (since rpmbuild does not respect environment variables):

   PG_CONFIG = /usr/pgsql-11/bin/pg_config

3. Create a tarball:

   tar cvfz postgresql${PGSHRT}-hll-${VER}.tar.gz postgresql-hll \
       --transform="s/postgresql-hll/postgresql${PGSHRT}-hll/g"

4. Execute rpmbuild:

   rpmbuild -tb postgresql${PGSHRT}-hll-${VER}.tar.gz

5. Install the RPM:
   • For the standard build:

     rpm -Uv rpmbuild/RPMS/x86_64/postgresql11-hll-2.21.x86_64.rpm

   • For the debug build:

     rpm -Uv rpmbuild/RPMS/x86_64/postgresql11-hll-debuginfo-2.21.x86_64.rpm

The hll type can be initialized with four parameters to tune accuracy, memory, and behavior. The default signature is: hll(log2m=11, regwidth=5, expthresh=-1, sparseon=1)

Parameters:

• log2m: (Integer, 4 to 31) The log-base-2 of the number of registers. Higher values increase accuracy but double the storage per increment. Relative error $\approx \pm 1.04/\sqrt{2^{\text{log2m}}}$.
• regwidth: (Integer, 1 to 8) Bits per register. In conjunction with log2m, this determines the maximum cardinality that can be estimated.
• expthresh: (Integer, -1, 0, or 1-18) Controls when the EXPLICIT representation is promoted to SPARSE.
  • -1: 'auto' mode (optimal memory usage).
  • 0: Skip EXPLICIT entirely (promote EMPTY $\rightarrow$ SPARSE).
  • 1-18: Promote at $2^{\text{expthresh}-1}$ cardinality.
• sparseon: (Integer, 0 or 1) Enables (1) or disables (0) the SPARSE representation. If disabled, EMPTY promotes directly to FULL.

To use hll, you must initialize an empty set, hash your input values, and then add them to the set.

Important: You cannot add raw integers or strings directly to an hll object. You must use the provided hashing functions (e.g., hll_hash_integer, hll_hash_text) to convert inputs into the hll_hashval type. Alternatively, you can cast an integer to hll_hashval if you want to bypass hashing.

--- 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;

In large fact tables, instead of using COUNT DISTINCT (which is slow), you can pre-aggregate unique users into hll columns. This allows for extremely fast queries over various time windows (days, weeks, months) using hll_union_agg and hll_cardinality.

-- 1. Create the destination table
CREATE TABLE daily_uniques (
  date            date UNIQUE,
  users           hll
);

-- 2. Fill it with aggregated unique statistics from a fact table
INSERT INTO daily_uniques(date, users)
  SELECT date, hll_add_agg(hll_hash_integer(user_id))
  FROM facts
  GROUP BY 1;

-- 3. Query weekly uniques
SELECT hll_cardinality(hll_union_agg(users)) 
FROM daily_uniques 
WHERE date >= '2012-01-02'::date AND date <= '2012-01-08'::date;

-- 4. Query using a sliding window (e.g., 7-day window)
SELECT date, #hll_union_agg(users) OVER seven_days
FROM daily_uniques
WINDOW seven_days AS (ORDER BY date ASC ROWS 6 PRECEDING);