“现在加入 Blocked(k)={2,NULL}，用普通等号 NOT EXISTS排除客户。它只去掉 B，最终为 (A,1,3,2,20) 两份，以及 (C,3,0,0,NULL)、(D,N…”
形式陈述
只问是否存在，不枚举全部伙伴
输入 R、S 为有限 bag，条件 θ 是纯、确定、无错误的三值谓词。定义
因此同一 r 的全部原始份数或者保留、或者删除；右侧有一份还是一百份匹配不改变结果。两种输出按 bag 相加恰好还原 R。EXISTS(SELECT 1 FROM S WHERE θ) 计算 e；NOT EXISTS 计算 1−e，二者自身始终为 T 或 F，即使内部比较产生 U。
本页进一步只对单列标量普通等号讨论 IN。把 x 与右侧每份值比较，并将结果作三值 OR：出现 T 则 IN=T；没有 T 但有 U 则 IN=U；全部为 F 或右侧为空则 IN=F。NOT IN 再取三值 NOT。因此它问的不是“没有找到 T 吗”，而是“所有相等比较都已经为 F 吗”，空右侧按全称真处理。
完成后才能作为否定证据的成员表
为固定只读右输入建立状态
只有完整读到 EOF 才从 BUILD 进入 READY。此时 probe(x) 对 IN 按以下顺序返回：empty 为真则 F；否则 x 为 NULL 则 U；否则 x∈H 则 T；否则 hasNull 为真则 U；其余 F。NOT IN 对此结果取反；普通等号 NOT EXISTS 则在 x 非 NULL 且 x∈H 时为 F，其余为 T。READY 之前不得把一次未命中宣告为最终不存在。
H 可用精确链地址哈希表实现：哈希只定位候选桶，仍比较完整键；重复键只保留一个成员项。若容量为 C 个不同非 NULL 键，插入第 C+1 个新键时进入 FAILED 并返回 CapacityExceeded，不能丢弃这个键后继续宣称结果正确。读失败同样不能被解释为 EOF。失败计划可由调用者重新选择另一个完整执行计划；已经不完整的表不能供 probe。
直觉
内连接记录每一对伙伴；半连接只给每份左行盖一个“找到过”的章。右侧重复会放大内连接输出，却不会给同一左出现重复盖章。左侧原来有两个完全相同的顾客，两人仍各自保留。
NOT EXISTS 的否定对象是“有一行通过了筛选”。NULL 比较没通过筛选，所以不算存在。NOT IN 保留比较中的未知信息：没有相等见证，但还存在一个无法判断是否相等的 NULL，就不能断言所有候选都不同。
一份未读完的黑名单不能证明某人不在名单上。实现中的 READY 与数学定义中的完整 S 对应；它不是为了性能随意增加的等待。
例子与边界
同一批客户的存在查询
Customer 含 (A,1) 两份及 (B,2)、(C,3)、(D,NULL)、(E,4) 各一份。ok 订单键的 bag 为 1、1、1、2、NULL、4、4。按普通等号问有没有 ok 订单：半连接得到 A 两份、B、E，共四份；反连接得到 C、D，共两份。
若先内连接再仅投影客户列，A 会出现六份，E 两份，明显超过半连接。若接着 DISTINCT，A 又只剩一份。两种“修补”都没有保持原来两份 A 的身份。正确的半连接是对原左出现问存在，再输出该出现一次。
黑名单中的NULL改变了哪一个问题
令 Blocked(k)=(2)、(NULL)。对六份客户，NOT EXISTS(SELECT 1 FROM Blocked b WHERE b.k=c.k) 只删除 B，留下 A 两份、C、D、E，共五份。把它改成 c.k NOT IN (SELECT k FROM Blocked)，结果却为空。
| 左键 | 与 2 比较 | 与 NULL 比较 | IN | NOT IN | NOT EXISTS |
|---|---|---|---|---|---|
| 1、3 或 4 | F | U | U | U | T |
| 2 | T | U | T | F | F |
| NULL | U | U | U | U | T |
T 匹配优先于右侧的 U，所以键 2 的 IN 为 T，不是 U。右侧为空时，NULL IN 空查询为 F，NULL NOT IN 空查询为 T；因此 probe 必须先检查 empty，不能见到左 NULL 就无条件返回 U。
从黑名单中筛掉 NULL 仍不足以让两种写法普遍等价。若右侧变成非空的 {2}，NULL NOT IN {2}=U，而 NOT EXISTS 的普通等号没有真匹配，结果为 T。对两侧参与比较的键都能证明非 NULL 时，这两种排除才可直接交换；也可以逐个工作负载证明更弱的条件，但不能只检查一边。
一条真正失效的执行轨迹
容量 C=1，右输入依次为 2、NULL、5。读前两份后 H={2}、hasNull=true；若此时就探测左键 5，NOT EXISTS 会暂时得到“没有命中”。第三份 5 推翻它。正确过程仍处于 BUILD；插入 5 又超过容量，必须转入 FAILED，不能输出基于残缺表的排除结果。
在本页共同输入 Blocked={2,NULL} 中，C=1 足够：H 只有一个不同非 NULL 键，两个标志保存空表与 NULL 信息。把右输入改成一百万个 2，不会需要一百万个集合项；但读取成本仍是一百万次消费。
推论与应用
为什么四种探测分支足够
在 READY 时，构建不变量保证 H 精确等于全部非 NULL 右值，empty 精确表示右 bag 为空，hasNull 精确记录是否含 NULL。若右侧为空，没有任何比较，IN 为 F；若非空且左值为 NULL，每个比较为 U；若左值非空且命中 H，至少一个 T 决定 OR 为 T；若未命中，非 NULL 右值只贡献 F，结果由是否存在 NULL 决定。这个分类互斥且覆盖全部情况，故 probe 与定义一致。
右侧重复值可以去重，是因为三值 OR 满足幂等性 v OR v=v；它并不允许去重左侧。对每份原左出现作一次相同探测，恰好得到定义中的
成本、碰撞与更复杂的条件
设右侧 N 份、左侧 M 份、不同非 NULL 右键 D 个。固定字长键、兼容的相等和哈希、负载因子受控且采用适当随机哈希时，构建及全部探测的期望时间为 O(N+M)，空间为 O(D+1)，另计输出。若所有键碰撞到一条链，仍能通过完整比较得到正确结果，但比较成本可上升到 O((N+M)(D+1))。程序故意允许强制碰撞，以分开正确性与期望性能假设。
容量以成员项数表达的是教学合同，真实字节预算还包括桶头、键编码、链指针及控制状态。内存不足可用分区或外存排序重做，但不能只把右表分区后遗漏全局 hasNull/empty 信息；单列 NOT IN 的一个 NULL 会影响其他键分区中的未命中探测。
若 θ 还包含 amount>客户阈值，单存键集合不够：同键候选中可能没有一行通过附加条件，需要保存足够的右数据或证明另一个摘要。多列行值 IN 也不能直接用一位 hasNull 概括；例如 (1,NULL) 与 (2,5) 已因第一列不同而不等，并非只要出现 NULL 就一律 U。本页的线性哈希合同明确限于单列普通相等。
Bloom 过滤器可以排除确定不存在的键，可能命中仍须精确复核；把假阳性当作真实命中会让反连接误删左行。完整结果和容量失败可在NULL-6 终点检查器复算。
参考资料
- PostgreSQL 18，Subquery Expressions，§§9.24.1–9.24.5：EXISTS、IN、NOT IN 与 ANY/ALL 的真假规则。本文的有界成员表、状态证明、碰撞试验及 NULL-6 反例为独立构造。
- Thomas Neumann、Alfons Kemper，Unnesting Arbitrary Queries，§2、§3.1：存在子查询向半连接的转换；本文额外显式保留左侧 bag 重数与 NULL 敏感排除边界。