第七章-动态规划和遗传算法

一、核心主题

本章介绍 PostgreSQL 查询优化器如何生成连接路径（Join Paths），重点讲解两种搜索算法：

• 动态规划（Dynamic Programming）- 保证全局最优解
• 遗传算法（Genetic Algorithm）- 近似最优解，适用于表数量多的场景

二、为什么需要连接顺序优化

问题本质：多表连接时，不同连接顺序的执行代价差异巨大。

示例说明：

• TEST_A、TEST_B、TEST_C 各10000条数据
• 先连接 TEST_B 和 TEST_C → 产生5000条中间结果
• 先连接 TEST_A 和 TEST_B → 产生50,000,000条中间结果
• 查询优化器选择前者，通过物化5000条记录获得更好性能

组合爆炸问题：

• N 个表的全连接顺序数量为(2N-3)!!（双阶乘）
• 10个表 ≈ 3.4万种顺序
• 15个表 ≈ 7.6亿种顺序
• 20个表 ≈ 超过 2万亿种顺序

三、动态规划算法详解（7.1节）

3.1 算法原理

动态规划（Dynamic Programming, DP）是解决多阶段决策过程最优化问题的数学方法。

核心思想：

• 将复杂问题分解为相互重叠的子问题
• 每个子问题只求解一次，保存结果
• 后续需要时直接查表，避免重复计算

适用条件：

1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：不同子问题之间存在公共子问题
3. 无后效性：子问题的解一旦确定，不受后续决策影响

3.2 PostgreSQL中的DP实现

3.2.1 状态定义

dp[k][S] = 使用集合S中的k个表，能达到的最小连接代价

其中：

• k：当前连接的表数量（层级）
• S：表集合（用位图表示）
• dp[k][S]：最优连接路径的代价

3.2.2 状态转移方程

dp[k][S] = min { dp[k-1][S'] + cost(join(S', T)) for all T ∈ S, S' = S - {T} }

即：当前最优解 = 子问题最优解 + 新连接代价

3.2.3 迭代过程（以4表为例）

初始化层（k=1）： dp[1][{A}] = cost(scan A) dp[1][{B}] = cost(scan B) dp[1][{C}] = cost(scan C) dp[1][{D}] = cost(scan D) 第2层（k=2）： dp[2][{A,B}] = min(dp[1][{A}] + cost(join A,B), dp[1][{B}] + cost(join B,A)) dp[2][{A,C}] = ... dp[2][{A,D}] = ... dp[2][{B,C}] = ... dp[2][{B,D}] = ... dp[2][{C,D}] = ... 第3层（k=3）： dp[3][{A,B,C}] = min(dp[2][{A,B}] + cost(join AB,C), dp[2][{A,C}] + cost(join AC,B), dp[2][{B,C}] + cost(join BC,A)) ... 第4层（k=4）： dp[4][{A,B,C,D}] = 最终最优解

3.2.4 时间复杂度分析

• 空间复杂度：O(2^N × N)
• 时间复杂度：O(3^N)（每个子集枚举所有子集）
• PostgreSQL通过以下策略优化：
  • 剪枝：优先处理有连接条件的表对
  • 保存较优解集：每个状态保存多个候选路径

3.3 PostgreSQL的改进：保存较优解集

问题：经典DP只保存单一最优解，但查询优化需要考虑多种情况。

PostgreSQL的解决方案：

• 每个RelOptInfo保存一个路径链表
• 包含：最优启动代价路径、最优总代价路径、参数化路径等
• 在"堆积"过程中，根据不同上层需求选择合适的子路径

示例：

假设连接顺序 A×B×C 路径1：顺序扫描A → 索引扫描B → Merge Join - 启动代价：100 - 总代价：1000 路径2：索引扫描A → 顺序扫描B → Hash Join - 启动代价：500 - 总代价：800 如果上层是 Nested Loop → 选择路径2（总代价低） 如果上层需要排序输出 → 选择路径1（启动代价低）

3.4 连接树形状

PostgreSQL在DP过程中生成三种连接树形状：

3.4.1 左深树（Left Deep Tree）

Join / \ Join D / \ Join C / \ A B

• 特点：每次连接一个基表和一个中间结果
• 优势：适合流水线执行，无需物化中间结果

3.4.2 右深树（Right Deep Tree）

Join / \ A Join / \ B Join / \ C D

• 与左深树镜像对称
• PostgreSQL会同时尝试生成左深树和右深树

3.4.3 浓密树（Bushy Tree）

Join / \ Join Join / \ / \ A B C D

• 特点：可以并行执行多个子连接
• 适用：表之间无连接顺序限制时

四、遗传算法详解（7.2节）

4.1 算法原理

遗传算法（Genetic Algorithm, GA）是模拟自然选择和遗传机制的优化算法。

核心思想：

• 将问题解编码为"染色体"
• 通过选择、交叉、变异操作生成新解
• 保留优质解，淘汰劣质解
• 迭代逼近全局最优

