多表连接优化的组合爆炸与两种应对算法

多表连接的执行顺序有多种等价选择（先连哪两张表、再连哪张），随着 参与连接的表数增多，可能的连接顺序数量按阶乘级别爆炸式增长—— n个表的连接顺序数量是(2(n−1))!/(n−1)!，这意味着穷举所有顺序、 逐一计算代价来找最优解，在表数稍多时就变得不可行（计算最优方案 本身花的时间超过了优化能省下的时间）。两种主流应对算法用不同方式 牺牲一部分搜索完备性换取可行的计算时间。基于动态规划的算法把”n个 表的最优连接方案”递归拆解成”任意两个不相交子集各自的最优方案+ 连接这两个子集结果的最佳算法”，通过记忆化避免重复计算子问题—— 这样穷举的是所有子集划分方式，而不是所有排列顺序，把问题规模从 阶乘级降到O(3^n)，仍然只在表数较少时可行。System-R算法更激进地 缩小搜索范围：只探索”左深连接树”这一类特定形状的连接顺序——从两个 关系的连接开始，每次只往结果里再追加一个新关系，不考虑”先分别连接 两对表、再把两个中间结果连起来”这类非左深的树形结构，把时间复杂度 进一步压到O(n·2^n)，代价是可能错过某些非左深树形态下的更优解。 当表数继续增大、这两种算法也扛不住时，一些数据库系统会转而用遗传 算法、模拟退火这类启发式搜索算法直接找次优解，彻底放弃”找到全局 最优”这个目标，换取在合理时间内拿到一个够用的方案。

结构图：

flowchart TD
    A[多表连接顺序优化] --> B["搜索空间: (2(n-1))!/(n-1)!种顺序<br/>阶乘级爆炸"]
    B --> C["动态规划算法<br/>O(3^n): 穷举子集划分,记忆化子问题"]
    B --> D["System-R算法<br/>O(n·2^n): 只探索左深连接树"]
    C --> E[表数继续增大]
    D --> E
    E --> F[启发式算法: 遗传算法/模拟退火<br/>放弃全局最优, 求次优解]