Uploaded image for project: 'CouchDB'
  1. CouchDB
  2. COUCHDB-2971

Provide cardinality estimate (COUNT DISTINCT) as builtin reducer

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 2.2
    • Component/s: None
    • Labels:
      None

      Description

      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.

        Attachments

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              kocolosk Adam Kocoloski
            • Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: