HyperLogLog
HyperLogLog is a probabilistic algorithm for estimating the number of distinct elements in a large dataset (cardinality) using a small, fixed amount of memory, at the cost of a small, predictable error margin.
Overview
Counting exact distinct values over a huge dataset normally requires tracking every unique value seen, which uses memory proportional to the number of distinct items — potentially gigabytes for a large enough dataset. HyperLogLog (HLL) is an algorithm that estimates that same distinct count using a small, fixed-size data structure (often just a few kilobytes) regardless of how many total or distinct values are processed, by cleverly hashing values and tracking statistical patterns in the hash bits. The trade-off is a small amount of estimation error, typically around 1-2% for standard configurations, in exchange for massive memory savings and the ability to merge cardinality estimates across data partitions (useful in distributed systems).
Approximate distinct counting in DuckDB
DuckDB implements approx_count_distinct, which uses HyperLogLog internally to estimate COUNT(DISTINCT ...) without materializing every distinct value.
Copy code
SELECT approx_count_distinct(user_id) AS estimated_unique_users
FROM events;
Against a large table, this can be dramatically faster and use far less memory than the exact COUNT(DISTINCT user_id), particularly when the column has very high cardinality. It's well suited to dashboards and monitoring use cases where an estimate within a percent or two is perfectly acceptable, and less suited to contexts that require an exact count, such as financial reporting or billing.
Why it matters
HyperLogLog (and its variants) is widely used across analytics systems — including Redis's PFCOUNT, Postgres extensions, Spark, and BigQuery's APPROX_COUNT_DISTINCT — as the standard technique for fast, low-memory approximate cardinality estimation at scale.
Related terms
Approximate aggregation refers to computing statistics like distinct counts, quantiles, or samples using algorithms that trade a small, bounded amount of accuracy for large gains in speed and memory efficiency.
Cardinality →Cardinality refers to the number of distinct values in a column or dataset, or, in data modeling, the nature of a relationship between two tables (such as one-to-many).
DISTINCT →DISTINCT removes duplicate rows from a query's result set, returning only unique combinations of the selected columns.
Data profiling →Data profiling is the process of examining a dataset to understand its structure, content, and quality — things like data types, value distributions, null rates, and cardinality — before using it for analysis or building pipelines on top of it.
Cost-based optimizer →A cost-based optimizer chooses among logically equivalent query plans by estimating the execution cost of each one, using statistics about table sizes and data distributions, and picking the cheapest estimate.
Dictionary encoding →Dictionary encoding is a compression technique that replaces repeated column values with small integer codes, storing the distinct values once in a separate lookup table.
FAQS
It uses a HyperLogLog-based estimator with a typical error rate on the order of 1-2%, which is generally accurate enough for dashboards and exploratory analysis but not for use cases requiring an exact count.
Exact distinct counting needs to track every unique value it has seen, which can require substantial memory on very high-cardinality columns over huge datasets. HyperLogLog-based approximation uses a small, fixed amount of memory instead, trading a little accuracy for a lot of speed and scalability.
