Contents

• ddsketch extension
  • Basic usage
  • Accuracy
  • Advanced usage
  • Pre-aggregated data
  • Incremental updates
  • Trimmed aggregates
  • Functions
    • ddsketch_percentile(value, alpha, nbuckets, percentile)
    • ddsketch_percentile(value, count, alpha, nbuckets, percentile)
    • ddsketch_percentile(value, alpha, nbuckets, percentile[])
    • ddsketch_percentile(value, count, alpha, nbuckets, percentile[])
    • ddsketch_percentile_of(value, alpha, nbuckets, hypothetical_value)
    • ddsketch_percentile_of(value, count, alpha, nbuckets, hypothetical_value)
    • ddsketch_percentile_of(value, alpha, nbuckets, hypothetical_value[])
    • ddsketch_percentile_of(value, count, alpha, nbuckets, hypothetical_value[])
    • ddsketch(value, alpha, nbuckets)
    • ddsketch(value, count, alpha, nbuckets)
    • ddsketch_count(ddsketch)
    • ddsketch_percentile(ddsketch, percentile)
    • ddsketch_percentile(sketch, percentile[])
    • ddsketch_percentile_of(sketch, hypothetical_value)
    • ddsketch_percentile_of(sketch, hypothetical_value[])
    • ddsketch_add(ddsketch, double precision)
    • ddsketch_add(ddsketch, double precision[])
    • ddsketch_union(ddsketch, ddsketch)
    • ddsketch_sum(value, alpha, nbuckets, low, high)
    • ddsketch_sum(value, count, alpha, nbuckets, low, high)
    • ddsketch_sum(sketch, low, high)
    • ddsketch_avg(value, alpha, nbuckets, low, high)
    • ddsketch_avg(value, count, alpha, nbuckets, low, high)
    • ddsketch_avg(sketch, low, high)
    • ddsketch_sketch_sum(sketch, low, high)
    • ddsketch_sketch_avg(sketch, low, high)
  • Notes
  • License

ddsketch extension

:warning: Warning: This extension is still an early WIP version, not suitable for production use. The on-disk format, function signatures etc. may change and so on.

This PostgreSQL extension implements ddsketch, a data structure for on-line accumulation of quantiles, as described in a paper

DDSketch: A Fast and Fully-Mergeable Quantile Sketch with
Relative-Error Guarantees, Charles Masson, Jee E. Rim, Homin K. Lee,
Proceedings of the VLDB Endowment, Vol. 12, No. 12, ISSN 2150-8097
DOI: https://doi.org/10.14778/3352063.3352135

The algorithm is very friendly to parallel programs, fully mergeable, etc. A second paper published in 2020 introduces a variant of the sketch, using a more elaborate procedure when collapsing buckets

UDDSketch: Accurate Tracking of Quantiles in Data Streams; Italo
Epicoco, Catiuscia Melle, Massimo Cafaro, Marco Pulimeno, Giuseppe
Morleo; https://arxiv.org/abs/2004.08604

This allows providing formal accuracy guarantees even for sketches with collapsed buckets, which is not possible for ddsketch.

Basic usage

The extension provides two functions, which you can see as a replacement of percentile_cont aggregate:

• ddsketch_percentile(value double precision, alpha double precision, nbuckets int, quantile double precision)

• ddsketch_percentile(value double precision, alpha double precision, nbuckets int, quantiles double precision[])

• ddsketch_percentile_of(value double precision, alpha double precision, nbuckets int, value double precision)

• ddsketch_percentile_of(value double precision, alpha double precision, nbuckets int, values double precision[])

That is, instead of running

SELECT percentile_cont(0.95) WITHIN GROUP (ORDER BY a) FROM t

you might now run

SELECT ddsketch_percentile(a, 0.05, 1024, 0.95) FROM t

and similarly for the variants with array of percentiles. This should run much faster, as the ddsketch does not require any sorting of the data and can be parallelized. Also, the memory usage is very limited, depending on the alpha and nbuckets parameters.

Accuracy

All functions building the ddsketch summaries accept alpha parameter that determines how closely is the CDF approximated. The value limits the size of the “buckets” in the ddsketch, so the lower the value the larger the sketch.

Each bucket is represented by a single 8B counter, so 1000 buckets means the ddsketch is ~8kB. That is however before the transparent compression all varlena types go through, so the on-disk size may be much smaller.

Advanced usage

The extension also provides a ddsketch data type, which makes it possible to precompute sketches for subsets of data, and then quickly combine those “partial” sketched into a sketch representing the whole data set. Those prebuilt sketches should be much smaller compared to the original data set, allowing significantly faster response times.

