“考虑固定只读快照中的等值内连接B⋈P,键为整数或NULL,普通SQL等号只让两个非NULL相等键匹配。两侧都是保留出现重数的bag:四个键7的B行与两个键7的P行,应产生八个出现对。”
形式陈述
重复行也是查询输入
集合关系代数只记录一行是否出现。多重集关系(bag)还记录它出现多少次:对每个元组
本页固定有限 bag、相等连接和精确有理数数值列,不包含 NULL、排序、外连接、窗口或 DISTINCT 聚合。自然连接将匹配行的重数相乘;投影将落入同一输出行的重数相加。这与查询来源的自然数标注相符,但本页要进一步把重数用于计算结果列中的数值。
若输入含 NULL,先用三值谓词明确哪些出现通过筛选,再按外连接补行区分真实匹配和占位。相关聚合的去相关另外保留 COUNT(*)、COUNT(列)、SUM 的空输入合同,并在共享参数计算后恢复外层每份出现;这些扩展不改变本页无 NULL 的有限和证明及数学空和约定。
给定分组键
普通按键分组对每个
输出行的重数为一。列中的
可合并状态与空组
为一个分组保存状态
单位状态为
按显式键分组时,空输入没有出现过的键,结果为空。全局聚合则约定只有一个空键,即使输入为空也输出状态
直觉
连接把匹配事实配成对。若一条订单出现两份、与它匹配的标签也出现两份,就有四个订单—标签配对;每个配对都参与聚合。列值相同不意味着这些贡献可以悄悄合并成一份。
分组是把相同键的贡献收集到一起。COUNT 统计贡献份数,SUM 累计每份的数值,AVG 把这两个量相除。例如金额
提前聚合可以减少连接中反复处理的行,但摘要必须保存后续仍会用到的信息。连接键决定去找谁,分组键决定最后算进哪一组,
例子与边界
两张有重复行的表
订单表 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 |
十种不同元组代表
A/sale 这一组包含四份金额
| Customer | Tag | COUNT | SUM | AVG |
|---|---|---|---|---|
| A | sale | 7 | 200 | |
| A | featured | 6 | 350 | |
| B | sale | 4 | 140 | |
| B | featured | 7 | 320 |
四个计数之和为
用摘要重做同一个查询
先按 (Customer, Product) 汇总 Orders,保留连接列 Product:
| Customer | Product | ||
|---|---|---|---|
| A | p | 3 | 50 |
| A | q | 1 | 100 |
| B | p | 1 | 20 |
| B | q | 2 | 100 |
| C | r | 1 | 7 |
摘要遇到重数为
结果与展开连接完全相同。C/r 的摘要找不到标签,仍没有贡献。这里使用相同数据完成两种执行方式,下一节的有限和证明则保证它们对整个模型都等价。
三种看似省事、实际改变结果的改写
把重复元组去掉。 若在完整连接后做 DISTINCT,A/sale 只留下金额
只携带平均值。 A/p 的部分平均是
与正确的
过早丢掉 Product。 比较两份单行 Orders:一份是
推论与应用
连接之前聚合的精确条件与证明
设
定义两侧摘要
那么每个最终组满足
证明从原始连接的重数开始。计数为
SUM 在同一求和中多乘一个金额
所有支撑有限,重排和分配都合法,不涉及极限或绝对收敛。对于显式键分组,
若
这说明一种正确的执行方式:先把 R 按
与集合查询、来源和执行代价的边界
这份改写要求后续操作只读取留下的键和摘要。若过滤条件还要判断原金额是否大于某个阈值,就应先在原数据上过滤,或另外证明摘要足以支持该判断。上面的等式也不直接处理 DISTINCT AVG、外连接补行或 NULL 的三值语义。
COUNT/SUM 可通过加法合并部分状态,AVG 则需要固定大小的
当输入允许删除时,可撤回分组聚合继续按带符号贡献更新(n,s),并用值频数区分“删掉一份”和“删掉最后一份”。MIN需要剩余值信息,DISTINCT只在频数跨零时改变;结果摘要自身应撤回旧行并插入新行,不能把数值总和变化当成摘要行重数。普通空组消失,全局空聚合仍使用已声明的另一份输出合同。
查询来源中的自然数标注解释了为什么连接乘重数、投影加重数;聚合又把金额与重数结合,生成新的数值列。因此这里没有宣称原来的来源多项式通用求值定理已覆盖任意聚合。经典关系代数与演算的集合表达力等价也保留原来的不含聚合范围。
正确下推可以压缩重复贡献,但是否更快取决于分组数量、摘要大小和连接实现。若每条输入都带不同的
终点自测:从两张输入表重建十种连接元组及其
同一状态的外存执行与溢写边界
上述有限和定义并不要求把每组全部原始行同时留在内存。输入按分组键排序时,使用外存排序把同键出现连续排列;扫描只保存当前键的(n,s),遇新键便输出上一组,直到EOF还要输出最后一组。循环不变量是当前状态恰好累加了当前组已经读过的出现;已输出组不会再出现。若输入为空,仍沿用本页显式键/全局聚合的不同输出约定。
无需有序输出时,可用哈希表保存key→(n,s)。每条原始行把该组加(1,v),每条压缩输入若明确携带重数m就加(m,mv)。摘要行本身的物理出现一次,不可又把(n,s)重复n次。内存主要取决于不同组数及状态宽度,不是原始行总数;COUNT/SUM的一亿份相同键可以只占一个固定状态,而精确MEDIAN通常不能用相同的两数状态完成。
若所有组状态装不下,可按组键分区写临时文件,再逐分区建状态表;同键必须同分区。固定每页2条记录,输入[(a,1),(b,2)]、[(a,3),(c,4)]、[(b,5),(d,6)]共3页,4个数据帧。取分区{a,c}与{b,d},各3条占2页,共4临时页。分区用1帧输入、2帧分区输出,读3写4;逐分区聚合再读4,输入/临时成本11。每个分区只有2个组,规定每份(key,n,s)含开销为64B,可装1个128B帧,另有1输入帧、1输出帧,峰值不超过4。
完整摘要为a:(2,4)、b:(2,7)、c:(1,4)、d:(1,6)。若输出也每页2摘要,写2页,总13。临时文件各有半空尾页,所以直接写3×3=9会漏2次I/O。若递归分区仍有太多不同键落入同一桶,可改用排序聚合并计排序成本;单个热键对COUNT/SUM状态不导致相同程度的内存膨胀,这与必须保存全部匹配出现的hash连接不同。DISTINCT集合、精确分位数等状态另需证明可合并性与内存界。
参考资料
- 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 与本页数学空和约定。
- CMU 15-445/645 Fall 2025,Sorting & Aggregation Algorithms,§3:排序/哈希聚合与溢写;六行页账本为本文独立例题。