与经典遗传算法的差异：

• PostgreSQL的GA没有变异操作，只有交叉
• 通过概率选择实现"优胜劣汰"

4.2 编码方式

PostgreSQL使用实数编码（不同于常见的二进制编码）：

染色体 = [基因1, 基因2, ..., 基因N] 基因值 = 表编号（1, 2, ..., N） 示例（4个表）： 染色体1: [1, 2, 3, 4] → A×B×C×D 染色体2: [2, 4, 3, 1] → B×D×C×A 染色体3: [3, 1, 4, 2] → C×A×D×B

4.3 种群初始化

4.3.1 改进的Fisher-Yates洗牌算法

经典Fisher-Yates：

1. 初始化有序数组 [1, 2, 3, ..., N] 2. 从后往前，每次随机交换当前位置与之前某个位置

PostgreSQL改进版：

1. 从第1个位置开始 2. 对于位置i，生成随机数j（0 ≤ j ≤ i） 3. 如果j ≠ i，交换位置i和j的内容 4. 重复直到所有位置处理完毕

时间复杂度：O(N)，空间复杂度：O(N)

4.3.2 种群大小确定

pool_size = max(geqo_pool_size, 50 + (N-12) × 5)

其中N为表数量，默认geqo_pool_size = 0（自动计算）

4.4 选择算子（Selection）

4.4.1 概率分布选择

PostgreSQL使用非均匀概率分布，倾向选择适应度高的染色体：

概率密度函数：

e(x) = Ndrd - 2(Ndrd-1)x (0 < x < 1)

累积分布函数：

P(x) = Ndrd·x - (Ndrd-1)x²

逆函数法生成随机数：

index = max × (bias - √(bias² - 4(bias-1)·r)) / 2(bias-1)

其中：

• max：种群大小
• bias：偏向参数（默认2.0）
• r：[0,1]均匀随机数

效果验证（bias=2.0时）：

结论：选择概率随染色体排名递减，优质染色体被选中概率更高

4.5 交叉算子（Crossover）

PostgreSQL提供5种交叉方法：

4.5.1 位置交叉（PX, Position Crossover）

步骤：

1. 从父染色体随机选择 1/3~2/3 的基因
2. 将这些基因按原位置复制到子染色体
3. 从母染色体按顺序填充剩余位置

示例：

父染色体: [1, 3, 2, 4] 母染色体: [2, 3, 1, 4] 交叉过程： 1. 从父染色体选择位置1和2的基因：[3, 2, _, _] 2. 母染色体排除已选基因后为 [1, 4] 3. 按母染色体顺序填充：[3, 2, 1, 4] 子染色体: [3, 2, 1, 4]

4.5.2 边重组交叉（ERX, Edge Recombination）

特点：保留父母染色体中的"边"信息（相邻关系）

步骤：

1. 构建邻接表，记录每个基因在两个父染色体中的邻居
2. 从起点开始，优先选择邻居最少的未访问基因
3. 若所有邻居都已访问，随机选择未访问基因

优势：适合TSP问题，保留路径连续性

4.5.3 部分匹配交叉（PMX, Partially Matched Crossover）

步骤：

1. 随机选择两个交叉点
2. 直接复制父染色体两点之间的基因
3. 通过映射关系填充剩余位置

示例：

父染色体: [1, 2|3, 4|5] 母染色体: [3, 5|1, 2|4] 交叉点之间：父[3,4]，母[1,2] 映射关系：3↔1, 4↔2 子染色体: [1, 2|3, 4|5]（父的交叉段） 填充剩余：通过映射关系避免重复

4.5.4 循环交叉（CX, Cycle Crossover）

特点：子染色体的每个位置都来自父或母之一

步骤：

1. 从位置0开始，从父染色体取基因
2. 找到该基因在母染色体中的位置，从母染色体取该位置的基因
3. 重复直到形成完整循环
4. 未参与循环的位置从另一个父染色体取

4.5.5 顺序交叉（OX, Order Crossover）

步骤：

1. 从父染色体随机选择一段基因
2. 保持这段基因的相对顺序
3. 从母染色体按顺序填充剩余位置，跳过已存在的基因

4.6 适应度计算

4.6.1 连接树生成（gimme_tree）

核心函数：merge_clump

算法流程：

输入：染色体编码 [g1, g2, ..., gN] 输出：连接树（可能失败） 1. 初始化空clumps列表 2. for i = 1 to N: a. 创建单节点Clump（基因gi） b. 调用merge_clump尝试合并： - 遍历clumps列表 - 尝试将当前Clump与已有Clump连接 - 如果连接成功，合并为新Clump - 递归尝试继续合并 3. 如果clumps列表有多个节点： a. 设置force=true b. 强制尝试连接所有Clump 4. 如果仍无法合并为单个树： a. 设置适应度为DBL_MAX（无效染色体） 5. 否则： a. 计算连接树总代价作为适应度

