Page 292 - 《软件学报》2026年第1期

何家豪 等: 智能查询优化算法研究综述 289

(1) 传统优化方法依赖于固定的规则和历史数据, 而强化学习具有平衡探索与利用的特点, 能够动态地在不同
的查询场景中进行探索, 逐步发现更优的连接顺序和方式. 而且通过适当的探索, 可以避免陷入局部最优解;
(2) 数据库的工作负载是动态变化的, 不同的查询在不同的时间点上可能会有不同的最优执行计划. 强化学习
具有动态适应性, 可以不断学习和调整策略以适应这些变化, 从而提供持续的优化效果;
(3) 连接优化通常涉及多个步骤, 强化学习具有延迟奖励机制, 可以综合考虑这些步骤的最终效果, 逐步优化
整个查询计划, 而不仅是局部的某一步优化.
3.4 与连接优化相关的其他工作

除了使用强化学习找出最优的连接顺序和连接方式的主线任务之外, 还有一些与连接优化相关的其他工作.
● L1-error [84] 提出了一种识别低效率的连接顺序的方法, 并指出对于大部分查询只要前 4 个表顺序是正确的,
整体性能就已经接近最优了. 所以在实际应用中只需要花比较小的开销规避掉最差的几种连接顺序就可以达到不
错的性能效果, 不一定每次都花费很高的开销去寻找最优的连接顺序.
● ADOPT [85] 提出了一种多表连接优化算法, 即一次连接多个连接条件在同样键上的表, 而不是每次仅多连接
一个表. 这样连接表顺序的问题就变成了连接键顺序的问题, ADOPT 可以确保在最差情况下连接操作的复杂度
是 O(n) 的.

4 计划生成

基于机器学习的方法在代价估计和连接优化两个特定方面取得不错的成效之后, 研究者们希望可以更进一
步, 从生成整个计划的角度端到端地解决查询优化问题. 此方向的研究与单独地进行连接优化的最主要区别在于:
在计划生成算法中评估的对象通常是完整的查询计划, 而不是仅选择下一个表的连接顺序或者连接方式. 计划生
成算法在智能查询优化研究中具有里程碑意义: 它突破了传统的单环节优化 (如仅解决代价估计或连接顺序问
题) 的局限, 开始试图构建一个完整的智能查询优化系统, 标志着智能查询优化从模块化改进向全流程智能化的
转变.
在人工智能赋能的查询优化算法尚未兴起之前, 前人就在此方向做过了许多研究. 比如: 文献 [86] 提出了一
种对查询进行聚类, 然后对于在同一个聚类中的查询采取类似的查询计划的方案; 文献 [87] 中提出了一种特定的
编码方式, 将优化关系型查询的问题建模成了一个删除自由的优化问题, 然后将贪心算法应用其中.
这些算法的研究从不同维度提升了系统性能. 有一些方法专注于直接降低查询执行的成本, 有一些则着眼于
优化查询优化过程本身的资源消耗. 这些方法通常能够提供可观的优化成果, 实现相对简便, 并且多数采用可解释
的白盒模型. 但是由于这类方法多依赖于预设的规则和静态的数据统计信息, 往往难以深入挖掘数据和查询内容
中潜藏的复杂关系和模式. 所以这些传统算法在面对频繁变化的查询负载和相关性比较复杂的底层数据时会面临
一定的挑战.
基于深度学习的技术开始应用于查询优化领域之后, 很大程度上克服了传统算法在处理复杂查询和动态数据
环境中的局限性. 现在计划生成方向的工作基本可以分为两类: 一是选择抛弃传统数据库的查询优化器, 采用一个
全新的算法来端到端地构造查询计划 [39,88−92] ; 二是采用较为渐进的策略, 将智能算法作为传统优化器的辅助和指
导, 修正传统优化器产生的查询计划, 以期在保留现有系统可解释性的基础上引入智能算法的优势 [5,40,61,93−95] .
4.1 端到端地进行计划生成
虽然传统优化器具有种种缺陷 (见第 1 节), 但是想要完全用机器学习模型取代它还是有不小的难度 [88] . 这主
要体现在以下 3 点.
(1) 机器学习模型在训练的初期往往效果不佳, 需要很久才可以达到传统优化器的水平.
(2) 与其他机器学习任务不同, 对于计划生成任务而言收集训练数据需要实际执行若干查询并收集相关信息,
开销较大.
(3) 计划生成任务涉及的输出空间 (执行生成计划的动作) 极大, 收敛更加困难.