Chapter 12Grouping and Aggregation

This chapter explains how GQL transforms bags of bindings into grouped summaries using the GROUP BY clause and aggregate functions. We formalize grouping as a partitioning of binding tables by key expressions, specify the behavior of standard and collection-valued aggregates (including their treatment of $null$ and empty inputs), and describe the evaluation pipeline that combines WHERE, GROUP BY, HAVING, DISTINCT, and ordering into a single coherent semantics.

12.1 GROUP BY and Aggregates

A concrete use of GROUP BY and SUM appears in Section 4.4.

Grouping function. Let $T \in BT$ be an input binding table with $bag (T) = ⟨ τ, B ⟩$ , and $K = ⟨ k_{1}, \dots, k_{s} ⟩$ be an ordered sequence of grouping keys (names or expressions). We define the key extractor

κ_{K} (r) = ⟨ ⟦ k_{1} ⟧ (r), \dots, ⟦ k_{s} ⟧ (r) ⟩ .

Write $u \approx_{nd} v$ when $u$ and $v$ are not distinct under GQL’s recursive distinctness rules. The grouping induces a finite index set $I$ (one index per distinctness class of $κ_{K}$ -values) and a family of pairwise disjoint sub-bags ${(B_{i})}_{i \in I}$ with $B_{i} ⊑_{bag} B$ such that

B = \underset{i \in I}{⊎} B_{i} and \forall i \in I \forall r, s \in B_{i} : κ_{K} (r) \approx_{nd} κ_{K} (s) .

Here $B_{i} ⊑_{bag} B$ means $B_{i} (r) \leq B (r)$ for every record $r$ . If distinctness cannot be determined because two values are not comparable, grouping raises data exception 22G04. For the empty grouping sequence $K = ⟨ ⟩$ , take $I = {*}$ and $B_{*} = B$ , including when $B$ is empty. Thus global aggregation has one group and, on empty input, evaluates aggregates over the empty multiset.

Aggregators. An aggregator is a partial function

F : M_{fin} (𝕍) ⇀ 𝕍 \cup {null}

equipped with a null-handling policy and an input-type requirement appropriate to the particular aggregate operation. For a value expression $E$ , the notation $F (E)$ denotes the application of $F$ to the multiset

{{⟦E⟧ (r) ∣ r \in B_{i}}}

obtained by evaluating $E$ for every record of a group $B_{i}$ .

Except for $COUNT (*)$ , aggregate functions eliminate $null$ inputs before computing their result. If no set quantifier is specified, $ALL$ is implicit, so duplicate values and their multiplicities are preserved. With $DISTINCT$ , duplicate non- $null$ values are eliminated before the aggregate operation is applied.

The principal aggregators and their default empty-input behavior are as follows:

$COUNT (E)$ : returns the number of records in the group for which $⟦E⟧ (r) \neq null$ . Under $ALL$ , repeated values are counted repeatedly; under $DISTINCT$ , each distinct non- $null$ value is counted once. If no non- $null$ value remains, the result is $0$ .
${COUNT}^{*} \equiv COUNT (*)$ : returns the number of records in the group, independently of the values contained in those records. In particular, records containing only $null$ values are still counted. On an empty group, the result is $0$ .
$SUM (E)$ : returns the arithmetic sum of the non- $null$ numeric values of $E$ , with multiplicities preserved under $ALL$ . If no non- $null$ value remains, the default result is $null$ .
$AVG (E)$ : if at least one non- $null$ numeric value of $E$ remains, returns their arithmetic mean, that is, their sum divided by their number. If no non- $null$ value remains, the result is $null$ .
$MIN (E)$ : returns the least non- $null$ value of $E$ , according to the applicable GQL ordering rules. If no non- $null$ value remains, the result is $null$ .
$MAX (E)$ : returns the greatest non- $null$ value of $E$ , according to the applicable GQL ordering rules. If no non- $null$ value remains, the result is $null$ .
$PRODUCT (E)$ , if supported: returns the arithmetic product of the non- $null$ numeric values of $E$ , with multiplicities preserved under $ALL$ . If no non- $null$ value remains, the default result is $null$ .
$COLLECT_LIST (E)$ , when optional Feature $GF 10$ is supported: returns a list containing the non- $null$ values of $E$ . Under $ALL$ , multiplicities are preserved; under $DISTINCT$ , each distinct value occurs once. The list follows the order induced by the input group when such an order is defined; no application-independent order is assumed for an unordered group. If no non- $null$ value remains, the result is the empty list.

