SQL三值谓词与筛选等价

形式陈述

值、谓词和留下来的行

本页在有限多重集上加入 SQL 的 NULL。输入列取整数、字符串或 NULL；NULL 是缺失标记，不是零、空字符串或一条不存在的记录。谓词的结果为 TRUE、FALSE、UNKNOWN，以下简写 T、F、U。布尔列中的 NULL 表示 U，但“列里有 NULL”和“整行不存在”仍是两件事。

普通相等比较在两个操作数都非 NULL 时按原值判断；任一操作数为 NULL 就得到 U。因此 NULL=NULL 与 NULL<>NULL 都是 U。标量测试 x IS NULL 始终返回 T 或 F；x IS NOT DISTINCT FROM y 在两者都为 NULL 时为 T，只有一者为 NULL 时为 F，其余与普通相等一致。本页只讨论标量和显式逐分量的参数比较，不把复合行的 IS NULL 特例混进来。

固定有限输入、同一只读数据视图，以及纯、确定、对每行都有定义的表达式。这里排除了随机函数、序列递增、除零、溢出和表达式副作用。该限制让我们先证明值与行数保持；它不授权依赖 SQL 的从左到右求值或短路顺序。

完整的三值运算

NOT 把 T、F 对调，保留 U。AND 与 OR 的全部九种组合如下；不是先把 U 强制转换成 F 再运算。

p	q	p AND q	p OR q
T	T	T	T
T	F	F	T
T	U	U	T
F	T	F	T
F	F	F	F
F	U	F	U
U	T	U	T
U	F	F	U
U	U	U	U

WHERE 的筛选算子只保留值为 T 的出现。用指示函数 $[P]$ 表示断言成立时为 1、否则为 0，则

m_{\sigma_p R}(t)=m_R(t)[p(t)=T].

F 与 U 都被筛掉，却仍是不同谓词值。称 p、q 值等价，若每个合法输入上 p(t)=q(t)；称二者筛选等价，若每个合法输入上 $[p(t)=T]=[q(t)=T]$ 。值等价蕴含筛选等价，反向不成立。优化器要先确定表达式用在筛选口、SELECT 结果列还是 NOT 内部，才能决定哪种等价足够。

直觉

UNKNOWN 表示这次比较没有足够信息断定真或假。若已经知道另一个合取条件为假，整个 AND 无论未知部分如何都不会成立，所以 F AND U=F；若已经知道另一个析取条件为真，则 T OR U=T。这解释了表中两个看似不对称的角落。

筛选像一道只接收“已证实为真”的门。F 和 U 都不能进门，不代表在门外可以把它们当成同一个值。先把 U 压成 F，再应用 NOT，就会从“不知道”错误地变成“已经证实为真”。

bag 的重数与三值是两条独立规则。一行通过门后保留原有的全部出现；UNKNOWN 不会产生半份行，筛选也不会替通过的重复行去重。

例子与边界

六份客户的一次筛选

共同输入 Customer(label,k) 是 (A,1) 两份、(B,2)、(C,3)、(D,NULL)、(E,4) 各一份。字母只是便于阅读的标签，没有声明唯一键；两份 A 是两次真实输入出现。

令 p 为 k=1，令 q 为 k IS NULL。完整计算如下：

客户值及重数	p	NOT p	p OR NOT p	q	p OR q
(A,1) ×2	T	F	T	F	T
(B,2)	F	T	T	F	F
(C,3)	F	T	T	F	F
(D,NULL)	U	U	U	T	T
(E,4)	F	T	T	F	F

WHERE p 返回 A 两份；WHERE NOT p 返回 B、C、E 三份；WHERE p OR NOT p 返回五份，漏掉 D。因而把排中式直接改写为常量 TRUE 会多出 D 一份。WHERE p OR q 则恰好返回 A 两份和 D 一份。

比较 p 与 p IS TRUE：前者在 D 上为 U，后者为 F，但二者作为 WHERE 都只选 A。放到 NOT 下，NOT p 不选 D，NOT(p IS TRUE) 却选 D。这个最短例子说明筛选等价不允许在任意表达式上下文中替换。

