Approximate Aggregation for Large Datasets: HyperLogLog and More

1. Why exact aggregation hits limits with large datasets

Approximate aggregation solves a problem that inevitably shows up as data volumes grow: COUNT(DISTINCT column) needs to internally retain every single value already seen in order to reliably detect duplicates, usually in a hash table or a sorted intermediate structure. For a table with a few thousand rows, that is trivial, but with several billion unique values, the memory footprint and runtime for an exact result quickly become impractical, especially when the metric needs to be computed live in an interactive dashboard.

Approximate aggregation addresses this problem with probabilistic algorithms that do not retain every single value exactly, but instead build a compact statistical summary, a so called sketch, from which estimates are derived with a known, controllable error margin. The central trade-off is: a small, predetermined relative error of usually under two percent is accepted, in exchange for memory footprint and runtime dropping by orders of magnitude, often from several gigabytes of intermediate storage down to a few kilobytes per sketch.

This article explains the working principle of HyperLogLog for distinct counts and t-digest for percentile estimation, shows concrete SQL syntax for approximate aggregation across various database platforms, and clearly delineates in which reporting scenarios exact values remain indispensable.

2. HyperLogLog: the principle behind distinct estimation

HyperLogLog is the best known algorithm for approximate aggregation of distinct counts and rests on an elegant statistical observation: once every input value is hashed, the resulting bit patterns are distributed uniformly at random. The probability of finding a bit pattern with many leading zeros among n random bit patterns depends directly on n. From the longest observed run of leading zeros in the hash, you can therefore back-calculate the approximate number of distinct input values, without having stored every single value.

HyperLogLog improves the accuracy of this estimate by splitting the hash space into many registers, typically several thousand, with each register independently storing the longest zero run within its subrange. Averaging across all registers smooths out statistical noise and, in modern implementations, delivers a standard error of roughly one to two percent, with a memory footprint of only a few kilobytes per sketch, regardless of whether the underlying dataset comprises a thousand or ten billion rows.

-- Exact COUNT DISTINCT vs. approximate aggregation with HyperLogLog (BigQuery syntax)
SELECT
    DATE_TRUNC(event_date, MONTH) AS month,
    COUNT(DISTINCT user_id)            AS exact_unique_users,     -- slow, scans full data
    APPROX_COUNT_DISTINCT(user_id)     AS approx_unique_users     -- fast, ~1-2% error
FROM events
GROUP BY month
ORDER BY month;

3. Using APPROX_COUNT_DISTINCT in practice

Most large analytics databases offer approximate aggregation through a direct, easy to use function, without developers having to implement the underlying HyperLogLog algorithm themselves. BigQuery has APPROX_COUNT_DISTINCT as a direct replacement for COUNT(DISTINCT column), Redshift offers the same function under an identical name, PostgreSQL needs the hll extension for native HyperLogLog support, and ClickHouse ships uniqHLL12 as its own, performance optimized variant right in the database core.

Using APPROX_COUNT_DISTINCT in practice barely differs syntactically from COUNT(DISTINCT column), which usually reduces switching to approximate aggregation in existing reports to a simple function replacement. Before making the switch, it is important to check whether the specific metric strictly requires an exact number, for example in financial reporting, or whether an estimate with one to two percent error is entirely sufficient for the use case, for example an analytics dashboard with user counts.

-- Approximate aggregation across different database platforms
-- PostgreSQL with the hll extension
SELECT hll_cardinality(hll_add_agg(hll_hash_text(user_id))) AS approx_unique_users
FROM events;

-- ClickHouse native approximate distinct count
SELECT uniqHLL12(user_id) AS approx_unique_users
FROM events;

-- Redshift, syntax identical to BigQuery
SELECT APPROX_COUNT_DISTINCT(user_id) AS approx_unique_users
FROM events;

4. Combining sketches: union across multiple partitions

A decisive advantage of approximate aggregation over exact distinct counting shows up when combining partial results from different partitions or precomputed time periods. A HyperLogLog sketch for January and a separate sketch for February can be mathematically correctly merged into a combined sketch for January through February, without having to read the underlying raw data again, because the union of two HyperLogLog registers happens bitwise via taking the maximum.

This property makes approximate aggregation particularly valuable for incremental reporting pipelines: instead of rescanning the entire history every month to update a cumulative distinct count, only a new sketch for the current month needs to be computed and merged with the already stored sketches from previous months. An exact COUNT(DISTINCT) calculation offers no such property, because two exact distinct sets cannot be correctly merged without access to the complete original data.

-- Merging pre-computed HyperLogLog sketches across months (BigQuery)
WITH monthly_sketches AS (
    SELECT
        DATE_TRUNC(event_date, MONTH) AS month,
        HLL_COUNT.INIT(user_id) AS sketch
    FROM events
    GROUP BY month
)
SELECT
    HLL_COUNT.MERGE(sketch) AS approx_unique_users_year_to_date
FROM monthly_sketches
WHERE month BETWEEN '2026-01-01' AND '2026-06-30';
-- No need to re-scan raw events, sketches are merged directly

5. t-digest and percentile estimation at large scale

