“连接顺序DP可以穷尽指定搜索空间，却只对输入给它的成本模型最优。系统应同时保留estimated rows与actual rows，定位误差最早出现的算子，再判断它如何影响后续成本；不能看到…”
形式陈述
给定n张已过滤的有限bag、内等连接条件、统计基数、允许的物理算子和成本接口，优化器搜索某一计划集合。本页先限定左深树：每步把已连接子集A与一张尚未加入的基表j相连。所有已可计算的连接条件在相应步骤执行，属性保留到不再需要为止；只含内连接且无NULL、LIMIT、外连接等顺序敏感操作。
先取简化状态best[A]，条件是：同一子集的所有保留方案有同一输出表示、顺序承诺、统计基数和可重扫接口；未来增量成本只依赖A与下一表j，不依赖具体历史。令scan(j)为基例代价，c(A,j)为追加连接的增量，采用动态规划：
只有允许的连接转移参与最小值；若排除笛卡尔积，某个子集可能无合法左深计划，记∞。本页数值例允许中间笛卡尔积但实际所有表共用k，不会出现无连接条件的步骤。记录取最小的前驱即可回溯完整计划。
按|A|递增填表。不变量是每个已填子集记录该受限空间内最小预测成本。任一左深计划最后一步都有某个j；去掉j后是更小子集计划。若其前缀不是best，可以替换为best且不改变未来成本，这是状态充分性条件的作用。取遍j覆盖全部末步，所以归纳成立。固定常数时间转移与基数查表时，时间O(n2ⁿ)、表空间O(2ⁿ)；物理算法枚举、统计计算和属性状态另计。
直觉
DP不是猜“先连最小的两表”，而是把不同历史若能互换的部分折叠为同一个状态。关键问题是未来是否真的看不出这些历史的差异。
一个贵一点但已经有序的子计划，可能省掉下游更大的排序。若状态只写表集合，就把这份对未来有用的信息抹掉了。
例子与边界
三张表的完整填表
沿用DB-4的R六份、S八份，另加T(k)={(1),(2)}各一份。连接都按k。精确中间基数为|RS|=12、|RT|=4、|ST|=5、|RST|=10。这里为看清顺序，单独采用“逐记录嵌套循环的键比较次数”作成本单位；基表已给定，scan=0，不计I/O或输出复制。这是明确的简化成本，不能与页数11相加。
每次连接A与j需要|A||j|次比较，得到：
| 子集 | 最优比较次数 | 计算 |
|---|---|---|
| R、S、T各自 | 0 | 无连接 |
| RS | 48 | 6×8 |
| RT | 12 | 6×2 |
| ST | 16 | 8×2 |
| RST，最后加T | 72 | 48+12×2 |
| RST，最后加S | 44 | 12+4×8 |
| RST，最后加R | 46 | 16+5×6 |
最优为先RT再S，44次比较。RT保留R中键1、2的四份出现，再与S配对得到10份；另外两种顺序也得到这10份bag，差别是中间工作。T有两行并不代表每次先含T都一样：ST先做的总账是46。
每子集一方案何时失效
同一A有计划U成本10、输出无序；计划O成本13、按k有序。后续要求按k输出，U还要付100排序，O无需排序。只保留U得到110，保留O得到13。故真实优化器可用best[A,property]，分别保留有用顺序、分区方式等状态，并为产生所需属性的排序等enforcer计费。原System R的interesting orders正是这种保留差异的思想。
推论与应用
估计基数决定c与中间大小。DP最优性是对这些预测、允许算子及搜索空间而言；估计错误不违反递推证明，却能让实际最优计划被错选。应把“漏搜方案”“状态不足”“估计失真”分别诊断。
允许一般bushy树时，需要枚举A的二分A=B∪C，转移形如best[B]+best[C]+join(B,C)，而非只去掉一个单表。朴素子集二分总量为O(3ⁿ)级，物理属性再增加状态；本页的O(n2ⁿ)不是任意优化器的复杂度。
代价接口还须避免重复计读写。若子计划已经包括把中间结果写盘，父转移只能再计它的读取；若传递一次性流，应按实际同时内存占用决定可行性。单纯相加算子独占内存下的成本可能选出无法执行的计划。
参考资料
- P. Griffiths Selinger et al., “Access Path Selection in a Relational Database Management System”，SIGMOD 1979，§5，印刷pp.28–29：子集构造与interesting orders。
- CMU 15-445/645 Fall 2025，Query Planning & Optimization II，§1：左深计划与自底向上搜索。三表44次比较为本文独立例题。