“过滤器来自实际已完成的键集合，不依赖直方图预测正确。相反，q'比预测小或B比预测大，可能改变后续物理算法的成本排序；检查点重优化必须使用同一过滤状态下的完整输入规模比较候选，不能拿过滤前后的…”
形式陈述
可以在哪里改计划
优化器最初依靠估计选计划，执行到中途可能发现输入比预测大得多。重优化要回答两个问题：新计划是否真正更省，以及更换后是否仍在执行同一次查询。这两个问题需要分别核验。
本页沿用查询执行器的完成、资源所有权和输出接口。限定一个固定只读快照σ，确定性的纯读取等值内连接；输入行有稳定出现身份。两个子计划已完整结束，其输出被物化成不可变序列B和P，所有列与身份仍有效；连接后缀尚未向外部消费者输出任何行。NULL探测行已按内连接语义排除，物化P也可以已经过一个完整的保守运行时过滤。
这就是本页检查点。物化完成不是说某个缓冲区目前装满，而是生产者已成功到达END，全部行已拥有可持续读取的存储。任何ERROR都不能伪装成END。σ标签本身不建立快照隔离，它指向的稳定输入由数据库下层合同保证。[1, §2.4；2, §2.3, §3.1]
后缀候选必须同义且可执行
候选共享同一个逻辑结果：输出所有键相等的(B出现ID,P出现ID)，保留重复值产生的全部出现对。这里不要求输出顺序。可选实现为逐对比较NL、把P建哈希后扫描B的HP、把B建哈希后扫描P的HB；每个哈希键关联该键的完整出现列表，不能只留一个ID。
假如调用者要求排序，候选也必须满足该排序或显式补排序算子及费用；列、谓词、NULL规则、快照或bag重数不同的计划不属于这个候选集。旧连接计划的物理属性状态已经说明为何不能只按“表集合相同”比较成本。
容量同样先于排名。若哈希预算为M个行出现槽，HP须有|P|≤M，HB须有|B|≤M；这是本教学缓冲合同，只约束哈希记录槽，不是Python总字节数或整次查询内存上限。物化文件、索引、输出和控制结构分别占资源；它们不会因选择了更省槽的后缀而消失。
成本只比较共同边界之后
采用明确的物理成本模型。设已经完成的公共工作为S，保留当前后缀还需C_old；改用新后缀还需C_new，准备/安装代价为C_switch。仅当
才因成本理由切换，等号保留原计划。两边都加S不会改变排序。重用的物化结果若还要读，读成本属于未来；已经付过的生成成本属于S。新计划需要的额外排序、复制、清理或再次物化也必须进入未来费用。[1, §2.4]
实际优化器的剩余成本仍可能是估计，所以更低模型值不保证真实运行更快。本页用完全声明的两候选工作账本验证选择规则，不声称具有真实数据库的全局最优计划。
直觉
改路之前，先把已完成的工作固定
把检查点看成一张封存的输入清单：有哪些行、每行是什么版本、谁拥有存储，都已经确定。后缀可以用不同方法消费这张清单，却不能把一半旧行与一半新快照行拼接，也不能把旧方法已经交付的行再交一次。
一个小而完整的安装协议
- COLLECTING：收集两侧行，逐项验证执行身份；关闭一侧后不再追加。发生错误则终止，不发布部分输入
- FROZEN：两侧都成功关闭，转成不可变存储；计算真实规模并检查候选的合同和容量
- READY：原子记录唯一选定的后缀以及是否切换，保留输入所有权；若候选准备失败，不得同时启动两份后缀
- RUNNING：选定后缀开始消费并输出出现对，不再接受本协议的替换请求
- DONE：唯一后缀完整结束；生产执行器此时按所有权释放临时资源。下载示例为复核仍保留输入、ID集合、迭代器和已交付记录，不能据此声称这些空间已回收；错误路径报告失败
本页下载器串行执行这些转换，原子性由单调用控制流实现；多线程实现必须另加互斥/发布机制。它不含“边输出边改计划”的补偿算法。
例子与边界
初始预测选NL，真实数据促成换计划
沿用24行统计例。选择后的B预计36/5行，P先有8个非NULL出现。为便于复算，规定每次键比较或哈希输入操作记一单位，哈希后缀另收固定启动费48，改计划另收安装费6；输出枚举Z和公共物化费用分开记。这些数字是教学费用，不是设备毫秒或磁盘页数。
于是NL预测成本为(36/5)×8=288/5，HP为48+36/5+8=316/5，初始暂选NL。执行完成后，B实际有12行。若运行时过滤等待超时并全放行，P仍有8行，未来成本为：
| 后缀 | 基本工作账 | 安装额外费 | 总未来费用 |
|---|---|---|---|
| 保留NL | 12×8=96 | 0 | 96 |
| 改HP | 48+8+12=68 | 6 | 74 |
哈希容量M=8，HP可以建表，HB需要12槽而不可用。协议真正切换到HP。一个键对应完整P出现列表，扫描B逐一输出匹配，所以最终仍是17对，而不是按键取一个代表。
完整过滤后，切换并不划算
若两片过滤摘要完整，P物化后只有6行，含应被精确连接排除的假阳性16。此时NL为12×6=72，HP为48+6+12=66，加切换费6后也是72，应保留旧NL。
不能用旧的96与新的66比较来宣布节约30，因为96属于八行P，66属于六行P，比较的输入已经不同。也不能把初始预测57.6拿来和现在实际72比较决定换计划；决定点需要两候选对同一份冻结输入的剩余成本。
在严格不等号规则下，安装费从6改为5就会选择HP；把哈希槽预算从8改为5，则六行P也装不下，只能保留NL或另选具有明确溢出合同的算法。这两种迁移分别改变经济条件与物理可行性。
已输出前缀为什么阻止直接重启
假设NL已经交出首个匹配对(b₀,p₀)，随后重新从完整B和P启动HP并直接接着输出。HP又交出这同一对，于是原来17对变成18对。按值去重并不能普遍补救，因为原查询本来允许不同身份投影成相同值。
本页选择在RUNNING时拒绝替换，因而无需声称已经实现输出补偿。更广的重优化可以缓冲输出、追踪已交付身份或使用其他严格补偿机制，但必须给出完整证明；POP原文专门区分这类检查点。[2, §3]
快照、顺序与副作用
把B留在σ7，却重新读取σ8的P，若后者多出一个键7出现，结果将多出四对。这已不是同一份冻结输入上的算法替换。对会写表、调用有副作用函数或依赖易变表达式的前缀，重新执行还可能重复效果；本页只读确定性合同明确排除它们。
LIMIT、顺序敏感运算或要求固定输出顺序的消费者不能直接使用这里的无序bag等价。需要保留其完整语义和物理属性，不能因为两个纯连接全量结果相同就任意移动截断点。
推论与应用
哪些工作属于这个实现
检查点收集n+q个行出现并封存需要O(n+q+1)时间和引用空间；验证两侧身份、唯一ID与输入类型也在这一成本中。三个内建候选的规模/容量/公式比较为常数次算术，不是枚举所有查询计划。其他候选的搜索或编译费用须另外核算。
NL实际作nq次键比较，加上Z个输出；HP/HB用散列表保存重复键的出现列表，期望O(n+q+Z+1)工作，哈希记录槽分别为q或n。程序为验收保留完整输出列表，需要O(Z+1)额外空间；流式输出可避免这份缓存，却仍不能省掉Z次交付。字典的期望条件、ID/整数位长和输入物化存储不被48/6费用替代。
旧分区Hash join已经给出装不下时的页级分区及重键退路。本页将超容量候选直接排除，没有把一个Python字典悄悄增长当成已实现外存溢出。真正接入旧算法时，要重新使用其页宽、分区和I/O账本。
观察、否定证据与替换决策
直方图给执行前的分布预测；分片运行时过滤给实际键集合的安全负证据；本页用完成后的真实规模作同义候选选择。三种信息的用法不同，但可以在一份查询记录中逐步对接。
终结任务要求两条路径都产生完全相同的17个身份对，同时分别记录HP切换和NL保留。不能只报告“查询更快了”，也不能只检查结果行数相同而漏掉一对、重复另一对。核验器以完整身份对bag为判定对象。
参考资料
- Navin Kabra、David J. DeWitt，“Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans”，SIGMOD1998，§2.2–2.4，印刷pp.108–111；p.110脚注3强调同事务上下文，§2.4明确剩余执行与物化/优化开销。
- Volker Markl等，“Robust Query Processing through Progressive Optimization”，SIGMOD2004，§2.2–2.3、§3.1，PDF pp.4–6：物理属性、临时结果与同事务、完整物化点以及已输出行的补偿需求。本页只实现固定快照、无已发后缀的少量内建候选教学版本。