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

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

则集的优化更加灵活, 并且与端到端的计划生成方法相比, 它更简便、收敛速度更快, 且极少出现“尾部灾难”现象.
Bao 对传统优化器的辅助和指导可以理解为通过使用“提示”指导传统优化器进行优化. 这样的方式需要首先
构造出一个可以对计划生成过程产生影响的“提示集”, 然后再从“提示集”中为每条到来的查询选择适当的“提示”
对传统优化器进行指导. 之后的 DeepO [40] 在此基础上, 又将“提示集”推广到了连接顺序上, 并且还提供了带有置信
度的输出以供用户更加清晰地认知到其辅助和指导的过程.
随着“提示集”的规模逐渐扩大, 研究者们发现如何为每一条查询确定一个合理的“提示集”探索空间成为一个
新的问题. 比如在微软的 SCOPE 系统中有多达 256 条这样可开关的规则, 而且很多规则之间还存在依赖关系, 如
果为每一条查询都去枚举 2 256 的数量级的规则开关组合的“提示”, 然后再找出最优的提示集是不现实的 [5] . 所以
FASTgres [93] 和 SCOPE 的研究者就提出了对查询进行分组, 在每一个组内定制一个相对小一点的“提示集”, 然后
对组内的查询就只用在其组所对应的“提示集”内进行枚举的思路. 区别在于 SCOPE 采取的分组策略是根据“提示”
对查询计划产生影响的特性将查询分组, 每组查询通过启用或禁用相应的“提示集”的子集, 能够产生不同的查询
计划, 而无需考虑与组不相关的“提示”; FASTgres 则是依据参与连接的表和连接谓词作为分类依据将输入的查询
语句进行分组, 基于这种分组, 系统再进一步提取各组查询的谓词作为特征, 针对每个特定的查询组独立训练一个
专用的小型机器学习模型输出其相应的“提示”.
除了利用分组的思想限制“提示”的搜索空间之外, 研究者们还在实验过程中发现了“提示”的两个特点.
(1) 对于一条查询有提升的“提示”的子集也是有提升的“提示”.
(2) 一般有提升的“提示”的规模不会太大 (不超过 4).
所以探索“提示”是一个同时具有贪心选择性质和最优子结构的问题, AutoSteer [94] 便从这个角度出发, 提出了
一种贪心算法, 即: 在探索过程中如果发现单独关闭规则 R 1 和规则 R 2 都有提升, 那么下一步 AutoSteer 就会探索
同时关闭规则 R 1 和规则 R 2 的“提示”. AutoSteer 会按照这样的方式探索, 直到最优规则集无法再进一步拓展为止.
AutoSteer 通过这样的方式也一样可以有效地限制“提示”的搜索空间.
图 6 概括了使用“提示”对传统优化器进行辅助和指导的方法的发展流程.

将 “提示集” 拓展到连接顺序上

DeepO
首个使用 “提示” 的方法 利用分组限制 根据生效的 “提示” 分组
“提示” 搜索空间 SCOPE
Bao
根据涉及的表和谓词分组
FASTgres
利用贪心算法限制
“提示” 搜索空间
AutoSteer
图 6 使用“提示”对传统优化器进行辅助和指导的方法的发展流程

4.2.2 通过其他方式辅助和指导传统优化器进行计划生成
● 在主流算法大多在考虑使用传统优化器中规则的开关作为“提示”时, Lero [65,66] 选择将“增大或缩小传统优化
n
器中的基数估计 10 倍”作为“提示”. 对于单条查询而言, 这样修改基数估计的“提示”虽然不一定完全精准, 但是根
据排序学习 (第 2.4 节) 的思想, 对于即使不是完全正确的“提示”, 只要对其枚举出的候选计划之间的相对关系判
断是正确的, 就依然可以选择出最优计划. 所以 Lero 在使用了这样的“提示”之后又使用了一个成对 (pairwise) 的

代价模型去从枚举出的计划中选择最优的.
● FOSS [95] 则放弃了在传统优化器开始优化之前就去进行“提示”的做法, 而是在传统优化器生成计划之后去
再进行修补. 每一次的修补涉及一次连接方式、扫描方式的选择或是一次连接顺序的调整等. 这样的做法也有效
地达到了不亚于在优化之前进行“提示”的方法的效果, 为辅助和指导传统优化器提供了新思路.