“跳过较小键安全，因为另一侧剩余键不小于当前较大键，已不可能再匹配。相等键阶段输出G R(k)×G S(k)的全部出现对；不同k的组互斥。因此该过程与共同bag规格一致。”
形式陈述
物理计划给逻辑算子选择访问路径、算法、记录表示和执行调度。判断计划先做三件事：证明它输出指定多重集；证明任一时刻的内存和页引用不超预算；最后计算或估计成本。逻辑等价不意味着成本相等，成本低也不能修复少输出重复行的错误。
本页把I/O模型实例化为可手算的DB-4：每页有效载荷128B，每个输入槽64B（含固定元数据及预留链指针），输出槽128B。算子独占4个128B数据帧，另有本例专用64B控制区放有限游标、两个桶头、计数与标志。控制区只针对这份固定数据；一般算法必须随桶数、游标数另计元数据。页读、页写各计1；CPU、寻道差、日志和元数据I/O不在主账中。
两个输入以所列顺序两行一页：
| R(k,v,x,y) | R页 |
|---|---|
| (1,A,1,1), (2,B,1,1) | 1 |
| (1,A,1,1), (3,C,0,0) | 2 |
| (2,D,1,1), (4,E,0,0) | 3 |
| S(k,w) | S页 |
|---|---|
| (2,u), (1,v) | 1 |
| (2,u), (3,w) | 2 |
| (1,x), (5,y) | 3 |
| (4,z), (2,t) | 4 |
查询按k内连接，输出(k,v,w)，没有NULL、DISTINCT、并发更新或顺序要求。每种计划从冷缓存和已在盘上的同一输入开始，不复用另一计划的临时文件。输出可先流给消费者；若要求写盘，统一另加其输出页写入。
直觉
页数由行数和行宽共同决定。输出12行，每行64B是6页，每行128B则是12页。省略记录表示，就无法核对“写了几页”。
缓冲像限量工作台。可以先用四页完成排序，再释放并改作两游标、同键组和输出；不能在同一时刻给每个算子都画四页。阶段复用合法，同时超额不合法。
例子与边界
共同答案先于快慢
完整结果为(1,A,v)×2、(1,A,x)×2、(2,B,u)×2、(2,B,t)、(2,D,u)×2、(2,D,t)、(3,C,w)、(4,E,z)。八种不同值共有12份；按键也可核对2×2+2×3+1×1+1×1=12。输出每份一页，共12页。
分块嵌套循环固定R外侧，读3+ceil(3/2)×4=11；分区哈希连接按奇偶分区，尾页让临时文件变8页，读写7+8+8=23；排序归并连接先读写两输入14次，再读7页，合21次。这些数先排除输出；写盘时分别为23、35、33。具体循环、分区与同键组不变量见三个算法页。
反向分块嵌套循环以S外侧只读4+ceil(4/2)×3=10。更小外表通常有利的经验在取整边界失效，所以应实际比较两方向。
物化不能算两遍，也不能漏算
若一个6页中间结果已由子算子输出，接下来有两种接口。写成临时文件再由父算子读回，新增6次写+6次读；逐条传给父算子且无缓存重复读取，则没有这12次临时I/O。下游自己的输入页、工作表和最终输出仍计费。
去掉物化前要验证可重扫性：外层循环可能需要多次重读同一内层。一次性流不能免费rewind；可选保存中间结果，或重新执行其子计划，并计每次执行成本。物化也可能让子算子释放资源，降低同时占用的峰值。
若子算子仍pin两页，而父算子另要三页，总占用5>4，这个流水调度不可行。先物化并关闭子算子再运行父算子，可以把峰值改为max(2,3)=3，却增加临时I/O。这是一个资源可行性与数据移动的真实取舍。
推论与应用
精确执行账本使用实际行数和分区页数；优化器使用统计量估计它们，得到的是预测。相关列可使行数低估，再把hash build从“内存可装”推到需要溢写的另一算法分支。应保留估计值和实际值，而非执行后偷偷替换预测。
这份模型忽略随机/顺序差、CPU、并行与缓存。实际系统可加权页类型、计算键比较成本及首行延迟，但权重需测量，不能把本页11次I/O直接读成11毫秒。共同输出给各方案加上相同页数，不改变上述I/O排序；它若占主项，省几次输入I/O的相对改进比例会变小。
路线终点是能解释同一答案怎样由不同状态机得到，以及每个状态机的钱花在哪里。WCOJ研究的集合输出上界与固定查询枚举保证另有模型，不应被这份二元bag页账本替代。
完整DB-4任务与答案把输入页、三种执行、相关列与崩溃轨迹放在同一份账本中，并附可复算程序。
参考资料
- CMU 15-445/645 Fall 2025，Join Algorithms，§2：分开输入与输出I/O。
- P. Griffiths Selinger et al., “Access Path Selection in a Relational Database Management System”，SIGMOD 1979，§§4–5：访问路径的估价与选择。DB-4数据、槽宽和逐项账本为本文自定。