[
https://issues.apache.org/jira/browse/COUCHDB-2971?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16492798#comment-16492798
]
Adam Kocoloski commented on COUCHDB-2971:
-----------------------------------------
I rebased this branch and did subtree merges to pull in the commits on the
various repos that have since been merged into the main one.
After looking around a bit I think this reducer should be renamed
`_approx_count_distinct` as that seems to be an emerging standard. Examples
include
Google BigQuery:
[https://cloud.google.com/bigquery/docs/reference/standard-sql/functions-and-operators#approx_count_distinct]
MemSQL: [https://docs.memsql.com/sql-reference/v6.0/approx_count_distinct/]
Oracle: [https://docs.oracle.com/database/121/SQLRF/functions013.htm#SQLRF56900]
Apache Spark:
[https://spark.apache.org/docs/2.3.0/api/java/org/apache/spark/sql/functions.html]
I also noted that each of these implementations returns an integer as a
response. I spot-checked Spark's implementation and confirmed that it rounds
the estimate:
[https://github.com/apache/spark/blob/1270e7/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/util/HyperLogLogPlusPlusHelper.scala#L239]
I propose we do the same.
The other interesting observation is that BigQuery allows the user direct
access to the sketch via `HLL_COUNT.INIT()` which allows computing a distinct
count across datasets:
[https://cloud.google.com/blog/big-data/2017/07/counting-uniques-faster-in-bigquery-with-hyperloglog]
I can certainly see the use case there, and it would be technically easy to
expose this, but without a ready-made function to merge the individual sketches
I don't think it would get much adoption. So I'd say leave that out for now and
keep things simple.
> Provide cardinality estimate (COUNT DISTINCT) as builtin reducer
> ----------------------------------------------------------------
>
> Key: COUCHDB-2971
> URL: https://issues.apache.org/jira/browse/COUCHDB-2971
> Project: CouchDB
> Issue Type: Improvement
> Reporter: Adam Kocoloski
> Priority: Major
> Attachments: rebar.config.script
>
>
> We’ve seen a number of applications now where a user needs to count the
> number of unique keys in a view. Currently the recommended approach is to add
> a trivial reduce function and then count the number of rows in a _list
> function or client-side application code, but of course that doesn’t scale
> nicely.
> It seems that in a majority of these cases all that’s required is an
> approximation of the number of distinct entries, which brings us into the
> space of hash sets, linear probabilistic counters, and the ever-popular
> “HyperLogLog” algorithm. Taking HLL specifically, this seems like quite a
> nice candidate for a builtin reduce. The size of the data structure is
> independent of the number of input elements and individual HLL filters can be
> unioned together. There’s already what seems to be a good MIT-licensed
> implementation on GitHub:
> https://github.com/GameAnalytics/hyper
> One caveat is that this reducer would not work for group_level reductions;
> it’d only give the correct result for the exact key. I don’t think that
> should preclude us from evaluating it.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
