t-digest extension

⚠️ Warning: Version 2.0.0 reworks the API in a significant way, to make it closer to make it simpler, more convenient to use, and similar to postgresql-hll. The changes may break some queries, or silently change the behavior. See the section Upgrading to 2.0.0 for details about the changes, and how to rewrite the queries to continue working.

This PostgreSQL extension implements t-digest, a data structure for on-line accumulation of rank-based statistics such as quantiles and trimmed means. The algorithm is also very friendly to parallel programs.

The t-digest data structure was introduced by Ted Dunning in 2013, and a more detailed description and an example implementation are available in his GitHub repository [1]. In particular, see the paper [2] explaining the idea. Some of the code was inspired by tdigestc [3] and tdigest [4] by ajwerner.

The accuracy of estimates produced by t-digests can be orders of magnitude more accurate than those produced by previous digest algorithms in spite of the fact that t-digests are much more compact when stored on disk.

Basic usage

For the basic use case the extension provides an aggregate function building the tdigest sketch from source data

• tdigest(value double precision, compression int) -> tdigest

And then several functions processing the digests. The tdigest_percentile ones can be seen as a replacement of the percentile_cont aggregate, while the tdigest_percentile_of ones perform the inverse operation, estimating the relative rank of a given value:

• tdigest_percentile(p_digest tdigest, p_percentile double precision) -> double precision

• tdigest_percentile(p_digest tdigest, p_percentiles double precision[]) -> double precision[]

• tdigest_percentile_of(p_digest tdigest, p_value double precision) -> double precision

• tdigest_percentile_of(p_digest tdigest, p_values double precision[]) -> double precision[]

That is, instead of running

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

you might now run

SELECT tdigest_percentile(tdigest(a, 100), 0.95) FROM t

and similarly for the variants with an array of percentiles. This should run much faster, as the t-digest does not require sorting all the data and can be parallelized. Also, the memory usage is very limited, depending on the compression parameter.

Accuracy

Functions building t-digests accept a compression parameter that controls the trade-off between accuracy, digest size, memory use and processing cost. Larger values generally retain more, smaller centroids. The accepted range is [10, 10000]; values outside this range are rejected with an error.

Compression is neither the number of centroids nor an error bound. Accuracy depends on the data distribution, input order and history of merging digests. There is no general 1/N error guarantee for a digest with N centroids, and compression 100 does not promise 1% error relative to the range of data values. Values such as 100, used in the examples, are starting points to evaluate against exact results on representative data.

Each bucket is represented by a double precision mean and a 64-bit count (i.e. 16B per bucket), and the buffer holds 10 * compression buckets, so the maximum of 10000 for the compression means the largest possible t-digest has 100000 buckets and is ~1.5 MiB. For columns using extended storage, PostgreSQL attempts compression before moving large values out of line, so the on-disk footprint may be much smaller. Version 2.0.0 changes the type's default to extended on PostgreSQL 13 and later only. See Upgrading to 2.0.0 for older servers and columns created by an earlier version.

The algorithm allows smaller centroid weights near quantiles 0.0 and 1.0 than near the median. This concentrates resolution in the tails, but does not impose a fixed error bound in the units of the input values.

Digest size and storage

The centroid buffer holds at most 10 * compression centroids, including uncompacted input. A compacted digest is usually much smaller. Each centroid stores an 8-byte double precision mean and an 8-byte integer count. With the 24-byte full header, a digest uses 24 + 16 * ncentroids bytes before any TOAST processing. The largest permitted value therefore has 100000 centroids and occupies 1,600,024 bytes (about 1.53 MiB).

The on-disk digests are typically much smaller than the centroid buffer, due to compaction which merges centroids depending on how close to the median of the dataset they lie.

Since 2.0.0 the type uses PostgreSQL's extended storage policy by default on PostgreSQL 13 and later, so large values can be compressed and, if that is not enough, stored out of line using TOAST. On PostgreSQL 11 and 12 the type keeps the external policy it always had, which stores large values out of line without compressing them.

Either way a column can override the setting with

ALTER TABLE ... ALTER COLUMN ... SET STORAGE

and changing it does not itself rewrite existing values - see Upgrading to 2.0.0. Tuple and TOAST overhead are additional to the size of the digest.