4.6.2 代价计算

连接树代价计算遵循以下公式：

顺序扫描代价：

cost = seq_page_cost × pages + cpu_tuple_cost × tuples

索引扫描代价：

cost = index_page_cost × index_pages + cpu_tuple_cost × selected_tuples + random_page_cost × (pages × selectivity)

嵌套循环连接代价：

cost = outer_cost + outer_rows × (inner_cost + inner_tuple_cost × inner_rows)

排序合并连接代价：

cost = outer_cost + inner_cost + sort_cost(outer) + sort_cost(inner) + merge_tuple_cost × (outer_rows + inner_rows)

哈希连接代价：

cost = outer_cost + inner_cost + hash_build_cost × inner_rows + hash_probe_cost × outer_rows

4.7 代际遗传

迭代次数控制：

generations = max(geqo_generations, 100 + (N-12) × 10)

终止条件：

• 达到最大迭代次数
• 或最优解连续多代无改善

种群更新策略：

1. 生成新染色体
2. 计算适应度
3. 使用二分法找到插入位置
4. 淘汰适应度最差的染色体

五、与其他数据库算法对比

5.1 Oracle的连接顺序优化

5.1.1 动态规划（小表集）

• 与PostgreSQL类似，使用DP搜索
• 差异：Oracle支持星型转换（Star Transformation）
• 星型查询优先连接事实表与维度表

5.1.2 启发式搜索（大表集）

• 当表数量超过阈值（默认5个），切换到启发式搜索
• 规则：优先连接选择率最低的表
• 优势：快速收敛，但可能错过最优解

5.1.3 对比总结

5.2 MySQL的连接顺序优化

5.2.1 贪心搜索（Greedy Search）

• 算法：每次选择当前最优的表加入连接
• 复杂度：O(N²)
• 问题：容易陷入局部最优

示例：

表：A(100行), B(1000行), C(10000行) 连接条件：A.id=B.aid AND B.id=C.bid 贪心选择： 1. 计算所有两表连接代价 2. 选择代价最小的：A×B（假设代价100） 3. 将A×B与C连接，代价1000 问题：如果B×C×A更优，贪心无法找到

5.2.2 动态规划（MySQL 8.0+）

• 引入基于代价的优化器（CBO）
• 支持动态规划，但默认关闭
• 需要设置optimizer_switch='optimizer_search_depth=0'

5.2.3 对比总结

5.3 SQL Server的连接顺序优化

5.3.1 动态规划（默认）

• 与PostgreSQL类似的DP实现
• 差异：SQL Server使用超图（Hypergraph）表示连接关系

5.3.2 贪心搜索（可选）

• 当表数量超过64时，切换到贪心搜索
• 或当查询复杂度超过阈值时

5.3.3 对比总结

5.4 DB2的连接顺序优化

5.4.1 动态规划（小表集）

• 标准DP实现
• 支持星型模式优化

5.4.2 启发式 + 遗传算法（大表集）

• 表数量 > 12 时使用启发式
• 可选启用遗传算法（实验性功能）

5.4.3 对比总结

5.5 综合对比表

六、算法选择策略

6.1 PostgreSQL的决策树

表数量 N < 12? ├─ 是 → 使用动态规划 └─ 否 → enable_geqo = on? ├─ 是 → 使用遗传算法 └─ 否 → 继续使用动态规划（可能很慢）

6.2 启发式规则

PostgreSQL在DP过程中应用的启发式规则：

1. 连接条件优先：有连接条件的表对优先连接
2. 选择率优先：选择率低的表优先连接
3. 参数化路径：考虑索引扫描等参数化路径
4. 启动代价：考虑排序、哈希等启动代价

6.3 性能调优建议

6.3.1 调整阈值

-- 增加阈值，使用更多DPSETgeqo_threshold=20;-- 减小阈值，更早使用GASETgeqo_threshold=8;

6.3.2 调整GA参数

-- 增加种群大小，提高搜索质量SETgeqo_pool_size=200;-- 增加迭代次数，更充分搜索SETgeqo_generations=500;-- 调整努力程度SETgeqo_effort=10;

6.3.3 禁用GA（调试用）

SETenable_geqo=off;

七、关键参数详解

八、小结

1. 动态规划是首选，保证全局最优，但表多时性能下降
2. 遗传算法是补充，通过随机搜索逼近最优解
3. PostgreSQL通过启发式规则限制搜索空间
4. 两种算法都记录较优解集，为上层决策提供灵活性

与其他数据库的主要差异：

• PostgreSQL使用遗传算法（GA），而Oracle/MySQL使用启发式搜索
• PostgreSQL的阈值（12）高于Oracle（5），更依赖DP
• PostgreSQL的GA实现更成熟，Oracle的启发式更简单高效

选择建议：

• 小表集（<12）：使用DP，保证最优
• 大表集（≥12）：使用GA，平衡质量与性能
• 特殊场景：调整参数或禁用GA进行调试