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

282 软件学报 2026 年第 37 卷第 1 期

动的方法是其中的一个关键分支. 数据驱动的方法的核心思想是对数据的分布进行联合概率建模, 然后依照判断
符合条件的元组在表中出现的概率对基数进行估算 (图 3(a)).

SQL: SELECT id Id Name Age Salary SQL1: SELECT id FROM employee WHERE age>30 AND salary<4400;
FROM employee 1 Peter 30 3 000 数据 SQL2: SELECT age FROM employee WHERE id>5 AND salary>3000;
WHERE age>30 2 Mary 33 4 500 SQL3: SELECT id FROM employee WHERE age>33 OR salary<5000;
AND salary<4400; 3 Jack 31 4 300
特征化编码
转化 学习
输入
SQL: SELECT id SQL1: [1, 0.5, 0.3, 0.8, 0.9, 0.1]
P(age>30, salary<4400) 数据联合 FROM employee SQL2: [0, 0.4, 0.6, 0.7, 0.5, 0.2]
分布模型 WHERE age>30 AND salary<4400; SQL3: [0.4, 1, 0.4, 0.5, 0.6, 0.9]
特征化编码 推理 训练
SQL4: [1, 0.3, 0.5, 0.7, 0.6, 0.6] 代价估计模型 代价估计
代价估计
(a) 数据驱动的基数估计模型 (b) 查询驱动的代价估计模型
图 3 数据驱动的基数估计模型和查询驱动的代价估计模型

传统的数据驱动方法仅利用单列信息并且假设表中列与列之间是独立的, 通过这些简单的假设收集信息来建
立粗粒度模型. 随着研究的不断深入, 更多细粒度的数据建模模型逐渐出现, 其中包括基于深度自回归模型的 [18]
方法和基于关系型求和乘积网络 (RSPN) 的方法 [19] 等 (术语对照见附录 A). 这些模型的主要贡献在于更好地考虑
了数据库列与列之间的联合分布以及函数依赖等相关性信息. 不过数据驱动的方法存在的不足之处在于: 一是数
据驱动的模型一般参数量较大, 预测开销高; 二是只能对固定结构的查询 (如 SPJ 查询) 预测出其基数, 难以对包
含大量聚合、子查询和复杂连接方式的查询进行代价预测. 表 1 中对比了一系列数据驱动的基数估计模型.

表 1 数据驱动的基数估计模型对比

方法 数据建模模型 动态更新方式 采样方式 是否支持多表查询
KDE [20] 核密度模型 维护样本 随机采样 －
MOSE [21] 格回归模型 不支持 随机采样 －
QuickSel [22] 均匀混合模型 依据查询更新 基于查询采样 －
DLM [23] 自回归模型 依据查询更新 适应性加权采样 －
Naru [24] 自回归模型 增量或重新训练 渐进式采样 －
NeuroCard [25] 自回归模型 增量或重新训练 渐进式采样 √
FLAT [26] FSPN 增量更新FSPN 无采样 √
ASM [27,28] 自回归模型 增量或重新训练 随机采样 －
Grid-AR [29] 自回归模型 不支持 无采样 √
ICE [30] 多维索引模型 通过索引维护 排序空间采样 －
DeepDB [19] RSPN 增量更新RSPN 无采样 √
LHist [31] 多维直方图 通过更新直方图 无采样 －
Chow-Liu Trees [32] 贝叶斯网络 重新计算CPD 无采样 －

2.2 查询驱动的代价估计模型
为了更深入地考虑查询计划的特征, 研究者们设计了查询驱动的代价估计模型. 对于查询驱动的代价模型而
言, 无论模型输出代价的实际意义是基数还是端到端的时延, 或是其他某种抽象的代价值, 都只需要在训练时更换
其标注值即可, 不影响模型设计. 因此, 后文提到的基数估计模型、代价估计模型等说法在方法上无本质区别.
对查询进行建模需要表示查询计划的树状结构、查询语句中的连接信息和每一个操作符内部的信息, 其建模
难度更高. 但是使用擅长学习复杂特征分布的机器学习模型依然可以达到更好的效果. 因此查询驱动的基数估计
方法因为其模型更加轻便, 且表现不亚于数据驱动的方法而逐渐被学者们深入研究 (图 3(b)). 但是因为查询驱动
的方法 [33,34] 没有对数据进行建模, 所以难以适应数据分布的变化. 同时, 查询驱动的方法在面对未学习过的特征表