Aggregation and Grouping

ProvSQL supports provenance tracking for GROUP BY queries and aggregate functions [Amsterdamer et al., 2011]. The semantics follow a semimodule model: aggregation is treated as a scalar multiplication of provenance values.

GROUP BY Queries

When a query includes a GROUP BY clause, each aggregate value is an agg_token, which pairs the value of each contributing row with that row’s provenance token. The group row’s own provenance token combines the tokens of the contributing rows:

SELECT dept, COUNT(*), provenance()
FROM employees
GROUP BY dept;

The resulting provenance token encodes which input tuples were combined to produce each aggregate value.

The value displayed for an aggregate (3 (*)) is the one plain SQL computes on the same data. Rows kept only for the worlds where they exist (the null-padded row of an outer join for a row that has a match, a group that a HAVING rejects, a row beyond an ORDER BY … LIMIT) do not count in it; they do in its provenance. present tells whether a row holds in the actual database:

SELECT e.name, p.project, present(provenance())
FROM employees e LEFT JOIN projects p ON p.lead = e.id;

ORDER BY on an aggregate result sorts on that displayed value, i.e., in the order of the actual database, not of each world, with a warning. A LIMIT after it is still read in every world (see ORDER BY, LIMIT and OFFSET).

NULL inputs are skipped exactly as SQL prescribes: a NULL-valued row contributes to count(*) but not to sum / avg / min / max or count(col), and an all-NULL group’s aggregate is NULL, including across possible worlds in HAVING (see the chapter on NULLs).

SELECT DISTINCT

SELECT DISTINCT is modelled as a GROUP BY on all selected columns. Each distinct output row gets a provenance token that captures all the duplicate source rows that were merged:

SELECT DISTINCT dept, provenance()
FROM employees;

Aggregate Functions

The aggregate functions COUNT, SUM, MIN, MAX, and AVG are all supported over provenance-tracked tables.

stddev, variance and their _samp and _pop forms are tracked over an exact argument (an integer, a numeric), as the arithmetic over sums and counts that defines them. Over a floating-point argument, they are read as a plain value, with a warning.

array_agg, string_agg, the json_agg family, xmlagg and choose read their rows in order. Where the query does not determine that order (no ORDER BY, or rows tying on it with different values, in any world), a WARNING says so, and the order of the database as it is is read in every world. This covers the choose a scalar subquery or a LATERAL join with ORDER BY … LIMIT 1 is read as, when rows tie on its ORDER BY.

Arithmetic on Aggregate Results

Arithmetic, explicit casts, and other expressions (COALESCE, GREATEST, etc.) on aggregate results are supported, both in the same query and over subquery results:

SELECT dept, COUNT(*) * 10 FROM employees GROUP BY dept;
SELECT dept, SUM(salary) + 1000 FROM employees GROUP BY dept;
SELECT dept, string_agg(name, ', ' ORDER BY name) || ' (team)' FROM employees GROUP BY dept;
SELECT cnt::numeric FROM (SELECT COUNT(*) AS cnt FROM employees GROUP BY dept) t;
SELECT dept, COALESCE(cnt, 0) FROM (SELECT dept, COUNT(*) AS cnt FROM employees GROUP BY dept) t;
SELECT dept, GREATEST(cnt, 3) FROM (SELECT dept, COUNT(*) AS cnt FROM employees GROUP BY dept) t;

An operation that ProvSQL does not track reads the aggregate result as a plain value of the aggregate’s return type (e.g., bigint for COUNT), without provenance, with one warning for the statement (see Parts Whose Provenance Is Not Tracked); provsql.implicit_freeze set to 'error' refuses the query instead. Wrap the part in plain to say that the plain value is meant and silence the warning. The provenance of the group itself is still tracked.

A cast to a number is tracked, rounding as PostgreSQL’s cast does; a cast to text, boolean or a date, and any cast of a text-valued aggregate, reads the plain value:

SELECT SUM(salary)::numeric FROM employees;   -- tracked
SELECT AVG(salary)::bigint  FROM employees;   -- tracked, rounded
SELECT SUM(salary)::text    FROM employees;   -- the plain value

A Boolean aggregate cast to an integer (bool_or(flag)::int) is tracked as an indicator: 1 in the worlds where some row of the group satisfies the condition, 0 where none does. In the worlds where the group has no row, it has no value; COALESCE(bool_or(flag), false)::int, or COALESCE(bool_or(flag)::int, 0), gives it 0 there instead.

ORDER BY on such a tracked expression sorts on the value shown, with a warning, since other worlds may order the values differently.

Window functions over aggregate results (e.g., SUM(cnt) OVER ()) execute but are not provenance-aware: the windowed value is an opaque scalar, and a WARNING is emitted. See Aggregates as Window Functions for the window functions that are tracked.

Random-Variable Aggregates

When the aggregated column has type random_variable (see Continuous Distributions), the standard arithmetic aggregates lift to the distribution algebra: sum, avg, and product, plus the order statistics min and max. Each returns a random_variable instead of a scalar, and each reports an empty group as SQL NULL, as the standard-SQL aggregates do. See Aggregation Over Random Variables for the semantics, empty-group identities, and worked examples.

HAVING

HAVING clauses are supported:

SELECT dept, COUNT(*) AS n, provenance()
FROM employees
GROUP BY dept
HAVING COUNT(*) > 2;

A group is not filtered on the current data: one that fails the predicate may still appear in the result, with a provenance that evaluates to zero where the predicate fails.

HAVING clauses whose outcome is a deterministic scalar are also supported, including conditions that wrap a random_variable aggregate in a moment function such as HAVING expected(avg(measurement)) > 20 (see Continuous Distributions): PostgreSQL evaluates the predicate on the surviving groups while ProvSQL still tracks the per-group provenance.

A random_variable aggregate can also be compared directly, as in HAVING sum(measurement) > 40. The outcome is then uncertain, and goes into the provenance of the group: its probability is that of the group existing and the comparison holding. Such a comparison cannot be combined, in one HAVING clause, with a comparison on an ordinary aggregate (count(*) > 2).

Arithmetic in HAVING

HAVING conditions that apply arithmetic to aggregate results are supported, with provenance and probabilities tracked correctly:

-- constant arithmetic over a single aggregate
SELECT dept, provenance() FROM employees GROUP BY dept
HAVING sum(salary) + bonus > 100000;       -- folded to sum(salary) > 100000 - bonus

-- arithmetic across several aggregates, and constant/aggregate ratios
SELECT dept, provenance() FROM sales GROUP BY dept
HAVING sum(revenue) > sum(cost);           -- agg vs agg
SELECT dept, provenance() FROM sales GROUP BY dept
HAVING sum(revenue) * sum(margin) > 1000;  -- product of aggregates

Integer division truncates toward zero, as in SQL: HAVING sum(x) / 2 = 5 holds for an integer sum of 10 or 11; write sum(x) / 2.0 for numeric division. Arithmetic whose result is a floating-point number is tracked too. The displayed value of such an expression is the one SQL prints in its type (count(*) / 2 shows 1 for a count of 3).

A division by an aggregate that is zero in the actual database shows NULL, where plain PostgreSQL raises a division-by-zero error; the row is kept, with its provenance.

The choose Aggregate

The choose aggregate picks an arbitrary non-NULL value from a group. It is particularly useful for modelling mutually exclusive choices in a probabilistic setting: the provenance of the chosen value records which input tuple was selected, enabling correct probability computation over the choice.

SELECT city, choose(position) AS sample_position
FROM employees
GROUP BY city;

Comparing an aggregate with a text constant

A HAVING clause may compare min or max of a column of any ordered type (text, date, timestamp…) with a constant, by any comparison, using the type’s own order:

SELECT userid FROM badges GROUP BY userid
HAVING min(name) = 'Enthusiast';

