# postgresql-hll adds a HyperLogLog type with a promotion hierarchy

> postgresql-hll is an Apache-2.0 PostgreSQL extension that stores distinct-value estimates in a native hll column, moving from an exact list to sparse registers to a full sketch as cardinality grows. It suits analytics workloads that need set unions over daily aggregates, and its estimates are approximate once a sketch leaves the EXPLICIT stage.

**citusdata/postgresql-hll** — PostgreSQL extension adding HyperLogLog data structures as a native data type 

- Repository: https://github.com/citusdata/postgresql-hll
- Website: http://blog.aggregateknowledge.com/2013/02/04/open-source-release-postgresql-hll/
- Stars: 1,233 · Forks: 117
- Language: C
- License: Apache-2.0
- Published: 2026-10-19 · Updated: 2026-10-19 · Language: en
- Canonical page: https://hysenlabs.com/projects/citusdata-postgresql-hll

## The hll type is a fixed-size set with tunable precision

postgresql-hll is a PostgreSQL module that introduces a new data type called hll, which holds a HyperLogLog data structure. The README describes HyperLogLog as a fixed-size, set-like structure used for distinct value counting with tunable precision, and gives the headline figure: in 1280 bytes, hll can estimate the count of tens of billions of distinct values with only a few percent error.

The problem this solves is specific. Counting distinct values in a large fact table means either a full scan with a hash set, or an approximation that you compute in the application layer and store separately. A native column means the sketch lives in the same table as the aggregate, unions are a SQL function call, and the query planner can work with it.

The implementation is an augmentation of the algorithm from the original paper, described as improving accuracy and memory use without sacrificing much speed. The extension was originally developed by the Science team from Aggregate Knowledge, now part of Neustar, and the README points at an acknowledgements section for the contributor list.

The interesting part is not the paper, it is that this implementation does not use one representation. It picks between four depending on how much data has gone in, which is what makes it behave well on both a table with a handful of rows and a table with billions.

## Four representations, and the rules that promote between them

The README describes an hll as a combination of different set and distinct-value-counting algorithms that can be thought of as a hierarchy, with rules for moving up that hierarchy. Each algorithm has a name.

EMPTY is a constant value denoting the empty set. EXPLICIT is an explicit, unique, sorted list of integers in the set, maintained up to a fixed cardinality. SPARSE is a lazy, map-based implementation of HyperLogLog, a probabilistic set data structure, which 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 is a fully-materialised, list-based implementation of HyperLogLog that explicitly stores the value of every register in a list ordered by register index.

The promotion path is described step by step. Initialising and storing a new hll object allocates a small sentinel value symbolising the empty set. When the first few values are added, a sorted list of unique integers is stored in an EXPLICIT set. When you wish to stop trading accuracy for memory, the values in the sorted list are promoted to a SPARSE map-based structure. Finally, when there are enough registers, the map-based HLL is converted to a bit-packed FULL structure.

The accuracy consequence is direct. The cardinality estimates of the EMPTY and EXPLICIT representations are exact, while the accuracies of the SPARSE and FULL representations are governed by the guarantees provided by the original HLL algorithm. A small sketch in a dashboard is therefore a precise number, and only a large one becomes approximate.

## The memory argument is why EXPLICIT and SPARSE exist at all

The README is unusually explicit about the reasoning behind the deviations from the original algorithm, and it is worth following because it explains the design.

Naively, a HLL takes regwidth * 2^log2m bits to store. In typical usage, log2m equals 11 and regwidth equals 5, which requires 10,240 bits or 1,280 bytes. The README's reaction is: that is a lot of bytes.

The first addition came from realising that 1,280 bytes is the size of 160 64-bit integers. If you want more accuracy at low cardinalities, you can keep an explicit set of the inputs as a sorted list of 64-bit integers until you hit the 161st distinct value. That gives the true representation of the distinct values in the stream while requiring the same amount of memory. That is the EXPLICIT algorithm.

The second came from realising you do not need to store registers whose value is zero. You can represent the set of registers that have non-zero values as a map from index to value, stored as a list of index-value pairs that are bit-packed short words of length log2m + regwidth. That is the SPARSE algorithm.

Combining them gives the promotion hierarchy, which the README says allows the algorithm to be tuned for better accuracy, memory, or performance. The practical effect is that a table of daily aggregates does not pay 1,280 bytes per row for a day with three visitors.