The results are estimates computed from the centroids the digest happens to hold. That is worth spelling out because it changed in 2.0.0 for the trimmed functions: tdigest_sum and tdigest_avg used to be aggregates computing from the raw aggregate state, which buffers up to ten times compression values before compacting. Setting compression to at least a tenth of the number of input values therefore meant no compaction ever happened and the trimmed results came out exact. Building the digest is a separate step now, and the tdigest() aggregate compacts before returning, so tdigest_sum(tdigest(v, 100), ...) sees a compacted digest and returns an estimate like every other function. Queries relying on the old behaviour will see their results shift.

Note this is a property of how the digest was built, not of the trimmed functions - those summarize the centroids the digest happens to have. A digest built through the incremental API with p_compact := false reaches them uncompacted, and the fewer compactions happened while building it, the closer to exact the trimmed results are. The percentile functions do compact the digest they are given, so those always return estimates matching the compression level. See Incremental updates.

Here is a table of sizes for digests with different compression values, built on random data:

compression	centroids	length (B)	external (B)	extended (B)
10	18	305	309	308
50	40	655	659	658
100	61	993	997	997
200	100	1616	1620	1624
500	203	3275	3275	2238
1000	357	5732	5732	3765
2000	627	10058	10058	6432
5000	1318	21113	21113	12646
10000	2265	36260	36260	20177

Where centroids is the number of centroids in a compacted digest, and length is the "raw" size of the digest, without the 4-byte varlena header. external and extended are the on-disk sizes of the digest, depending on the storage policy set for the column. It's clear that external is almost the same as length, while extended is often much smaller thanks to compression.

This is merely an example - the actual values depend on the data. For example digests on integer values tend to be much more compressible, cutting the extended size about in half.

Advanced usage

The extension also provides a tdigest data type, which makes it possible to precompute digests for subsets of data, and then quickly combine those "partial" digests into a digest representing the whole data set. The prebuilt digests should be much smaller compared to the original data set, allowing significantly faster response times.

To compute a t-digest, use the tdigest aggregate function. The digests can then be stored on disk and later summarized using the tdigest_percentile functions (with tdigest as the first argument).

• tdigest(value double precision, compression int)

• tdigest(digest tdigest)

• tdigest_percentile(p_digest tdigest, p_percentile double precision)

• tdigest_percentile(p_digest tdigest, p_percentiles double precision[])

• tdigest_percentile_of(p_digest tdigest, p_value double precision)

• tdigest_percentile_of(p_digest tdigest, p_values double precision[])

The tdigest(digest tdigest) variant is an aggregate merging multiple pre-computed digests into a single digest, which can be stored again.

The tdigest(digest tdigest) aggregate accepts digests with different compression settings. Each aggregate state takes its compression from its first non-NULL digest; with parallel aggregation, the final choice can depend on worker and combine order. Use a consistent compression across input digests when that choice matters. Merging cannot recover detail already lost by compaction.

So for example you may do this:

-- table with some random source data, with "a" usable as a count of
-- occurrences (so it has to be positive)
CREATE TABLE t (a int, b int, c double precision);

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

-- table with pre-aggregated digests
CREATE TABLE p AS SELECT a, b, tdigest(c, 100) AS d FROM t GROUP BY a, b;

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

An example run produced a much smaller pre-aggregated table:

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

On the same machine, the last query took about 1.5 ms. Compare that to the following example timings on the source data; sizes and timings will vary with the data, PostgreSQL version and hardware:

\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)

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

-- tdigest estimate (4 workers)
SET max_parallel_workers_per_gather = 4;
SELECT a, tdigest_percentile(tdigest(c, 100), 0.95) FROM t GROUP BY a ORDER BY a;
  ...
Time: 893.538 ms

This illustrates how much faster the t-digest estimate can be than the exact query with percentile_cont. The difference can increase when sorting larger data sets requires spilling to disk.

It also shows how effective the pre-aggregation can be. In this example, there are 121 rows in table p, so with 120kB disk space that's ~1kB per row, each representing about 80k values. With 8B per value, that's ~640kB, or a compression ratio of about 640:1. For a fixed number of groups and a fixed compression, digest storage is bounded while the raw data grows.

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 an aggregate function that allows specifying the number of occurrences for each value. This reduces the number of SQL-function calls.

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

For a non-NULL input value, count determines how many times the value is added to the digest. A supplied count must be positive; a NULL count means one occurrence. NULL input values are skipped.

Incremental updates

An existing t-digest may be updated incrementally, either by adding a single value, or by merging-in a whole t-digest. The following examples use the table p with the pre-aggregated digests (in column d), built in Advanced usage. Each example adds the same new values to every row of p; use a WHERE clause when updating only selected groups.