仍然安全的连续筛选

对任意 p、q，由真值表可知 p AND q 为 T 当且仅当两者都是 T。因此

\begin{aligned} m_{\sigma_q(\sigma_pR)}(t) &=m_R(t)[p(t)=T][q(t)=T]\\ &=m_R(t)[(p\mathbin{\mathrm{AND}}q)(t)=T]. \end{aligned}

这证明 $\sigma_q(\sigma_pR)=\sigma_{p\,\mathrm{AND}\,q}R$ ，包括重复行、NULL 和空输入。证明逐个元组比较重数，故投影后相同输出再合并重数也保持一致。三值并没有使所有筛选下推都失效；它要求用正确的保真条件。

AND、OR 的交换律以及德摩根律也保持三值结果。交换律可直接看表的对称项；德摩根的第一式 NOT(p AND q)=(NOT p) OR (NOT q)，可把左式九项与右式九项逐一对应，第二式同理。另一方面，p OR NOT p 在 U 上仍为 U，所以不能由经典布尔代数的任意定理直接推出 SQL 恒等式。

OR 不能直接拆成 bag 拼接

若 p 为 k=1，q 为 k≤2，则 A 同时满足两者。把 WHERE p OR q 改成“筛 p 的结果 UNION ALL 筛 q 的结果”，A 会从两份变成四份。错误与 NULL 无关，来自重叠分支的重数相加。

正确的出现计数是 $[p=T]+[q=T]-[p=T\land q=T]$ 。若确实需要两个不重叠分支，可用“p 为 T”以及“q 为 T 且 p IS NOT TRUE”。第二分支要包括 p=U、q=T 的行，所以不能偷换成 q AND NOT p。普通 UNION 的去重又会把 A 压成一份，也不是原 bag 结果。

推论与应用

谓词优化先问观察位置

一个保持 T 集合的改写可以用于 WHERE 或内连接 ON 的保留测试；若谓词结果要被输出、取反或用于 IS UNKNOWN，则通常需要完整值等价。外连接还会根据“有没有 T 匹配”产生补行，移动谓词的位置会改变它所观察的输入，必须再证明补行行为。

NOT EXISTS 与 NOT IN的差别正是这个边界：前者否定“有没有被筛出的行”，后者对相等比较的三值结果求否定。先筛选再问是否为空，已经丢掉了“不匹配因为 F 还是 U”的信息，不能据此恢复 NOT IN。

一个可检查的实现合同

解释器可用三种互异标签实现 T、F、U，并让比较函数显式传播 NULL。Filter 接口必须写成“结果恰为 T 才返回当前出现”，不要使用宿主语言的非空对象判断；例如用字符串表示 U 时，它在许多语言中反而会被当作真值。

扫描 N 份输入并求值一个大小为 L 的表达式树，直接解释的时间为 O(NL)，工作栈为 O(L)，输出还需按通过份数付费。这是假定单次标量比较为常数成本的模型；长字符串、任意精度整数和函数调用另计。把一行求值两次省成一次的前提也是纯且确定，而不是只有符号长得相同。

共同检查器与终点逐项核对九格真值、六份客户、筛选合取恒等式和错误排中改写。有限穷举检验实现是否符合这张表，普遍的 bag 等价则由上面的逐元组重数证明承担。

参考资料

PostgreSQL 18，Logical Operators，§9.1：三值逻辑表与非固定求值顺序。本文的筛选等价定义、出现计数证明和六份客户例为独立推导。
PostgreSQL 18，Comparison Functions and Operators，§9.2：普通比较、标量 NULL 测试、IS NOT DISTINCT FROM 和布尔 IS 测试。
PostgreSQL 18，Table Expressions，§7.2.2：WHERE 只保留条件为真的行。

形式陈述 ​

值、谓词和留下来的行 ​

完整的三值运算 ​

六份客户的一次筛选 ​

仍然安全的连续筛选 ​

OR 不能直接拆成 bag 拼接 ​

谓词优化先问观察位置 ​

一个可检查的实现合同 ​

反向链接