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.