多重集分组聚合 | Codeboy's Blog

形式陈述

重复行也是查询输入

集合关系代数只记录一行是否出现。多重集关系（bag）还记录它出现多少次：对每个元组 $t$ ，用非负整数 $m_R(t)$ 表示重数，要求非零重数的元组只有有限多个。重数为零表示没有这行；相同值出现三次，就记作一行数据配重数 $3$ 。

本页固定有限 bag、相等连接和精确有理数数值列，不包含 NULL、排序、外连接、窗口或 DISTINCT 聚合。自然连接将匹配行的重数相乘；投影将落入同一输出行的重数相加。这与查询来源的自然数标注相符，但本页要进一步把重数用于计算结果列中的数值。

给定分组键 $k(t)$ 和数值列 $v(t)$ ，对一个键值 $g$ 定义

n_g=\sum_{k(t)=g}m_R(t),\qquad s_g=\sum_{k(t)=g}m_R(t)v(t).

普通按键分组对每个 $n_g>0$ 的键输出一行，其聚合值为

\operatorname{COUNT}(g)=n_g,\qquad \operatorname{SUM}(g)=s_g,\qquad \operatorname{AVG}(g)=\frac{s_g}{n_g}.

输出行的重数为一。列中的 $n_g$ 是这个摘要代表的输入行数，不是要求把摘要行再复制 $n_g$ 次。由于没有 NULL，COUNT(*) 与对所选数值列计数在本模型中相同。

可合并状态与空组

为一个分组保存状态 $(n,s)$ ，合并两份互不重叠的输入贡献时按分量相加：

(n_1,s_1)\oplus(n_2,s_2)=(n_1+n_2,s_1+s_2).

单位状态为 $(0,0)$ 。COUNT 读取第一分量，SUM 读取第二分量，AVG 等全部贡献合并后再做一次 $s/n$ 。因此只保存部分平均值通常不够；还需知道每个平均值代表多少行。

按显式键分组时，空输入没有出现过的键，结果为空。全局聚合则约定只有一个空键，即使输入为空也输出状态 $(0,0)$ ：COUNT 为零，本页数学 SUM 取空和零，AVG 因分母为零而未定义。这是本页的空输入接口；SQL 的空输入 SUM/AVG 通常返回 NULL，不能把这里的空和约定不加说明地当作 SQL 返回值。

直觉

连接把匹配事实配成对。若一条订单出现两份、与它匹配的标签也出现两份，就有四个订单—标签配对；每个配对都参与聚合。列值相同不意味着这些贡献可以悄悄合并成一份。

分组是把相同键的贡献收集到一起。COUNT 统计贡献份数，SUM 累计每份的数值，AVG 把这两个量相除。例如金额 $10,10,30$ 的摘要是 $(3,50)$ ，平均是 $50/3$ 。它再与一份金额 $100$ 合并时，正确结果来自 $(3,50)+(1,100)=(4,150)$ ，而不是给两个局部平均相同权重。

提前聚合可以减少连接中反复处理的行，但摘要必须保存后续仍会用到的信息。连接键决定去找谁，分组键决定最后算进哪一组， $(n,s)$ 决定已经压缩了多少份贡献、总值是多少。只要其中一项丢失，后续就可能无法还原原查询。

同一客户的两份订单摘要按标签重数缩放，再合并成七份贡献、总金额二百，最后求平均二百除以七 — 先保留份数与总和，再合并求平均

例子与边界

两张有重复行的表

订单表 Orders(Customer, Product, Amount) 如下。最后一列是 bag 重数，金额采用精确整数；它不是价格乘数量的业务规则，而是明确表示输入中这条元组有几份。

Customer	Product	Amount	重数
A	p	10	2
A	p	30	1
A	q	100	1
B	p	20	1
B	q	50	2
C	r	7	1

标签表 Tags(Product, Tag) 为：

Product	Tag	重数
p	sale	2
p	featured	1
q	sale	1
q	featured	3

查询按 Product 连接，再按 (Customer, Tag) 分组，计算订单金额的 COUNT、SUM、AVG。两表在 Product 上都不要求唯一；正是多对多匹配让重复计数成为核心问题。

展开全部连接贡献

连接中的每行重数等于两条输入重数之积：

Customer	Product	Amount	Tag	连接重数
A	p	10	sale	4
A	p	10	featured	2
A	p	30	sale	2
A	p	30	featured	1
A	q	100	sale	1
A	q	100	featured	3
B	p	20	sale	2
B	p	20	featured	1
B	q	50	sale	2
B	q	50	featured	6

