DataSketches Quantiles Sketch module

This module provides Apache Druid aggregators based on numeric quantiles DoublesSketch from Apache DataSketches library. Quantiles sketch is a mergeable streaming algorithm to estimate the distribution of values, and approximately answer queries about the rank of a value, probability mass function of the distribution (PMF) or histogram, cumulative distribution function (CDF), and quantiles (median, min, max, 95th percentile and such). See Quantiles Sketch Overview.

There are three major modes of operation:

  1. Ingesting sketches built outside of Druid (say, with Pig or Hive)
  2. Building sketches from raw data during ingestion
  3. Building sketches from raw data at query time

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

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

Aggregator

The result of the aggregation is a DoublesSketch that is the union of all sketches either built from raw data or read from the segments.

  1. {
  2. "type" : "quantilesDoublesSketch",
  3. "name" : <output_name>,
  4. "fieldName" : <metric_name>,
  5. "k": <parameter that controls size and accuracy>
  6. }
propertydescriptionrequired?
typeThis String should always be “quantilesDoublesSketch”yes
nameA String for the output (result) name of the calculation.yes
fieldNameA String for the name of the input field (can contain sketches or raw numeric values).yes
kParameter that determines the accuracy and size of the sketch. Higher k means higher accuracy but more space to store sketches. Must be a power of 2 from 2 to 32768. See accuracy information in the DataSketches documentation for details.no, defaults to 128
maxStreamLengthThis parameter is a temporary solution to avoid a known issue. It may be removed in a future release after the bug is fixed. This parameter defines the maximum number of items to store in each sketch. If a sketch reaches the limit, the query can throw IllegalStateException. To workaround this issue, increase the maximum stream length. See accuracy information in the DataSketches documentation for how many bytes are required per stream length.no, defaults to 1000000000

Post Aggregators

Quantile

This returns an approximation to the value that would be preceded by a given fraction of a hypothetical sorted version of the input stream.

  1. {
  2. "type" : "quantilesDoublesSketchToQuantile",
  3. "name": <output name>,
  4. "field" : <post aggregator that refers to a DoublesSketch (fieldAccess or another post aggregator)>,
  5. "fraction" : <fractional position in the hypothetical sorted stream, number from 0 to 1 inclusive>
  6. }

Quantiles

This returns an array of quantiles corresponding to a given array of fractions

  1. {
  2. "type" : "quantilesDoublesSketchToQuantiles",
  3. "name": <output name>,
  4. "field" : <post aggregator that refers to a DoublesSketch (fieldAccess or another post aggregator)>,
  5. "fractions" : <array of fractional positions in the hypothetical sorted stream, number from 0 to 1 inclusive>
  6. }

Histogram

This returns an approximation to the histogram given an array of split points that define the histogram bins or a number of bins (not both). An array of m unique, monotonically increasing split points divide the real number line into m+1 consecutive disjoint intervals. The definition of an interval is inclusive of the left split point and exclusive of the right split point. If the number of bins is specified instead of split points, the interval between the minimum and maximum values is divided into the given number of equally-spaced bins.

  1. {
  2. "type" : "quantilesDoublesSketchToHistogram",
  3. "name": <output name>,
  4. "field" : <post aggregator that refers to a DoublesSketch (fieldAccess or another post aggregator)>,
  5. "splitPoints" : <array of split points (optional)>,
  6. "numBins" : <number of bins (optional, defaults to 10)>
  7. }

Rank

This returns an approximation to the rank of a given value that is the fraction of the distribution less than that value.

  1. {
  2. "type" : "quantilesDoublesSketchToRank",
  3. "name": <output name>,
  4. "field" : <post aggregator that refers to a DoublesSketch (fieldAccess or another post aggregator)>,
  5. "value" : <value>
  6. }

CDF

This returns an approximation to the Cumulative Distribution Function given an array of split points that define the edges of the bins. An array of m unique, monotonically increasing split points divide the real number line into m+1 consecutive disjoint intervals. The definition of an interval is inclusive of the left split point and exclusive of the right split point. The resulting array of fractions can be viewed as ranks of each split point with one additional rank that is always 1.

  1. {
  2. "type" : "quantilesDoublesSketchToCDF",
  3. "name": <output name>,
  4. "field" : <post aggregator that refers to a DoublesSketch (fieldAccess or another post aggregator)>,
  5. "splitPoints" : <array of split points>
  6. }

Sketch Summary

This returns a summary of the sketch that can be used for debugging. This is the result of calling toString() method.

  1. {
  2. "type" : "quantilesDoublesSketchToString",
  3. "name": <output name>,
  4. "field" : <post aggregator that refers to a DoublesSketch (fieldAccess or another post aggregator)>
  5. }