apache / apache/doris

[Feature] Add uniq_theta: a Theta-sketch based approximate distinct-count aggregate function

Open
#66,240 0 comments 0 reactions 0 assignees View on GitHub
kind/feature
Dominant language
Java
Stars
15.9k
Forks
3.9k
Avg merge
2d 23h
Merged PRs (30d)
520

Description

### Search before asking

- [x] I had searched in the [issues](https://github.com/apache/doris/issues?q=is%3Aissue) and found no similar issues.

### Description

Doris currently offers `approx_count_distinct` / `ndv`, which is based on HyperLogLog. HLL supports only *union* — it cannot do clean intersection or difference on the serialized state.

This proposes adding **`uniq_theta`**, an approximate distinct-count aggregate backed by the [Apache DataSketches](https://datasketches.apache.org/docs/Theta/ThetaSketches.html) **Theta
Sketch** (ported from ClickHouse's `uniqTheta`). Theta sketches add capabilities HLL lacks:

- **Set operations on the serialized sketch** — union / intersect / difference. This enables answering questions like "how many users appeared in both campaign A and B" directly from two
precomputed sketches, without rescanning raw data.
- **Precompute-once, query-many** — a theta sketch can be materialized as an `agg_state` column and repeatedly merged / unioned / intersected across partitions, dimensions, or time
windows (funnels, retention, audience overlap).
- **Cross-engine interoperability** — feeding raw value bytes to the DataSketches hash (matching ClickHouse's `insertOriginal`) keeps the inner sketch payload compatible with other
DataSketches-based engines (ES, ClickHouse, Spark, etc.), a common requirement when sketches are pre-aggregated in Hive and analyzed across systems.
- **Documented error bound** — ~3.125% relative error at 95% confidence with the default 4096 nominal entries; exact for small cardinalities.

The DataSketches dependency was already introduced by #63143 (which added `datasketches_hll_union_agg` and the `contrib/datasketches-cpp` submodule), and that PR explicitly noted theta
sketch as an easy follow-up. This proposal builds directly on that infrastructure.

### Use case

Users migrating from ClickHouse expect uniqTheta parity. More generally, teams that pre-aggregate detailed data into Theta sketches in Hive (or another engine) need to load and combine
those sketches in Doris and get cross-engine-consistent cardinality with set operations — which HLL-based approx_count_distinct cannot provide.

### Related issues

- #63142 / #63143 — DataSketches HLL sketch aggregate (added the datasketches-cpp submodule this builds on)
- #26416, #56246 — related sketch / distinct-count discussions

### Are you willing to submit PR?

- [x] Yes I am willing to submit a PR!

### Code of Conduct

- [x] I agree to follow this project's [Code of Conduct](https://www.apache.org/foundation/policies/conduct)

Contributor guide

Open the contributing guide

Research direction

Start by reading the existing datasketches_hll_union_agg implementation and the contrib/datasketches-cpp submodule referenced in the issue, then compare their aggregate-state handling with approx_count_distinct and ndv. Define how uniq_theta should represent, merge, union, intersect, and difference serialized sketches, and validate completion against ClickHouse-compatible hashing, the stated error bound, and the requested pre-aggregated use cases.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, sql
Domain
databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.