当前位置：首页 > news >正文

论文导读 | 数据库系统中基于机器学习的基数估计方法

news 来源：原创 2025/6/18 6:30:50

背景

基数估计任务是在一个查询执行之前预测其基数，基于代价的查询优化器（Cost Based Optimizer）将枚举所有可能的执行计划，并利用估计的基数选出期望执行代价最小的计划，从而完成查询优化的任务。

然而，传统的基数估计方法，例如PostgreSQL基于直方图（Histogram）的方法，往往采用简单的独立性假设、均匀假设，用有限的统计信息来预测查询的基数，导致了较大的基数估计误差。事实上，现实中的数据是复杂的、富有关联的，传统的基数估计方法往往不能刻画数据的复杂分布，产生巨大的基数估计误差从而诱发大量的次优计划甚至灾难性计划。

为此，研究者们近年来将目光投放于基于机器学习的查询优化方法，利用机器学习的基数，来完成基数估计这个传统方法难以很好解决的问题。现有的基于机器学习的方法主要可以分为如下两大类：

**Query-driven：即查询驱动。**直接学习查询特征到其基数的映射，i.e. $ f_\Theta(Q) \to \text{Card} $。通常是一个回归模型，但需要大量的查询及其真实基数作为训练集$ { <Q, \text{Card}>}$。
**Data-driven：即数据驱动。**与查询驱动的思想不同，数据驱动并不直接学习查询的基数，而是学习底层数据的分布，并用这个分布来回答查询的基数。例如，一个具有属性 $\{A_1, A_2, \cdots, A_n\}$ 的表 $T$ ，可以看作是定义在 $\Pi_{i=1}^n dom(A_i)$ 上的多元概率分布 $P_T(A_1, A_2, \cdots, A_n)$ ，用机器学习模型来拟合此分布，得到 $\hat{P}_T(A_1, A_2, \cdots, A_n)$ 。之后，原表 $T$ 上的带有选择谓词的查询，可以看作在 $\hat{P}_T$ 上的积分来近似估计基数。

讨论的范围：当然了，目前主要的基数估计研究主要关注于如下形式的Select-Project-Join查询。多表连接最基本的查询单元、也是查询优化中最为困难的部分之一。

SELECT COUNT(*)
FROM T1, T2, ..., Tm
WHERE Join condition AND Filtering predicates

相关文献整理如下。下面，将从中选部分代表性的工作介绍。

Category	Estimator	Model
Query	MSCN[1]	Multi-Set Convolutional Network
Query	Robust-MSCN[2]	Multi-Set Convolutional Network + Query Masking + Join Bitmap
Query	JGMP[3]	Join Graph Message Passing Neural Network
Query	ALECE[4]	Multi-head Attention
Data	DeepDB[5]	Sum Product Network
Data	FLAT[6]	Factorized Sum Product Network
Data	NeuroCard[7]	Deep Autoregressive Model
Data	BayesCard[8]	Bayesian Network
Data	FactorJoin[9]	Bayesian Network + Join Histogram
Data	ASM[10]	Deep Autoregressive Model + Join Histogram

查询驱动的方法

MSCN [1, CIDR’ 19]

这是较早的一篇工作，用查询的特征来预测基数，是查询驱动的代表性工作。具体来说，该方法将一个连接查询 $Q$ 表示为一个三元组<T_Q, J_Q, F_Q>，分别表示查询 $Q$ 涉及的表的集合、连接条件的集合、过滤谓词的集合。其中，表、连接的编码都可以通过one-hot完成，谓词的用 <col,op,val>分别编码。同时，为了增强模型的能力，MSCN还引入了bitmap编码。即，在每个表上采样若干行，用过滤条件进行过滤，将保留（1）过滤（0）信息编码到bitmap作为输入特征。

ALECE[4, VLDB’ 23]

该方法的着眼点是动态场景，即底层数据会被更新，因此模型必须有感知底层数据变化的能力。为此，该方法将底层数据的直方图作为特征交给模型，并且直方图会随着底层数据的更新而更新，使得模型具备了动态场景下完成较好的基数估计的可能性。

数据驱动的方法

DeepDB [5, VLDB’ 20]

DeepDB使用了Sum-Product Networks来学习数据的联合分布 $P(A_1, A_2, \cdots, A_n)$ 。该方法训练得到的数据结构如图©所示。其中，Sum node（+）将表横向切分，这部分是信息无损的；Product node假设表的某部分列是相互独立的，然后纵向切分，这部分应用了独立性假设。最后，叶子结点是一列，用直方图来刻画该列的分布。有了这个训练好的数据结构，关于求解概率、条件期望等问题都可以在这个Sum-Product完成，从而能够很好的支持单表带选择谓词的基数估计。关于连接查询，DeepDB的方法是预计算一些表（文中最多3个表）的全外连接，设计更多的表的查询应用独立性假设完成，技术细节请参考原文。

NeuroCard [7, VLDB’ 20]

使用了深度自回归模型来建模数据分布，该方法分为两部分：

如何建模表的分布？即上述的自回归建模，这部分工作在作者的前序工作[12, VLDB’ 19]中完成。
如何处理连接查询？这是本文的任务。方法的思想是直接建模所有表的全外连接的分布。注意到全外连接包含了所有表的信息、所有可能的连接的信息。只不过有一些行因为外连接在结果中多次重复，这只要引入一些额外的列记录重复度（fanout）即可，技术细节参考原文。