When the corresponding optional feature is supported, GQL permits an explicit empty-aggregate behavior for $SUM$ and $PRODUCT$ . For example,

SUM (E, 0 ON EMPTY) returns 0, and PRODUCT (E, 1 ON EMPTY) returns 1,

when no non- $null$ input value remains.

Empty-aggregate behavior. By default, aggregates over an empty input multiset yield $null$ , except that $COUNT (*)$ and $COUNT (E)$ yield $0$ , and $COLLECT_LIST$ yields the empty list. When the optional feature $F 443$ (empty aggregate behavior) is supported, the aggregate functions $SUM$ and $PRODUCT$ admit an ON EMPTY clause:

SUM (E, 0 ON EMPTY) and PRODUCT (E, 1 ON EMPTY),

which override the default $null$ result on empty input (as specified in GQL). Using NULL ON EMPTY is permitted but semantically redundant with the default behavior.

Grouped extend. For expressions $E_{j}$ used inside aggregators and a per-group bag projection

π_{E_{j}}^{*} (B_{i}) = {{⟦ E_{j} ⟧ (r) ∣ r \in B_{i}}} (i \in I),

(a multiset, possibly containing $null$ values), let $r_{i}$ be the record consisting of the key fields determined by partition $i$ and the aggregated fields $n_{j} : = F_{j} (π_{E_{j}}^{*} (B_{i}))$ . Let $τ_{K}$ be the record type contributed by the grouping keys and $τ_{j}$ the result type of the $j$ -th aggregate. The grouped result of applying GROUP BY with aggregation is

bag (GROUP BY K AGG {F_{j} (E_{j}) \mapsto n_{j}}_{j} (T)) = ⟨ τ_{K} \cup {n_{j} \mapsto τ_{j}}_{j}, \underset{i \in I}{⊎} {r_{i}} ⟩,

with the complete output descriptor carrying the ordering and preferred-column metadata prescribed for the result statement.

HAVING and post-aggregation filtering. In a SELECT statement, the HAVING clause filters groups after grouping and aggregate evaluation. In contrast to WHERE, which filters individual input records before grouping, HAVING retains only those grouped result records for which its search condition evaluates to $⊤$ .

Formally, a HAVING clause is modeled as a selection $σ_{φ}$ applied after grouping, where the predicate $φ$ may refer to grouping keys and aggregate outputs. If no HAVING clause is present, the corresponding selection is the identity, equivalently with predicate $φ \equiv ⊤$ .

Concrete syntax for GROUP BY and HAVING. At the concrete-syntax level, grouping and post-aggregation filtering are available in a SELECT statement as an optional GROUP BY clause followed by an optional HAVING clause. A RETURN statement may contain GROUP BY, but not HAVING. The following simplified BNF summarizes the relevant fragments, leaving the surrounding statement productions to the GQL standard:

BNF

group-by-clause ::= "GROUP" "BY"
                    grouping-element-list

grouping-element-list ::= grouping-element
                          { "," grouping-element }
                        | "()"  /* empty grouping set */

grouping-element ::= binding-variable-reference

having-clause ::= "HAVING" search-condition

search-condition ::= ...  /* boolean expression */

Intuitively, each binding-variable-reference identifies one grouping key, while "()" denotes the empty grouping-element list (global aggregation). The having-clause attaches a search-condition that is evaluated per group over the grouping keys and aggregate outputs, matching the post-aggregation filtering semantics described above. The non-terminal search-condition ranges over boolean expressions in the three-valued logic.