For example, it's possible to add 1000 random values to the t-digests like this:

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

The overhead of doing this is fairly high, though - the t-digest 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 t-digest.

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

Alternatively, it's possible to use pre-aggregated t-digest values instead of the arrays:

WITH batch AS (
    SELECT tdigest(random(), 100) AS d FROM generate_series(1,1000)
)
UPDATE p SET d = tdigest_union(p.d, batch.d) FROM batch;

It may be undesirable to perform compaction after every incremental update, especially when adding values one by one. Setting p_compact to false skips compaction at the end of the call; compaction still occurs when adding to a full centroid buffer. The result may be unsorted and larger than a compacted digest, but remains subject to the 10 * compression centroid limit.

Use the multi-value functions with compaction after each batch when possible, or compact a stored digest by re-aggregating it:

UPDATE p SET d = (SELECT tdigest(x) FROM (SELECT p.d) s(x));

Adding a NULL value or a NULL array with tdigest_add returns the original digest unchanged. A non-NULL value or array with a NULL digest instead creates a new digest and requires a compression value.

When either input to tdigest_union is NULL, it returns the other digest unchanged, so tdigest_union(NULL, d) does not compact d; two NULL digests produce NULL. In all incremental functions, the p_compact flag itself must not be NULL, even for calls that otherwise do nothing.

The functions taking a digest name their arguments with a p_ prefix, so they may also be called using named arguments. (The tdigest() aggregates are the exception - their arguments have no names and have to be passed positionally.) To start a new digest while postponing final compaction, for example:

SELECT tdigest_add(NULL::tdigest, 42.0,
                   p_compression => 100, p_compact => false);

Trimmed statistics

The extension provides functions allowing to calculate trimmed (truncated) sum and average, from a digest:

• tdigest_sum(p_digest tdigest, p_low double precision, p_high double precision)

• tdigest_avg(p_digest tdigest, p_low double precision, p_high double precision)

The p_low and p_high parameters specify where to truncate the data. They are percentiles (not values), so both have to be in [0.0, 1.0] with p_low <= p_high, otherwise an error is raised. For example p_low = 0.1 and p_high = 0.9 means the lowest and highest 10% of the values are discarded. The thresholds are optional, defaulting to p_low = 0.0 and p_high = 1.0.

When no values fall between the thresholds - for example with p_low = p_high = 0.0, or p_low = p_high = 0.5 and an even number of values - both functions return NULL.

Upgrading to 2.0.0

Version 2.0.0 replaces the twenty-odd aggregate variants of earlier releases with a single tdigest() aggregate that builds a digest, plus plain functions that consume one. Queries using the removed aggregates have to be rewritten; the existing tdigest() builder and merge calls are unchanged.

This development branch installs version 2.0.0-dev, which is the version to use when specifying an explicit upgrade target.

Most of the removed aggregates no longer exist under any signature, so those queries fail with function ... does not exist and are easy to find. Six do not, and those are the dangerous ones.

Running the upgrade

Install the new version as usual, and then run

ALTER EXTENSION tdigest UPDATE;

in every database that has the extension installed. Installing the files replaces the shared library for the whole instance, but the SQL definitions are per-database and only change when you run the statement above.

Between the two steps a database still has the old SQL definitions pointing at C functions the rework removed. Calling one of the removed aggregates in that window reports

ERROR:  function is no longer supported by the tdigest extension
HINT:  The shared library has been upgraded but the SQL definitions have not.
       Run "ALTER EXTENSION tdigest UPDATE".

rather than failing to resolve the symbol. Once the update has run, calls to the removed raw-value signatures give the usual function ... does not exist. The six digest-taking signatures below still resolve, but as plain functions, and can silently change the meaning of existing queries.

The silent change

These six kept their exact signatures but turned from aggregates into plain functions:

tdigest_percentile(tdigest, double precision)
tdigest_percentile(tdigest, double precision[])
tdigest_percentile_of(tdigest, double precision)
tdigest_percentile_of(tdigest, double precision[])
tdigest_sum(tdigest, double precision, double precision)
tdigest_avg(tdigest, double precision, double precision)

A query with GROUP BY can fail loudly:

SELECT a, tdigest_percentile(d, 0.5) FROM p GROUP BY a;
ERROR:  column "p.d" must appear in the GROUP BY clause or be used in an aggregate function

