Mailing-List: contact dev-help@phoenix.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@phoenix.apache.org
Date: Wed, 6 Sep 2017 07:01:17 +0000 (UTC)
From: "James Taylor (JIRA)" <jira@apache.org>
To: dev@phoenix.apache.org
Message-ID: <JIRA.13099935.1504643990000.36649.1504681277408@Atlassian.JIRA>
In-Reply-To: <JIRA.13099935.1504643990000@Atlassian.JIRA>
References: <JIRA.13099935.1504643990000@Atlassian.JIRA> <JIRA.13099935.1504643990139@jira-lw-us.apache.org>
Subject: [jira] [Commented] (PHOENIX-4160) research for a proper hash size
 set for APPROX_COUNT_DISTINCT
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
archived-at: Wed, 06 Sep 2017 07:01:27 -0000


    [ https://issues.apache.org/jira/browse/PHOENIX-4160?page=3Dcom.atlassi=
an.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=3D16=
154912#comment-16154912 ]=20

James Taylor commented on PHOENIX-4160:
---------------------------------------

[~lhofhansl] - likely a duplicate of PHOENIX-4164? [~aertoria] has some gre=
at pointers - what's your opinion on the best way to go?

> research for a proper hash size set for APPROX_COUNT_DISTINCT
> -------------------------------------------------------------
>
>                 Key: PHOENIX-4160
>                 URL: https://issues.apache.org/jira/browse/PHOENIX-4160
>             Project: Phoenix
>          Issue Type: Improvement
>         Environment:=20
>            Reporter: Ethan Wang
>
> Now after -PHOENIX-418- finishes, we want to study to find a proper defau=
lt size for hll hash. Currently the hash size is hard coded as 25/16 bits b=
y default (a design we follow Apache Druid. discussion see CALCITE-1588).
> Note:
> 1, the std error of hyperloglog is bound by 1/sqrt(size of hash). i.e.,  =
{code:java}sqrt(3\*ln(2)-1)/sqrt(2^precision){code} Detail see the page 129=
 of this [paper|http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf].
> To try on a bigger size, the performance of hll under different bucket/ha=
sh size has been studied here: https://metron.apache.org/current-book/metro=
n-analytics/metron-statistics/HLLP.html
> 2, When the estimate cardinalities is large enough, as Timok and Flajolet=
 et al found out, this performance of hll will become problematic because t=
he hash collisions (saturation). In fact, Timok proposed that any number la=
rger than {code}2^{32}/30{code} should consider "to large" for a 32 bit has=
h. See study [Google=E2=80=99s Take On Engineering HLL|https://research.neu=
star.biz/2013/01/24/hyperloglog-googles-take-on-engineering-hll/] and sugge=
sted by the Figure 8 of this [paper|https://stefanheule.com/papers/edbt13-h=
yperloglog.pdf]


--
This message was sent by Atlassian JIRA
(v6.4.14#64029)