多重集外连接与谓词位置

形式陈述

按左侧每份出现决定是否补行

输入 R、S 为有限 bag，左右列先重命名为互异；连接条件 θ 使用SQL 三值谓词，只把 T 当匹配。固定同一读视图，表达式纯、确定、无求值错误。给出现临时编号只是证明和检查方法，不要求数据库里存在用户主键。

对一份左出现 r，令 $M(r)$ 为 S 中使 θ(r,s)=T 的出现集合。左外连接逐份产生：若 M(r) 非空，输出每一对 (r,s)，不额外补行；若 M(r) 为空，恰好输出一份 $(r,\bot_S)$ ，其中右侧所有列填 NULL。F 和 U 都不构成匹配。

若同值左元组 r 的重数为 $m_R(r)$ ，令

n(r)=\sum_s m_S(s)[\theta(r,s)=T].

来自这种左值的输出总份数是 $m_R(r)\max(1,n(r))$ 。匹配对的重数为 $m_R(r)m_S(s)$ ；补行的重数为 $m_R(r)[n(r)=0]$ 。最终去掉内部出现编号，若不同来源碰巧得到同一输出值，就相加其重数。补出的 NULL 与原来存储的 NULL 在结果值上可以相同，不能用结果长相反推来源。

一个不会多补或漏补的执行过程

最直接的实现对每份 r 将 matched 置为 false，从头检查 S。每遇一份 T 匹配就置 true 并输出该对；扫描完整个 S 后，仅当 matched 仍为 false 时输出一次补行。然后才开始下一份 r。S 为空也经过“扫描结束”的分支，所以每份 r 仍有一份补行；R 为空则没有输出。

循环不变量是：当前 r 已输出的恰好是已检查右出现中的全部 T 匹配；matched 为真当且仅当这样的匹配至少一份。已完成的左出现已经完整输出且不再处理。内扫描结束后，matched 的两种值正好对应定义的两种情况，因此算法既不会漏匹配，也不会在已有匹配后多补一行。

若实现为open/next/close 迭代器，一次 next 返回匹配后必须保存当前 r、右游标和 matched。补行返回后还要标记该左出现已经完成，下一次 next 才能取新 r。EOF 是单独控制标记；一条全 NULL 记录仍可能是合法输出。

直觉

左外连接的承诺是“每份左输入都留下痕迹”。它先寻找真正匹配，只有完全找不到时才用一个占位记录表示缺失。占位不是每次比较失败都补一次，也不是把已有匹配中的 NULL 字段补成默认值。

ON 决定哪些右行可以成为伙伴；WHERE 则检查已经形成的输出，其中可能有占位行。把筛子从配对之后挪到配对之前，会改变“完全找不到伙伴”这件事本身。

每份左出现先完成全部匹配判断，再决定输出匹配组还是恰好一个NULL占位；真实匹配的NULL金额不触发补行 — 匹配证据与补行必须分开

例子与边界

同一份输入产生十二、十一或九份结果

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)。金额是整数或 NULL。

先按 c.k=o.k 左连接。A 的每份出现有三个匹配，两份共六行；B 有两行；C、D 各一份补行；E 有两行，合 $6+2+1+1+2=12$ 。订单的 NULL 键不匹配客户 D，因为 NULL=NULL 为 U。

若把 status=ok 加在 ON 中，A 仍六行；B 只匹配金额 NULL 的那一行；C、D 仍各补一行；E 两行，合十一行。若先按键左连接，再在 WHERE 中要求 status=ok，则 C、D 的补行在该比较上为 U，被筛掉，最终只有九行。

左值	按键左连接	ON 同时要求 ok	左连接后 WHERE ok
A，两份	6	6	6
B	2	1	1
C	1	1	0
D，NULL 键	1	1	0
E	2	2	2
合计	12	11	9

B 的 ok 匹配有 NULL 金额，但它是真实订单；以 amount IS NULL 当作“没有匹配”的标志，就会误把 B 当作空组。需要区分来源时，在右输入进入外连接之前增加一个非 NULL 常量 present=1；真实匹配保留 1，补行时这个列才成为 NULL。该标志不要求金额或业务键非空。