Do not follow that advice. tdigest has no equality operator, so it cannot be grouped on, and adding the column to GROUP BY only trades one error for another:

SELECT a, tdigest_percentile(d, 0.5) FROM p GROUP BY a, d;
ERROR:  could not identify an equality operator for type tdigest

What the query needs is the tdigest() wrapper described below, which turns the digests of each group back into one digest:

SELECT a, tdigest_percentile(tdigest(d), 0.5) FROM p GROUP BY a;

A query without a GROUP BY keeps working and quietly means something else. It used to merge every digest into a single result; now it returns one row per digest:

-- 1.x: one row, the 0.5 percentile of all the digests combined
-- 2.0.0: one row per digest, each with its own 0.5 percentile
SELECT tdigest_percentile(d, 0.5) FROM p;

Wrap the digest in tdigest() to get the old behaviour back:

SELECT tdigest_percentile(tdigest(d), 0.5) FROM p;

Review all uses of these six names before upgrading, including grouped queries. Any call intended to combine multiple digest rows needs the tdigest() wrapper; the plain function itself processes only one digest.

Rewriting the removed aggregates

The aggregates taking raw values built a digest and consumed it in one step. Split that into tdigest() plus the matching function:

1.x	2.0.0
tdigest_percentile(v, c, p)	tdigest_percentile(tdigest(v, c), p)
tdigest_percentile(v, n, c, p)	tdigest_percentile(tdigest(v, n, c), p)
tdigest_percentile_of(v, c, x)	tdigest_percentile_of(tdigest(v, c), x)
tdigest_percentile_of(v, n, c, x)	tdigest_percentile_of(tdigest(v, n, c), x)
tdigest_percentile(d, p)	tdigest_percentile(tdigest(d), p)
tdigest_percentile_of(d, x)	tdigest_percentile_of(tdigest(d), x)
tdigest_sum(v, c, low, high)	tdigest_sum(tdigest(v, c), low, high)
tdigest_sum(v, n, c, low, high)	tdigest_sum(tdigest(v, n, c), low, high)
tdigest_sum(d, low, high)	tdigest_sum(tdigest(d), low, high)
tdigest_avg(v, c, low, high)	tdigest_avg(tdigest(v, c), low, high)
tdigest_avg(v, n, c, low, high)	tdigest_avg(tdigest(v, n, c), low, high)
tdigest_avg(d, low, high)	tdigest_avg(tdigest(d), low, high)
tdigest_digest_sum(d, low, high)	tdigest_sum(d, low, high)
tdigest_digest_avg(d, low, high)	tdigest_avg(d, low, high)

The array variants follow the same pattern. tdigest_digest_sum and tdigest_digest_avg were already plain functions and were simply renamed, since the names they wanted are now free. The upgrade renames these two functions in place, preserving stored views and other tracked dependencies, as well as their grants and comments. SQL text using the old names still needs to be rewritten.

The rewrites are not exact: tdigest() compacts the digest it returns, and the removed aggregates computed from the raw aggregate state. For the percentile functions that makes no practical difference, since they compact their input anyway. For tdigest_sum and tdigest_avg it does, because those work with the centroids they are given:

• An aggregate over few enough raw values to fit into the buffer without a compaction used to return the exact trimmed sum or mean. The rewritten query returns an estimate.

• An aggregate over several pre-aggregated digests used to see all the centroids of all of them, as long as they fit into the buffer without a compaction. The rewritten query first merges them into one compacted digest, which can easily cost a few times the relative error. Raise the compression of the stored digests if the difference matters.

Aggregate modifiers belong on tdigest(), not on the consuming function. Move DISTINCT and aggregate ORDER BY inside the builder call, and attach FILTER or OVER to that call. For example:

-- 1.x
SELECT tdigest_percentile(v, 100, 0.95) FILTER (WHERE v >= 0) FROM t;

-- 2.0.0
SELECT tdigest_percentile(tdigest(v, 100) FILTER (WHERE v >= 0), 0.95) FROM t;

Percentiles, hypothetical values, and trim thresholds are now ordinary function arguments. In grouped queries they must satisfy the usual PostgreSQL grouping rules; they are no longer taken from the first contributing input row.

NULL handling

The six functions that replace the aggregates - tdigest_percentile, tdigest_percentile_of, tdigest_sum and tdigest_avg - are STRICT, so a NULL in any argument produces a NULL result. The aggregates they replace raised an error for a NULL percentile, hypothetical value or trim threshold on the first contributing input row:

-- 1.x: ERROR:  percentile must not be NULL
SELECT tdigest_percentile(d, NULL::double precision) FROM p;

-- 2.0.0: NULL
SELECT tdigest_percentile(tdigest(d), NULL::double precision) FROM p;

Queries relying on that error to catch a bad percentile, value or trim threshold must now validate the argument explicitly. This does not permit NULL elements inside percentile/value arrays: those arrays must be nonempty, one-dimensional, and contain no NULL elements.

The incremental API is unchanged and is not STRICT. tdigest_add and tdigest_union treat a NULL digest or a NULL value as something to skip or to start from, not as a reason to return NULL - see Incremental updates.

Applying the upgrade

The update drops the removed aggregate objects. PostgreSQL will refuse to drop one if a view, materialized view, or another tracked database object depends on it. Rewriting application queries alone is therefore not enough: inventory those dependencies and save their definitions, owners, and grants before upgrading.

Quiesce sessions using the extension before replacing the shared library, install the 2.0.0 files, and use a fresh database connection for the update so it does not retain a previously loaded library. In each database, run:

ALTER EXTENSION tdigest UPDATE TO '2.0.0-dev';

If there are dependencies on removed aggregates, perform a planned migration in one transaction: explicitly drop the affected dependent objects, update the extension, then recreate those objects with the rewritten queries and restore their ownership and grants. Recreate any dependent objects in dependency order and repopulate materialized views as needed. Do not use broad DROP ... CASCADE commands as a shortcut, since those can remove application objects and data.

The scalar tdigest_digest_sum and tdigest_digest_avg renames preserve tracked dependencies, as described above. Function bodies and dynamic SQL stored as text still need to be searched and rewritten, even when PostgreSQL does not record a dependency on the old name.

The API rework does not change the on-disk digest format, so the new SQL API reads existing digest columns exactly as they are.

They do need attention for the storage change, though. Up to 1.4.7 the tdigest type used external storage, which pushes large values out to TOAST without attempting compression. On PostgreSQL 13 and later, the upgrade switches the type's default to extended:

ALTER TYPE tdigest SET (STORAGE = extended);

extended permits PostgreSQL to try compression before moving a large value out of line. Compression is not guaranteed: a value that does not compress well enough can still be stored out of line uncompressed.

PostgreSQL 11 and 12 do not support changing type storage this way, so the upgrade leaves their type default as external. The per-column ALTER TABLE command below works on those versions too; use it for existing columns and for new columns that should allow compression.

The ALTER TYPE statement changes the default recorded for the type, which is what new columns pick up. Columns that already exist keep the storage they were created with; an external column does not start requesting compression automatically. Check for those with

SELECT c.relname, a.attname, a.attstorage
  FROM pg_attribute a JOIN pg_class c ON c.oid = a.attrelid
 WHERE a.atttypid = 'tdigest'::regtype
   AND a.attnum > 0 AND NOT a.attisdropped
   AND c.relkind IN ('r', 'm', 'p')
   AND a.attstorage <> 'x';

and switch the ones worth converting:

ALTER TABLE p ALTER COLUMN d SET STORAGE EXTENDED;

SET STORAGE does not rewrite existing values. A table rewrite with VACUUM FULL or CLUSTER can apply the new policy to them, but requires an ACCESS EXCLUSIVE table lock. A no-op update such as UPDATE p SET d = d can reuse the old TOAST value without compressing it. To reconstruct the values without compacting their centroids, use a text round trip with sufficient floating-point output precision:

BEGIN;
SET LOCAL extra_float_digits = 3;
UPDATE p SET d = d::text::tdigest;
COMMIT;

This also converts digests in the old sum-based format to the mean-based format, just as the input functions normally do.

ALTER TABLE ... SET STORAGE has no version restriction, so it is also the way to get compressed digests on PostgreSQL 11 and 12, where the type keeps its external default. The query above lists every tdigest column there, including ones created after the upgrade.

The change is optional. Nothing breaks if a column is left on external storage - both representations are readable, and a table can hold a mix of them. A digest is 24B of header plus 16B per centroid, and how many centroids a compaction leaves behind is not bounded by compression - it depends on the data, and ranges from a fraction of compression to somewhat above it (compression 10 typically gives about 17 centroids). A digest built with compression 100 is around 1kB and stays in the tuple, while compression 500 and above produces digests of several kB, which do reach TOAST. The storage change matters for those.

