相关子查询去相关：重数、空组与标量错误

两张完全相同的问卷可以需要同一个统计答案，但最后仍要给两位提交者各发一份结果。去相关把“算几次”与“交付几份”拆开：相同参数的计算共享一次，交付仍按原外层出现进行。

空组和多行错误是子查询接口的一部分。优化后的计划即使返回了相同的非空金额，也可能漏掉没有订单的客户，或把本来应报错的子查询变成两行普通连接输出。检查正确性时不能只盯着成功匹配的值。

六份客户、三种容易混淆的聚合 ​

Customer(label,k) 为 (A,1) 两份、(B,2)、(C,3)、(D,NULL)、(E,4) 各一份。Orders(k,amount,status) 为 (1,10,ok) 两份、(1,NULL,ok)、(2,20,hold)、(2,NULL,ok)、(NULL,99,ok)、(4,0,ok)、(4,5,ok)。对每份客户，用普通等号取其 ok 订单，计算 COUNT(*)、COUNT(amount)、SUM(amount)。

用状态 $(n,c,s)$：n 计真实订单出现，c 计非 NULL 金额，s 累加非 NULL 金额，数值累加从 0 开始。每个符合条件的订单把状态加 $(1,[amount\mathrm{IS}\mathrm{NOT}\mathrm{NULL}],amoun{t}^{\ast })$，其中指示项在金额非 NULL 时为 1、否则为 0，NULL 金额的 $amoun{t}^{\ast }=0$。完成值是 $(n,c,s)$ 当 c>0，否则为 $(n,0,NULL)$。因此内部空和为零不意味着 SQL SUM 返回零。

全局聚合没有 GROUP BY，所以即使子查询输入为空，仍有一条摘要行。B 与 C 的 SUM 都是 NULL，但 COUNT(*) 区分一份全 NULL 输入与空输入。E 的零金额仍是一个非 NULL 值，必须计入 COUNT(amount)。

一次扫描得到同一答案 ​

对 Orders 先筛 status=ok，再丢弃 NULL 键，用哈希表理路哈希表Hash table用哈希函数把键映射到桶并处理冲突的字典结构。按非 NULL k 建表 G。这里丢弃 NULL 键只因为原相关条件是普通等号。扫描结束后，G 的内部状态为 1→(3,2,20)、2→(1,0,0)、4→(2,2,5)。按上述规则完成金额为 NULL 的组，得到三个摘要。

接着逐份扫描原 Customer。非 NULL 键命中 G 时取其摘要，未命中或左键为 NULL 时取默认 $(0,0,NULL)$；两份 A 分别输出。等价的 SQL 形状是先按 k GROUP BY，再从 Customer LEFT JOIN 摘要：只对缺失摘要的计数列补零，SUM 列保留 NULL。按键摘要的 COUNT(*) 与 COUNT(amount) 本身永不为 NULL，所以 COALESCE 两个计数列为零能正确修补缺组。

不能把 SUM 也无条件 COALESCE 成零：它会把 B 的全 NULL 组和 C 的空组都改写为数值 0。也不能直接把原订单 LEFT JOIN 后做 COUNT(*)，因为 C 的占位行会被计为 1。若确需“先外连接再聚合”的形式，应在右侧先加非 NULL present 标志，并只统计真实匹配；还必须按外层出现身份分组或先计算参数域，避免把两份 A 合成一组。

现在加入 Blocked(k)={2,NULL}，用普通等号 NOT EXISTS理路半连接、反连接与NULL敏感排除Bag semijoin · Bag antijoin · NULL-aware anti join · NOT EXISTS versus NOT IN在保留左侧出现次数的前提下判定存在与不存在，完整区分NOT EXISTS和NOT IN，并实现有容量与完成状态的精确成员表。排除客户。它只去掉 B，最终为 (A,1,3,2,20) 两份，以及 (C,3,0,0,NULL)、(D,NULL,0,0,NULL)、(E,4,2,2,5) 各一份，共五份。改成 NOT IN 会得到空结果，不能称作同一去相关计划。

参数域、空组和错误的三个短反例 ​

参数域 D 为 {1,2,3,NULL,4}，共五值，原外层却有六份。若先计算每个参数的完整摘要，再用普通 = 回连，NULL 参数无法与自身匹配，D 客户消失；身份回连必须用 IS NOT DISTINCT FROM。专用 G 计划通过显式默认值直接处理左 NULL，不需要把 NULL 摘要放进 G，两种实现的责任不同。