## Building the extension from source uses PGXS and a C11 object

The extension is a compiled C module, and the repository layout follows the standard PostgreSQL extension shape. The top level holds hll.control, the Makefile, include/ and src/ for the C sources, sql/ for the regression test queries, expected/ for their expected output, update/ for the versioned SQL update scripts, and a DEVELOPER.md alongside REFERENCE.md and a CHANGELOG.md.

The Makefile is where the PostgreSQL conventions show. It sets EXTENSION to hll and MODULE_big to the same name, then locates the PostgreSQL build system through PGXS:

```bash
EXTENSION = hll
MODULE_big = $(EXTENSION)
OBJS = $(patsubst %.c,%.o,$(wildcard src/*.c)) $(patsubst %.cpp,%.o,$(wildcard src/*.cpp))

PG_CPPFLAGS = -fPIC -Wall -Wextra -Werror -Wno-unused-parameter -Wno-implicit-fallthrough -Iinclude -I$(libpq_srcdir)

PG_CONFIG ?= pg_config
PGXS = $(shell $(PG_CONFIG) --pgxs)
include $(PGXS)
```

Two details are worth a note. The compiler flags include -Werror, so warnings break the build, and the update scripts are preprocessed by the C preprocessor through the SQLPP variable, which means the.sql files under update/ can contain shared fragments and macro substitutions rather than being plain SQL.

The regression suite is defined by REGRESS, which globs the files in sql/ and adds a setup file first, with the matching expected output in expected/. The src/hll.o object is compiled with a C11 standard flag, and SHLIB_LINK adds the C++ standard library, which tells you part of the implementation is in C++.

## The dashboard pattern: pre-aggregate into a daily table, then union the sketches

The README works through a data warehouse use case that is the reason to use this extension at all.

The starting point is a fact table recording users' visits, what they did and where they came from, with hundreds of millions of rows, where table scans take minutes or at least lots and lots of seconds. The goal is a quick, millisecond idea of how many unique users visit per day for a dashboard. The aggregate table is simple:

```sql
CREATE TABLE daily_uniques (
  date            date UNIQUE,
  users           hll
);

INSERT INTO daily_uniques(date, users)
  SELECT date, hll_add_agg(hll_hash_integer(user_id))
  FROM facts
  GROUP BY 1;
```

The user_id is hashed first, then the hashed values are aggregated into one hll per day. Asking for cardinality is then a scan of the small table:

```sql
SELECT date, hll_cardinality(users) FROM daily_uniques;
```

The reason to do all this instead of COUNT DISTINCT is the follow-up questions. The README's point is that COUNT DISTINCT answers only one question, how many unique users per day, whereas unions over the stored sketches answer many:

```sql
SELECT hll_cardinality(hll_union_agg(users)) FROM daily_uniques WHERE date >= '2012-01-02'::date AND date <= '2012-01-08'::date;
```

The same union aggregate works for monthly totals with a GROUP BY on the extracted month, and for sliding windows using the OVER clause with a WINDOW definition, for example a seven-day window over ROWS 6 PRECEDING, and for a subtraction of the window union minus the current value to get the number of uniques you saw earlier that you did not see today. Those set operations are the feature that a stored sketch enables and a plain count cannot do.

## Incremental ingestion uses hll_add on a stored column, not a rebuild

The hello world example shows the lower level API, and it is the API you need if you are writing to a single sketch over time rather than building one per group.

```sql
CREATE TABLE helloworld (
        id              integer,
        set     hll
);

INSERT INTO helloworld(id, set) VALUES (1, hll_empty());

UPDATE helloworld SET set = hll_add(set, hll_hash_integer(12345)) WHERE id = 1;

SELECT hll_cardinality(set) FROM helloworld WHERE id = 1;
```

The sequence matters. A new hll starts as the empty set via hll_empty, values are added one at a time with hll_add, and hll_cardinality reports the estimate. The values added are hashes, not the original strings, so the column never stores the raw data, and hll_hash_text and hll_hash_integer are the two hashing entry points shown.

That is the shape of a streaming ingestion path. Each new event is hashed and added to the existing column, and the row is updated. The cost is that the column grows and is rewritten on each update, and the estimates become approximate once the sketch is promoted past EXPLICIT.