Functions

The following list covers the aggregates and utility functions provided by this extension. Type I/O functions and internal aggregate support functions are not listed. The accuracy parameter in these descriptions is the compression used when building the t-digest, as described in the Accuracy section.

The tdigest is an aggregate (a parallel safe one), while tdigest_percentile, tdigest_percentile_of, tdigest_avg, tdigest_sum, tdigest_count, tdigest_add, tdigest_union, tdigest_json, tdigest_double_array and tdigest_is_valid are plain functions, taking a single tdigest value (or two, in the case of tdigest_union). All of them are parallel safe.

The examples use a table t with the values in column c, and - for the variants with a count parameter - the number of occurrences of each value in column a. Supplied counts must be positive; NULL counts mean one occurrence. The incremental-update examples use the digest column p.d from Advanced usage.

tdigest(value, accuracy)

Computes t-digest with the specified accuracy.

The accuracy is taken from the first row with a non-NULL value, and ignored in later rows, so keep it the same for all rows.

Synopsis

SELECT tdigest(t.c, 100) FROM t

Parameters

• value - values to aggregate
• accuracy - accuracy of the t-digest

tdigest(value, count, accuracy)

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

The accuracy is taken from the first row with a non-NULL value, and ignored in later rows, so keep it the same for all rows.

Synopsis

SELECT tdigest(t.c, t.a, 100) FROM t

Parameters

• value - values to aggregate
• count - number of occurrences for each value (NULL means one)
• accuracy - accuracy of the t-digest

tdigest(digest)

Merges pre-computed t-digests into a single t-digest. This is also the way to force compaction of a digest built with p_compact = false.

Synopsis

SELECT tdigest(d) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t GROUP BY t.a
) foo

Parameters

• digest - t-digests to merge

tdigest_count(p_digest tdigest)

Returns the number of items represented by the t-digest. This is a plain function, not an aggregate.

Synopsis

SELECT tdigest_count(d) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t
) foo

Parameters

• p_digest - t-digest to inspect

tdigest_percentile(p_digest tdigest, p_percentile double precision)

Computes the requested percentile from a pre-computed t-digest.

Synopsis

SELECT tdigest_percentile(d, 0.99) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t
) foo

Parameters

• p_digest - t-digest to process
• p_percentile - value in [0, 1] specifying the percentile

tdigest_percentile(p_digest tdigest, p_percentiles double precision[])

Computes the requested percentiles from a pre-computed t-digest.

Synopsis

SELECT tdigest_percentile(d, ARRAY[0.95, 0.99]) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t
) foo

Parameters

• p_digest - t-digest to process
• p_percentiles - values in [0, 1] specifying the percentiles

tdigest_percentile_of(p_digest tdigest, p_value double precision)

Estimates the relative rank of a hypothetical value using a pre-computed t-digest.

At an exact centroid mean, half of the total weight of all centroids with that mean is counted. A digest containing only copies of one value therefore returns 0.5 at that value, not the fraction of rows strictly below it (0.0). This is a smoothed rank estimate, not an exact count of smaller values.

A value below the smallest centroid mean (including -Infinity) returns 0.0, a value above the largest one (including Infinity) returns 1.0, and NaN returns NaN.

Synopsis

SELECT tdigest_percentile_of(d, 349834.1) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t
) foo

Parameters

• p_digest - t-digest to process
• p_value - hypothetical value

tdigest_percentile_of(p_digest tdigest, p_values double precision[])

Estimates relative ranks of hypothetical values using a pre-computed t-digest, with the same conventions for centroid means, values outside the digest and non-finite values as the scalar form.

Synopsis

SELECT tdigest_percentile_of(d, ARRAY[438.256, 349834.1]) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t
) foo

Parameters

• p_digest - t-digest to process
• p_values - hypothetical values

tdigest_add(p_digest tdigest, p_element double precision, p_compression int, p_compact bool)

Performs incremental update of the t-digest by adding a single value.

Synopsis

UPDATE p SET d = tdigest_add(d, random());

Parameters

• p_digest - t-digest to update (may be NULL)
• p_element - value to add, which must be finite; NULL leaves the digest unchanged
• p_compression - required to initialize a digest from a non-NULL value; ignored for an existing digest (default: NULL)
• p_compact - compact at the end of the call (default: true; must not be NULL)

tdigest_add(p_digest tdigest, p_elements double precision[], p_compression int, p_compact bool)