右边先筛选也可能凭空造出结果

考虑一份 R=(k=2) 与一份 S=(k=2,status=hold)，输出条件 q 为 S.status IS NULL。原来按键左连接得到真实 hold 行，WHERE q 把它删掉，结果为空。

若先把 S 用 q 筛空，再左连接，并且仍保留外层 WHERE q，外连接反而产生 status=NULL 的补行，q 为 T，结果多出一行。可见“筛选后仍保留原 WHERE”并不自动安全。这里 q 接受补行，恰好把筛选造成的新缺失变成了新答案。

推论与应用

三条有条件的改写及逐份证明

第一，p 只读取左侧原列时， $\sigma_p(R\mathbin{\mathrm{LEFT}}_\theta S)=(\sigma_pR)\mathbin{\mathrm{LEFT}}_\theta S$ 。若 p(r) 不是 T，两边都没有该左出现的输出；若为 T，两边使用完全相同的右输入和匹配集合。p 不因补行改变，故匹配与补行的份数均相同。

第二，q 只读取右侧列时， $R\mathbin{\mathrm{LEFT}}_{\theta\,\mathrm{AND}\,q}S=R\mathbin{\mathrm{LEFT}}_\theta(\sigma_qS)$ 。左边的真匹配恰好满足 θ=T 且 q=T，正是右边留下的匹配出现。每份 r 的匹配集合相同，因此是否补行也相同。这里移动的是 ON 中的 q，并没有声称 WHERE 中的 q 可直接这样移动。

第三，若对每个合法 r 都有 $q(r,\bot_S)\ne T$ ，称 q 对右侧补行拒绝 NULL。此时

\sigma_q(R\mathbin{\mathrm{LEFT}}_\theta S) =R\mathbin{\mathrm{INNER}}_{\theta\,\mathrm{AND}\,q}S.

证明分两类输出：原来的匹配对恰好在 θ 与 q 都为 T 时保留，符合右式；原来的补行全部被 q 拒绝，右式也不产生它们。真实匹配因 q 被删完时不重新补行，因为筛选发生在外连接完成之后。这就是可以把某些外连接降为内连接的条件。q 可以同时读取左右列，但拒绝补行的证明必须覆盖所有合法左值。

成本和可推广边界

直接嵌套扫描检查 $|R||S|$ 个出现对，另枚举 Z 份输出；单次谓词成本固定时为 $O(|R|+|R||S|+Z)$ ，其中 $|R|$ 项覆盖空右表时的逐份补行。若 S 可重扫，工作状态只需当前左行、右游标和一个 matched 位；若 S 是一次性流，就必须缓存、物化或重新执行，并为资源另计成本。

哈希实现仍可先按等值键找候选，但 matched 只有在完整 ON 条件为 T 后才可设置。桶中有同键记录而附加条件全部失败时，仍必须补行。FULL OUTER JOIN 还要为右侧每份出现记录是否匹配，不能只给每个键一个标志；本页的左侧状态机不直接证明这个更强接口。

外连接也不能不加条件地套用普通内连接的交换、结合和重排。先固定哪边必须保留、哪些列可能被补 NULL，以及后续谓词观察这些列的方式，再讨论等价计划。按业务值 GROUP BY 还可能把重复客户的两份出现合并；去相关给出保留外层重数的办法。

参考资料

PostgreSQL 18，Joined Tables，§7.2.1.1：外连接的补行与 ON/WHERE 顺序。本文出现级状态机、三条条件改写及 NULL-6 数据为独立推导。
Thomas Neumann、Alfons Kemper，Unnesting Arbitrary Queries，BTW 2015，§§2–3：依赖连接及外连接在改写中的语义责任。本文不把有限左外连接证明称作该论文一般去相关定理的完整证明。

形式陈述 ​

按左侧每份出现决定是否补行 ​

一个不会多补或漏补的执行过程 ​

同一份输入产生十二、十一或九份结果 ​

右边先筛选也可能凭空造出结果 ​

三条有条件的改写及逐份证明 ​

成本和可推广边界 ​

反向链接