[IMPALA-10439] Implement count(distinct) function (DataSketches/Theta)

• Type: Epic
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Component/s: Backend
• Epic Name: datasketches-theta
• Epic Color: ghx-label-13
• Assignee: Unassigned
• Reporter: Fucun Chu
• Created: 16/Jan/21 03:44
• Updated: 12/Jul/21 01:42

Description

Implement the count(distinct) function from the DataSketches library for Theta in C++.

Theta sketch provides approximate distinct counting with set operations (union, intersection and set difference).
This can be used for retention analysis, eg: "How many unique users signed up in week 1, and purchased something in week 2?"

General info about the sketch:
https://datasketches.apache.org/docs/Theta/ThetaSketchFramework.html

C++ implementation to wrap:
https://github.com/apache/datasketches-cpp/tree/master/theta

Using thetaSketch in Druid:
https://druid.apache.org/docs/latest/development/extensions-core/datasketches-theta.html