“分片运行时过滤进一步规定负证据何时可以发布：完整build分片清单、执行/快照/哈希身份一致、全部最终摘要完成后按OR合并。局部未出现不能证明其他片也无匹配；超时全放行只放弃优化，不能把缺失…”
形式陈述
要过滤的是不可能匹配的探测行
考虑固定只读快照中的等值内连接B⋈P，键为整数或NULL，普通SQL等号只让两个非NULL相等键匹配。两侧都是保留出现重数的bag：四个键7的B行与两个键7的P行，应产生八个出现对。
逻辑build输入B被完整分成已知分片集合S={s₀,…,s_{a−1}}，每份出现恰属于一片。这里的build是过滤证据来源；后续物理连接若换了建哈希侧，B的逻辑身份并不跟着交换。本页只做预过滤，真正连接仍须取得完整B，并核对精确键值。
每片完成其整个输入后，用相同m位长度和同一组k个哈希映射构造Bloom位图F_s，包含该片全部非NULL键。协调器使用消息接收最终摘要，消息可迟到、重复或缺失。它不能从“目前没收到”推断某片为空。
同一查询与完整分片是合并前提
消息带上查询编号、执行epoch、快照标识、连接编号、分片编号及哈希配置。执行epoch区分同一查询的一次重试；哈希配置至少规定m、映射版本和种子，跨类型编码也须一致。本页整数编码固定，示例两映射确定，不为其假阳性作随机独立假设。
接收器先确认消息属于当前执行、来自期望分片且配置一致。旧执行或错误配置的消息不参加计数；同一分片同一最终摘要的重复只确认一次。每份合法最终摘要是不可变的，同身份却有不同内容属于协议错误，应停止这次查询，而非悄悄选择一份继续发布成功。
只有全部期望分片都已确认完成，才发布
空分片仍须交一份最终零位图。若S本来为空，逻辑B为空，可直接发布零位图。等待超时允许停止这项优化，发布全放行TOP；TOP不是零位图，也不是部分分片的OR。本页超时后保持TOP，迟到摘要不再改变它。
不漏结果的逐键证明
取任一真匹配(b,p)。键非NULL且相等。b属于某一片s，因此它的k个哈希位在F_s中全为1，完整OR后在F中也全为1，p不可能被过滤。TOP当然也保留它。
因此丢弃“有任一哈希位为0”的探测行不会删掉任何真出现对。余下行必须进行精确连接：位全为1可能来自其他键的碰撞，只能表示尚未排除。后续逐一枚举所有匹配出现，便恢复原来的完整bag结果。位图按键去重不会删除B的真实行，且不能被拿来替代连接本身。
直觉
一片的零位，只能为那一片作证
在B₀中没有键7，不代表B₁也没有。局部位图的负结果回答“这片不可能匹配”；全局负结果需要所有片都能排除它。完整OR中某位仍为0，才说明每一片的该位都为0。
把各片位图AND会问成另一件事：是否每一片都把每个位设过。连接只需要任意一片存在匹配，故AND可能丢掉真实结果。这个错误不属于可接受的假阳性，而是破坏答案的假阴性。
等待可以有预算，答案不能只做一部分
超时全放行只放弃减少探测工作，不改变原查询的输入和目标。如果B本身读取失败，而不仅是摘要消息丢失，精确连接仍须恢复完整输入或报告查询失败。把摘要优化关闭不能把缺失的B行变成空片。
同样，快照编号相同只是消息的配对标签。它的含义依赖存储层确实提供固定的可见行；伪造标识、错误producer漏键或位图传输损坏不在本页诚实摘要合同内。发现同身份最终内容冲突时，尤其不能用“现在改TOP”声称已经撤销先前所有删除。
例子与边界
十二个build出现、两个分片
B的键为0、1、4、5、6四份、7四份，共12行。B₀含0、1、4、5及四个6，B₁含四个7。取m=16、k=2，映射为
B₀置位集合为{0,1,4,5,6,10,15}，B₁为{4,7}，完整OR为{0,1,4,5,6,7,10,15}。只到B₀时，键7所需的位7尚为0；因此当前状态必须继续全放行，不能发出否定。
P九行的键为0、2、6、6、7、7、10、16、NULL。NULL先按普通等值内连接语义排除，剩八行。完整过滤保留0、6、6、7、7、16六行；2和10各有零位被删掉。16与0的两哈希位完全相同，虽然B里没有16，它仍是一个应交给精确连接的假阳性。
精确结果有17个出现对：键0贡献1，键6贡献2×4=8，键7贡献2×4=8。16贡献零。若错误使用B₀的部分位图，两个探测7被删掉，输出仅9对，少了八对；若输出键集合，则只剩0、6、7三个值，同样不是原查询结果。
重复、错配置和迟到
执行q/epoch2/σ7/joinJ预期两片。先收B₀最终摘要，再重复一次B₀，只完成一片；一条epoch1的B₁消息不能补足；一条m=32的B₁也不能与m=16的位位置作OR。直到匹配当前执行和配置的B₁到达，才READY。
另一条执行在只收到B₀后超时，转TOP；后来收到正确B₁仍维持TOP。八个非NULL探测行都会进精确连接，输出仍为17，只是没有那两次探测删减。完整B为空时零过滤器可排除全部非NULL探测；空build与尚未完成build不可混为一谈。
不能原样推给外连接和否定
若P是左外连接的保留侧，过滤掉无匹配的p会丢掉本应输出的NULL扩展行。可以利用负证据直接生成相应外连接行，但那是另一个执行规则，不是本页的删除规则。对于NOT IN及含NULL的反连接，还必须处理UNKNOWN；旧半连接与NULL感知排除已给出相应真值合同。
一个完整过滤器也不自动保证少读磁盘页。只有底层分区、文件或行组布局提供可用的键范围证据，才能进一步跳过读取；连接器是否支持这种下推是独立条件。[1, Analysis and confirmation]
推论与应用
计算、消息与保留状态
设build行数n、非NULL探测行数q、最终保留q'行。插入build键共O(1+nk)次置位操作，预过滤O(1+qk)次；精确连接及其Z份输出另计。还要为a份分片位图清零、存储并传输。长度m位图在w位字上表示时，每份初始化或全OR需O(1+⌈m/w⌉)字操作，因此除插入键外的全分片初始化、合并和传输总成本为O(a(1+⌈m/w⌉))，协调器自身还有一份汇总位图的初始化。
本页下载器用bytearray(m)便于逐位检查，每位实际占一个字节；收到每片后复制并验证其位值，合并扫描m项，所以每份消息O(m+1)，保存所有最终副本为O(a(m+1))空间，另有汇总位图。保留副本用于检查同身份重复是否一致，不能把它报成仅一个m位数组。已公布且不可变的状态可被消费者只读借用；异步实现还须保证发布原子性。
与预测、换计划的接口
过滤器来自实际已完成的键集合，不依赖直方图预测正确。相反，q'比预测小或B比预测大，可能改变后续物理算法的成本排序；检查点重优化必须使用同一过滤状态下的完整输入规模比较候选，不能拿过滤前后的成本混算。
共同终点要求交付两片位图、消息次序、六个保留出现和十七个精确身份对。核验器另外给出部分OR、AND、旧epoch凑完成数等错误策略的反例，不把有限消息枚举当作整个分布式数据库认证。
参考资料
- Trino官方，Dynamic filtering，2026-10-09读取页眉483：首节的build侧候选、协调器完成收集后分发，以及Analysis and confirmation的连接/连接器条件。本文消息身份、Bloom聚合状态机和16位实例是独立教学构造，不是Trino消息实现复刻。
- Burton H. Bloom，“Space/Time Trade-offs in Hash Coding with Allowable Errors”，Communications of the ACM13(7)，1970，pp.422–426；位图成员查询合同由旧Bloom Filter页复用。本页不套独立随机哈希的概率公式给两个示例映射。