把相关查询改成 SELECT amount FROM Orders WHERE k=c.k AND status=ok，即不聚合的标量子查询。C、D 零行返回 NULL；B 一行 NULL 也返回 NULL；E 两行 0、5 报错；A 三行也报错。即便把 A 改成只有两份相同金额 10，仍是两行错误。普通连接输出两份 10、MAX 输出一个 10、先 DISTINCT 再取标量，三者都改变了合同。

若 R 为空，即使 Orders 含很多同键行，也没有被需求的参数，结果为空而不是 CardinalityError。若外层过滤只留下 C，也不应因无关的 A 键多行而失败。对全内表建摘要可以先记录多行标志，但应在被需求的参数探测时才解释为错误。

聚合计划的一般正确性 ​

处理 Orders 前缀时，对每个已存键 k，G[k] 恰好是此前所有符合 ok 且普通等号可匹配的订单贡献之和。初始空表满足不变量；下一份不合格订单不改变任何状态，合格非 NULL 键订单只给对应组增加自己的贡献，故归纳保持。EOF 后得到全部真实组。

对一份客户 c 分情况：若 c.k 为 NULL，没有任何普通等号真匹配，默认摘要就是原全局空聚合；若键非 NULL 且 G 有组，不变量给出与逐行相关扫描完全相同的订单多重集摘要；若没有组，仍取全局空聚合默认值。每份客户只输出一次，所以外层重数不变。排除先行或后行对这个无错误聚合都只删除 B 的出现；它不对可能报错的任意表达式构成通用求值顺序定理。

标量去相关需要保留断言 ​

为标量 Q 保存每个参数的状态 (count,first)，其中 count 只需取 0、1、2 三档，2 表示至少两份；first 保留第一份值，包括 NULL。扫描前缀的不变量是 count=min(2,已读到的合格出现数)，first 等于第一份合格出现的值，哪怕它是 NULL。每次合格出现使计数按 0→1→2→2 前进，只在原计数为 0 时设置 first；初始空状态满足不变量，逐份更新保持它。合并或扫描必须数出现，不能数不同值。探测被需求参数时，0 返回 NULL，1 返回 first，2 抛 CardinalityError。键域、筛选和参数依赖仍必须与原 Q 一致。

若有已经验证且适用于过滤后查询的唯一性约束，可以证明 count 永不超过 1，再省去该断言。仅凭当前样本碰巧没有重复，或者把金额 MIN/MAX 当作“任选一值”，都没有这个证明。一般非等值相关条件还可能需要参数域与内表配对；去掉嵌套语法不自动得到线性算法。

可复算的资源账本 ​

共同无索引模型中，把三个聚合融合进一次相关扫描，六份客户各检查八份订单，共 48 次候选对条件求值；相同 A 的计算做了两遍。只对五个不同参数求一次，还需 40 次候选检查，再付参数建域及重连成本。专用等值 G 计划则只扫描八份订单，执行六次组状态更新，保留三个组；随后扫描六份客户，逐份探测并保留重数。这些是不同种类的操作，不能把“48 对比 8”直接说成墙钟快六倍。

与黑名单合成时，先读两份 Blocked，精确集合只存键 2；Orders 的六次状态更新建成三个组；最后扫描六份 Customer，D 的 NULL 键无需做普通键集合探测，其余五份各作一次排除探测。B 被删除后，A 两份、C、E 共四份探测摘要表，D 直接取默认值。最终输出五份。

计不同键状态而非字节时，峰值为三个聚合项加一个黑名单项，另有桶头、游标、标志与输出缓冲；哈希碰撞仍须完整比较。固定字长键和累加器、受控哈希负载且表能装下时，期望时间为 O(|Orders|+|Blocked|+|Customer|)，额外状态 O(g+b+1)，g、b 是两表不同有效键数。数学证明采用精确整数；若累加器超出机器字长，必须增加算术与存储成本或报告溢出，不能悄悄回绕。

页 I/O 需另给行宽、页容量和驻留安排，本页的记录操作账本不与旧 DB-4 的页数混加。客户很少且订单已有高选择性索引时，逐客户索引探测也可能更便宜；逻辑等价给优化器增加候选，并不保证一次全表汇总总是最快。

NULL-6 完整任务附出现级检查器、SQL 形状、错误变体和容量失败试验。它用于验证本页受限合同，不声称实现一般 SQL 优化器或证明任意子查询均已线性去相关。