Performs incremental update of the t-digest by adding values from an array.

Synopsis

UPDATE p SET d = tdigest_add(d, ARRAY[random(), random(), random()]);

Parameters

• p_digest - t-digest to update (may be NULL)
• p_elements - nonempty, one-dimensional array of finite, non-NULL values; a NULL array leaves the digest unchanged
• p_compression - required to initialize a digest from a non-NULL array; ignored for an existing digest (default: NULL)
• p_compact - compact at the end of the call (default: true; must not be NULL)

tdigest_union(p_digest1 tdigest, p_digest2 tdigest, p_compact bool)

Performs incremental update of the t-digest by merging-in another digest. When either of the digests is NULL, the other one is returned unchanged (without compaction). When both are non-NULL, the result uses the compression of p_digest1, even if p_digest2 has a different compression.

Synopsis

WITH x AS (SELECT tdigest(random(), 100) AS d FROM generate_series(1,1000))
UPDATE p SET d = tdigest_union(p.d, x.d) FROM x;

Parameters

• p_digest1 - t-digest to update
• p_digest2 - t-digest to merge into p_digest1
• p_compact - compact at the end of the call (default: true; must not be NULL)

tdigest_json(p_digest tdigest)

Returns the t-digest as a JSON value. The function is also exposed as a cast from tdigest to json.

The document has the keys flags, count (the total number of items), compression and centroids (the number of centroids), followed by the per-centroid means and counts arrays.

Synopsis

SELECT tdigest_json(d) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t
) foo;

SELECT CAST(d AS json) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t
) foo;

Parameters

• p_digest - t-digest to cast to a json value

tdigest_double_array(p_digest tdigest) -> double precision[]

Returns the t-digest as a double precision[] array. The function is also exposed as a cast from tdigest to double precision[]. The array contains the flags, the total number of items, the compression and the number of centroids, followed by a (mean, count) pair for each centroid.

Synopsis

SELECT tdigest_double_array(d) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t
) foo;

SELECT CAST(d AS double precision[]) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t
) foo;

Parameters

• p_digest - t-digest to cast to a double precision[] value

tdigest_avg(p_digest tdigest, p_low double precision, p_high double precision)

Computes trimmed mean of values, discarding values at the low and high end. The p_low and p_high values are percentiles in [0, 1] (with p_low <= p_high) specifying which part of the sample should be included in the mean, so e.g. p_low = 0.1 and p_high = 0.9 means 10% low and high values will be discarded. Returns NULL when no values fall between the thresholds.

Synopsis

SELECT tdigest_avg(d, 0.05, 0.95) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t
) foo;

Parameters

• p_digest - t-digest to calculate mean from
• p_low - low threshold percentile (default: 0.0)
• p_high - high threshold percentile (default: 1.0)

tdigest_sum(p_digest tdigest, p_low double precision, p_high double precision)

Computes trimmed sum of values, discarding values at the low and high end. The p_low and p_high values are percentiles in [0, 1] (with p_low <= p_high) specifying which part of the sample should be included in the sum, so e.g. p_low = 0.1 and p_high = 0.9 means 10% low and high values will be discarded. Returns NULL when no values fall between the thresholds.

Synopsis

SELECT tdigest_sum(d, 0.05, 0.95) FROM (
    SELECT tdigest(t.c, 100) AS d FROM t
) foo;

Parameters

• p_digest - t-digest to calculate sum from
• p_low - low threshold percentile (default: 0.0)
• p_high - high threshold percentile (default: 1.0)

tdigest_is_valid(p_digest tdigest)

Checks whether the t-digest is valid, i.e. that it passes the same sanity checks as the input functions (parsing the text or binary representation). Returns true for valid digests, false otherwise.

Digests produced by the extension are always valid, and it's not possible to construct an invalid one through the input functions. But digests stored by older versions of the extension (which did not have all the checks) may be broken in various ways, and the values are not re-validated when read back. This function makes it possible to find such digests.

Synopsis

SELECT a, b FROM p WHERE NOT tdigest_is_valid(p.d);

Parameters

• p_digest - t-digest to check

Notes

Input values and centroid means use double precision. PostgreSQL can convert other numeric types to it implicitly, but those conversions can lose precision. The digest does not retain the native precision of bigint or numeric inputs.

Input values must also be finite. The tdigest() aggregates and tdigest_add raise an error for NaN, Infinity and -Infinity, so filter such values out if the data may contain them. NULL values are skipped.

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 digests, which are then combined together).