To compute the ddsketch use ddsketch aggregate function. The sketches can then be stored on disk and later summarized using the ddsketch_percentile functions (with ddsketch as the first argument).

• ddsketch(value double precision, alpha double precision, nbuckets int)

• ddsketch_percentile(sketch ddsketch, alpha double precision, nbuckets int, quantile double precision)

• ddsketch_percentile(sketch ddsketch, alpha double precision, nbuckets int, quantiles double precision[])

• ddsketch_percentile_of(sketch ddsketch, alpha double precision, nbuckets int, value double precision)

• ddsketch_percentile_of(sketch ddsketch, alpha double precision, nbuckets int, values double precision[])

So for example you may do this:

-- table with some random source data
CREATE TABLE t (a int, b int, c double precision);

INSERT INTO t SELECT 1000 * random(), 1000 * random(), 1000 * random()
                FROM generate_series(1,10000000);

-- table with pre-aggregated sketches into table "p"
CREATE TABLE p AS SELECT a, b, ddsketch(c, 0.05, 1024) AS d FROM t GROUP BY a, b;

-- summarize the data from "p" (compute the 95-th percentile)
SELECT a, ddsketch_percentile(d, 0.95) FROM p GROUP BY a ORDER BY a;

The pre-aggregated table is indeed much smaller:

db=# \d+
                                  List of relations
 Schema | Name | Type  | Owner | Persistence | Access method |  Size   | Description 
--------+------+-------+-------+-------------+---------------+---------+-------------
 public | p    | table | user  | permanent   | heap          | 2264 kB | 
 public | t    | table | user  | permanent   | heap          | 422 MB  | 
(2 rows)

And on my machine the last query takes ~1.5ms. Compare that to queries on the source data:

\timing on

-- exact results
SELECT a, percentile_cont(0.95) WITHIN GROUP (ORDER BY c)
  FROM t GROUP BY a ORDER BY a;
  ...
Time: 6956.566 ms (00:06.957)

-- ddsketch estimate (no parallelism)
SET max_parallel_workers_per_gather = 0;
SELECT a, ddsketch_percentile(c, 0.05, 1024, 0.95) FROM t GROUP BY a ORDER BY a;
  ...
Time: 2873.116 ms (00:02.873)

-- ddsketch estimate (4 workers)
SET max_parallel_workers_per_gather = 4;
SELECT a, ddsketch_percentile(c, 0.05, 1024, 0.95) FROM t GROUP BY a ORDER BY a;
  ...
Time: 893.538 ms

This shows how much more efficient the ddsketch estimate is compared to the exact query with percentile_cont (the difference would increase for larger data sets, due to increased overhead for spilling to disk).

It also shows how effective the pre-aggregation can be. There are 121 rows in table p so with 2264kB disk space that’s ~20kB per row, each representing about 80k values. With 8B per value, that’s ~640kB, i.e. a compression ratio of 30:1. As the sketch size is not tied to the number of items, this will only improve for larger data set.

Pre-aggregated data

When dealing with data sets with a lot of redundancy (values repeating many times), it may be more efficient to partially pre-aggregate the data and use functions that allow specifying the number of occurrences for each value. This reduces the number of SQL-function calls.

There are five such aggregate functions:

• ddsketch_percentile(value double precision, count bigint, compression int, quantile double precision)

• ddsketch_percentile(value double precision, count bigint, compression int, quantiles double precision[])

• ddsketch_percentile_of(value double precision, count bigint, compression int, value double precision)

• ddsketch_percentile_of(value double precision, count bigint, compression int, values double precision[])

• ddsketch(value double precision, count bigint, compression int)

Incremental updates

An existing ddsketch may be updated incrementally, either by adding a single value, or by merging-in a whole ddsketch. For example, it’s possible to add 1000 random values to the ddsketch like this:

DO LANGUAGE plpgsql $$
DECLARE
  r record;
BEGIN
  FOR r IN (SELECT random() AS v FROM generate_series(1,1000)) LOOP
    UPDATE t SET d = ddsketch_add(d, r.v);
  END LOOP;
END $$;

The overhead of doing this is fairly high, though - the ddsketch has to be deserialized and serialized over and over, for each value we’re adding. That overhead may be reduced by pre-aggregating data, either into an array or a ddsketch.

DO LANGUAGE plpgsql $$
DECLARE
  a double precision[];
BEGIN
  SELECT array_agg(random()) INTO a FROM generate_series(1,1000);
  UPDATE t SET d = ddsketch_add(d, a);
