Aggregation Provenance

Aggregation is the most subtle feature of ProvSQL’s query rewriter: unlike selection or join, an aggregate function fundamentally combines values rather than just propagating them, so the provenance of an aggregate result cannot be a plain semiring value of the same type as a tuple’s provenance. This chapter explains the data model ProvSQL uses to represent aggregate provenance, the gate types involved, and how the rewriter glues everything together. The final section is a step-by-step guide for adding a new aggregate function in C++.

For the user-facing semantics see Aggregation and Grouping; for the formal semantics over the extended relational algebra see the ICDE 2026 paper [Sen et al., 2026].

The Semimodule Picture

The semiring framework for positive relational algebra (selection, projection, join, union) annotates tuples: each row of a K-relation carries a single element of a commutative semiring K. Aggregation does not fit that picture, because the result of SUM(salary) is a value, not a tuple, and the question “where does this value come from?” has to track both the contributing rows and the payload each row contributed. Amsterdamer, Deutch, and Tannen ([Amsterdamer et al., 2011]) resolved this by annotating tuples and values simultaneously using a K-semimodule.

A K-semimodule is a commutative monoid together with a scalar multiplication that distributes over the semiring operations on K and over the monoid addition on M. The intuition is that elements of M are “aggregate values” and elements of K are “provenance annotations”; scaling m by k produces an M-element “tagged” with the provenance k.

The specific K-semimodule the paper builds for aggregate provenance is the tensor product , whose elements are finite formal sums of pairs (“simple tensors”) , modulo the equivalences that make bilinear (, etc.). Note how this mixes three different operations: is the ⊕ of the semiring K, is the monoid addition of the semimodule , and is the tensor product that glues a K-element to an M-element. A simple tensor should be read as “the tuple with provenance k contributed the value m”. The whole is itself a K-semimodule, with scalar multiplication .

Concretely, for a query like

SELECT city, SUM(salary) FROM personnel GROUP BY city;

the provenance of the aggregate value in one group is

where k_i is the semiring annotation of the i-th input tuple in the group and m_i is its salary payload (lifted into M). The sum is not collapsed into a single number – it carries, for every contributing tuple, both its provenance and the value it contributed, and concrete semirings (Counting, Formula, …) are free to specialise the aggregation over into a meaningful scalar only at evaluation time.

Strictly speaking, the Amsterdamer et al. construction requires to be a commutative monoid, which rules out aggregate operators that are non-associative or non-commutative (ARRAY_AGG with a user-supplied order, for instance). ProvSQL therefore reuses the semimodule framework – the tensor product , the semimod / agg / value gate types, the circuit shape – but does not bake the monoid axioms into it. An agg gate is treated as an abstract formal sum of simple tensors, and it is up to each concrete accumulator to decide what “combining” those tensors means. Aggregates whose operator genuinely is a commutative monoid (SUM, COUNT, MIN, MAX, AND, OR, …) open the door to optimisations – reordering, partial folding during traversal, and so on – that accumulators for order-sensitive or non-associative aggregates cannot use. The distinction is a property of the accumulator, not of the gate representation.

ProvSQL realises this construction directly as a circuit built from three gate types in gate_type:

• value – a leaf carrying a constant payload (stored as a string in the persistent representation; the C++ accumulator parses it into the appropriate native type).

• semimod – a binary gate representing one simple tensor . Its two children are the tuple’s provenance (a sub-circuit evaluating to ) and a value gate carrying .

• agg – the aggregate root, the formal sum taken over all tuples in the group. Its annotations (info1 / info2 from get_infos) record the PostgreSQL OID of the aggregate function and the OID of its result type, so the evaluator can later instantiate the right C++ accumulator. The high bit of info2 (PROVSQL_AGG_SCALAR_FLAG, in provsql_utils.h) flags a scalar (no GROUP BY) aggregation; consumers AND info2 with PROVSQL_AGG_TYPE_MASK to recover the result-type OID before using it. So info2 of a count reads 20 (int8), of a text aggregate 25, of a float8 one 701, each with the high bit set where there is no GROUP BY. This is the only place the type of a value is recorded: an evaluator that instead infers it from how the value’s text looks will read a text column of numerals as numbers, and order it numerically where PostgreSQL orders it lexicographically.

Row-level provenance and the δ operator

An agg gate gives the provenance of the aggregate value in one column of one output row, but the row itself also has a provenance – “this row exists in the result” – that the downstream evaluators need. That row-level provenance is the ⊕ of the per-tuple tokens of the group, just like for a plain GROUP BY without aggregates. However, summing raw tuple annotations can over-count existence: a row that exists in multiplicity in the input would naively have a row-level provenance of (n times), whereas what we want is a single “it exists”.

The δ operator (Amsterdamer, Deutch, Tannen [Amsterdamer et al., 2011]) solves this. A δ-semiring is a semiring together with a unary operation δ satisfying and regardless of the number of s. Intuitively, δ collapses “any positive number of witnesses” to a single “exists”. The rewriter emits a delta gate wrapping the row-level ⊕ for grouped aggregation whose HAVING clause (if any) is not lifted into the provenance circuit (see make_provenance_expression). Scalar aggregation (no GROUP BY) gets gate_one instead: the single result row always exists, even over an empty input. A HAVING predicate left for native PostgreSQL evaluation still gets the δ; a lifted HAVING – one referencing aggregate provenance – instead supersedes it with provenance_cmp: such a predicate constrains existence in a way that depends on the aggregate value, so the row-level token has to carry more information than a flat “exists”, and the rewriter routes the result through cmp gates that having_semantics.hpp evaluates ahead of the main traversal (see Optional Methods). The cmp gate subsumes the δ rather than multiplying with it: its possible-world enumeration ranges over the non-empty worlds of the same per-row tokens, so it already entails the group’s existence, and conjoining both would count that factor twice in a non-idempotent semiring.

For MIN / MAX against a constant in an absorptive semiring (Semiring::absorptive() true; see Optional Methods), the enumeration is replaced by a single-scan closed form. With the -sums of the contributors whose value is the constant, MIN < C is , MIN <= C is , MIN >= C is , MIN > C is , MIN = C is and MIN <> C is ; MAX is the mirror image with and exchanged. The two monus-free forms are the existential comparisons: MIN < C holds in exactly the worlds containing some contributor below , a family closed under supersets whose minimal elements are the singletons, and on such a family the monus cancels from the possible-world sum, so absorptivity alone makes the sum of the witnesses exact (Lean Having.sum_ann_meet and the *_site_rewrite theorems of Provenance/HavingMonotone.lean). The four other forms are proved only when also distributes over (Semiring::mul_sub_left_distributive() true; Lean Having.minScan_correct / Having.maxScan_correct in Provenance/HavingMinMax.lean), so in the security (min-max) semiring, absorptive but not distributive, only the existential comparisons take the scan and the others keep the enumeration. Whether distributivity is necessary for them is not settled: the five-element chain of Provenance/Semirings/ChainFive.lean refutes the COUNT = 1 and COUNT <= 1 identities without it, but is not a counterexample to the MIN / MAX forms. The same existential collapse serves bool_or = true and bool_and = false, whose valid worlds are those meeting the trigger class. Short of absorptivity, idempotence (Semiring::idempotent(), true of why- and which-provenance) already cancels the monus from the possible-world sum over any family closed under supersets (Lean Having.witness_identity): for those two conditions, and for MIN below and MAX above a constant, COUNT above one and SUM above one over non-negative values, an idempotent semiring keeps the exhaustive enumeration but annotates each valid world by the product of its present annotations alone. The empty world never satisfies the comparison (MIN / MAX of an empty group is NULL), so scalar aggregation needs no special case. The certifying Boolean-circuit construction (BoolExpr over independent base tuples) keeps the complete enumeration, whose mutually exclusive world terms its d-DNNF certificate needs; the closed form is what it builds when the contributors are derived sub-circuits (a join, a subquery).

What the cmp supersedes is the compared group’s δ, not the whole row token it sits in. The distinction matters when the comparison was written in an outer WHERE over a subquery’s aggregate: migrate_probabilistic_quals routes such a qual to that outer level’s havingQual, where the row token is the product of every input at that level, and only the δ inside it is superseded. Those tokens are opaque UUIDs at planning time, so make_provenance_expression defers the decision to provenance_cmp_times, which walks them at evaluation time through cmp_surviving_factors:

• a bare δ over the compared group disappears – the plain γ-then-σ shape, whose annotation is then the cmp alone, the same gate the fused HAVING builds;

• a times keeps its other factors, so a join partner’s annotation survives even when the aggregation and the join reach this level bundled inside one view or CTE token;

• anything else is kept whole and multiplied – in particular an earlier comparison’s cmp on the same group, which a second comparison does not subsume, so σ∘σ yields the product of both comparisons rather than the later one alone.

A δ counts as the compared group’s when its ⊕ child’s operands are exactly the provenance children of that aggregate’s semimod wires, i.e. when it collapses the multiplicity of the very group the comparison ranges over.

The supersede is licensed only when the predicate really does entail that the group exists. An aggregate-free leaf does not: it lowers to a deterministic regular_indicator, 𝟙 or 𝟘 by the value of a grouping column, which says nothing about whether any row is present. HAVING count(*) >= 4 OR g = 1 would otherwise report certainty for a group that is empty half the time, since 𝟘 ⊕ 𝟙 = 𝟙. having_entails_group_existence decides this the way the semiring composes: under ⊗ one entailing factor suffices, under ⊕ every disjunct must entail. Where it does not hold the δ stays – wrapped around the group’s ⊕ in the fused shape, left in place in the row tokens otherwise.

Note

This supersede discipline is machine-checked in the ProvSQL Lean 4 library, on a query syntax whose columns are indexed by the three kinds ProvSQL distinguishes by type – regular values, aggregate tokens, provenance values (see the formal-verification section of the rewriting chapter). Row annotations there are factored (GenAnn): a grouping leaves its group-existence factor pending, an aggregate comparison supersedes exactly the compared groups’ factors with the predicate provenance of the token, and a projection cashes the factors of the token columns it drops. Whether the guard is superseded or kept is decided by GenPred.entailsExistence, the counterpart of having_entails_group_existence: an aggregate-only predicate always supersedes it (GenPred.aggOnly_entailsExistence), one with a regular atom reachable in an empty group does not – that atom being an indicator gate (TermG.chiGate), the counterpart of regular_indicator. For the fused shape, one aggregate comparison directly above a grouping, the annotation is proved to be exactly the possible-world predicate provenance of the group, one row per group key (AggQuery.havingSite_evaluateAnnotated).

Groups that fail in every world

A lifted HAVING predicate becomes a gate whose value is only known once the circuit is evaluated. Some groups can be told to be zero without that: those where the predicate cannot hold whichever rows of the group are present. What decides it is the range of values the aggregate takes over the non-empty selections of the group’s rows, and PostgreSQL computes the ends of that range as ordinary aggregates of the same GROUP BY. having_possible builds, from the predicate, an ordinary SQL condition that is true when the predicate may hold in some world; make_provenance_expression leaves it as the HAVING clause of the rewritten query, so PostgreSQL drops the other groups before their gates are created. A row whose provenance is zero being the same as an absent row, this changes no result; it restores SQL’s row set on such groups and spares their gates and evaluation, at a cost that does not show (a few ordinary aggregates, next to one provenance_semimod call per row).

The ends used, for a comparison of the aggregate with an aggregate-free term (a constant, an expression over grouping keys):

• count: at most the count itself;

• sum: at most the sum of the positive values (sum(x) FILTER (WHERE x > 0)), or 0 without any, and symmetrically below; the group must also have a non-NULL value at all;

• max, min, avg: between the min and the max of the values, the sibling aggregate being looked up on the exact argument type.

>= needs the upper end to reach the term, <= the lower end, = both; <>, a comparison of two aggregates, any other aggregate, or an aggregate column coming from a subquery leave the group alone. The Boolean structure follows the lift: NOT is pushed to the atoms, a conjunction keeps what is known of its parts, a disjunction is known only if every part is, and a regular atom is its own condition. A NULL condition drops the group: the comparison is then unknown in every world.