Security

If you believe you have found a security vulnerability in this repository, please report it using this form [5] of this GitHub project. This creates a private communication channel between the reporter and the maintainers.

If you are absolutely unable to or have strong reasons not to use GitHub's vulnerability reporting workflow, please reach out to the maintainer at tomas@vondra.me.

Notes:

• The code assumes digests stored on-disk are valid and not corrupted. If the suspected vulnerability requires a corrupted digest, without a way to create such digests (using the current version), it's not a security issue. This is in line with general assumptions in the Postgres code.

• A valid vulnerability must not require superuser privileges. A superuser can do almost anything (ultimately can read/write memory) and does not need to bother with vulnerabilities.

Known issues

incorrect alignment

The SQL data type is defined without specifying the ALIGNMENT parameter, so it uses the default 4-byte alignment. Its C representation contains double and int64 fields that can require 8-byte alignment. Accessing misaligned fields may incur a performance penalty on amd64/arm64 and can cause SIGBUS crashes on platforms with strict alignment requirements.

The implementation handles this in tdigest_detoast() by making an aligned copy when necessary. Detoasting out-of-line values, compressed values or values with a short varlena header already produces an aligned allocation. Inline values with a 4-byte header need no copy during ordinary detoasting, so they may need the additional alignment copy.

Whether a digest stays inline depends on its actual centroid count, the other columns in the tuple, and the column's storage settings. There is no compression-parameter threshold that guarantees out-of-line storage. With the extended policy the type uses since 2.0.0 (on PostgreSQL 13 and later), a large digest is more likely to be compressed than moved out of line, and a compressed value is detoasted into an aligned allocation just like an out-of-line one.

The extra copy requires an allocation and a single memcpy() of the digest. For small inline values, this overhead is usually modest.

The SQL data type retains its original 4-byte alignment for compatibility with existing on-disk values.

FINALFUNC_MODIFY = READ_ONLY

All three aggregates share a single final function, tdigest_digest(), and it mutates the aggregate state - it sorts and compacts it before turning it into a digest. That means FINALFUNC_MODIFY should not be READ_ONLY. It is, though, because that's what the aggregates were created with, and changing it would break upgrades of existing installations.

Instead, the final function checks AggStateIsShared(), and works on a copy when the state may be needed again - that is, when the aggregate is used as a window function, or when several aggregates share a single transition state. So the results are correct in those cases, at the cost of copying the state.

Before 2.0.0, the percentile aggregates had final functions of their own, which compacted the state too, and copied it in the same way when shared. The final functions of the trimmed tdigest_sum() and tdigest_avg() aggregates only sorted the state, and did not need the copy. All of these are plain functions taking a digest now, so they have no aggregate state to protect. Like every other function consuming a digest, they never modify it in place - they work on a copy when they need to sort or compact it.

fused multiply-add (FMA)

Various places in the code use expressions of the form a * b + c (e.g. when calculating the mean of two merged centroids, or when interpolating between two centroid means). Compilers are allowed to contract such expressions into a single fused multiply-add (FMA) instruction, which rounds only once, and so produces slightly different results than a separate multiplication and addition.

Whether that happens depends on the platform and on the compiler flags. FMA is part of the baseline instruction set on aarch64, so gcc contracts by default there (at -O2 and higher - the contraction happens in a pass enabled only by -O2), while on x86-64 it does not, because FMA requires -mfma or a sufficiently recent -march. The results then differ in the last couple of digits, and the regression tests - which compare the exact float8 output - fail.

For now, the Makefile builds with -ffp-contract=off, if the compiler understands the option, so that the results do not depend on which instructions happen to be available. The option is added to both CFLAGS and BITCODE_CFLAGS, because the LLVM bitcode used for JIT inlining is compiled separately and does not inherit CFLAGS. Compilers spelling the option differently (or not having it at all) may still produce digests that differ in the last digit or two.

This is merely a workaround to make the tests pass. Ideally, we want to allow FMA, because it's expected to be faster and give more precise results (thanks to a single rounding).

License

This software is distributed under the terms of the PostgreSQL license. See LICENSE or https://www.postgresql.org/about/licence/ for more details.

[1] https://github.com/tdunning/t-digest

[2] https://github.com/tdunning/t-digest/blob/master/docs/t-digest-paper/histo.pdf

[3] https://github.com/ajwerner/tdigestc

[4] https://github.com/ajwerner/tdigest