END $$;

Alternatively, it’s possible to use pre-aggregated sketch values instead of the arrays:

DO LANGUAGE plpgsql $$
DECLARE
  r record;
BEGIN
  FOR r IN (SELECT mod(i,3) AS a, ddsketch(random(), 0.05, 1024) AS d FROM generate_series(1,1000) s(i) GROUP BY mod(i,3)) LOOP
    UPDATE t SET d = ddsketch_union(d, r.d);
  END LOOP;
END $$;

Trimmed aggregates

The extension provides several variants of trimmed (truncated) average and sum aggregates, both for individual values and pre-aggregated sketches.

• ddsketch_sum(value double precision, alpha double precision, nbuckets int, low double precision, high double precision)

• ddsketch_sum(value double precision, count bigint, alpha double precision, nbuckets int, low double precision, high double precision)

• ddsketch_sum(sketch ddsketch, low double precision, high double precision)

• ddsketch_avg(value double precision, alpha double precision, nbuckets int, low double precision, high double precision)

• ddsketch_avg(value double precision, count bigint, alpha double precision, nbuckets int, low double precision, high double precision)

• ddsketch_avg(sketch ddsketch, low double precision, high double precision)

The extension also provides two regular functions allowing to calculate trimmed (truncated) sum and average from an existing sketch.

• ddsketch_sketch_sum(digest ddsketch, low double precision, high double precision)

• ddsketch_sketch_avg(digest ddsketch, low double precision, high double precision)

The low and high parameters specify where to truncate the data. This is useful when processing individual sketches without having to add an unnecessary aggregation.

Functions

ddsketch_percentile(value, alpha, nbuckets, percentile)

Computes a requested percentile from the data, using a sketch with the specified accuracy.

Synopsis

SELECT ddsketch_percentile(t.c, 0.05, 1024, 0.95) FROM t

Parameters

• value - values to aggregate
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch
• percentile - value in [0, 1] specifying the percentile

ddsketch_percentile(value, count, alpha, nbuckets, percentile)

Computes a requested percentile from the data, using a sketch with the specified accuracy.

Synopsis

SELECT ddsketch_percentile(t.c, t.a, 0.05, 1024, 0.95) FROM t

Parameters

• value - values to aggregate
• count - number of occurrences of the value
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch
• percentile - value in [0, 1] specifying the percentile

ddsketch_percentile(value, alpha, nbuckets, percentile[])

Computes requested percentiles from the data, using a sketch with the specified accuracy.

Synopsis

SELECT ddsketch_percentile(t.c, 0.05, 1024, ARRAY[0.95, 0.99]) FROM t

Parameters

• value - values to aggregate
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch
• percentile[] - array of values in [0, 1] specifying the percentiles

ddsketch_percentile(value, count, alpha, nbuckets, percentile[])

Computes requested percentiles from the data, using a sketch with the specified accuracy.

Synopsis

SELECT ddsketch_percentile(t.c, t.a, 0.05, 1024, ARRAY[0.95, 0.99]) FROM t

Parameters

• value - values to aggregate
• count - number of occurrences of the value
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch
• percentile[] - array of values in [0, 1] specifying the percentiles

ddsketch_percentile_of(value, alpha, nbuckets, hypothetical_value)

Computes relative rank of a hypothetical value, using a sketch with the specified accuracy.

Synopsis

SELECT ddsketch_percentile_of(t.c, 0.05, 1024, 139832.3) FROM t

Parameters

• value - values to aggregate
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch
• hypothetical_value - hypothetical value

ddsketch_percentile_of(value, count, alpha, nbuckets, hypothetical_value)

Computes relative rank of a hypothetical value, using a sketch with the specified accuracy.

Synopsis

SELECT ddsketch_percentile_of(t.c, t.a, 0.05, 1024, 139832.3) FROM t

Parameters

• value - values to aggregate
• count - number of occurrences of the value
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch
• hypothetical_value - hypothetical value

ddsketch_percentile_of(value, alpha, nbuckets, hypothetical_value[])

Computes relative ranks of a hypothetical values, using a sketch with the specified accuracy.

Synopsis

SELECT ddsketch_percentile_of(t.c, 0.05, 1024, ARRAY[6343.43, 139832.3]) FROM t

Parameters

• value - values to aggregate
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch
• hypothetical_value - hypothetical values

ddsketch_percentile_of(value, count, alpha, nbuckets, hypothetical_value[])

Computes relative ranks of a hypothetical values, using a sketch with the specified accuracy.

