[Feature] Add uniq_theta: a Theta-sketch based approximate distinct-count aggregate function
- 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
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