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

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

智能查询优化算法
代价模型 指导 连接优化 (第3节)
(第2节)
使用启发式算法 使用代价估计 使用强化学习
数据驱动的基数 优化连接顺序 决定连接方式 对连接进行优化
估计模型
查询驱动的代价 指导 计划生成 (第4节)
估计模型 端到端地进行 辅助和指导优化器
计划生成 进行计划生成
数据和查询驱动
的代价估计模型
查询改写 (第5节)
指导
基于排序学习的 优化已有规则的
代价估计模型 应用策略 创造新规则

图 2 智能查询优化算法逻辑关系图

第 2 节介绍各类用于评估候选计划优劣的代价模型. 此类模型通过对查询进行建模作为输入, 然后采用机器
学习的模型来评估查询计划的优劣. 虽然代价模型本身并不直接对查询进行优化, 但是许多算法都需要有代价模
型来对其枚举出的候选方案进行评估, 所以代价模型是为它们提供指导的重要组成部分. 其中主要包括数据驱动
的基数估计模型, 查询驱动的代价模型, 结合数据和查询驱动的代价估计模型以及基于排序学习的代价估计模型.
第 3 节介绍一系列连接优化算法. 此类方法的优化目标包括连接顺序和连接方式. 连接顺序和连接方式是决
定查询性能的两个重要特征, 也是早期研究者们研究查询优化问题的主要优化目标. 在进入强化学习的时代之后,
连接优化算法也迎来了新的突破.
第 4 节介绍计划生成方法. 在机器学习模型可以单独解决代价估计和连接优化问题之后, 研究者们试图用机
器学习方法为一条查询语句直接生成完整的计划, 而并非仅优化计划中某些单独的特征. 达成此目的方法主要分
为两类: 端到端地进行计划生成与辅助和指导传统优化器进行计划生成.
第 5 节主要介绍查询改写算法. 查询改写的关注点并不是查询计划上的缺陷, 而是查询语句结构上的缺陷. 这
些问题大多只能通过查询在真正输入数据库之前的查询改写环节解决, 所以查询改写是查询优化过程中不可替代
的重要步骤. 查询改写一般基于规则进行, 其优化方式主要分为: 优化已有规则的应用策略和创造新的规则.
第 6 节总结本文的主要内容, 并对未来的研究方向进行展望.

2 代价模型

代价模型输入一个 (子) 查询计划, 输出其对应的代价值. 虽然代价模型实现的功能比较简单, 但是它对其他各
种智能查询优化算法具有指导性意义, 比如: 它可以判断哪种连接顺序的代价更低, 某一次扫描操作选择哪种算子
代价更低等. 代价模型就通过这样的定量分析对其他查询优化算法 (如连接优化, 计划生成) 起指导作用, 它的性能
可以直接影响其他优化算法的效果. 传统优化器中的代价模型设计比较简单, 它们一般会直接采用一个固定的公式
将统计信息中的基数, 磁盘 I/O 开销等变量进行简单建模并计算得到预测代价. 这类代价模型的预测值与真实值往
往偏差较大, 从而使得传统优化器会错误地选择次优计划. 而基于机器学习的代价模型可以从数据分布和查询计划
中考虑更丰富的输入特征, 更复杂的关联关系, 从而达到更高的预测精度, 引导优化器选择更优的查询计划.
2.1 数据驱动的基数估计模型
基数估计指在一个子计划或算子执行之前事先预测出其输出的元组数. 虽然基数估计相对于代价估计而言缺
少了对物理运算符和其他系统环境的感知, 但它还是影响着代价估计的最重要因素, 以至于一些传统优化器就是
直接使用基数估计的结果来作为代价估计值. 所以研究者们最先开始改进的也是基数估计模型 [15−17] . 其中数据驱