十种不同元组代表 $24$ 份配对。也可以按产品核对：p 有四份订单、三份标签，贡献 $4\cdot3=12$ ；q 有三份订单、四份标签，贡献 $12$ 。r 没有匹配标签，C 的订单在内连接中不产生结果。

A/sale 这一组包含四份金额 $10$ 、两份金额 $30$ 、一份金额 $100$ ，所以 COUNT 为 $7$ ，SUM 为 $4\cdot10+2\cdot30+100=200$ 。同样计算其余组，得到完整结果：

Customer	Tag	COUNT	SUM	AVG
A	sale	7	200	$200/7$
A	featured	6	350	$175/3$
B	sale	4	140	$35$
B	featured	7	320	$320/7$

四个计数之和为 $24$ ，四个总和之和为 $1010$ 。这两个汇总是检查转写的方便方法；查询本身仍返回四组，不能把各组 AVG 再不加权地平均成全表平均。

用摘要重做同一个查询

先按 (Customer, Product) 汇总 Orders，保留连接列 Product：

Customer	Product	$n$	$s$
A	p	3	50
A	q	1	100
B	p	1	20
B	q	2	100
C	r	1	7

摘要遇到重数为 $u$ 的匹配标签，就贡献 $(un,us)$ 。再按 (Customer, Tag) 合并这些状态，四组依次为

\begin{aligned} \text{A/sale}:&\quad 2(3,50)+(1,100)=(7,200),\\ \text{A/featured}:&\quad (3,50)+3(1,100)=(6,350),\\ \text{B/sale}:&\quad 2(1,20)+(2,100)=(4,140),\\ \text{B/featured}:&\quad (1,20)+3(2,100)=(7,320). \end{aligned}

结果与展开连接完全相同。C/r 的摘要找不到标签，仍没有贡献。这里使用相同数据完成两种执行方式，下一节的有限和证明则保证它们对整个模型都等价。

三种看似省事、实际改变结果的改写

把重复元组去掉。 若在完整连接后做 DISTINCT，A/sale 只留下金额 $10,30,100$ 各一份，计数变成 $3$ ，总和变成 $140$ 。这是另一条查询，不是原 bag 查询的优化。仅把 Tags 的重复行去掉也会改变答案：A/sale 会变为计数 $4$ 、总和 $150$ 。

只携带平均值。 A/p 的部分平均是 $50/3$ ，A/q 是 $100$ 。摘要与原 Tags 连接后，前者出现两次、后者一次；若对这三条摘要记录直接取平均，就得到

\frac{2(50/3)+100}{3}=\frac{400}{9},

与正确的 $200/7$ 不同。错误在于给三个摘要副本相同权重，忘了 A/p 的每份摘要代表三份原订单。对摘要行再做 COUNT(*) 也只会得到 $3$ ；正确计数要累加它们携带的 $n$ ，得到 $7$ 。

过早丢掉 Product。 比较两份单行 Orders：一份是 $(A,p,10)$ ，另一份是 $(A,q,10)$ ，Tags 只含 $(p,\mathrm{sale})$ 。若只按 Customer 提前汇总，两份都变成 $(A,n=1,s=10)$ ，但原查询在第一份上有结果，在第二份上为空。相同摘要对应不同答案，已经证明这种摘要没有保留足够信息。

推论与应用

连接之前聚合的精确条件与证明

设 $R$ 的列分成 $(A,J,X)$ ， $S$ 的列分成 $(J,B,Y)$ 。其中 $J$ 是全部连接列， $A,B$ 是各侧最后要保留的分组列， $X$ 是一列要相加的有理数， $Y$ 表示其余不参与聚合的列。 $A,J,B,Y$ 可以为空或包含多列，左右除 $J$ 外先重命名为互异列。查询按 $J$ 的相等值连接，按 $(A,B)$ 分组，聚合左侧 $X$ 。

定义两侧摘要

c_R(a,j)=\sum_xm_R(a,j,x),\qquad s_R(a,j)=\sum_xm_R(a,j,x)x,\qquad c_S(j,b)=\sum_ym_S(j,b,y).

那么每个最终组满足

\boxed{n_{a,b}=\sum_jc_R(a,j)c_S(j,b),\qquad s_{a,b}=\sum_js_R(a,j)c_S(j,b).}

证明从原始连接的重数开始。计数为

\begin{aligned} n_{a,b} &=\sum_{j,x,y}m_R(a,j,x)m_S(j,b,y)\\ &=\sum_j\left(\sum_xm_R(a,j,x)\right) \left(\sum_ym_S(j,b,y)\right)\\ &=\sum_jc_R(a,j)c_S(j,b). \end{aligned}