下面重点介绍如何建模表的分布、如何从自回归模型中估计概率密度（即过滤谓词的选择度）。

训练

和NLP中的语言模型类似，将"Tuple"视为"sentence"，将"value"视为"token"，用交叉熵损失训练。

概率密度估计

训练好后，单点的概率密度很容易估计，直接将所有条件概率乘起来就可以。区间密度的估计，文中介绍了渐进式采样高效完成。

FactorJoin [9, SIGMOD’ 23]

连接查询的估计对之前的Data-driven的方法仍然非常具有挑战性。先前的方法依赖于预计算一些表的外连接，用模型来建模这些外连接，训练成本较高，并且如果新来的连接查询并不完全被已有模型包含，需要用独立性假设将这个查询拆开，也不尽人意。

FactorJoin提出了一个全新的基数估计框架：只需要用模型建模单表的分布，连接查询借助连接键的直方图来回答。下面这个例子介绍了FactorJoin的想法。要估计 $A$ 、 $B$ 两个表的连接查询，可以先执行两个表上各自的过滤条件，得到过滤后的表为 $A ∣ Q (A)$ 、 $B ∣ Q (B)$ 。之后，统计过滤后的表的连接键在表中出现的次数（下图中的Value count），将相同键的计数对应相乘再求和即可：
$\sum_{\substack{v \in dom(A.id)}}P_A(A.id=v|Q(A))*|Q(A)|*P_B(B.Aid=v|Q(B))*|Q(B)|$
在这里插入图片描述

注意到，单表上的条件概率是能够用单表的模型回答的。但是，最外面的求和号遍历所有可能的连接键，其复杂度不亚于做连接了，所以文中用Join-key Histogram，将连接键聚集到若干bucket里面，牺牲了准确性，但使得外层求和号变成了对bucket的数目求和，从而能够进行求解。

总结一句，FactorJoin实现了仅对单表建模、并利用连接键的直方图来完成对多表连接查询的基数估计。这种想法训练快、模型轻量，同时精度也不错，非常practical。后续工作[10, SIGMOD’ 24]是在这个框架下的完善，[11, SIGMOD’ 24]将这个方法应用到了字节跳动的数据仓库中的基数估计。

总结

A good cardinality estimator should be effective, efficient, and practical for deployment

Query-driven

✅ Lightweight, fast inference speed

❌ Requires a lot of training data, long data collection process, not practical

❌ Out-of-distribution problem, doesn’t generalize well

🤔 The potential of pretraining? [13, 14]

Data-driven

✅ Usually more accurate than query driven methods (at least according to recent works)

✅ Much less setup time (no need to collect queries and cardinalities)

✅ Generalizes well, no out-of-distribution problem

😞 Challenging to capture cross-join correlation, trade-off between accuracy, training time, time/space efficiency

参考文献

[1] Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, Alfons Kemper: Learned Cardinalities: Estimating Correlated Joins with Deep Learning. CIDR 2019.

[2] Parimarjan Negi, Ziniu Wu, Andreas Kipf, Nesime Tatbul, Ryan Marcus, Sam Madden, Tim Kraska, Mohammad Alizadeh. Robust Query Driven Cardinality Estimation under Changing Workloads. VLDB 2023.

[3] Silvan Reiner, Michael Grossniklaus: Sample-Efficient Cardinality Estimation Using Geometric Deep Learning. VLDB 2023.

[4] Pengfei Li, Wenqing Wei, Rong Zhu, Bolin Ding, Jingren Zhou, Hua Lu: ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads. VLDB 2023.

[5] Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, Carsten Binnig: DeepDB: Learn from Data, not from Queries! VLDB 2020.

[6] Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Bin Cui: FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation.

[7] Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, Ion Stoica: NeuroCard: One Cardinality Estimator for All Tables. VLDB 2020.

[8] Ziniu Wu, Amir Shaikhha, Rong Zhu, Kai Zeng, Yuxing Han, Jingren Zhou: BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation. ArXiv 2020.

[9] Ziniu Wu, Parimarjan Negi, Mohammad Alizadeh, Tim Kraska, Samuel Madden: FactorJoin: A New Cardinality Estimation Framework for Join Queries. SIGMOD 2023.

[10] Kyoungmin Kim, Sangoh Lee, Injung Kim, Wook-Shin Han: ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation. SIGMOD 2024.

[11] Yuxing Han, Haoyu Wang, Lixiang Chen, Yifeng Dong, Xing Chen, Benquan Yu, Chengcheng Yang, and Weining Qian. ByteCard: Enhancing ByteDance’s Data Warehouse with Learned Cardinality Estimation. SIGMOD 2024.

[12] Zongheng Yang, Eric Liang, Amog Kamsetty, Chenggang Wu, Yan Duan, Xi Chen, Pieter Abbeel, Joseph M. Hellerstein, Sanjay Krishnan, Ion Stoica. Deep Unsupervised Cardinality Estimation. VLDB 2019.

[13] CardBench: A Benchmark for Learned Cardinality Estimation in Relational Databases. Arixv 2024.

[14] PRICE: A Pretrained Model for Cross-Database Cardinality Estimation. Arxiv 2024.

背景