The check is a sufficient one – sum(x) = 5 over {2, 4} lies inside the range and is kept, to be evaluated to zero; telling such cases is NP-hard – and it rests on an invariant of the rewriting: the rows PostgreSQL aggregates over are a superset of the rows present in any world. A row that some world lacks is kept with a token that is zero in that world (monus for differences, antijoins and null-padded outer-join rows, comparison gates for lifted predicates), never filtered on the current instance. The one construct that breaks it, a LIMIT / OFFSET in a subquery, raises a warning of its own. The same predicate written as a selection on the aggregate column of a subquery is not checked (no HAVING clause can carry the condition at that level); its zero rows stay visible, which is equivalent. An evaluation-time counterpart exists in RangeCheck.cpp, which resolves the comparisons that reach the evaluator.

The agg_token Type

PostgreSQL evaluates aggregates using its own machinery, which expects them to return ordinary scalar types (an INT, a FLOAT…). But the rewritten query needs the aggregate result to carry both the scalar value and the provenance gate that captures how it was computed – otherwise downstream references to provenance would have nothing to return.

ProvSQL solves this by introducing agg_token, a composite SQL type wrapping a UUID (the root agg gate) and a string form of the aggregate value. The rewriter wraps every Aggref in a call to provenance_aggregate whose return type is agg_token. When the executor processes the result, every aggregate column carries an agg_token and both pieces of information flow downstream:

• provenance extracts the UUID for the user.

• Cast operators on agg_token (defined in agg_token.c) extract the scalar value when the user treats the result as a number, e.g. for further arithmetic.

Arithmetic on aggregate results preserves provenance: once you write SUM(x) * 2, the rewriter (cast_agg_token_mutator / try_swap_agg_arith in provsql.c) swaps the scalar operator for the + - * / operators defined on agg_token (in sql/provsql.common.sql), so the result is again an agg_token whose UUID points at an arith gate over the operand circuits. Provenance is lost only on a genuine cast out of agg_token – e.g. storing the result into a numeric column – and the cast functions in agg_token.c emit an execution-time warning when that happens. Comparisons of aggregate results are routed through cmp gates so that HAVING predicates preserve provenance too – see Semiring Evaluation for the gory details of how that pre-evaluation works.

What the Rewriter Builds

The generic rewriting pipeline in Query Rewriting Pipeline covers aggregation at the pipeline level: Step 4 calls rewrite_agg_distinct to lift a single-argument AGG(DISTINCT ...) into an inner GROUP BY, Step 8 calls migrate_probabilistic_quals, then replace_aggregations_by_provenance_aggregate (and rewrite_agg_cases), then insert_agg_token_casts, and Step 9 fuses the row-level tokens with provenance_plus(array_agg(...)) and wraps the result in provenance_delta. This section only documents the aggregation-specific structures those passes produce – the pieces that the generic pipeline description is too terse to spell out.

The call that make_aggregation_expression synthesises to replace an Aggref is a FuncExpr for provenance_aggregate whose arguments are:

• the OID of the aggregate function;

• the OID of its result type;

• the original Aggref itself, so PostgreSQL still computes the scalar value (this is what ends up inside the agg_token). When a row reaching the aggregate may be false in the database as it is (plain_row_token: its token has a monus or a cmp, or comes from a relation of derived tokens), a FILTER (WHERE plain_truth(t)) on the row token t is added to it, so that the value is the one plain SQL computes on the same data. plain_truth is sr_boolean without a mapping, walking times / plus / monus / … gates directly and evaluating a comparison over the Boolean semiring. The HAVING pruning bounds, which range over every world, read the Aggref without that filter (aggref_over_all_rows);

• an array_agg of per-tuple provenance_semimod(arg, t) calls – one semimod gate per input the aggregate reads, glueing the row’s provenance t to the row’s contributed value arg (see Which rows are children of the agg gate below for which rows those are);

• a boolean is_scalar (DEFAULT false), set for scalar (no GROUP BY) aggregation; it flows into the high bit of the agg gate’s info2.

That fourth argument is where the semimodule construction of The Semimodule Picture is actually assembled: every semimod gate is one simple tensor , and the agg gate at the root of the provenance_aggregate call is their formal sum .

Which rows are children of the agg gate

The invariant is that the children of an agg gate are exactly the inputs the aggregate reads; the value-aware evaluators (HAVING, moments, sampling) rely on it. Three cases, decided in make_row_semimod, which builds the contribution of a row for make_aggregation_expression:

• NULL-skipping aggregates (sum, min, max, avg, string_agg, choose, …). provenance_semimod returns NULL for a NULL value and provenance_aggregate drops such entries, so a row with a NULL argument is no child. A FILTER (WHERE f) clause is folded into the argument, as CASE WHEN f THEN arg END, which makes a row failing f indistinguishable from a row with a NULL argument – including for HAVING agg IS [NOT] NULL, which splits the group on that per-row value.

• count. count(*) contributes the constant 1 and count(e) the value CASE WHEN e IS NOT NULL THEN 1 ELSE 0 END; with a FILTER the condition becomes f (respectively f AND e IS NOT NULL). A row that does not count thus stays a child, of value 0: it still witnesses its group, and a lifted HAVING count(...) = 0 replaces the group’s δ, so dropping the row would let the comparison hold in the world where the group is empty. The gate keeps the COUNT operator, which is what tells evaluators that the empty input has value 0 and not NULL.

• NULL-keeping aggregates (array_agg, json_agg, jsonb_agg, json_object_agg, jsonb_object_agg, and user-defined aggregates with a non-strict transition function; see aggregate_keeps_nulls), whose result enumerates every input. They use provenance_semimod_nullable, which maps a NULL value to a semimod gate over the constant value gate gate_null; a FILTER is copied onto the token array_agg, removing children exactly as it removes inputs. No existence issue arises here: over an empty input these aggregates are NULL, and a comparison with NULL never holds. HAVING agg IS [NOT] NULL accordingly splits the group on “passes the filter”, not on the value.

For built-in aggregates the catalog cannot tell the first and last cases apart: a non-strict transition function says nothing (sum(bigint) and string_agg have one and skip NULL), hence the explicit list. For a user-defined aggregate the transition function is all there is to go by: a strict one is never called on a NULL input, so the aggregate is NULL-skipping; a non-strict one does receive NULL inputs, and the aggregate is treated as NULL-keeping, which loses nothing (a kept NULL input can still be ignored by an evaluator, a dropped one cannot be recovered). ProvSQL’s own choose, non-strict and NULL-skipping, is exempted. No user-defined aggregate has an evaluator, so this choice shows in the displayed circuit and in HAVING agg IS [NOT] NULL only.

gate_null is a constant in the manner of gate_zero and gate_one, but of type value, with NULL as its display text. The C++ side knows it by its UUID (GATE_NULL_UUID in having_semantics.hpp), which is what distinguishes it from the value gate of the string 'NULL': its seed, 'null', is not of the form 'value' || text that every actual value has. The array_agg comparison of having_semantics.hpp maps it, and an unquoted NULL of the constant array, to one element that equals only itself, which is how PostgreSQL compares arrays.

Aggregates over random_variable (next section but one) take a different route, and handle FILTER differently: the aggregates make_rv_aggregate_expression rebuilds simply carry the clause over, since their result is a random_variable built from the rows PostgreSQL feeds them.

Constant arithmetic on an aggregate (sum(x) * 2) is pushed into the argument by try_push_into_aggref before all this, so it composes with FILTER: the identities it uses hold over any multiset of rows.

The row-level side of the rewrite is much simpler. It reuses the ordinary get_provenance_attributes collection, combines the per-row tokens with provenance_plus(array_agg(...)), and – for grouped aggregation whose HAVING (if any) is not lifted – wraps the result in provenance_delta (scalar aggregation gets gate_one; a lifted HAVING replaces the token with provenance_cmp). The row-level token therefore has no semimodule content: it only records which input rows witness the output row’s existence.

The end result is that each row of the aggregation output carries:

• per-aggregate-column agg_token values whose UUID points to an agg gate combining semimod per-tuple contributions;

• a row-level provsql token whose root is a delta gate over the ⊕ of the group’s row tokens.

These two pieces are independent: an evaluator that asks for the provenance of a value in the result reaches an agg gate; an evaluator that asks for the provenance of the row itself reaches a delta gate.

Aggregates as window functions

An aggregate used as a window function, in a query without aggregation of its own, is rewritten by replace_window_aggregations, which calls make_window_aggregation_expression on each WindowFunc of the target list:

provenance_aggregate(fn, type,
                     f(x) OVER w,
                     array_agg(provenance_semimod(x, k)) OVER w,
                     is_scalar)

Both window calls reference the same WindowClause (the same winref), so the token array is collected over exactly the rows of the frame, and make_row_semimod builds each row’s contribution as for a group. The row-level token is left as it is: a window function neither merges nor removes rows. For a whole-partition window, the gate of each row is the gate of the GROUP BY on the partition attributes, as the equivalence of a window aggregate with the join of each row to the grouped query predicts (Equivalence (4) of Lindner, Naumann and Lerner, Window Function Optimization: Co-Evaluation and Other Techniques, PVLDB 19(11), 2026).

The frame of a window is only known in each possible world if it depends on the values of the rows, not on their positions: the previous row of a world is its previous present row. window_frame_by_values accepts a window without ORDER BY, RANGE frames, GROUPS frames without offsets and ROWS frames over the whole partition; any other window function is left as it is, and process_query emits its warning. is_scalar is set when the frame may exclude the current row (window_frame_has_current_row): the frame may then be empty in a world where the row exists, and has the value of an aggregation over no row, for which provenance_aggregate builds an agg gate without children rather than gate_zero. When the frame always contains the current row, the grouped convention is kept, which is what makes whole-partition gates those of the GROUP BY.

A sort key on a rewritten value is moved to a junk copy of the original window call, so ORDER BY sorts on the displayed value.

The ranks are counts over a frame appended to the query (make_rank_window): a copy of the window of the rank with the frame RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW EXCLUDE GROUP, the rows strictly before the current one, which needs PostgreSQL 11.

• rank() is 1 + count(*) over that frame (make_rank_expression). The frame excludes the current row, so the count does not read the token that multiplies the comparisons on it, and the comparison evaluators, which fold the + 1 into their threshold (see Probability Evaluation), see independent contributors.

• dense_rank() counts the distinct ordering values of that frame (make_dense_rank_expression). Window aggregates have no DISTINCT: two array_agg over the frame collect the ordering values, as a row value, and the row tokens, and window_distinct_tokens groups them by value into one semimod(1, ⊕ tokens) per value, the children of a scalar COUNT gate whose value is dense_rank() - 1.

• row_number() is its rank wrapped in row_number_as_rank, which returns the rank and warns, once per statement, when PostgreSQL’s row number differs from it.

Currently Supported Aggregates

The AggregationOperator enum in Aggregation.h lists the operators recognised in C++: COUNT (whose per-row values are 0 or 1, but which stays distinct from SUM because it is 0, not NULL, over an empty input), SUM, MIN, MAX, AVG, AND, OR, CHOOSE, and ARRAY_AGG. Only the aggregates the Monte-Carlo sampler and the subset enumerator evaluate directly get an Aggregator accumulator (the numeric ones – SUM / COUNT / MIN / MAX / AVG – and CHOOSE); the boolean aggregates (bool_and / bool_or / every) and array_agg exist only as enum values for routing, because their HAVING comparisons are resolved entirely by the m-semiring rewrite in having_semantics.cpp (a first-present-occurrence characterisation, a closed form in absorptive -over- distributive semirings, a sum of witnesses for the existential bool_or = true / bool_and = false in every absorptive semiring, and an exact enumeration elsewhere, and a possible-worlds enumeration respectively) and never reach the deterministic sampler. Adding to the accumulator list is the topic of the next section.

Random-Variable Aggregates

When the aggregated column has type random_variable (see Continuous Distributions), the rewriter routes through a separate path: instead of producing a provenance_aggregate call that wraps the original Aggref in an agg_token, it produces an aggregate that returns a random_variable root. The aggregate’s result is the lifted scalar (or its product / average / extremum analogue), realised as a single gate_arith over per-row gate_mixture children.

