我们来详细剖析CBO优化器中几种核心的连接顺序选择算法。
核心问题：为什么需要这些算法？
在多表连接查询（如
T1 JOIN T2 JOIN T3 ... JOIN Tn
）时，连接顺序的不同会产生数量巨大的执行计划。可能的连接顺序是
卡特兰数
，这是一个比指数增长还快的组合爆炸。例如：
-
3个表： 12种可能
-
5个表： 1,680种可能
-
10个表： 超过 17,600亿 种可能
CBO的核心任务就是在如此巨大的搜索空间中，高效地找到一个成本足够低（不一定是最优）的执行计划。
1. 动态规划
这是经典CBO（如Oracle, PostgreSQL）处理中小规模查询的基石算法。
-
核心思想 ：自底向上地计算并存储所有子集的最优解，最终组合得到全局最优解。它遵循“最优子结构”原则：一个全局最优计划必然由它的子集的最优计划组成。
-
过程（自底向上） ：
-
为每个基表（单表）找到最优的访问路径（全表扫描、索引扫描等）。
-
考虑所有两表连接组合，为每个两表组合找到成本最低的连接方法和顺序。
-
考虑所有三表连接组合，它由“一个两表组合 + 一个单表”组成，直接利用第二步的结果，找到成本最低的三表连接计划。
-
重复此过程，直到计算出所有N个表连接的最优计划。
-
剖析
| 维度 | 分析 |
|---|---|
| 时间复杂度 | O(3ⁿ) 。对于每个子集，需要考虑其所有划分方式。这是该算法的主要瓶颈。 |
| 解质量 | 最高（理论最优） 。在搜索空间内，它能保证找到成本最低的执行计划。 |
| 内存占用 | 高 。需要存储从1到N个表的所有子集的最优计划及其成本，空间复杂度为 O(2ⁿ)。 |
| 可解释性 | 高 。优化器路径可以清晰地展示为“为什么选择这个计划”，因为它系统地比较了所有可能。 |
| 可扩展性 | 差 。当表数量N增大时，时间和空间消耗呈指数级增长，通常 N>10 就会变得非常缓慢。 |
| CPU使用 | 高 。需要进行大量的成本计算和比较。 |
适用场景与举例
-
场景 ：中小型查询，通常表数量 N < 10~12 。是大多数OLTP和简单OLAP查询的首选。
-
举例 ：
SELECT * FROM A, B, C WHERE A.id = B.aid AND B.id = C.bid;-
最佳(A)，最佳(B)，最佳(C) -
最佳(A⋈B)，最佳(A⋈C)，最佳(B⋈C) -
最佳((A⋈B)⋈C)，最佳((A⋈C)⋈B)，最佳((B⋈C)⋈A)
最终从三个三表连接计划中选出成本最低的那个。
-
2. 贪心算法
这是一种启发式算法，在解质量上做出妥协以换取速度。
-
核心思想 ：每一步都做出当前看来最优的局部选择，希望最终得到全局较优的解。
-
过程（最近邻策略） ：
-
从一个表开始（通常是成本最低或选择性最高的表）。
-
在剩余的表集合中，找到一个与当前部分计划进行连接后， 成本增量最小 的表。
-
将该表加入当前部分计划。
-
重复步骤2-3，直到所有表都加入。
-
剖析
| 维度 | 分析 |
|---|---|
| 时间复杂度 | O(n²) 。非常高效，因为它每一步只关注当前最优的选择。 |
| 解质量 | 不稳定，通常较差 。非常容易陷入局部最优，而错过全局最优解。 |
| 内存占用 | 极低 。只需要维护当前的部分计划和剩余表集合。 |
| 可解释性 | 中 。可以解释为“一步步选择当前最有利的连接”，但无法证明全局最优。 |
| 可扩展性 | 极好 。即使表数量N很大，也能在多项式时间内给出一个计划。 |
| CPU使用 | 极低 。计算量远小于动态规划。 |
适用场景与举例
-
场景 ：对优化时间非常敏感，且可以接受次优解的超大型查询；或在资源受限的嵌入式数据库中。
-
举例 ：
SELECT * FROM A, B, C, D WHERE ...-
假设从表A开始。
-
计算
A⋈B,A⋈C,A⋈D的成本，发现A⋈B成本最低。当前计划：A⋈B。 -
计算
(A⋈B)⋈C和(A⋈B)⋈D的成本，发现(A⋈B)⋈C成本最低。当前计划：(A⋈B)⋈C。 -
最后加入D，得到最终计划：
((A⋈B)⋈C)⋈D。
问题 ：它可能完全错过了(B⋈C)⋈(A⋈D)这样更优的浓密树计划。
-
3. 基因算法
这是一种基于生物进化原理的随机优化算法，用于在巨大搜索空间中寻找“满意解”。
-
核心思想 ：模拟自然选择。一个“种群”由多个候选执行计划（染色体）组成。通过“选择”、“交叉”（杂交）、“变异”等操作，不断进化出更好的种群。
-
过程 ：
-
初始化 ：随机生成一批执行计划（连接顺序）作为初始种群。
-
评估 ：计算每个执行计划的成本（适应度）。
-
选择 ：根据适应度（成本低=适应度高）选择优秀的个体进行繁殖。
-
交叉 ：随机交换两个父代计划的部分连接顺序，产生子代。
-
变异 ：随机改变某个计划的局部连接顺序。
-
迭代 ：重复步骤2-5，直到达到终止条件（如迭代次数、时间上限或解的质量稳定）。
-
剖析
| 维度 | 分析 |
|---|---|
| 时间复杂度 | O(P * G) 。P是种群大小，G是迭代代数。它不直接依赖于N的指数，但P和G需要设置。 |
| 解质量 | 高（满意解） 。虽然不是理论最优，但通常能找到非常接近最优的高质量解，远胜于贪心算法。 |
| 内存占用 | 中 。需要存储整个种群（P个计划）的信息。 |
| 可解释性 | 差 。进化过程是随机和并行的，很难解释“为什么最终是这个计划”。 |
| 可扩展性 | 非常好 。通过调整种群大小和迭代次数，可以应对从几十到上百个表的连接。 |
| CPU使用 | 非常高 。每一代都需要对P个计划进行成本计算，计算密集型。 |
适用场景与举例
-
场景 ： 大型数据仓库查询（OLAP） ，表数量众多（N > 12），其中动态规划不可行，且对解质量要求高于贪心算法。
-
举例 ：一个涉及20个表的星型模型查询。
-
染色体 ：可能表示为
[Fact, Dim1, Dim3, Dim2, ...]的连接顺序列表。 -
交叉 ：父代1
[A,B,C,D]和 父代2[C,A,D,B]可能产生子代[A,B,D,B]和[C,A,C,D]。 -
变异 ：一个计划
[A,B,C,D]可能突变为[A,C,B,D]。 -
经过数百次迭代后，种群中最优个体的成本会收敛到一个很低的值。
-
4. 线性算法
在数据库CBO语境下，“线性算法”通常不是一个独立的连接排序算法，而是指：
-
左深树或右深树限制 ：动态规划等算法在搜索时，可以限制只生成左深树。这极大地缩小了搜索空间（从O(3ⁿ)降到约O(2ⁿ)），牺牲了找到浓密树计划的可能性，但大大提升了优化速度。
-
系统R算法 ：这是动态规划的经典实现，它本身就采用了左深树假设。
剖析（在左深树限制下）
| 维度 | 分析 |
|---|---|
| 时间复杂度 | O(2ⁿ) 。比无限制的动态规划低，但仍是指数级。 |
| 解质量 | 高（在左深树中最优） 。放弃了浓密树，但在大多数情况下（尤其有索引时）左深树已经足够好。 |
| 内存占用 | 中高 。比完全动态规划略低，因为需要存储的状态变少了。 |
| 可扩展性 | 中等 。比完全动态规划好，但表数量N很大时依然不行。 |
适用场景与举例
-
场景 ：这是 工业界的标准实践 。绝大多数数据库的动态规划实现默认只考虑左深树或右深树，因为它很好地平衡了优化时间和解质量。
-
举例 ：
((A⋈B)⋈C)⋈D是一个左深树计划，它非常适合流水线执行和索引嵌套循环连接。
总结对比与实战策略
| 算法 | 表数量(N) | 解质量 | 优化速度 | 核心思想 |
|---|---|---|---|---|
| 动态规划（左深树） | 小 (N<10) | 高（受限最优） | 慢 | “分而治之，记忆化搜索” |
| 贪心算法 | 大 (N>15) | 低 | 极快 | “眼前利益最大化” |
| 基因算法 | 超大 (N>12) | 高（满意解） | 慢（但可控） | “物竞天择，适者生存” |
现代数据库的实战策略：
-
基于阈值的混合策略 ：
-
当
N < threshold_low(e.g., 5-8)：使用 动态规划 寻找最优解。 -
当
threshold_low < N < threshold_high(e.g., 8-15)：使用 基因算法 或 随机化算法 寻找高质量解。 -
当
N > threshold_high：使用快速的 贪心算法 获得一个“能用”的计划，或者提示用户重写查询。
-
-
并行与启发式 ：
-
在动态规划中，可以使用 剪枝 技术（如“有趣顺序”）来减少需要保留的计划数量。
-
基因算法可以并行评估种群中个体的成本，充分利用多核CPU。
-
结论 ：没有一种算法是通用的。数据库CBO优化器是一个复杂的系统工程，其强大之处在于能够根据查询的复杂度和系统配置，智能地选择或组合这些算法，在优化时间与执行计划质量之间做出最佳权衡。
