[
https://issues.apache.org/jira/browse/IMPALA-2658?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16839440#comment-16839440
]
Peter Ebert commented on IMPALA-2658:
-------------------------------------
Based on the research papers
[http://algo.inria.fr/flajolet/Publications/FlMa85.pdf] and
[https://ai.google/research/pubs/pub40671]
It has been some time since I read them but I do not recall seeing precisions
outside of that range in the research. Above 18 the register size becomes
quite large and smaller than 4 the accuracy was very low.
> Extend the NDV function to accept a precision
> ---------------------------------------------
>
> Key: IMPALA-2658
> URL: https://issues.apache.org/jira/browse/IMPALA-2658
> Project: IMPALA
> Issue Type: Improvement
> Components: Backend
> Affects Versions: Impala 2.2.4
> Reporter: Peter Ebert
> Priority: Minor
> Labels: ramp-up
> Attachments: Comparison of HLL Memory usage, Query Duration and
> Accuracy.jpg
>
>
> Hyperloglog algorithm used by NDV defaults to a precision of 10. Being able
> to set this precision would have two benefits:
> # Lower precision sizes can speed up the performance, as a precision of 9 has
> 1/2 the number of registers as 10 (exponential) and may be just as accurate
> depending on expected cardinality.
> # Higher precision can help with very large cardinalities (100 million to
> billion range) and will typically provide more accurate data. Those who are
> presenting estimates to end users will likely be willing to trade some
> performance cost for more accuracy, while still out performing the naive
> approach by a large margin.
> Propose adding the overloaded function NDV(expression, int precision)
> with accepted range between 18 and 4 inclusive.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
