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

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

● 一些方法关注于某些特定查询结构细节的代价估计, 比如对于 SUBSTR、GROUP BY 的基数估计: 文献 [71]
提出了一个对于单表且包含 HAVING 子句的基数估计方法; 文献 [72,73] 提出了两种对包含子串筛选 (LIKE) 查
询的基数估计方法; 文献 [74] 提出了一种可以对包含列属性为集合的查询进行基数估计的方法.
● 一些方法提出了对于收集代价模型训练资料的优化方向. 比如: DataFarm [75] 可以从查询负载需求、数据需
求和资源限制这 3 个角度出发生成量身裁定的数据; Hit the Gym [68] 通过“宏加速”和“微加速”两种手段加速了训练
数据的获取, 使得不必再通过真实执行查询语句来获取每条数据的标注值.
[76]
● PACE 提出了一个研究基数估计模型安全性的问题. 它指出如果商业产品中使用了基于机器学习的代价
模型, 那么恶意攻击者只需要通过执行 SELECT 语句就可以攻击到代价模型的性能, 从而影响业务执行的整体效
率. PACE 的作者还实现了一个恶意攻击代价估计模型的算法, 它可以有效降低现行的多种代价估计模型的效果.
3 连接优化

当一条查询需要从多个表中取得其需要的数据并进行分析时, 连接 (join) 操作是不可避免的. 而在连接涉及
的数据量较大、数据相关性较强时, 连接操作的性能就会显得至关重要. 在 OLAP 应用场景中, 一条查询往往都会
涉及大量数据以及多个表的连接操作, 一些对连接操作敏感的查询可能会因为没有进行有效的连接优化而导致性
能下降数十倍. 因此, 连接优化多年来一直是被广泛研究的课题 [77] . 连接优化算法在智能查询优化研究中具有奠
基性意义: 通过智能化手段解决多表连接这一在查询优化领域中的经典问题成为机器学习技术应用于查询优化领
域的关键突破口, 为后续更多的智能查询优化算法打下了基础. 目前, 连接优化的主流做法是使用强化学习优化连
接顺序和方式.
3.1 使用启发式算法对连接顺序进行优化
连接顺序的优化是谈及连接优化问题时第 1 个可以直观地联想到的优化问题, 因为连接顺序的优化可以仅通
过改变逻辑查询计划中表的连接顺序来实现. 连接顺序问题的解空间是一棵排列树, 传统优化器中的连接优化方
法主要通过遍历这棵排列树, 同时结合代价估计对排列树进行剪枝来完成连接顺序优化. 这样的优化方式即使在
代价估计足够准确的情况下也伴随着相当大的计算开销 (O(n!)) [78] . 更何况对于传统优化器的代价估计而言, 产生
[2]
足以让动态规划算法得到最优连接顺序的代价估计几乎是不现实的. 其他如 GEQO 、QuickPick-1000 [79] 等启发
式方法可以加速连接顺序的生成, 但通常无法生成最佳的连接顺序. 同时类似 System R、PostgreSQL 中的传统优
化器在决定一个连接顺序并执行后就会忘记它们曾经优化过的这个连接顺序. 所以即使传统优化器在某一次连接
优化结束后得到了最佳的连接顺序, 也会由于缺乏反馈, 重复地进行连接优化操作, 选择相同的次优顺序, 不会从
之前或好或坏的选择中学习到经验.
3.2 使用代价估计值决定连接方式
确定每一次连接操作的连接方式是在确定了连接顺序之后需要解决的第 2 个问题. 它决定了每一次逻辑上的
连接 (join) 将采用什么样的物理方式实现, 比如归并连接 (merge join)、哈希连接 (hash join) 等. 它相较于连接顺
序而言是一个相对简单的问题, 但也经常会影响性能. 传统优化器一般会根据它自身并不准确的代价估计选择连
接方式, 所以常常会选择出次优的连接方式.
比如, 哈希连接在内存空间足够的前提下是一个不错的连接方式, 因为其时间复杂度是 O(n); 但在内存空间
无法容纳下构建侧构建出来的哈希表时, 它的性能就会因为频繁访问不在内存中的数据而退化到不如归并连接.
所以当错误的代价估计导致优化器认为内存空间足够, 但实际上内存空间不足时, 优化器就会错误地选择哈希连
接导致性能退化.
类似的问题在分布式场景下的数据库系统中会更加严重, 因为分布式场景下还需要考虑到每一个具体的连接
方式在节点之间传输数据量的成本, 比如即使都是哈希连接, 分布式场景下也需要考虑要采用的是将整个小表广
播出去的广播哈希连接 (broadcast hash join) 还是按照键分布组合在每个节点上只完成部分连接任务的混洗哈希
连接 (shuffle hash join). 连接方式的错误在严重的情况下可能会导致部分节点内存溢出而宕机.