It may compare an array_agg with a constant array or with another array_agg, using = or <> (the arrays read in the aggregate’s input order), and choose with a constant, using = or <>:

SELECT city, provenance()
FROM employees
GROUP BY city
HAVING choose(position ORDER BY name) = 'Analyst';

choose is PICKFIRST: in each possible world its value is the first present non-NULL occurrence of the group, so write choose(col ORDER BY key) to make the result deterministic; otherwise the physical scan order decides, with a warning where the values differ. The group’s elements need not be mutually exclusive.

Comparing any other aggregate with a text constant raises an error. Two numeric aggregate results compare by any comparison, read in each possible world over the rows they depend on (up to provsql.max_worlds of them); two array_agg only with = or <>, and an aggregate ProvSQL has no evaluator for (string_agg…) not at all, when its probability is asked for.

CASE over aggregates

A searched CASE whose WHEN guards are aggregate comparisons and whose branches are aggregates is a guarded selection over aggregates: which branch is taken depends on the (uncertain) input provenance, so the result is itself an agg_token.

SELECT district,
       CASE WHEN sum(pm25) > 300 THEN max(pm25)
            WHEN avg(pm25) > 50   THEN avg(pm25)
            ELSE 0 END AS headline
FROM readings GROUP BY district;

The result behaves like a bare aggregate: it displays as value (*), the CASE evaluated on the actual data, and expected, variance and moment give the distribution of the selected value over the possible worlds, conditioned on it being defined. This is exact for branches that are a single sum, count, min or max, a numeric constant or a nested CASE. An avg branch, or an arithmetic combination of aggregates (THEN sum(y) + sum(z)), is exact when it depends on at most 20 input tuples, and estimated by Monte Carlo otherwise (see provsql.rv_mc_samples).

COALESCE(aggregate, default) is tracked in the same way, as the CASE it means, when it has two arguments and the default holds no aggregate (a constant, a grouping column, or an expression over them); otherwise it is read as a plain value:

SELECT district, COALESCE(sum(pm25), 0) AS total
FROM readings GROUP BY district;

So are GREATEST and LEAST of two arguments, such as GREATEST(sum(pm25), 2), where an argument that is not a plain value must be an aggregate that is NULL exactly when it reads no value (count, sum, avg, min, max, choose, stddev_pop, var_pop, the bitwise and Boolean ones), or arithmetic over such aggregates; and NULLIF(aggregate, value), when the compared value holds no aggregate.

These guarded expressions may be nested, and compared in a HAVING or in the guard of a CASE, exactly:

SELECT district FROM readings GROUP BY district
HAVING GREATEST(sum(pm25), 2) > 3;

Aggregates as Window Functions

An aggregate used as a window function, f(x) OVER (…), is tracked as the aggregate of a group is. Each output row keeps the provenance of its input row, and the value becomes an agg_token over the rows of the frame: in each possible world, it is f applied to the rows of the frame that are present in that world. FILTER clauses and the aggregates of Aggregate Functions are supported.

SELECT name, dept, salary,
       sum(salary) OVER (PARTITION BY dept) AS dept_total,
       count(*) OVER (PARTITION BY dept ORDER BY salary DESC) AS at_least_as_paid
FROM employees;

A comparison on the value in an enclosing query goes into the provenance of the row, as for the aggregates of a grouped subquery.

The frame must be determined by the values of the rows, not by their positions: a window without ORDER BY, a RANGE frame (including the default frame of a window with ORDER BY), a GROUPS frame bounded by UNBOUNDED or CURRENT ROW, or a ROWS frame spanning the whole partition, with any EXCLUDE clause.

The ranking functions rank, dense_rank and row_number are tracked too (on PostgreSQL 11 and later). Selecting the first rows of each partition gives each row the probability of being among them:

SELECT name, dept, probability_evaluate(provenance())
FROM (SELECT name, dept,
             rank() OVER (PARTITION BY dept ORDER BY salary DESC) AS rk
      FROM employees) t
WHERE rk <= 3;