The dispatch in make_aggregation_expression keys on aggtype (the aggregate’s result type OID): when aggtype = OID_TYPE_RANDOM_VARIABLE, the per-row argument X_i is wrapped in rv_aggregate_semimod (a mixture over the row’s provenance gate and the identity for the aggregate) before it reaches the SFUNC. The identity is dispatched per aggregate — 0 for sum, and through the three-argument identity-parameterised form of rv_aggregate_semimod, 1 for product, -Infinity for max, +Infinity for min — so a row absent in a world contributes the fold’s identity rather than perturbing it. avg is rewritten at the same site into the “AVG = SUM / COUNT” identity (a numerator sum over the wrapped rows divided by a sum of mixture(prov_i, 1, 0) indicators). The aggregate’s SFUNC accumulates the wrapped per-row UUIDs; the FFUNC is then a plain fold building the final gate_arith root (PLUS / TIMES / MAX / MIN). The RV-returning aggregates currently shipped – sum, avg, product, max, min – share an INITCOND = '{}' so the FFUNC runs even on an empty group, and can therefore tell an empty group apart from a group whose every input was NULL. Both report SQL NULL.

This is the semimodule-of-mixtures shape: rather than minting a new M-polymorphic gate_agg that would require parallel evaluation paths in every analytical evaluator, the rewrite composes through the existing gate_arith / gate_mixture rules. See Continuous Distributions for the FFUNC details.

Step-by-Step: Adding a New Aggregate

As a running example, assume we want to add bit_and – the bitwise-AND of all non-null integer values in a group. The mechanics are independent of which aggregate you are adding; the only design point is the C++ accumulator that knows how to combine the values incrementally.

1. Add an enum value. In Aggregation.h, extend AggregationOperator:

   enum class AggregationOperator {
     COUNT, SUM, MIN, MAX, AVG,
     AND, OR,
     CHOOSE, ARRAY_AGG,
     BIT_AND,     // new
     NONE,
   };
   

