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 OR REPLACE 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(sketch)               -- merge aggregate over sketches
       ) 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(sketch) AS s
                   FROM daily_uniques
                   WHERE day BETWEEN CURRENT_DATE - 14 AND CURRENT_DATE - 7),
     this_week AS (SELECT datasketch_theta(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 — aggregates over a sketch column that produce a rolled-up sketch (datasketch_hll_union, datasketch_cpc_union, or the sketch aggregate itself given a sketch, e.g. datasketch_theta(sketch), datasketch_kll(200, sketch)), plus scalar unions of sketches in the same row (datasketch_hll_merge, datasketch_cpc_merge, datasketch_theta_union(a, b, …)).

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)

Distinct keys with per-key metrics

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.

Tuple sketches: distinct keys that carry values

A Tuple sketch is a Theta sketch in which every retained key also carries a summary. datasketch_tuple(key, value) keeps one DOUBLE per key, combined by mode := — 'sum' (default), 'min', 'max' or 'one' — so one pass answers both “how many distinct customers?” and “how much did they spend?”:

SELECT datasketch_tuple_estimate(s) AS customers,
       datasketch_tuple_sum(s)      AS revenue,               -- estimated total over all keys
       datasketch_tuple_mean(s)     AS revenue_per_customer
FROM (SELECT datasketch_tuple(customer_id, amount) AS s FROM orders);

datasketch_aod(key, [m1, m2, …]) is the array-of-doubles variant: each key carries 1–255 DOUBLE values summed element-wise, read back with datasketch_aod_column_sums / datasketch_aod_column_means. Both families support the Theta algebra (_union, _intersect, _intersect_agg, _a_not_b), Jaccard similarity on the key sets, and conversion to a plain Theta sketch with _to_theta. The Tuple sketch’s mode is not stored in the sketch (as in the other DataSketches libraries), so pass the same mode := to merges, unions and intersections. Sketches with different seeds — or array-of-doubles sketches with different numbers of values — cannot be combined.

Theta options: seeds, sampling, and storage

datasketch_theta, datasketch_tuple and datasketch_aod take keyword options seed := (the hash seed) and p := (an up-front sampling probability in (0, 1]). Compact sketches store only a 16-bit hash of the seed (datasketch_theta_seed_hash), and every function reads and combines seeded sketches without being told the seed again; combining sketches whose seed hashes differ is an error. Unions keep the largest lg_k of their inputs (at least 12) unless you pass one. Theta results are written in the compressed compact format (serial version 4) when it applies; versions 1–4 are all readable, and DataSketches C++ 4.0+, Java and Python read version 4. To hash raw BLOB bytes use datasketch_theta_blob — datasketch_theta(BLOB) merges serialized sketches.

Behavior changes in recent releases

The October 2026 releases (Apache DataSketches C++ 5.3.0) change a few behaviors. Unless marked DuckDB 2.0 build, the change also ships in the current DuckDB 1.5 build.

• CDF and PMF always return LIST(DOUBLE) (DuckDB 2.0 build). datasketch_{kll,quantiles,req}_cdf and _pmf used to return a list of the sketch’s item type, which truncated CDF ranks for integer sketches and could corrupt PMF results. Update code that expects, say, INTEGER[].
• Frequent Items keys for FLOAT/DOUBLE are exact. Items are now keyed by their shortest round-trip text (like CAST(x AS VARCHAR)) instead of six fixed decimals, so 0.1234567 and 0.1234568 stay distinct. Sketches of FLOAT/DOUBLE items built by earlier versions hold the old spellings: lookups against them usually return 0 and merges keep both spellings, so rebuild them from source data. VARCHAR and integer sketches are unaffected. lg_max_k must now be between 3 and 30 (out-of-range values used to be silently truncated).
• Theta unions keep their size. datasketch_theta_union and the datasketch_theta(sketch) merge used to run at lg_k 12 regardless of their inputs; they now keep the inputs’ lg_k.
• Constant arguments are honored. Queries that combined the same aggregate with different constant sizes (e.g. datasketch_kll(12, v) and datasketch_kll(16, v) in one UNION ALL) could previously return the first sketch twice.
• New in the DuckDB 2.0 build: Tuple and array-of-doubles sketches; batch _quantiles / _ranks and _sorted_view for KLL, Quantiles and REQ; VARCHAR items for KLL and Quantiles; REQ accuracy mode and rank bounds; T-Digest exact min/max; HLL register encodings, composite estimate and datasketch_hll_merge / datasketch_cpc_merge; Theta Jaccard similarity, datasketch_theta_intersect_agg, variadic union/intersect, seed := / p := options, unsigned-integer input, datasketch_theta_blob and compressed storage. datasketch_theta_get_seed is now documented as an alias of datasketch_theta_seed_hash (it always returned the seed hash).

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 OR REPLACE 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. datasketch_theta_union and datasketch_theta_intersect take two or more sketches, and datasketch_theta_intersect_agg intersects a whole column of them.

How similar are two audiences? — Theta Jaccard

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_jaccard(a.s, b.s)               AS jaccard,         -- {lower, estimate, upper}
       datasketch_theta_similarity_test(a.s, b.s, 0.3)  AS at_least_30pct
FROM a, b;

datasketch_theta_jaccard returns |A ∩ B| / |A ∪ B| with approximate bounds; the similarity / dissimilarity tests answer “at least / at most this similar” with high confidence.

Distinct customers and their revenue — Tuple sketch

A Tuple sketch is a Theta sketch whose keys carry a value, so one pass counts distinct keys and aggregates a metric per key.

SELECT datasketch_tuple_estimate(s) AS customers,
       datasketch_tuple_sum(s)      AS revenue,
       datasketch_tuple_mean(s)     AS revenue_per_customer
FROM (SELECT datasketch_tuple(customer_id, amount) AS s FROM orders);

mode := 'min' | 'max' | 'one' changes how a key’s values combine (the default is 'sum'). Tuple sketches merge, union, intersect and diff like Theta sketches — e.g. the revenue of customers present in two segments is datasketch_tuple_sum(datasketch_tuple_intersect(a, b)). For several metrics per key, use the array-of-doubles sketch:

SELECT datasketch_aod_column_sums(s)  AS totals,         -- [revenue, items]
       datasketch_aod_column_means(s) AS per_customer
FROM (SELECT datasketch_aod(customer_id, [amount, items]) AS s FROM orders);

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;

Or ask for several quantiles in one call with datasketch_kll_quantiles — datasketch_kll_quantiles(sketch, [0.5, 0.95, 0.99], true) returns a list — and the reverse with datasketch_kll_ranks. 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 a LIST(DOUBLE) of cumulative ranks, one per split point plus a final 1.0 — directly usable for histograms. CDF and PMF results are always DOUBLE, whatever the sketch’s item type. For the retained items themselves, with their weights, use datasketch_kll_sorted_view. 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 OR REPLACE 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_k — 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; valid values are 3–30 and 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.