You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by fj...@apache.org on 2019/03/06 01:06:43 UTC
[incubator-druid] branch 0.14.0-incubating updated: Add more
approximate algorithm docs (#7195) (#7196)
This is an automated email from the ASF dual-hosted git repository.
fjy pushed a commit to branch 0.14.0-incubating
in repository https://gitbox.apache.org/repos/asf/incubator-druid.git
The following commit(s) were added to refs/heads/0.14.0-incubating by this push:
new 62a655a Add more approximate algorithm docs (#7195) (#7196)
62a655a is described below
commit 62a655a14ef5f5c409b6a1480f938c81de23d7e1
Author: Jonathan Wei <jo...@users.noreply.github.com>
AuthorDate: Tue Mar 5 17:06:38 2019 -0800
Add more approximate algorithm docs (#7195) (#7196)
---
.../extensions-core/approximate-histograms.md | 6 ++++-
docs/content/development/extensions.md | 2 +-
docs/content/querying/aggregations.md | 31 ++++++++++++++++++++--
3 files changed, 35 insertions(+), 4 deletions(-)
diff --git a/docs/content/development/extensions-core/approximate-histograms.md b/docs/content/development/extensions-core/approximate-histograms.md
index ea9e17b..b60ff13 100644
--- a/docs/content/development/extensions-core/approximate-histograms.md
+++ b/docs/content/development/extensions-core/approximate-histograms.md
@@ -28,7 +28,11 @@ Make sure to [include](../../operations/including-extensions.html) `druid-histog
The `druid-histogram` extension provides an approximate histogram aggregator and a fixed buckets histogram aggregator.
-## Approximate Histogram aggregator
+## Approximate Histogram aggregator (Deprecated)
+
+<div class="note caution">
+The Approximate Histogram aggregator is deprecated. Please use <a href="../extensions-core/datasketches-quantiles.html">DataSketches Quantiles</a> instead which provides a superior distribution-independent algorithm with formal error guarantees.
+</div>
This aggregator is based on
[http://jmlr.org/papers/volume11/ben-haim10a/ben-haim10a.pdf](http://jmlr.org/papers/volume11/ben-haim10a/ben-haim10a.pdf)
diff --git a/docs/content/development/extensions.md b/docs/content/development/extensions.md
index d5f5531..91f6add 100644
--- a/docs/content/development/extensions.md
+++ b/docs/content/development/extensions.md
@@ -47,7 +47,7 @@ Core extensions are maintained by Druid committers.
|druid-caffeine-cache|A local cache implementation backed by Caffeine.|[link](../development/extensions-core/caffeine-cache.html)|
|druid-datasketches|Support for approximate counts and set operations with [DataSketches](http://datasketches.github.io/).|[link](../development/extensions-core/datasketches-extension.html)|
|druid-hdfs-storage|HDFS deep storage.|[link](../development/extensions-core/hdfs.html)|
-|druid-histogram|Approximate histograms and quantiles aggregator.|[link](../development/extensions-core/approximate-histograms.html)|
+|druid-histogram|Approximate histograms and quantiles aggregator. Deprecated, please use the [DataSketches quantiles aggregator](../development/extensions-core/datasketches-quantiles.html) from the `druid-datasketches` extension instead.|[link](../development/extensions-core/approximate-histograms.html)|
|druid-kafka-eight|Kafka ingest firehose (high level consumer) for realtime nodes.|[link](../development/extensions-core/kafka-eight-firehose.html)|
|druid-kafka-extraction-namespace|Kafka-based namespaced lookup. Requires namespace lookup extension.|[link](../development/extensions-core/kafka-extraction-namespace.html)|
|druid-kafka-indexing-service|Supervised exactly-once Kafka ingestion for the indexing service.|[link](../development/extensions-core/kafka-ingestion.html)|
diff --git a/docs/content/querying/aggregations.md b/docs/content/querying/aggregations.md
index c2d2c72..a9a819b 100644
--- a/docs/content/querying/aggregations.md
+++ b/docs/content/querying/aggregations.md
@@ -277,10 +277,16 @@ The [DataSketches Theta Sketch](../development/extensions-core/datasketches-thet
The [DataSketches HLL Sketch](../development/extensions-core/datasketches-hll.html) extension-provided aggregator gives distinct count estimates using the HyperLogLog algorithm. The HLL Sketch is faster and requires less storage than the Theta Sketch, but does not support intersection or difference operations.
-#### Cardinality/HyperUnique
+#### Cardinality/HyperUnique (Deprecated)
+
+<div class="note caution">
+The Cardinality and HyperUnique aggregators are deprecated. Please use <a href="../extensions-core/datasketches-hll.html">DataSketches HLL Sketch</a> instead.
+</div>
The [Cardinality and HyperUnique](../hll-old.html) aggregators are older aggregator implementations available by default in Druid that also provide distinct count estimates using the HyperLogLog algorithm. The newer [DataSketches HLL Sketch](../development/extensions-core/datasketches-hll.html) extension-provided aggregator has superior accuracy and performance and is recommended instead.
+The DataSketches team has published a [comparison study](https://datasketches.github.io/docs/HLL/HllSketchVsDruidHyperLogLogCollector.html) between Druid's original HLL algorithm and the DataSketches HLL algorithm. Based on the demonstrated advantages of the DataSketches implementation, we have deprecated Druid's original HLL aggregator.
+
Please note that DataSketches HLL aggregators and `hyperUnique` aggregators are not mutually compatible.
### Histograms and quantiles
@@ -289,10 +295,31 @@ Please note that DataSketches HLL aggregators and `hyperUnique` aggregators are
The [DataSketches Quantiles Sketch](../development/extensions-core/datasketches-quantiles.html) extension-provided aggregator provides quantile estimates and histogram approximations using the numeric quantiles DoublesSketch from the [datasketches](http://datasketches.github.io/) library.
-#### Approximate Histogram
+We recommend this aggregator in general for quantiles/histogram use cases, as it provides formal error bounds and has distribution-independent accuracy.
+
+#### Fixed Buckets Histogram
+
+Druid also provides a [simple histogram implementation]((../development/extensions-core/approxiate-histograms.html#fixed-buckets-histogram) that uses a fixed range and fixed number of buckets with support for quantile estimation, backed by an array of bucket count values.
+
+The fixed buckets histogram can perform well when the distribution of the input data allows a small number of buckets to be used.
+
+We do not recommend the fixed buckets histogram for general use, as its usefulness is extremely data dependent. However, it is made available for users that have already identified use cases where a fixed buckets histogram is suitable.
+
+#### Approximate Histogram (Deprecated)
The [Approximate Histogram](../development/extensions-core/approxiate-histograms.html) extension-provided aggregator also provides quantile estimates and histogram approximations, based on [http://jmlr.org/papers/volume11/ben-haim10a/ben-haim10a.pdf](http://jmlr.org/papers/volume11/ben-haim10a/ben-haim10a.pdf).
+The algorithm used by this deprecated aggregator is highly distribution-dependent and its output is subject to serious distortions when the input does not fit within the algorithm's limitations.
+
+A [study published by the DataSketches team](https://datasketches.github.io/docs/Quantiles/DruidApproxHistogramStudy.html) demonstrates some of the known failure modes of this algorithm:
+- The algorithm's quantile calculations can fail to provide results for a large range of rank values (all ranks less than 0.89 in the example used in the study), returning all zeroes instead.
+- The algorithm can completely fail to record spikes in the tail ends of the distribution
+- In general, the histogram produced by the algorithm can deviate significantly from the true histogram, with no bounds on the errors.
+
+It is not possible to determine a priori how well this aggregator will behave for a given input stream, nor does the aggregator provide any indication that serious distortions are present in the output.
+
+For these reasons, we have deprecated this aggregator and do not recommend its use.
+
## Miscellaneous Aggregations
### Filtered Aggregator
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org