2. Map the PostgreSQL function name to the enum. In Aggregation.cpp, extend getAggregationOperator with a case matching the PostgreSQL function name returned by get_func_name():

   } else if(func_name == "bit_and") {
     op = AggregationOperator::BIT_AND;
   

   Each PostgreSQL aggregate function with distinct semantics needs its own enum value and accumulator; aliases with identical semantics (e.g. stddev / stddev_samp) can share one.

3. Implement the accumulator. Add a templated Aggregator subclass in Aggregation.cpp next to the existing ones (SumAgg, MinAgg, AvgAgg, etc.). The interface is three virtual methods (resultType() defaults to inputType()):

   template <typename T>
   struct BitAndAgg : Aggregator {
     T acc = ~T{0};  // all-ones identity
     bool has = false;
     void add(const AggValue& x) override {
       if (x.getType() == ValueType::NONE) return;
       acc &= std::get<T>(x.v);
       has = true;
     }
     AggValue finalize() const override {
       return has ? AggValue{acc} : AggValue{};
     }
     ValueType inputType() const override { return ValueType::INT; }
   };
   

   An accumulator is only warranted for an aggregate the sampler / enumerator must evaluate on concrete values; an aggregate whose HAVING semantics are resolved by the m-semiring rewrite (like the boolean aggregates and array_agg) needs only the enum value and routing in having_semantics.cpp.

4. Instantiate the accumulator. Extend makeAggregator in Aggregation.cpp with a case that creates the right template instantiation for each supported input type:

   case AggregationOperator::BIT_AND:
     switch (t) {
       case ValueType::INT: return std::make_unique<BitAndAgg<long>>();
       default:
         throw std::runtime_error("BIT_AND not supported for this type");
     }
   

5. Add a regression test. Create test/sql/agg_bit_and.sql and its expected output, following the pattern of the existing aggregation tests. Reference it from test/schedule.common (see Testing and Build System for the schedule conventions).

6. Update the user guide. Mention the new aggregate in Aggregation and Grouping, and add it to the list of currently supported operators in the “Currently Supported Aggregates” section above.

Nothing else needs to change: the query rewriter, the provenance_aggregate SQL function, and the agg_token composite type all operate on OIDs and metadata, so they pick up new aggregates automatically once steps 1–4 are in place.

CASE over aggregates

A searched CASE whose branches are aggregates lowers to a gate_case carried by an agg_token – the aggregate-carrier counterpart of the RV-carrier CASE (Continuous Distributions). The gate type is carrier-agnostic (its branch types discriminate the carrier), so no new gate or on-disk change is needed.

Planner lowering (provsql.c). Unlike the RV pass, which runs early, the aggregate-CASE rewrite (rewrite_agg_cases) must run after replace_aggregations_by_provenance_aggregate – only then are the branch sum(y) / guard sum(x) > 3 lowered to agg_token and an agg comparison. It runs before insert_agg_token_casts so the result stays an agg_token (rather than being cast to numeric, which would drop the provenance). build_agg_case mirrors build_rv_case but lowers each guard with having_Expr_to_provenance_cmp (the same evaluator as a HAVING comparison, which the RV path’s predicate_to_condition_gate cannot reach post-lowering because it dispatches on the now-absent Aggref), and casts each branch value agg_token -> uuid (a constant branch is lifted with agg_value_gate, the agg-side as_random). It emits agg_case(uuid[]).

Degradation when the lowering does not apply. A CASE the rewrite leaves alone – the simple form CASE <arg> WHEN ..., a shape build_agg_case declines, or a schema whose upgrade path predates agg_case (OID_FUNCTION_AGG_CASE invalid) – still carries agg_token-typed branches under the original (e.g. numeric) CASE type. cast_agg_token_mutator therefore has a CaseExpr arm that casts such branches back to the CASE’s result type (their actual-world values, with the provenance-loss warning). This is load-bearing: a bare 117-byte fixed-length agg_token datum left under a varlena-typed CASE would be reinterpreted as a varlena whose “length” is UUID text bytes – a server crash in tts_virtual_materialize or silent tuple corruption.

Exact evaluation (agg_raw_moment). A case gate is handled by the conditional-on-defined possible-worlds identity over the first-match regions (built with provenance_times / provenance_not), each conjoined with the branch’s defined event (agg_defined_event: gate_one for sum / count / constants, whose empty group is the real value 0; “some contributing row present” – the OR of the semimod children’s row tokens – for min / max / avg, which are NULL on an empty group; recursive for a nested CASE). The moment therefore conditions on the CASE’s value being defined, matching the bare MIN / MAX convention, and returns NULL only when the defined mass is zero; when every branch is defined everywhere the defined mass equals and the formula reduces to the plain region-weighted sum. Both factors reuse existing exact machinery – the Boolean probability of the region-and-defined event and a recursive conditional agg_raw_moment of the branch (whose MIN / MAX / CASE arms condition on their own definedness within the region, so the two factors weigh the same worlds) – so no new possible-worlds enumeration is written; the regions are mutually exclusive, so the terms sum without inclusion–exclusion. Per branch: a constant is a Dirac (), a single aggregate or nested CASE is exact via agg_raw_moment, and an arithmetic / composite / avg branch falls back to the Monte-Carlo scalar path (rv_moment), which composes gate_case with the aggregate leaves. The MC sampler already handles gate_case + gate_agg with no change.

AVG moments (agg_raw_moment’s avg arm). AVG = SUM/COUNT is a ratio of two correlated world-dependent quantities, so the SUM arm’s k-tuple expansion does not apply. The exact arm (agg_avg_moment_exact -> aggAvgRawMomentExact in AggMarginalEvaluator.cpp) computes from the joint distribution – the sumCountPMF machinery the HAVING comparison pre-pass already uses, now templated on the weight type (the integral instantiation keeps the HAVING path byte-identical; the double instantiation shares the independent-fold and laminar-shared-root branches, so join-anchored groups stay exact, and self-gates on the integer-only additive-separation product branch). Any out-of-scope shape – an outer conditioning event, shared leaves beyond the laminar class, compound contributors – falls back to the Monte-Carlo scalar path, whose NaN-skip on empty draws implements the same conditional-on-defined convention.

Display. The token’s cell carries the actual-world CASE value, like any aggregate’s cell: agg_case resolves it through the circuit with agg_gate_value (agg / arith / value gates read their recorded extra; a case walks its guards first-match via agg_guard_holds, which evaluates each cmp gate on its operands’ deterministic values under the operator recorded in info1, with Kleene AND/OR for times / plus combinations). agg_token_value_text uses the same walker for case / conditioned / semimod / value roots, so every aggregate-carrying token renders as value (*) – both in psql cells and in Studio result tables (which recover the display from the bare UUID).

Open: closed-form moments for arithmetic-combination branches (inherits the bare sum(x) + sum(y) limitation).