row_number is tracked as rank; where the ORDER BY of the window leaves ties, in any world, the value is the rank, and a WARNING says so. cume_dist(), percent_rank() and ntile() are tracked as well. Rows that tie on the ORDER BY of an ntile share the bucket of their rank, where SQL may split them between two buckets; a WARNING says so when it does.

The other window functions run with a WARNING, their value untracked: lag, lead, first_value, last_value, nth_value, ROWS and GROUPS frames with an offset, and windows over aggregate results other than the ranks below. A second WARNING says when the order they read is not determined: lag and lead with rows tying on the ORDER BY; first_value, last_value and nth_value with tying rows of different values.

The circuit of a running aggregate, whose frame moves with the current row, is quadratic in the size of the partition.

Ranking the groups of an aggregation

rank(), dense_rank() and row_number() over an ORDER BY that reads an aggregate result (the aggregates of the query’s own GROUP BY, or the aggregate columns of a subquery) are tracked:

SELECT tag, count(*) AS n, rank() OVER (ORDER BY count(*) DESC)
FROM posttags GROUP BY tag;

In each world, the rank of a group is the number of groups that come before it, itself included, and expected and the other moments report its distribution. ORDER BY an aggregate with a LIMIT keeps the groups that are among the first k in a world (see ORDER BY, LIMIT and OFFSET).

dense_rank() requires an aggregate whose values can be enumerated (see Grouping by the value of an aggregate); over another one, a sum() for instance, it is an untracked window, with a WARNING.

ORDER BY on a window value sorts on its displayed value.

Aggregates of aggregate results

An aggregate of the aggregate results of a subquery is supported when it is of the same kind: sum over a sum or a count, max over a max, min over a min. It is then the aggregate of the rows of the groups, in every semiring; and count over a count counts the groups:

SELECT dept, sum(n) AS employees          -- = count(*) per dept
FROM (SELECT dept, city, count(*) AS n FROM employees
      GROUP BY dept, city) t
GROUP BY dept;

Any other aggregate of an aggregate result (avg of a count, max of a sum, an aggregate of an arithmetic expression over aggregates) is also tracked, its value read in every possible world:

SELECT avg(n) AS employees_per_city
FROM (SELECT city, count(*) AS n FROM employees GROUP BY city) t;

A probability or a moment over it is read in the possible worlds: so expected(avg(n)) is the average of the counts of the cities present in each world. It is exact over few input tuples, and estimated by sampling beyond that (see 'sq-rewrite', 'bounded-jw', 'reachability').

An aggregate that reads such a result in a FILTER, an ORDER BY or a DISTINCT of its own, or whose inner value is not numeric, reads it as a plain value, with a warning (see Parts Whose Provenance Is Not Tracked).

Functions of an aggregate result

round, floor, ceil (and its synonym ceiling), abs, ln, exp, sqrt and power (and its synonym pow, with an exponent that is not itself an aggregate result) of an aggregate result are tracked, their value read in every possible world:

SELECT city, round(avg(salary), 2) AS average
FROM employees GROUP BY city;

A probability or a moment over the result is computed per world: expected(floor(avg(x))) is the average of the floors, not the floor of the average. A comparison on it is read per world too: in a HAVING, the groups where it holds in no world are dropped; outside the aggregation (a WHERE on a derived table’s aggregate), such a row is kept with a provenance of zero.

Any other function reads the aggregate result as a plain value, with a warning (see Parts Whose Provenance Is Not Tracked).

Grouping by the value of an aggregate

The value of an aggregate is one per possible world, so grouping rows by it, or deduplicating on it, reads it as its explosion: one row per value it takes over the worlds, each annotated by the condition that it takes that value:

SELECT n, count(*) AS cities          -- how many cities have n employees
FROM (SELECT city, count(*) AS n FROM employees GROUP BY city) t
GROUP BY n;

A city whose count is 1 or 2 over the worlds gives two rows, one per value, mutually exclusive, each with the provenance of counting that many; the row of a value has the probability that some group takes it. The same holds for a SELECT DISTINCT on the value at the level of the aggregation itself, and for UNION, EXCEPT and INTERSECT, which match the values of their arms:

