Druid Data Cookbook: Quantiles in Druid with Data Sketches

Let’s try some fun with data sketches in Apache Druid.

Data sketches are a way to get a good estimate of measures that you would normally only obtain by going through every single row of your data, which could become prohibitive as the amount of data grows.

One common example is counting unique things, such as visitors to a web site. But today I am going to look at quantiles sketches.

According to Wikipedia,

quantiles are cut points dividing the range of a probability distribution into continuous intervals with equal probabilities, or dividing the observations in a sample in the same way.

So, the 0.5-quantile of a variable is the cut point such that 50% of rows have a value less than or equal to it, and 50% are above it. The 0.5-quantile is also known as the median. For a standard bell curve, the median and the mean (average) coincide:

Likewise, the cut point such that 25% of values are less than or equal to it, is the first quartile. The median is the second quartile, and so on.

Quantiles are handy when trying to describe properties of distributions that are skewed or have outliers. This is something we are going to look at today.

Generating Data

First, let’s generate some data. I am logging down the incomes of a fictional population that is split into four segments:

• Segment A’s income is normal distributed (bell curve) with the peak at 10,000 and a standard deviation of 2,000.
• Segment B has a normal distribution too, but wider with a standard deviation of 10,000, so we can compare it to Segment C.
• Segment C’s income follows an exponential distribution with a mean of 10,000 (and a standard deviation of 10,000, that’s how the exponential distribution works.)
• Segment D has a bimodal distribution, with the majority of members making around 10,000, and a small group that peaks around 50,000. This is modeled as the weighted sum of two bell curves.

Here’s the code:

import time
import random
import json


def bimodal(m1, m2, s, p):

    if random.random() <= p:
        m = m1
    else:
        m = m2
    return random.gauss(m, s)


def main():
 
    distr = {
        'A': { 'fn': random.gauss,       'param': (10000, 2000) },
        'B': { 'fn': random.gauss,       'param': (10000, 10000) },
        'C': { 'fn': random.expovariate, 'param': (0.0001,) },
        'D': { 'fn': bimodal,            'param': (10000, 50000, 2000, 0.8) },
    }
    for i in range(0, 10000):
        grp = random.choices('ABCD', cum_weights=(0.50, 0.75, 0.90, 1.00), k=1)[0]
        rec = {
            'tn': time.time() - 10000 + i,
            'cn': grp,
            'rn': distr[grp]['fn'](*distr[grp]['param'])
        }
        print(json.dumps(rec))

if __name__ == "__main__":
    main()

Run this code to generate an input file for Druid, and set up ingestion using the Load data wizard. We are going to roll up the data with a query granularity of 15 minutes, and we want to have three metrics:

• the standard count metric
• the equally standard sum of salaries sum_rn so we can actually compute the mean salary for each segment
• a quantiles sketch over rn.

This is configured in the Configure schema section of the wizard like so:

You can set the segment granularity to HOUR.

Getting Quantiles

In order to work with data sketches, you would usually run a GROUP BY query, and run a sketch aggregation over the sketch field. In the case of quantiles sketches, the aggregator is DS_QUANTILES_SKETCH. On top of this, you can run sketch functions that do something useful.

Median vs. Mean

Let’s compute the median income for each population segment:

SELECT 
  cn, 
  DS_GET_QUANTILE(DS_QUANTILES_SKETCH(qs_rn, 128), 0.5) AS median_s,
  SUM(sum_rn) / SUM("count") AS mean_s
FROM randstream_salary
GROUP BY 1

(Since these are random numbers, your result will be slightly different.)

As we expected, for segments A and B the median and mean values coincide (more or less.) Segment C, the one with the exponential distribution, has a difference - the mean value is 1 / λ, the parameter of the distribution, while the median is ln(2) / λ, and ln(2) ≃ 0.693 so we’re good.

Segment D has the most pronounced discrepancy between mean and median - the median is well within the big first bump of the distribution and reflects what “most” of the population members can expect to earn. The mean shows a distorted picture because of the small subsegment of high earners:

