apache / apache/druid

[Proposal]general exactly count distinct support in Druid

Open
#6,716 5 comments 1 reaction 0 assignees View on GitHub
Proposal stale
Dominant language
Java
Stars
14.1k
Forks
3.8k
Avg merge
2d 31m
Merged PRs (30d)
209

Description

the pr for branch master here:https://github.com/apache/incubator-druid/pull/7594
the pr for branch 0.12.x here:https://github.com/apache/incubator-druid/pull/7582

### **Motivation**
In many case, we need exactly count distinct, like charging.
But now, druid can not do well.

Now, there are three method in dimension:
1. cardinality aggregator: use HLL, not exact.
2. nested group by: exact, but need huge resource
3. http://druid.io/docs/latest/development/extensions-contrib/distinctcount.html : exact, but many limits
1) only one dimension
2) can not across intervals

one method in metrics:
1.HyperUnique/DataSketches aggregator: use HLL, faster than cardinality aggregator because pre-calculate at ingest , not exact

We need a more general method to support
1.more than one dimension
2.can across all intervals

**Design target**
1.Because exactly count distinct is not very needed in realtime ,We first will design to implement in offline Ingestion.
2.Only implement in metrics, so we can pre-calculate at ingest. If need count distinct a dimension, we can add a metric to do instead.
3.It will be a pluggable extension

**The detail design is divided into two parts.**
**1.One is** the how to convert different dim value(string/double/long) to a different global uniq int ID , and same dim value in different intervals will convert to the same ID, so roll up can be done across all intervals. We need a global dict to do this, which is a trieTreeDict for one column
And because the dict may be large, we put it on hdfs and build it with MapReduce.
And maybe two or more tasks build one dict, we need a zookeeper distribute lock to keep consistency.
about the trieTreeDict, we can simply reuse the data structure in apache kylin.
**2.and the other is** how to store uniq int IDs in druid metrics with least storage, so we need a new metrics type driven by bitmap.

**the overview design is like this**
![image](https://user-images.githubusercontent.com/2594619/56955281-864b3e80-6b73-11e9-9903-af6ce2567cec.png)

**the build process**
![image](https://user-images.githubusercontent.com/2594619/56953532-60239f80-6b6f-11e9-92ca-7c684c927044.png)

**Ingestion and query schema**
![image](https://user-images.githubusercontent.com/2594619/56953873-0bccef80-6b70-11e9-8050-6d8054102acc.png)

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the proposed designs and the referenced pull requests 7594 and 7582, focusing on the offline ingestion flow, global dictionary, and bitmap-based metric. Done would mean a general exact distinct-count metric supporting multiple dimensions and queries across intervals, with the proposed extension and ingestion constraints addressed.

Written by the indexing model from the issue text.

Assessment

Tech stack
hadoop, java
Domain
data-engineering, databases, distributed-systems
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.