Beyond distinct counts, approximate aggregation also covers percentile calculations, which likewise become expensive with very large datasets, because an exact percentile calculation requires a full sort of all values. The t-digest algorithm solves this problem by condensing the value distribution into a variable number of clusters, with clusters at the edges of the distribution, where percentiles like P95 or P99 typically matter, resolved more finely than clusters in the middle of the distribution.

This uneven resolution is the key design trick of t-digest in approximate aggregation: for the median, that is P50, a rough estimate is usually sufficient, while extreme percentiles like P99 or P99.9 are especially important in monitoring and latency reports and are therefore mapped with higher precision. Databases like ClickHouse and analytics platforms like Druid natively offer t-digest based percentile functions, which lets P95 latencies across billions of log rows be computed in milliseconds instead of minutes.

-- Approximate percentile estimation with t-digest style functions (ClickHouse)
SELECT
    endpoint,
    quantile(0.50)(response_time_ms) AS p50_approx,
    quantile(0.95)(response_time_ms) AS p95_approx,
    quantile(0.99)(response_time_ms) AS p99_approx
FROM request_logs
GROUP BY endpoint;

6. Understanding and controlling error bounds

The error in approximate aggregation is not random noise, but a known, mathematically derivable quantity that can be deliberately controlled via the number of registers or clusters used. With HyperLogLog, the relative standard error decreases roughly proportional to one divided by the square root of the register count, so doubling the registers reduces the error by about 30 percent, though it also doubles the memory footprint per sketch.

This relationship between accuracy and resource consumption is deliberately configurable in approximate aggregation, not fixed. For an internal analytics dashboard where a two percent error in user counts goes unnoticed by anyone, the default configuration is usually entirely sufficient. For a metric that appears in a regulatory filing or a customer billing statement, approximate aggregation should instead either be configured with significantly more registers or replaced entirely by exact calculation.

-- BigQuery: trading precision for cost via the optional precision parameter
SELECT
    -- Default precision, ~1-2% relative error, smallest sketch
    APPROX_COUNT_DISTINCT(user_id) AS approx_default,
    -- HLL_COUNT.INIT allows explicit precision control (10-24, higher = more accurate)
    HLL_COUNT.EXTRACT(HLL_COUNT.INIT(user_id, 20)) AS approx_higher_precision
FROM events;

7. Common use cases: analytics, monitoring, reach

Approximate aggregation has established itself as a standard tool in three areas. In web and product analytics, daily, weekly, and monthly active user counts are computed almost exclusively approximately, because the absolute precision of a single user count is business-irrelevant as long as the trend over time remains correctly visible. In infrastructure monitoring, latency percentiles like P95 and P99 across huge volumes of log rows are estimated nearly universally with t-digest style algorithms, because an exact sort of billions of log entries per minute would overload the monitoring pipeline itself.

The third classic use case is reach measurement in advertising and marketing systems, where the number of uniquely reached users across multiple campaigns and channels needs to be estimated. Since HyperLogLog sketches, as described in section four, can be correctly merged in a set-theoretic sense, approximate aggregation can here even estimate overlaps between campaigns, a calculation that would be practically infeasible with exact counts given the sheer data volume of commercial advertising platforms.

8. When approximate aggregation is the wrong choice

As useful as approximate aggregation is, there are clear boundaries where exact calculation remains mandatory. Financial metrics like revenue totals, account balances, or tax amounts must never be approximated, because even a fraction of a percent deviation can have legal and accounting consequences. Approximate aggregation is equally unsuitable for small datasets, where exact calculation is fast enough anyway and the time saved does not justify the added complexity of a sketch based approach.

Another case where approximate aggregation should be avoided concerns metrics with very small absolute values, for example a distinct count of under a hundred unique values. HyperLogLog produces proportionally larger relative errors for such small cardinalities than for millions of values, because the algorithm is optimized for large value ranges. For small, precision-critical counts, an exact COUNT(DISTINCT) query remains the right and inherently fast choice.

9. Exact vs. approximate aggregation compared

The following overview summarizes when exact and when approximate aggregation is the appropriate choice.

The choice between exact and approximate aggregation is not purely a performance question, but a deliberate business decision that weighs whether the metric requires absolute precision or whether a small, controlled error is economically acceptable for the given use case.

Applying approximate aggregation deliberately to the right metrics, and leaving exact calculation where it is business-critical, gains substantial performance on large datasets without endangering the reliability of critical numbers.

10. Summary

Approximate aggregation replaces exact calculations like COUNT(DISTINCT) or percentiles with probabilistic algorithms such as HyperLogLog and t-digest, which trade a controlled error, usually one to two percent, for substantial performance and memory gains on very large datasets. HyperLogLog estimates distinct counts via hash based registers, t-digest estimates percentiles via an unevenly resolved cluster structure.

The special advantage of approximate aggregation lies in the combinability of sketches across partition boundaries, which is what makes incremental reporting pipelines practical in the first place. Financial metrics and small datasets, however, remain a domain of exact calculation, because there either precision is strictly required or the performance advantage of approximate aggregation does not justify the added complexity.

11. FAQ: Approximate Aggregation