SELECT count(*) FROM employees GROUP BY city
UNION
SELECT count(*) FROM employees WHERE remote GROUP BY city;

A set operation is refused where one arm aggregates at that column and another does not.

This applies to count(), min(), max(), choose, and sum() over an integer column, and to such an aggregate given a default by COALESCE(aggregate, constant), whose values are the aggregate’s and the default. A sum(), min() or max() of aggregate results (the totals of a view of subtotals) takes the values that combine those of its contributions. Other aggregates (sum() over a non-integer column, avg(), string_agg()…) are refused with SQLSTATE 0A000; group by their value shown with plain instead:

SELECT plain(total), count(*)
FROM (SELECT city, sum(salary) AS total FROM employees GROUP BY city) t
GROUP BY plain(total);

For an aggregation without GROUP BY, NULL is one of the values, taken in the worlds where no row it reads is present (except for count, which is then 0). An aggregate with a NULL contribution, or over more than a thousand rows, is refused.

This explosion into the values an aggregate takes differs from the one of Joining and exploding aggregated provenance, into the rows it aggregates.

Reading the truth of a comparison

A comparison of an aggregate against a constant, or against an expression over the grouping columns, read in the select list or as the condition of a CASE whose branches are not aggregates, explodes each row into the truth values it takes:

SELECT city, count(*) > 5 AS crowded FROM employees GROUP BY city;

Each city gives a row where the comparison holds and a row where it does not, each annotated with the provenance of that truth value, and, where the aggregate can have no value, a third row for SQL’s unknown. The same holds one level up, for an aggregate column of a subquery or of a view, read in a query that does not aggregate itself:

CREATE VIEW city_size AS
  SELECT city, count(*) AS n FROM employees GROUP BY city;
SELECT city, n > 5 AS crowded FROM city_size;

IS NULL and IS NOT NULL of an expression over aggregates give two rows the same way (a division is refused there).

This works for count, sum, avg, min, max and choose, with or without GROUP BY, and for such an aggregate given a default by COALESCE(aggregate, constant), which has a value wherever its row is there, so that only a NULL on the other side of the comparison makes it unknown. A comparison between two of these aggregates, without COALESCE (sum(x) FILTER (WHERE …) > sum(x) FILTER (WHERE …)), explodes the same way, its unknown row holding where either has no value. One over an aggregate whose NULL does not mean “no value” (stddev), and one in a query that also computes a window function, are read as plain values, with a warning. A HAVING condition is not exploded: it is already the provenance of the group.

Joining and exploding aggregated provenance

A column produced by an aggregate has the agg_token type. Two facilities let such a column take part in further provenance-aware processing.

A JOIN whose condition equates an agg_token column with an ordinary (non-aggregate) column is supported: the aggregate is exploded into one row per contributing row, with its value and provenance, and the join compares these values. This reads the value of the aggregate as one of the values it aggregates, which only holds for choose: exploding the result of any other aggregate (a count, whose rows each contribute 1) is refused.

-- agg.sample is an aggregate (agg_token) column; lookup.name is text
SELECT agg.city, lookup.name, provenance()
FROM (SELECT city, choose(position ORDER BY name) AS sample FROM employees GROUP BY city) agg
JOIN lookup ON agg.sample = lookup.name;

The same explosion is available explicitly through the explode_table function, which rewrites a stored table in place, turning its agg_token column into one row per child with the matching value and provenance:

CREATE TABLE grouped AS
  SELECT city, choose(position ORDER BY name) AS sample FROM employees GROUP BY city;
SELECT explode_table('grouped', 'sample');

Grouping Sets

GROUPING SETS, CUBE, and ROLLUP are read as the UNION ALL of one GROUP BY per grouping set: each group has the provenance it has in that GROUP BY, and the empty set () is an aggregation without GROUP BY, whose single row is always there.