For the batch path, hll_add_agg does the same job over a set of rows, which is what the daily aggregate uses. The distinction to keep in mind when designing tables is that hll_add_agg consumes a group of values at once, while hll_add mutates a single stored sketch. A design that only ever calls hll_add on a growing column answers the daily question well and the range question badly, because you cannot union sketches you never stored separately.

## Apache-2.0, and a release record that shows a slower cadence

The licence is Apache-2.0, and the LICENSE file in the repository is the authoritative text. The Makefile header carries the same Apache 2.0 notice with the 2013 Aggregate Knowledge copyright, so the licence terms have been in place since the beginning. This is a licensing statement rather than legal advice.

The release record shows a project with a slower, more deliberate cadence than most. Recent tags are v2.21 on 2026-06-02, v2.20 on 2026-05-27 and v2.19 on 2025-10-17, and the repository is not archived with the last push on 2026-06-02.

The gap between v2.19 in October 2025 and v2.20 in May 2026 is the sort of interval that makes people wonder whether a project is still moving. The date of the last push answers that question precisely, and it is worth knowing if you are evaluating a dependency on this extension: the codebase is not under active development at the pace of a PostgreSQL core contribution, and the update/ directory of versioned SQL scripts, plus the changelog, is where you look to see whether a new PostgreSQL major version has been addressed.

That structure also tells you how upgrades work. Because the extension ships as a module with a shared library and versioned SQL update files, a PostgreSQL major version upgrade means loading the new library and running the update script, and the compatibility range is encoded in hll.control and the update directory rather than in application code.

## Conclusion

Adopt postgresql-hll if you are running analytics queries that need distinct-value counts or set unions over time ranges, and you can accept an approximate answer once the sketch leaves the exact representation. Do not adopt it as a drop-in replacement for COUNT DISTINCT on a single table, because the whole point is the pre-aggregated sketch pattern. Before you install, check the server version against the extension's compatibility range in the update directory, and design your aggregate table so that the hll column is updated with hll_add_agg rather than by inserting raw values, because a sketch that is only ever added to and never unioned loses the ability to answer the range questions.

## FAQ

### What does the hll data type in postgresql-hll actually store?

It stores a HyperLogLog data structure, a fixed-size set-like structure for distinct value counting with tunable precision. The README says 1280 bytes can estimate the count of tens of billions of distinct values with only a few percent error.

### Is the distinct count from an hll column always exact?

No. The cardinality estimates of the EMPTY and EXPLICIT representations are exact, while the accuracies of the SPARSE and FULL representations are governed by the guarantees of the original HLL algorithm. A sketch is promoted out of the exact representation as it grows.

### How do I aggregate unique visitors per day with postgresql-hll?

Hash the identifier and aggregate the hashes into one sketch per group, as in INSERT INTO daily_uniques(date, users) SELECT date, hll_add_agg(hll_hash_integer(user_id)) FROM facts GROUP BY 1. Then read the estimate with SELECT hll_cardinality(users) FROM daily_uniques.

### Can I compute uniques across a date range with postgresql-hll?

Yes, by unioning the stored sketches with hll_union_agg, for example SELECT hll_cardinality(hll_union_agg(users)) FROM daily_uniques WHERE date >= '2012-01-02'::date AND date <= '2012-01-08'::date. The same aggregate works inside a window definition for sliding windows.

### What is the difference between the EXPLICIT, SPARSE and FULL representations?

EXPLICIT is a sorted list of unique integers kept up to a fixed cardinality, SPARSE is a map-based HyperLogLog that stores only the non-zero registers, and FULL is a bit-packed list holding the value of every register. The README describes a promotion path where a sketch moves from EXPLICIT to SPARSE and then to FULL as it grows.

## Sources

- [citusdata/postgresql-hll on GitHub](https://github.com/citusdata/postgresql-hll)
- [License: Apache-2.0](https://github.com/citusdata/postgresql-hll/blob/master/LICENSE)
- [Project website](http://blog.aggregateknowledge.com/2013/02/04/open-source-release-postgresql-hll/)
- [README](https://github.com/citusdata/postgresql-hll/blob/master/README.md)
- [Releases](https://github.com/citusdata/postgresql-hll/releases)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/citusdata-postgresql-hll