Page 363 - 《软件学报》2026年第2期
P. 363

842                                                        软件学报  2026  年第  37  卷第  2  期


                 一个神经网络单元, 该网络除了输出当前操作的执行时间, 还输出一个向量, 这个向量和该操作符的父节点特征共
                 同作为父节点模型的输入. Neo       [218] 、E2E [219] 和  QueryFormer [220] 分别设计了更加复杂的查询计划编码方式和基于树
                 形结构的神经网络模型. Neo       基于树卷积神经网络模型使用三角形滤波器                (父节点、左子节点、右子节点) 在查询
                 计划树上滑动, 使得它们无需递归步骤即可捕获物理计划树的父子依赖关系. 这样的设计使得模型可以并行处理
                 节点特征, 加快训练速度. 但由于树卷积具有较小的感受野, 每个节点只能从附近的邻居中看到特征, 所以                               Neo  无
                 法捕获从叶节点到根节点的长路径信息流. E2E              使用   Tree-LSTM  模型, 将信息自底向上从叶节点聚合到根节点,
                 并使用最终的输出向量作为物理计划的表示, 最后由多层全连接网络映射为计划的代价估计. QueryFormer 额外
                 添加了数据的采样信息和直方图信息特征, 并分别为这些特征单独编码, 然后使用基于注意力机制的树形神经网
                 络进行代价学习, 这种方法一步改进了神经网络在学习查询计划树形结构特征向量时的信息传输机制, 使得模型
                 能够关注到计划的全局结构特征. Zero-shot        [221] 通过选择计划中可迁移的特征增强了模型的泛化性, 该方法使用前
                 n  个数据库上的查询负载作为训练集, 在第           n+1  个数据库上进行查询代价预测. Zero-shot 的输入特征中包含计划
                 节点的基数估计, 因此需要依赖基数估计模型. ParamTree            [222] 通过建立  C-Param (数据库参数、硬件配置以及计划
                 操作符特征等) 到     R-Param (数据库查询优化器参数中代价函数的各权重值) 的映射函数使得传统代价函数估计器
                 的估计更加准确.
                  4.2.4    计划优化
                    将查询解析得到逻辑计划后, 查询优化器将基于计划树的各个节点代价估计输出最终物理执行计划. 生成物
                 理执行计划的过程包括表连接           (Join) 顺序优化和对物理算子选择        (如选择连接算子、扫描算子等). 连接顺序对查
                 询计划性能的影响显著, 一些方法只关注连接顺序优化. 更完整的计划优化方法考虑到整体物理查询计划的影响,
                 这些方法构造了端到端的查询优化器.
                    (1) 连接顺序优化
                    查询计划中表的连接顺序显著影响了查询的性能, 然而寻找最优连接顺序是一个                            NP-Hard  问题. 传统的方法
                 主要是基于动态规划或贪心算法等启发式算法选择计划连接顺序, 智能连接顺序优化方法将构造计划连接顺序的
                 问题建模为马尔可夫过程并使用强化学习方法解决. 智能连接顺序优化方法从独立的单表开始自下而上连接子计
                 划和计划中的表以生成完整的连接顺序.
                         [223]
                    Rejoin  采用基于策略的强化学习方法. Rejoin         训练策略网络直接预测下一步动作, 并收集计划代价和状态
                 向量来更新策略网络参数. 一些方法           [224−228] 使用基于值的强化学习方法, 主要范式为训练价值网络             Q  来预测计划
                 或子计划的未来最小执行时间或代价估计, 然后使用该预测值并基于启发式策略引导完整连接顺序的生成. DQ                                  [225]
                 使用贪心策略, 根据      Q  网络的输出只选择当前最有利的动作. RTOS           [227] 则进一步改进  Q  网络, 使用  Tree-LSTM  网
                 络表示连接顺序的状态, 同时通过改进训练阶段的损失函数                    (包括代价损失函数和延迟损失函数) 来平衡生成连
                 接顺序的时间和效果. JOGGER       [228] 根据数据库主键-外键关系构建模式图以捕捉表之间的相关性, 同时利用图卷积
                 网络对查询图进行编码, 并设计一个基于树的注意力机制模块对连接计划进行编码. JOGGER                            还按照查询的复杂
                 程度分级训练     Q  网络, 采用分层学习的方法来加速         Q  网络的收敛.
                    (2) 端到端查询优化
                    端到端的查询优化更加关注计划的整体性能, 是从查询到生成查询计划的完整优化方法. 本文根据执行计划
                 生成方式的不同将现有技术分为自下而上的查询优化方法和规则引导的查询优化方法. 自下而上的优化方法利用
                 机器学习技术完全取代传统查询优化器. 规则引导的查询优化方法旨在充分利用传统查询优化器的专家知识, 通
                 过外部规则的限制引导传统优化器生成更好的查询计划.
                    自下而上的查询优化方法仍基于强化学习算法框架, 这些方法在                      DQ [225] 方法的基础上进行拓展, 也通过价值
                 网络的引导以自下而上的方式逐步完成计划构造. 不同的是, 他们不仅优化了连接顺序, 还关注了物理算子的选
                 择, 包括连接算子和表操作符. Neo       [218] 首先从历史查询负载中学习初始化价值网络, 然后实时地根据输入的查询和
                 其执行结果更新价值网络. 对于输入的查询, Neo             从初始状态     (各个独立单表) 枚举所有可行动作           (包括指定表扫
                 描算子或用某连接算子连接两表) 并得到所有子状态, 再根据价值网络对子状态的预测代价将各个子状态放入一
   358   359   360   361   362   363   364   365   366   367   368