Example (aggregate results and HAVING). For the two INCLUDES edges associated with Alice in the library instance, the multiset of late fees is

M_{Alice} = {{0.0, 2.5}} .

Consequently,

\begin{gathered} COUNT (*) = 2, AVG (i.late_fee) = 1.25, \\ MIN (i.late_fee) = 0.0, MAX (i.late_fee) = 2.5 . \end{gathered}

When optional Feature $GF 10$ is supported, one possible value is

COLLECT_LIST (i.late_fee) = [0.0, 2.5],

but the reverse order is also permitted because the input group is unordered. In a SELECT statement, the group is retained by the condition

HAVING AVG(i.late_fee) > 1.0,

because its average is $1.25$ .

12.2 HAVING and DISTINCT

Grouped projection and pagination. For a bag $B$ , we write $γ_{g \to; h \to} (B)$ for the combined grouping and aggregate-projection operator. It partitions the records of $B$ according to the grouping expressions $g \to$ and produces one output record for each group by evaluating the expressions $h \to$ , which may include grouping expressions and aggregate expressions, over that group. This is a meta-level algebraic operator, not concrete GQL syntax.

For a sequence $S = ⟨ s_{1}, \dots, s_{n} ⟩$ , let ${OFFSET}_{o} (S)$ denote the sequence obtained by discarding its first $o$ elements, or the empty sequence if $o \geq n$ . Similarly, ${LIMIT}_{ℓ} (S)$ denotes the sequence containing at most the first $ℓ$ elements of $S$ . When the corresponding clause is absent, the respective operation is the identity. For an unordered bag $B$ , let ${Enum}_{impl} (B)$ denote an implementation-dependent enumeration of its record occurrences.

Let $φ$ and $𝜃$ be the WHERE and HAVING predicates, $g \to$ and $h \to$ the grouping and output-expression vectors, $o \to$ the sort-specification list, and $o, ℓ$ non-negative integer offset and limit values, respectively. Given an input bag $B_{0}$ (from a pattern match or subquery), we define the following canonical SELECT evaluation pipeline:

\begin{aligned} B_{1} & = {filter}_{φ} (B_{0}) \\ (three-valued filter: keep only ⊤) \\ B_{2} & = {\begin{matrix} γ_{g \to; h \to} (B_{1}) & if a GROUP BY or implicit global grouping \\ is present \\ B_{1} & otherwise \end{matrix} \\ B_{3} & = {\begin{matrix} σ_{𝜃} (B_{2}) & if a HAVING clause is present \\ B_{2} & otherwise \end{matrix} \\ B_{4} & = {\begin{matrix} DISTINCT (B_{3}) & if DISTINCT is requested \\ B_{3} & otherwise \end{matrix} \\ S_{0} & = {\begin{matrix} {ORDER BY}_{o \to} (B_{4}) & if an ORDER BY clause is present \\ {Enum}_{impl} (B_{4}) & otherwise \end{matrix} \\ S_{1} & = {\begin{matrix} {OFFSET}_{o} (S_{0}) & if an OFFSET clause is present \\ S_{0} & otherwise \end{matrix} \\ S^{'} & = {\begin{matrix} {LIMIT}_{ℓ} (S_{1}) & if a LIMIT clause is present \\ S_{1} & otherwise . \end{matrix} \end{aligned}

Consequently, the particular records retained by OFFSET or LIMIT are not determined unless an explicit ORDER BY clause establishes the relevant order.

The final result is $S^{'}$ , represented here as a sequence. In the absence of a WHERE clause, we take $φ \equiv ⊤$ , so that $B_{1} = B_{0}$ . In the common case of aggregates without an explicit GROUP BY, $g \to$ is empty and $h \to$ contains aggregate expressions. All input records then form a single global group, which may contain no records when $B_{1}$ is empty.

If an update or side-effecting clause is present, it consumes $B_{1}$ or a later stage explicitly specified by the statement and executes according to the transactional semantics of Chapter 19. Ordering affects the selection performed by OFFSET and LIMIT; otherwise, it affects only the presentation of the query result unless the semantics of a particular statement explicitly depend on order.

12.3 Primitive Result Statements

Position in the language. In a linear query or data-modifying statement, the tail of the statement is a primitive result statement that turns the working binding table produced by the preceding clauses into the final result sequence. Concretely, this is the part of the statement that contains the RETURN clause, an optional set quantifier and grouping, and optional ordering and pagination, corresponding to the primitive result statement, return statement, and order by and page statement of the GQL standard. Concrete primitive result statements, including aggregation and pagination, are shown in Section 4.4.

Link to the canonical pipeline. The primitive result pipeline is the RETURN portion of the account in Section 12.2: projection and optional GROUP BY, followed by DISTINCT when requested, and then ORDER BY, OFFSET, and LIMIT. Unlike SELECT, a RETURN statement has no HAVING clause. For reference, we collect here a condensed, informative BNF for the concrete syntax that drives this pipeline. The normative concrete grammar remains that of ISO/IEC 39075.

Simplified BNF. Using the bracket conventions of this book ([ … ] for optionality and { … } for repetition), we write:

BNF

primitive-result-stmt ::= return-stmt [ order-by-and-page-stmt ]
                        | "FINISH"

return-stmt ::= "RETURN" return-body

return-body ::= [ set-quant ]
                ( "*" | return-item-list )
                [ group-by-clause ]

return-item-list ::= return-item { "," return-item }

return-item ::= expr [ "AS" alias ]

set-quant   ::= "DISTINCT" | "ALL"

expr   ::= ...   /* value or aggregating expression */
alias  ::= identifier

This summary follows the productions for primitive result statement, return statement, and return statement body in the GQL standard. All alternatives and non-terminals used here are either directly taken from that grammar, or are compact names for groups of its productions. The main points of note are:

If the set-quant is omitted, the default is ALL, that is, multiset semantics apply and duplicate rows in the result are preserved.
The "*" alternative abbreviates “all visible bindings” in the current working table, that is, one projected column for each visible name, as prescribed by the standard and by our projection operators in Chapter 9.
The non-terminal group-by-clause stands for an optional GROUP BY with its grouping keys. HAVING is available in a SELECT statement, not in this RETURN production.
The non-terminal order-by-and-page-stmt is expanded in Chapter 13; it permits ORDER BY with optional pagination, OFFSET with optional LIMIT, or LIMIT alone. Its denotation is the composition of ordering and slicing operators described there.
The metavariable expr ranges over value and aggregating expressions as defined in Part III (including aggregate function calls and scalar expressions); in the standard, this corresponds to the use of aggregating value expressions in the return statement body.
The alternative "FINISH" reflects the optional FINISH statement in the standard; it is present only when the corresponding conformance feature is supported. In linear data-modifying statements, it is used for “update-only” programs whose observable effect is confined to changes of the graph state.
The form RETURN NO BINDINGS is an internal specification device rather than syntax available to GQL users. It is equivalent to RETURN ALL with an empty return-item list and without a GROUP BY clause. Consequently, it produces one unit record $⟨ ⟩$ for each input record, preserving input multiplicities while exporting no binding columns. The standard uses this form in syntactic transformations, notably when an OPTIONAL MATCH supplies no new output bindings. Since the simplified grammar above describes user-visible syntax, this internal form is intentionally omitted from its productions.

Chapter 12 — Takeaways.

Purpose: Defined how GQL transforms bags of bindings into grouped summaries using grouping keys and aggregate functions.
Introduced: Grouping as partitioning of bindings by key; aggregate evaluation over each group; post-group filtering via HAVING; duplicate control via DISTINCT at the appropriate scope.
Key distinctions: Pre-aggregation filtering versus post-aggregation filtering; bag-preserving aggregation versus duplicate elimination in aggregate inputs.
Consequences: Fixed how unknown values and empty groups affected aggregates; made grouped outputs compositional within the binding-table algebra; enabled predictable analytic patterns on graph-shaped data.
Bridge: Prepared the final result-shaping layer: ordering and pagination of (possibly aggregated) results.