Approximate aggregation
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.
Overview
Some aggregate computations are expensive to do exactly at scale — most notably counting distinct values and computing quantiles/percentiles — because they require tracking information proportional to the size or cardinality of the data rather than a small, constant amount. Approximate aggregation algorithms solve this by using probabilistic data structures that summarize the data with a small, fixed memory footprint and give an estimate with a known, bounded error, rather than an exact answer.
Common approximate aggregation techniques
- Approximate distinct counting, typically via HyperLogLog, estimates
COUNT(DISTINCT ...). - Approximate quantiles, often via t-digest or similar sketch structures, estimate percentiles like the median or 95th percentile.
- Reservoir sampling maintains a fixed-size random sample of a stream of unknown or very large size, useful for sampling-based approximations of other statistics.
Approximate aggregation functions in DuckDB
DuckDB provides several built-in approximate aggregates:
Copy code
SELECT
approx_count_distinct(user_id) AS est_unique_users,
approx_quantile(latency_ms, 0.95) AS p95_latency,
reservoir_quantile(latency_ms, 0.5) AS median_estimate
FROM requests;
approx_count_distinct uses HyperLogLog internally; approx_quantile uses a t-digest sketch; reservoir_quantile estimates a quantile from a fixed-size reservoir sample (with a configurable sample size, defaulting to 8192) rather than sorting the full column, which is useful for very large or streaming-style datasets where an exact quantile_cont/quantile_disc computation would be too expensive.
When to reach for approximation
Approximate aggregation is a good fit for exploratory analysis, dashboards, and monitoring, where a value within a small percentage of exact is perfectly usable and the speed and memory savings matter more than precision. It's a poor fit for anything requiring an exact, auditable number — financial totals, billing, or compliance reporting — where DuckDB's exact aggregates (count(distinct ...), quantile_cont, median) should be used instead.
Related terms
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.
Percentile →A percentile is the value below which a given percentage of a dataset falls — for example, the 95th percentile (p95) of response times is the value that 95% of requests were faster than.
aggregation →Aggregation refers to the process of combining multiple individual data values into a single summary value.
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.
TABLESAMPLE →TABLESAMPLE (or a SAMPLE clause) returns a random subset of a table's rows, letting queries run faster on a representative fraction of the data instead of the full table.
FAQS
approx_quantile uses a t-digest sketch and tends to be more accurate for a given memory budget, while reservoir_quantile estimates from a fixed-size random sample of the data and can be a good option for very large or streaming datasets where maintaining a sketch structure is less convenient.
For high-cardinality distinct counts and quantiles over large datasets, yes, typically substantially — because these algorithms use bounded memory and avoid the sorting or full value-tracking that exact computation requires. For small datasets the difference is often negligible.