Because the combination DS_GET_QUANTILE(DS_QUANTILES_SKETCH(...)) is so frequently used, you can use the shorthand APPROX_QUANTILE(expr, probability, [resolution]) instead.

Quartiles and More

Let’s beef up this query a bit. We want to know the salary thresholds for 25%, 50%, and 75% of the population of each segment, respectively:

SELECT 
  cn, 
  DS_GET_QUANTILE(DS_QUANTILES_SKETCH(qs_rn, 128), 0.25) AS q1_s,
  DS_GET_QUANTILE(DS_QUANTILES_SKETCH(qs_rn, 128), 0.5) AS q2_s,
  DS_GET_QUANTILE(DS_QUANTILES_SKETCH(qs_rn, 128), 0.75) AS q3_s,
  SUM(sum_rn) / SUM("count") AS mean_s
FROM randstream_salary
GROUP BY 1

We can now see the difference between A and B, B being much broader distributed. Also the skewedness of D becomes even clearer - more then 75% of that segment are concentrated within the lower peak!

There’s a nice way to return multiple quantile values from one function call using DS_GET_QUANTILES. This function takes a variable number of relative frequency values and returns the quantiles for all of them in an SQL array:

SELECT 
  cn,
  DS_GET_QUANTILES(DS_QUANTILES_SKETCH(qs_rn, 128), 0.25, 0.5, 0.75) AS quartiles_s
FROM randstream_salary
GROUP BY 1

Outlier Detection

Finally, quantiles are handy to find boundaries of a value range if we want to exclude outliers. This query:

SELECT 
  cn,
  DS_GET_QUANTILE(DS_QUANTILES_SKETCH(qs_rn, 128), 0.98) AS most_s,
  SUM(sum_rn) / SUM("count") AS mean_s
FROM randstream_salary
GROUP BY 1

will give the maximum salary of each segment, excluding extreme outliers.

Going The Other Way Round: Approximating Histograms and Cumulative Distribution Functions

There’s a set of functions that, in a sense, is the reverse of the quantiles functions. Until now we have given the algorithm a relative frequency (such as 0.5) and asked for the value of the random variable that represented the cutoff for that share. What if we ask the other way round:

For a given value of X = x, what share of the population represents a value less than or equal to x?

This brings us to the problem of approximating the cumulative distribution function (CDF). Luckily, Druid has us covered here too!

CDF for a single value

You can get an estimate for a single value of the CDF by calling … DS_RANK on an aggregated quantiles sketch.

Show me the percentage of members in each segment that earn less than $10k:

SELECT 
  cn,
  DS_RANK(DS_QUANTILES_SKETCH(qs_rn, 128), 10000) AS f10k_s
FROM randstream_salary
GROUP BY 1

No surprises here! Since distributions A and B have a median of 10k, the CDF value should be 0.5 (or close to it), and that’s what we got!

CDF for multiple values

We also have the capability to return estimates of the CDF at multiple points in an array. This function is aptly named DS_CDF:

SELECT 
  cn,
  DS_CDF(DS_QUANTILES_SKETCH(qs_rn, 128), 5000, 10000, 20000, 30000) AS ff_s
FROM randstream_salary
GROUP BY 1

Approximate Histograms

Finally, if we want to know how many people are in each of a defined set of buckets, we can use the DS_HISTOGRAM function:

SELECT 
  cn,
  DS_HISTOGRAM(DS_QUANTILES_SKETCH(qs_rn, 128), 5000, 10000, 20000, 30000) AS hist_s
FROM randstream_salary
GROUP BY 1

If you give it n cutoff points, it creates n + 1 buckets and estimates the number of records in each:

Learnings

• Quantiles sketches are a powerful tool for estimating the shape of a distribution of values.
• They can be used to find “representative” or “most typical” values, and to exclude outliers.
• Quantiles and CDF estimators complement each other.
• Each estimator exists in a version that returns a single value, and another one that returns multiple values in an array.

“This image is taken from Page 500 of Praktisches Kochbuch für die gewöhnliche und feinere Küche” by Medical Heritage Library, Inc. is licensed under CC BY-NC-SA 2.0 .