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

一、核心主题本章介绍 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是解决多阶段决策过程最优化问题的数学方法。核心思想将复杂问题分解为相互重叠的子问题每个子问题只求解一次保存结果后续需要时直接查表避免重复计算适用条件最优子结构问题的最优解包含子问题的最优解重叠子问题不同子问题之间存在公共子问题无后效性子问题的解一旦确定不受后续决策影响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表为例初始化层k1 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层k2 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层k3 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层k4 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 TreeJoin / \ Join D / \ Join C / \ A B特点每次连接一个基表和一个中间结果优势适合流水线执行无需物化中间结果3.4.2 右深树Right Deep TreeJoin / \ A Join / \ B Join / \ C D与左深树镜像对称PostgreSQL会同时尝试生成左深树和右深树3.4.3 浓密树Bushy TreeJoin / \ 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×B4.3 种群初始化4.3.1 改进的Fisher-Yates洗牌算法经典Fisher-Yates1. 初始化有序数组 [1, 2, 3, ..., N] 2. 从后往前每次随机交换当前位置与之前某个位置PostgreSQL改进版1. 从第1个位置开始 2. 对于位置i生成随机数j0 ≤ 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 选择算子Selection4.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.0r[0,1]均匀随机数效果验证bias2.0时区间理论概率实际概率0.0-0.119%19.23%0.1-0.217%16.71%0.2-0.315%15.02%………0.9-1.01%0.99%结论选择概率随染色体排名递减优质染色体被选中概率更高4.5 交叉算子CrossoverPostgreSQL提供5种交叉方法4.5.1 位置交叉PX, Position Crossover步骤从父染色体随机选择 1/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特点保留父母染色体中的边信息相邻关系步骤构建邻接表记录每个基因在两个父染色体中的邻居从起点开始优先选择邻居最少的未访问基因若所有邻居都已访问随机选择未访问基因优势适合TSP问题保留路径连续性4.5.3 部分匹配交叉PMX, Partially Matched Crossover步骤随机选择两个交叉点直接复制父染色体两点之间的基因通过映射关系填充剩余位置示例父染色体: [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特点子染色体的每个位置都来自父或母之一步骤从位置0开始从父染色体取基因找到该基因在母染色体中的位置从母染色体取该位置的基因重复直到形成完整循环未参与循环的位置从另一个父染色体取4.5.5 顺序交叉OX, Order Crossover步骤从父染色体随机选择一段基因保持这段基因的相对顺序从母染色体按顺序填充剩余位置跳过已存在的基因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. 设置forcetrue 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_rows4.7 代际遗传迭代次数控制generations max(geqo_generations, 100 (N-12) × 10)终止条件达到最大迭代次数或最优解连续多代无改善种群更新策略生成新染色体计算适应度使用二分法找到插入位置淘汰适应度最差的染色体五、与其他数据库算法对比5.1 Oracle的连接顺序优化5.1.1 动态规划小表集与PostgreSQL类似使用DP搜索差异Oracle支持星型转换Star Transformation星型查询优先连接事实表与维度表5.1.2 启发式搜索大表集当表数量超过阈值默认5个切换到启发式搜索规则优先连接选择率最低的表优势快速收敛但可能错过最优解5.1.3 对比总结特性PostgreSQLOracle小表集算法动态规划动态规划大表集算法遗传算法启发式搜索阈值125解的质量近似最优局部最优5.2 MySQL的连接顺序优化5.2.1 贪心搜索Greedy Search算法每次选择当前最优的表加入连接复杂度O(N²)问题容易陷入局部最优示例表A(100行), B(1000行), C(10000行) 连接条件A.idB.aid AND B.idC.bid 贪心选择 1. 计算所有两表连接代价 2. 选择代价最小的A×B假设代价100 3. 将A×B与C连接代价1000 问题如果B×C×A更优贪心无法找到5.2.2 动态规划MySQL 8.0引入基于代价的优化器CBO支持动态规划但默认关闭需要设置optimizer_switchoptimizer_search_depth05.2.3 对比总结特性PostgreSQLMySQL默认算法动态规划 遗传算法贪心搜索复杂度控制可配置阈值固定O(N²)解的质量较好一般5.3 SQL Server的连接顺序优化5.3.1 动态规划默认与PostgreSQL类似的DP实现差异SQL Server使用超图Hypergraph表示连接关系5.3.2 贪心搜索可选当表数量超过64时切换到贪心搜索或当查询复杂度超过阈值时5.3.3 对比总结特性PostgreSQLSQL Server默认算法动态规划动态规划大表集处理遗传算法贪心搜索阈值12645.4 DB2的连接顺序优化5.4.1 动态规划小表集标准DP实现支持星型模式优化5.4.2 启发式 遗传算法大表集表数量 12 时使用启发式可选启用遗传算法实验性功能5.4.3 对比总结特性PostgreSQLDB2大表集处理遗传算法成熟启发式 GA实验性星型优化有限支持完整支持5.5 综合对比表数据库小表集算法大表集算法阈值解的质量性能PostgreSQL动态规划遗传算法12较好中等Oracle动态规划启发式搜索5一般较快MySQL贪心搜索贪心搜索-一般快SQL Server动态规划贪心搜索64较好中等DB2动态规划启发式GA12较好中等六、算法选择策略6.1 PostgreSQL的决策树表数量 N 12? ├─ 是 → 使用动态规划 └─ 否 → enable_geqo on? ├─ 是 → 使用遗传算法 └─ 否 → 继续使用动态规划可能很慢6.2 启发式规则PostgreSQL在DP过程中应用的启发式规则连接条件优先有连接条件的表对优先连接选择率优先选择率低的表优先连接参数化路径考虑索引扫描等参数化路径启动代价考虑排序、哈希等启动代价6.3 性能调优建议6.3.1 调整阈值-- 增加阈值使用更多DPSETgeqo_threshold20;-- 减小阈值更早使用GASETgeqo_threshold8;6.3.2 调整GA参数-- 增加种群大小提高搜索质量SETgeqo_pool_size200;-- 增加迭代次数更充分搜索SETgeqo_generations500;-- 调整努力程度SETgeqo_effort10;6.3.3 禁用GA调试用SETenable_geqooff;七、关键参数详解参数作用默认值建议范围enable_geqo启用遗传算法onon/offgeqo_threshold触发遗传算法的表数量阈值128-20geqo_pool_size种群大小0自动50-200geqo_generations交叉次数0自动100-500geqo_effort影响种群大小和交叉次数51-10from_collapse_limit控制子查询拉平的表数量88-16join_collapse_limit控制连接顺序重排的表数量88-16八、小结动态规划是首选保证全局最优但表多时性能下降遗传算法是补充通过随机搜索逼近最优解PostgreSQL通过启发式规则限制搜索空间两种算法都记录较优解集为上层决策提供灵活性与其他数据库的主要差异PostgreSQL使用遗传算法GA而Oracle/MySQL使用启发式搜索PostgreSQL的阈值12高于Oracle5更依赖DPPostgreSQL的GA实现更成熟Oracle的启发式更简单高效选择建议小表集12使用DP保证最优大表集≥12使用GA平衡质量与性能特殊场景调整参数或禁用GA进行调试