Synopsis

SELECT ddsketch_percentile_of(t.c, t.a, 0.05, 1024, ARRAY[6343.43, 139832.3]) FROM t

Parameters

• value - values to aggregate
• count - number of occurrences of the value
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch
• hypothetical_value - hypothetical values

ddsketch(value, alpha, nbuckets)

Computes sketch with the specified accuracy.

Synopsis

SELECT ddsketch(t.c, 0.05, 1024) FROM t

Parameters

• value - values to aggregate
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch

ddsketch(value, count, alpha, nbuckets)

Computes sketch with the specified accuracy. The values are added with as many occurrences as determined by the count parameter.

Synopsis

SELECT ddsketch(t.c, t.a, 0.05, 1024) FROM t

Parameters

• value - values to aggregate
• count - number of occurrences for each value
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch

ddsketch_count(ddsketch)

Returns number of items represented by the sketch.

Synopsis

SELECT ddsketch_count(d) FROM (
    SELECT ddsketch(t.c, 0.05, 1024) FROM t
) foo

ddsketch_percentile(ddsketch, percentile)

Computes requested percentile from the pre-computed ddsketch.

Synopsis

SELECT ddsketch_percentile(d, 0.99) FROM (
    SELECT ddsketch(t.c, 0.05, 1024) FROM t
) foo

Parameters

• sketch - ddsketch to aggregate and process
• percentile - value in [0, 1] specifying the percentile

ddsketch_percentile(sketch, percentile[])

Computes requested percentiles from the pre-computed ddsketch.

Synopsis

SELECT ddsketch_percentile(d, ARRAY[0.95, 0.99]) FROM (
    SELECT ddsketch(t.c, 0.05, 1024) FROM t
) foo

Parameters

• sketch - sketch to aggregate and process
• percentile - values in [0, 1] specifying the percentiles

ddsketch_percentile_of(sketch, hypothetical_value)

Computes relative rank of a hypothetical value, using a pre-computed sketch.

Synopsis

SELECT ddsketch_percentile_of(d, 349834.1) FROM (
    SELECT ddsketch(t.c, 0.05, 1024) FROM t
) foo

Parameters

• sketch - ddsketch to aggregate and process
• hypothetical_value - hypothetical value

ddsketch_percentile_of(sketch, hypothetical_value[])

Computes relative ranks of hypothetical values, using a pre-computed sketch.

Synopsis

SELECT ddsketch_percentile_of(d, ARRAY[438.256, 349834.1]) FROM (
    SELECT ddsketch(t.c, 0.05, 1024) FROM t
) foo

Parameters

• sketch - ddsketch to aggregate and process
• hypothetical_value - hypothetical values

ddsketch_add(ddsketch, double precision)

Performs incremental update of the sketch by adding a single value.

Synopsis

UPDATE t SET d = ddsketch_add(d, random());

Parameters

• sketch - ddsketch to update
• element - value to add to the sketch
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch

ddsketch_add(ddsketch, double precision[])

Performs incremental update of the sketch by adding values from an array.

Synopsis

UPDATE t SET d = ddsketch_add(d, ARRAY[random(), random(), random()]);

Parameters

• sketch - ddsketch to update
• elements - array of values to add to the sketch
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch

ddsketch_union(ddsketch, ddsketch)

Performs incremental update of the sketch by merging-in another sketch.

Synopsis

WITH x AS (SELECT ddsketch(random(), 0.05, 1024) AS d FROM generate_series(1,1000))
UPDATE t SET d = ddsketch_union(t.d, x.d) FROM x;

Parameters

• ddsketch - ddsketch to update
• ddsketch_add - sketch to merge into sketch
• alpha - accuracy of the sketch
• nbuckets - number of buckets in the sketch

ddsketch_sum(value, alpha, nbuckets, low, high)

Computes trimmed sum of values, discarding values at the low and high end. The low and high values specify which part of the sample should be included in the result, so e.g. low = 0.1 and high = 0.9 means 10% low and high values will be discarded.

Synopsis

SELECT ddsketch_sum(t.v, 0.05, 1024, 0.1, 0.9) FROM t

Parameters

• value - values to aggregate
• alpha - accuracy of the t-digest
• nbuckets - number of buckets in the sketch
• low - low threshold percentile (values below are discarded)
• high - high threshold percentile (values above are discarded)

ddsketch_sum(value, count, alpha, nbuckets, low, high)

Computes trimmed sum of values, discarding values at the low and high end. The low and high values specify which part of the sample should be included in the result, so e.g. low = 0.1 and high = 0.9 means 10% low and high values will be discarded.

