DataSketches HLL Sketch module

This module provides Apache Druid aggregators for distinct counting based on HLL sketch from Apache DataSketches library. At ingestion time, this aggregator creates the HLL sketch objects to be stored in Druid segments. At query time, sketches are read and merged together. In the end, by default, you receive the estimate of the number of distinct values presented to the sketch. Also, you can use post aggregator to produce a union of sketch columns in the same row. You can use the HLL sketch aggregator on columns of any identifiers. It will return estimated cardinality of the column.

To use this aggregator, make sure you include the extension in your config file:

  1. druid.extensions.loadList=["druid-datasketches"]

Aggregators

propertydescriptionrequired?
typeThis String should be HLLSketchBuild or HLLSketchMergeyes
nameA String for the output (result) name of the calculation.yes
fieldNameA String for the name of the input field.yes
lgKlog2 of K that is the number of buckets in the sketch, parameter that controls the size and the accuracy. Must be between 4 and 21 inclusively.no, defaults to 12
tgtHllTypeThe type of the target HLL sketch. Must be HLL_4, HLL_6 or HLL_8no, defaults to HLL_4
roundRound off values to whole numbers. Only affects query-time behavior and is ignored at ingestion-time.no, defaults to false

The default lgK value has proven to be sufficient for most use cases; expect only very negligible improvements in accuracy with lgK values over 16 in normal circumstances.

HLLSketchBuild Aggregator

  1. {
  2.   "type" : "HLLSketchBuild",
  3.   "name" : <output name>,
  4.   "fieldName" : <metric name>,
  5.   "lgK" : <size and accuracy parameter>,
  6.   "tgtHllType" : <target HLL type>,
  7.   "round": <false | true>
  8.  }

It is very common to use HLLSketchBuild in combination with rollup to create a metric on high-cardinality columns. In this example, a metric called userid_hll is included in the metricsSpec. This will perform a HLL sketch on the userid field at ingestion time, allowing for highly-performant approximate COUNT DISTINCT query operations and improving roll-up ratios when userid is then left out of the dimensionsSpec.

  1. :
  2. "metricsSpec": [
  3.  {
  4.    "type" : "HLLSketchBuild",
  5.    "name" : "userid_hll",
  6.    "fieldName" : "userid",
  7.    "lgK" : 12,
  8.    "tgtHllType" : "HLL_4"
  9.  }
  10. ]
  11. :

HLLSketchMerge Aggregator

  1. {
  2.   "type" : "HLLSketchMerge",
  3.   "name" : <output name>,
  4.   "fieldName" : <metric name>,
  5.   "lgK" : <size and accuracy parameter>,
  6.   "tgtHllType" : <target HLL type>,
  7.   "round": <false | true>
  8.  }

Post Aggregators

Estimate

Returns the distinct count estimate as a double.

  1. {
  2.   "type"  : "HLLSketchEstimate",
  3.   "name": <output name>,
  4.   "field"  : <post aggregator that returns an HLL Sketch>,
  5.   "round" : <if true, round the estimate. Default is false>
  6. }

Estimate with bounds

Returns a distinct count estimate and error bounds from an HLL sketch. The result will be an array containing three double values: estimate, lower bound and upper bound. The bounds are provided at a given number of standard deviations (optional, defaults to 1). This must be an integer value of 1, 2 or 3 corresponding to approximately 68.3%, 95.4% and 99.7% confidence intervals.

  1. {
  2.   "type"  : "HLLSketchEstimateWithBounds",
  3.   "name": <output name>,
  4.   "field"  : <post aggregator that returns an HLL Sketch>,
  5.   "numStdDev" : <number of standard deviations: 1 (default), 2 or 3>
  6. }

Union

  1. {
  2.   "type"  : "HLLSketchUnion",
  3.   "name": <output name>,
  4.   "fields"  : <array of post aggregators that return HLL sketches>,
  5.   "lgK": <log2 of K for the target sketch>,
  6.   "tgtHllType" : <target HLL type>
  7. }

Sketch to string

Human-readable sketch summary for debugging.

  1. {
  2.   "type"  : "HLLSketchToString",
  3.   "name": <output name>,
  4.   "field"  : <post aggregator that returns an HLL Sketch>
  5. }