SUM 在同一求和中多乘一个金额 $x$ ：

\begin{aligned} s_{a,b} &=\sum_{j,x,y}m_R(a,j,x)m_S(j,b,y)x\\ &=\sum_j\left(\sum_xm_R(a,j,x)x\right) \left(\sum_ym_S(j,b,y)\right)\\ &=\sum_js_R(a,j)c_S(j,b). \end{aligned}

所有支撑有限，重排和分配都合法，不涉及极限或绝对收敛。对于显式键分组， $n_{a,b}>0$ 恰好表示原连接存在该组，故输出哪些键也相同；最后对正计数组求 $s_{a,b}/n_{a,b}$ ，AVG 同样一致。没有匹配的连接键贡献零，空输入也符合这些等式。

若 $A=B=\varnothing$ 且采用全局聚合接口，两种执行都额外保留唯一空键：没有匹配行时输出状态 $(0,0)$ ，AVG 未定义。此时不以 $n>0$ 删除该行。空和恒等式仍成立，最后的输出约定也必须一致，才能得到完整的查询等价。

这说明一种正确的执行方式：先把 R 按 $(A,J)$ 聚合为 $(c_R,s_R)$ ，把 S 按 $(J,B)$ 聚合为 $c_S$ ；连接摘要后贡献 $(c_Rc_S,s_Rc_S)$ ，最后按 $(A,B)$ 合并。每条摘要结果仍只输出一次，代表的行数由列 $c_R,c_S$ 携带。证明没有假设外键、一对一或多对一关系，所以覆盖前面的多对多例子。

与集合查询、来源和执行代价的边界

这份改写要求后续操作只读取留下的键和摘要。若过滤条件还要判断原金额是否大于某个阈值，就应先在原数据上过滤，或另外证明摘要足以支持该判断。上面的等式也不直接处理 DISTINCT AVG、外连接补行或 NULL 的三值语义。

COUNT/SUM 可通过加法合并部分状态，AVG 则需要固定大小的 $(n,s)$ 状态；Gray 等人的分类称后者为代数型聚合。给每组只存一个平均数，无法区分“一行的平均”和“一百万行的平均”。对于一般精确中位数， $(n,s)$ 也不足够，不能把 AVG 的合并公式当成所有聚合的模板。

查询来源中的自然数标注解释了为什么连接乘重数、投影加重数；聚合又把金额与重数结合，生成新的数值列。因此这里没有宣称原来的来源多项式通用求值定理已覆盖任意聚合。经典关系代数与演算的集合表达力等价也保留原来的不含聚合范围。

正确下推可以压缩重复贡献，但是否更快取决于分组数量、摘要大小和连接实现。若每条输入都带不同的 $(A,J)$ ，预聚合几乎不能缩小左表，还会增加一次处理。上述证明给的是查询结果保持，成本优劣需要另行估计。

终点自测：从两张输入表重建十种连接元组及其 $24$ 份重数，计算四组结果；再只用五条 Orders 摘要重做查询，并分别指出去重、平均部分平均和遗漏 Product 破坏了证明中的哪一步。

参考资料

Todd J. Green, Grigoris Karvounarakis, and Val Tannen, “Provenance Semirings”, PODS 2007, pp. 31–40，§3，Definitions 3.1–3.2，p. 33：有限支撑关系、自然数 bag 标注与连接乘法、投影加法。
Jim Gray et al., “Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals”, Data Mining and Knowledge Discovery 1, 1997, pp. 29–53，§5，pp. 48–49：分布型与代数型聚合，AVG 的 sum/count 合并状态。
Surajit Chaudhuri and Kyuseok Shim, “Including Group-By in Query Optimization”, VLDB 1994, pp. 354–366，§2.3，pp. 356–357；§§3.2–3.4，pp. 358–361：提前分组保留的列、部分聚合与 Group-Count。本页独立证明明确有限 bag 模型中的两侧摘要恒等式。
PostgreSQL Documentation, Aggregate Functions，§9.21，聚合表后的空输入说明：COUNT 返回零，其他多数聚合包括 SUM 在空输入上返回 NULL。仅用于比较 SQL 与本页数学空和约定。

形式陈述 ​

重复行也是查询输入 ​

可合并状态与空组 ​

两张有重复行的表 ​

展开全部连接贡献 ​

用摘要重做同一个查询 ​

三种看似省事、实际改变结果的改写 ​

连接之前聚合的精确条件与证明 ​

与集合查询、来源和执行代价的边界 ​

反向链接