Synopsis

SELECT ddsketch_sum(t.v, t.c, 0.05, 1024, 0.1, 0.9) FROM t

Parameters

• value - values to aggregate
• count - number of occurrences of the value
• alpha - accuracy of the t-digest
• nbuckets - number of buckets in the sketch
• low - low threshold percentile (values below are discarded)
• high - high threshold percentile (values above are discarded)

ddsketch_sum(sketch, low, high)

Computes trimmed sum of values, discarding values at the low and high end. The low and high values specify which part of the sample should be included in the result, so e.g. low = 0.1 and high = 0.9 means 10% low and high values will be discarded.

Synopsis

SELECT ddsketch_sum(d, 0.1, 0.9) FROM (
    SELECT ddsketch(t.c, 0.05, 1024) FROM t
) foo

Parameters

• count - number of occurrences of the value
• low - low threshold percentile (values below are discarded)
• high - high threshold percentile (values above are discarded)

ddsketch_avg(value, alpha, nbuckets, low, high)

Computes trimmed average of values, discarding values at the low and high end. The low and high values specify which part of the sample should be included in the result, so e.g. low = 0.1 and high = 0.9 means 10% low and high values will be discarded.

Synopsis

SELECT ddsketch_avg(t.v, 0.05, 1024, 0.1, 0.9) FROM t

Parameters

• value - values to aggregate
• alpha - accuracy of the t-digest
• nbuckets - number of buckets in the sketch
• low - low threshold percentile (values below are discarded)
• high - high threshold percentile (values above are discarded)

ddsketch_avg(value, count, alpha, nbuckets, low, high)

Computes trimmed average of values, discarding values at the low and high end. The low and high values specify which part of the sample should be included in the result, so e.g. low = 0.1 and high = 0.9 means 10% low and high values will be discarded.

Synopsis

SELECT ddsketch_avg(t.v, 0.05, 1024, 0.1, 0.9) FROM t

Parameters

• value - values to aggregate
• count - number of occurrences of the value
• alpha - accuracy of the t-digest
• nbuckets - number of buckets in the sketch
• low - low threshold percentile (values below are discarded)
• high - high threshold percentile (values above are discarded)

ddsketch_avg(sketch, low, high)

Computes trimmed average of values, discarding values at the low and high end. The low and high values specify which part of the sample should be included in the result, so e.g. low = 0.1 and high = 0.9 means 10% low and high values will be discarded.

Synopsis

SELECT ddsketch_avg(d, 0.1, 0.9) FROM (
    SELECT ddsketch(t.c, 0.05, 1024) FROM t
) foo

Parameters

• sketch - ddsketch to aggregate and process
• low - low threshold percentile (values below are discarded)
• high - high threshold percentile (values above are discarded)

ddsketch_sketch_sum(sketch, low, high)

Calculates trimmed sum from a single sketch, without aggregation. The low and high values specify which part of the sample should be included in the result, so e.g. low = 0.1 and high = 0.9 means 10% low and high values will be discarded.

Synopsis

SELECT ddsketch_sketch_sum(
    (SELECT ddsketch(t.c, 0.05, 1024) FROM t),
    0.1, 0.9)

Parameters

• sketch - ddsketch to calculate trimmed sum for
• low - low threshold percentile (values below are discarded)
• high - high threshold percentile (values above are discarded)

ddsketch_sketch_avg(sketch, low, high)

Calculates trimmed average from a single sketch, without aggregation. The low and high values specify which part of the sample should be included in the result, so e.g. low = 0.1 and high = 0.9 means 10% low and high values will be discarded.

Synopsis

SELECT ddsketch_sketch_avg(
    (SELECT ddsketch(t.c, 0.05, 1024) FROM t),
    0.1, 0.9)

Parameters

• sketch - ddsketch to calculate trimmed average for
• low - low threshold percentile (values below are discarded)
• high - high threshold percentile (values above are discarded)

Notes

At the moment, the extension only supports double precision values, but it should not be very difficult to extend it to other numeric types (both integer and/or floating point, including numeric). Ultimately, it could support any data type with a concept of ordering and mean.

The estimates do depend on the order of incoming data, and so may differ between runs. This applies especially to parallel queries, for which the workers generally see different subsets of data for each run (and build different sketches, which are then combined together).

License

This software is distributed under the terms of PostgreSQL license. See LICENSE or http://www.opensource.org/licenses/bsd-license.php for more details.

[1] http://www.vldb.org/pvldb/vol12/p2195-masson.pdf