[
https://issues.apache.org/jira/browse/IMPALA-10464?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17286369#comment-17286369
]
ASF subversion and git services commented on IMPALA-10464:
----------------------------------------------------------
Commit 65c6a81ed908084da2175e97664c0f76ded9aed8 in impala's branch
refs/heads/master from Fucun Chu
[ https://gitbox.apache.org/repos/asf?p=impala.git;h=65c6a81 ]
IMPALA-10463: Implement ds_theta_sketch() and ds_theta_estimate() functions
These functions can be used to get cardinality estimates of data
using Theta algorithm from Apache DataSketches. ds_theta_sketch()
receives a dataset, e.g. a column from a table, and returns a
serialized Theta sketch in string format. This can be written to a
table or be fed directly to ds_theta_estimate() that returns the
cardinality estimate for that sketch.
Similar to the HLL sketch, the primary use-case for the Theta sketch
is for counting distinct values as a stream, and then merging
multiple sketches together for a total distinct count.
For more details about Apache DataSketches' Theta see:
https://datasketches.apache.org/docs/Theta/ThetaSketchFramework.html
Testing:
- Added some tests running estimates for small datasets where the
amount of data is small enough to get the correct results.
- Ran manual tests on tpch25_parquet.lineitem to compare perfomance
with ds_hll_*. ds_theta_* is faster than ds_hll_* on the original
data, the difference is around 1%-10%. ds_hll_estimate() is faster
than ds_theta_estimate() on existing sketch. HLL and Theta gives
closer estimate except for string. see IMPALA-10464.
Change-Id: I14f24c16b815eec75cf90bb92c8b8b0363dcbfbc
Reviewed-on: http://gerrit.cloudera.org:8080/17008
Reviewed-by: Impala Public Jenkins <[email protected]>
Tested-by: Impala Public Jenkins <[email protected]>
> Performance comparison between ndv() ds_hll_* and ds_theta_* functions
> ----------------------------------------------------------------------
>
> Key: IMPALA-10464
> URL: https://issues.apache.org/jira/browse/IMPALA-10464
> Project: IMPALA
> Issue Type: New Feature
> Components: Perf Investigation
> Reporter: Fucun Chu
> Assignee: Fucun Chu
> Priority: Major
> Fix For: Not Applicable
>
>
> Perf comparison doc:
> [https://docs.google.com/spreadsheets/d/1ew7XCENs7wLxIVlr70bymUBP59YAGUCnNXTR0i_uzv0/edit#gid=0]
> General observations included in the doc.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
