[jira] [Commented] (COUCHDB-2971) Provide cardinality estimate (COUNT DISTINCT) as builtin reducer

["Nick Vatamaniuc (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/COUCHDB-2971?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15204938#comment-15204938 ] 

Nick Vatamaniuc commented on COUCHDB-2971:
------------------------------------------

That would be neat to have. So if HLLs can be unioned then they satisfy the associativity and commutativity bit. 

So the algorithm could be if rereduce is false, then create an HLL object as an accumulator and add all keys to it, return that.  If it is true, then merge (union) together all HLL registers to produce a single HLL register (the hyper implementation above has that function).  It seems they'd need to be a final transformation of before returning the final result, extract estimated cardinality from the HLL object. Multiple precisions could be hacked together as a selection of <<"_distinct_hll_4">> or <<"_distinct_hll_6"">>, etc variants. 

> 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
>
> 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
(v6.3.4#6332)