Page 361 - 《软件学报》2026年第2期

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

基于人工智能的查询重写方法, 利用人工智能的方法选择重写规则的顺序, 从而达到重写查询提升查询效率
的目的. SIA [198] 提出了一种重写查询谓词的方法, SIA 解决了谓词重写的两大问题, 一是重写后谓词与原始谓词等
价的问题, 二是约束合成谓词中的列集合导致的错误问题. SIA 利用可满足性模理论 (SMT) 验证重写谓词和原谓
词的等价关系, 从而保证重写的等效性. SIA 还设计了一种反例指导的学习方式学习严格有效的重写谓词. WeTune [199]
受到了编译器超级优化的启发, 尝试有约束地枚举所有有效的查询重写规则构造新的查询树, 并从中筛选那些可
能有效的可行计划. 该方法也使用基于 SMT 问题的求解方法, 对数据库查询重写规则建模为允许编码的 SMT 问
题, 以检查查询重写后生成规则的正确性. WeTune 仍然基于数据库本身的代价优化器来计算重写后的查询树与
原查询的代价差距. 尽管 WeTune 与基于启发式规则的方法类似, 但其具有优化迅速, 组件可替代, 能够快速部署
的优点. LearnedRewrite [200] 基于蒙特卡洛树搜索设计了不同的查询重写方法, 该方法能够高效寻找最优重写顺序,
同时评估重写所降低的查询代价. LearnedRewrite 首先将查询重写规则建模成蒙特卡洛树, 树的根节点是数据库
生成的查询树, 每个非根节点是通过对其父节点应用单个重写规则获得的重写后的查询树, 而从根节点到叶节点
的路径就是对应的重写规则. LearnedRewrite 设计了单独的查询重写代价估计器用来估计重写给查询带来的代价
优化. 除此之外, 为了更快速地训练 LearnedRewrie 还设计了并行的蒙特卡洛树搜索方法以提高搜索效率.
4.2.2 规模估算
数据库查询规模估算就是估算数据库查询结果的基数 (cardinality) 或者选择率 (selectivity), 也就是查询操作
符生成的结果元组 (即行) 的数量, 或者结果元组数量与表的元组数量的比率. 数据库查询规模估算的准确性是决
定数据库代价估算准确性的最重要因素之一. 对于单表估算而言, 查询规模估算受到数据倾斜的影响, 而对于连
接 (join) 估算, 查询规模估算又受到关系之间关联性影响. 对于整个计划而言, 整体的规模估算又有可能受到底层
节点的误差传递影响. 智能查询规模估算方法就是利用人工智能的方法对查询的基数进行估算, 其可以分为数据
驱动的规模估算方法, 查询驱动的规模估算方法和数据与查询混合驱动的规模估算方法.
图 9 展示了智能数据库基数估计的标准化流程, 基数估计管道首先解析输入 SQL 查询以生成逻辑/物理执
行计划, 然后从查询谓词、连接运算符和数据分布 (例如直方图) 中提取多维特征, 最后将这些特征输入估计模型
(例如概率图形模型或神经网络) 以预测基数. 其中数据驱动方法学习从数据分布到基数的映射, 而查询驱动方法
仅使用查询和计划特征关注计划到基数的关系, 通过解耦特征工程和模型推理实现模块化扩展.

估计模型
SQL 查询计划 查询驱动
特征提取 基数/代价
数据分布 数据驱动

图 9 规模/代价估算标准化架构

数据驱动的规模估算方法主要以无监督学习的方式学习数据的联合概率分布或条件概率分布. DeepDB [201] 使
用和积网络 (SPN) 拟合数据联合分布, 递归地将一个表的行数据用 sum 节点分为不同的行组、用 product 节点将
属性分为不同的列组. 每个叶节点使用统计直方图或分段线性函数估算不同属性数据分布. 在计算查询选择率时,
从叶节点开始自底向上计算, 并根据节点类型累加 (sum) 或相乘 (product) 子节点选择率. 对于多表查询, DeepDB
计算属性的随机依赖系数, 并依据此系数评估多表之间的相关性关系构建和积网络模型并估算选择率. FLAT [202]
在 SPN 的基础上提出 FSPN 模型, 它可以支持多属性的统计直方图, 并且在树结构中加入新的节点类型, 增加了
SPN 模型对数据分布拟合的灵活性, 进一步提高了选择率估算的准确性.
而 Naru [203] 和 DQM-D [204] 则将单表的联合分布用链式法则分解为条件概率分布. 他们使用深度自回归模型例
如 MADE [205] 拟合条件概率分布, 这类方法可以直接对点查询的选择率进行估算. 对于范围查询, Naru 采用渐进采
样策略, Naru 根据条件概率分布的每个内部输出逐列采样, 在深度自回归模型的引导下, 采样器将更加关注查询
区域中高影响的部分, 输出用重要性加权补偿诱导的偏差; DQM-D 采用多阶段采样策略, 在每个阶段, 该方法根