Apache DataSketches

A billion-row distinct count, persisted

A naive COUNT(DISTINCT user_id) over a billion-row event table is a sort plus a hash table — minutes of work, gigabytes of memory, a fresh scan every time someone asks again. With a Theta sketch, it’s a fixed-memory aggregate you build once per partition and roll up on demand:

-- One pass, per-day sketch state, persisted as a typed BLOB column
CREATE TABLE daily_uniques AS
SELECT date_trunc('day', ts)        AS day,
       datasketch_theta(12, user_id) AS sketch        -- ~64 KB per day
FROM events
GROUP BY 1;

-- Rolling 7-day uniques: union the per-day sketches, no rescan
SELECT datasketch_theta_estimate(
         datasketch_theta_union(sketch)
       ) AS uniques_last_7d
FROM daily_uniques
WHERE day >= CURRENT_DATE - 7;

-- Retention: users active in BOTH last week AND this week
WITH last_week AS (SELECT datasketch_theta_union(sketch) AS s
                   FROM daily_uniques
                   WHERE day BETWEEN CURRENT_DATE - 14 AND CURRENT_DATE - 7),
     this_week AS (SELECT datasketch_theta_union(sketch) AS s
                   FROM daily_uniques
                   WHERE day >= CURRENT_DATE - 7)
SELECT datasketch_theta_estimate(
         datasketch_theta_intersect(last_week.s, this_week.s)
       ) AS retained
FROM last_week, this_week;

The first query touches the source rows once. The next two — and any other window, set difference, or intersection you care to ask — operate on the sketch state alone.

Architecture

This extension is a thin DuckDB wrapper around the Apache DataSketches C++ library. Every sketch family registers:

• An aggregate (datasketch_kll, datasketch_hll, datasketch_theta, …) that builds the sketch in one pass over input values.
• A typed BLOB column type (sketch_kll_double, sketch_hll, sketch_theta, …) — a strict superset of BLOB carrying the serialized sketch.
• Reader scalars (datasketch_*_quantile, datasketch_*_estimate, datasketch_*_cdf, …) that decode the BLOB and return values without rebuilding from rows.
• Mergers (datasketch_hll_union, datasketch_theta_union, …) — aggregates over a sketch column that produce a rolled-up sketch.

The serialization format is the same one the Java reference implementation writes, which is the format Druid, Pinot, BigQuery, and Spark integrations consume. A sketch built in DuckDB and written to Parquet can be merged inside Druid or vice versa — no re-aggregation across systems.

Choosing a sketch

The right sketch depends on what you’re estimating and which constraint binds first — read latency, sketch size, or set algebra.

Distinct counts (cardinality)

Quantiles

Frequency

A single family — Frequent Items — for top-K heavy hitters with confidence-bounded frequencies. Use 'NO_FALSE_POSITIVES' to get items that are definitely heavy, 'NO_FALSE_NEGATIVES' to get every candidate that might be.

Compared to alternatives

• DuckDB’s built-in approx_count_distinct and approx_quantile — both ship in DuckDB and use HLL / TDigest internally, but expose only the final estimate. Reach for this extension when you need the sketch as state — to persist it as a column, merge later, tune sketch parameters (lg_k, K, map_size), or interoperate with other Apache DataSketches consumers.
• Exact aggregates (COUNT(DISTINCT), quantile_cont, mode) — the right answer when policy demands exact and your data fits. DuckDB’s vectorized exact aggregates are fast at most analytical scales; measure before reaching for an approximate sketch.
• Reservoir / streaming aggregates rolled by hand — sketches give you the same bounded-memory streaming property plus mathematically grounded error bounds plus mergeability across processes. For anything that needs to survive a process restart or roll up across shards, the sketch is the better primitive.
• Druid / Pinot / BigQuery sketch columns — those systems use the same serialization format. If you’re already producing sketches there, this extension lets DuckDB read and merge them; if you’re building them in DuckDB, downstream OLAP systems can consume the BLOBs directly.

Persistence and portability

Every sketch round-trips through a typed BLOB column (sketch_kll_double, sketch_hll, sketch_theta, etc.) that’s a strict superset of BLOB. Sketches written into a Parquet file can be read back into any DuckDB instance with this extension loaded, or into any other DataSketches-aware system, and merged without a re-scan. Aggregate functions accept either raw input values or an existing sketch column, so incremental rollup is just another SELECT.

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.