Apache DataSketches

Distinct count with HLL

The bread-and-butter sketch — approximate COUNT(DISTINCT) in a few KB of memory.

SELECT datasketch_hll_estimate(datasketch_hll(12, user_id)) AS distinct_users
FROM events;

The 12 is lg_k — base-2 log of the bucket count. lg_k = 12 (4096 buckets, ~4 KB sketch, ~1.6% standard error) is a common default. Bracket the estimate with datasketch_hll_lower_bound / datasketch_hll_upper_bound when you want a confidence interval.

Per-day HLL sketches, rolled up on demand

Build the sketch state once; query any window without rescanning.

CREATE TABLE daily_uniques (day DATE, hll sketch_hll);

INSERT INTO daily_uniques
SELECT date_trunc('day', ts) AS day,
       datasketch_hll(12, user_id) AS hll
FROM events
GROUP BY 1;

-- Rolling 7-day uniques — reads sketch state, not source events
SELECT datasketch_hll_estimate(datasketch_hll_union(12, hll)) AS uniques_last_7d
FROM daily_uniques
WHERE day >= CURRENT_DATE - 7;

The same pattern works for datasketch_cpc (smaller on disk, slower to write) and datasketch_theta (supports set operations beyond union).

Set operations with Theta — funnel, retention, churn

Theta is the only distinct-count family with full set algebra.

WITH a AS (SELECT datasketch_theta(12, user_id) AS s FROM events_jan),
     b AS (SELECT datasketch_theta(12, user_id) AS s FROM events_feb)
SELECT
  datasketch_theta_estimate(datasketch_theta_union(a.s, b.s))     AS jan_or_feb,
  datasketch_theta_estimate(datasketch_theta_intersect(a.s, b.s)) AS retained,    -- in both
  datasketch_theta_estimate(datasketch_theta_a_not_b(a.s, b.s))   AS churned,     -- jan not feb
  datasketch_theta_estimate(datasketch_theta_a_not_b(b.s, a.s))   AS new_users    -- feb not jan
FROM a, b;

This is the headline use case for Theta — funnel and cohort analysis directly off sketch state.

p50 / p95 / p99 with KLL

KLL is the recommended general-purpose quantile sketch.

WITH agg AS (
  SELECT datasketch_kll(200, latency_ms) AS sketch FROM requests
)
SELECT
  datasketch_kll_quantile(sketch, 0.50, true) AS p50,
  datasketch_kll_quantile(sketch, 0.95, true) AS p95,
  datasketch_kll_quantile(sketch, 0.99, true) AS p99
FROM agg;

K = 200 is a sensible production starting point. Higher K → smaller error, larger sketch. The trailing true is the inclusive flag — true for inclusive search (P[X ≤ q]), false for exclusive (P[X < q]). Use datasketch_kll_normalized_rank_error to inspect the actual rank-error guarantee for the configured K.

Histograms in one query — KLL CDF / PMF

Get the cumulative distribution at any set of split points without a second pass.

SELECT datasketch_kll_cdf(
         datasketch_kll(200, latency_ms),
         [10, 50, 100, 250, 500, 1000],
         /* inclusive */ true
       ) AS cdf
FROM requests;

Returns one row of cumulative ranks at each split point — directly usable for histograms. Swap cdf for datasketch_kll_pmf to get per-bucket probability mass instead.

Tail-accurate quantiles with TDigest

When p99 / p999 matters more than the median (SLO reporting), reach for t-digest.

CREATE TABLE readings(temp DOUBLE);
INSERT INTO readings(temp) SELECT unnest(generate_series(1, 10))::DOUBLE;

-- Rank of value 5 within the aggregated sketch
SELECT datasketch_tdigest_rank(datasketch_tdigest(100, temp), 5) AS rank_of_5
FROM readings;

CDF over multiple split points in one call:

SELECT datasketch_tdigest_cdf(datasketch_tdigest(100, temp), [1, 5, 9]) AS cdf
FROM readings;

TDigest accepts FLOAT/DOUBLE only. For integer or skewed-rank quantile work, see datasketch_kll or datasketch_req.

Top-K heavy hitters with Frequent Items

Find the most frequent items in a stream — with confidence bounds on each estimate.

SELECT datasketch_frequent_items_get_frequent(
         datasketch_frequent_items(8, country_code),
         'NO_FALSE_POSITIVES'
       ) AS heavy_hitters
FROM page_views;

The result is a list of structs — (item, estimate, lower_bound, upper_bound). Use 'NO_FALSE_POSITIVES' for items that are definitely heavy hitters, 'NO_FALSE_NEGATIVES' for the union of all candidates that might be. The leading 8 is lg_max_map_size — log₂ of the maximum number of tracked items (so 8 → up to 256 candidates). Bigger values track more candidates and tighten the per-item error bound; typical values run 4–12.

Skew-aware quantiles with REQ

When the distribution is heavily skewed and you want predictable accuracy across the whole rank space, REQ scales its error with rank rather than fixing it.

SELECT
  datasketch_req_quantile(datasketch_req(12, value), 0.001, true) AS p001,
  datasketch_req_quantile(datasketch_req(12, value), 0.5,   true) AS p50,
  datasketch_req_quantile(datasketch_req(12, value), 0.999, true) AS p999
FROM measurements;

Persist sketches to Parquet, merge in another DuckDB

Sketch BLOBs are portable across processes and across DuckDB instances:

COPY (SELECT day, hll FROM daily_uniques)
  TO 'daily_uniques.parquet' (FORMAT PARQUET);

-- Later, anywhere with this extension loaded:
SELECT datasketch_hll_estimate(datasketch_hll_union(12, hll))
FROM read_parquet('daily_uniques.parquet')
WHERE day BETWEEN DATE '2026-01-01' AND DATE '2026-01-31';

The serialization format is the same one used by Druid, Pinot, BigQuery, and the Apache DataSketches Java library — sketches built here can be merged in those systems and vice versa.