论文导读 | 机器学习在数据库基数估计中的应用

  基数估计的问题定义和意义

给定一个数据表T，以及查询Q，基数估计 (cardinality estimation) 便是需要估计查询结果的大小。等价地，基数估计也可以表达为对查询选择性 (selectivity)的估计，这样最终的查询基数可通过选择性和整表大小的乘积得到。

有时候我们也需要对不止一个表的复杂查询（包含多表连接（join）、范围查询（range query）等）估计基数，这些都是数据库基数估计的研究内容。

基数估计的作用主要可概括成如下两个方面：

 （1）基数估计是数据库查询优化的重要一环。由于子查询的基数代表了中间结果的大小，因此现有的大多数基于代价的查询优化技术对子查询计划代价的估计强烈依赖对子查询基数的估计。一个优秀的基数估计模型能帮助优化器更好地选择合适的执行计划。

 （2）基数估计可以帮助回答一些只需要知道结果数量的查询。例如某个用户可能想知道全中国有多少大学生学习计算机专业，这个查询只关心结果的数目而不需要知道每条结果的具体值。对这样的查询我们可以通过基数估计的方法快速返回结果大小的近似值。

目前方法的分类

基数估计是一个重要且较为困难的问题，几十年来一直有研究者尝试用各种方法和技巧提升估计的准确性和稳健性，现有的方法可以分为如下几类：

总体上可以分类传统型方法和基于机器学习的方法。下面会选取其中具有代表性的几个工作简要介绍。

传统型基数估计方法

传统型基数估计方法大体上可以分为基于概要(synopsis-based)和采样(sampling)的两大类方法。

基于概要的基数估计方法会预先收集数据库的一些统计信息，并基于独立性等简单假设，能够方便快速地求解查询基数。

例如基于直方图(histogram)的方法，其对数据表中每一列总结成一张等宽(equal width)或等深(equal depth)的直方图，最后根据查询条件，基于列与列之间相互独立的假设，估计出查询结果的大小。当然有时这样的独立性假设效果不好，便可根据多维直方图(multi-dimensional histogram)的方法求解。

数据画像(sketching)也属于基于概要的基数估计方法，其使用bitmap或哈希的方法，估计数据库中互不相同的元素个数，比较适合流式数据的场景。更新的一类数据画像的方法如loglog、hyperloglog等，更加注重节约内存和提升估计的稳健性。

基于采样的方法会从原始数据表中随机抽取一定比例或者一定数量的元组，最终根据在采样集上执行查询后的结果大小除以相应的缩放比例便可得到查询在原数据库的基数估计。基于采样的方法在采样策略较好、能反映大部分数据分布的情况下效果较好，但也很容易由于采样的随机性无法产生采样集上匹配结果的情况，便有研究者提出了一种基于索引的采样方法(index-based sampling) [1]，其在多表连接时，会根据查询的连接条件选择要采样的范围，能减少采样出现零结果的情况，具体图示如下：

查询驱动的学习型基数估计方法

由于基数估计可以视为“查询”到”基数值”的回归问题(当数据库没有更新时)，故我们可以将监督学习的技巧迁移到本问题上，直接学习查询到基数的对应关系。一般的查询驱动方法的工作流程如下所示：

其难点主要在于训练数据的获取和查询语句的表示两方面。

通常而言，当数据库给定时，我们可以假设查询框架(schema)是已知的（例如，某两个表会根据哪些列做连接等），由此我们可以随机产生一些查询语句，将这些语句真实运行之后，我们便得到了这些查询的真实基数，这就构成了训练模型需要的训练数据。当然也可以根据数据库的查询日志直接获取查询。需要注意的是，训练数据一定要有代表性，否则模型不能学习到工作环境中常见的查询模式到基数的对应，会影响到预测的准确性。

查询语句的表示主要由查询表、谓词条件、连接条件等决定，更复杂的情况包括含正则表示式之类的“like”查询。

工作 [2] 应用回归模型估计查询基数。其将用户的输入总结成一些语意相关的类，称为 templates，对于每条 template，都有一些可以调整的参数作为查询语句的表示，不同的参数构成了不同的查询。本篇工作的模型较为简单，主要测试了线性回归、模型树和局部加权回归三种模型。

2019年，在工作 [3] 中，研究者提出了多集合卷积网络(multi-set convolutional network, MSCN)。其将查询表示为三元组的形式，其中元素分别代表了查询表、连接条件和谓词选择，都是有对应结构的集合。该模型综合了表、连接和谓词条件的信息后，再通过若干层网络，得到最后的基数估计。需要注意的是，随机生成的训练查询最多只包含两个连接条件，而研究者希望模型能通过学习较少数量的模式自动泛化到多连接。其整体架构如下所示：

工作 [4] 中，作者将基数估计和查询计划的代价估计结合在同一个端到端的学习型估计模型里。其依赖于数据库系统的优化器对于输入查询产生一个物理计划，训练数据则由(查询计划，准确基数，准确计划代价)三元组的形式构成。由于查询计划为树状结构，故其模型使用树形LSTM。简而言之，计划树中的每个节点都接收来自子节点的信息，并和自己的信息综合，最终将查询数根节点的输出送入预测基数和预测代价的两个模型得到想要的估计。本篇工作中还提出了根据谓词条件的联系（AND、OR等），分别使用MIN、MAX池化，具体细节可以参照其论文。下图展示了其模型的工作流程：

数据驱动的学习型基数估计方法

与查询驱动类的方法不同，数据驱动的基数估计方法为无监督的一类方法，直接从数据表中学习数据的分布，因此训练较为简单。

在工作 [5] 中，作者使用核密度估计(kernel density estimation, KDE)的方法估计查询基数。其想法为在数据表中随机抽取若干元组，这样查询点和采样元组越靠近，那该查询有结果的可能性就会较大。作者使用了高斯核，并用可学习的参数控制概率密度的分散程度。对于数据库更新场景，作者使用蓄水池抽样(reservoir sampling)应对数据插入；通过监测去除某个采样元组对估计效果的影响应对数据删除（即如果删去某个元组能提升估计效果，则将其删去）。由于计算只需要对每个采样元组计算概率再相加，故可以通过GPU加速计算。作者也在之后的研究中，将核密度估计的方法拓展到多表连接的基数估计 [6]。下图展示了核密度估计的主要思想：

还有一类使用自回归模型估计基数的方法。在工作[7]中，作者提出了Naru模型，在训练过程中还融合了采样和Mask技巧，能够提升模型的准确性。作者其后也将该方法拓展到多表连接的情形 [8]。

另外一类数据驱动的方法使用了SPN(sum product network)。主要思想为通过对数据表做横向划分（例如使用KMeans等聚类方法），使元组各列在分割后的数据上近似独立，这样便可通过在每一列上构建直方图或线性回归模型估计基数。DeepDB [9] 是一个使用SPN的基数估计方法，近年来也有对SPN的改进，如FLAT [10]，其将数据表的各类分为强相关和弱相关两类，再进一步使用SPN方法划分数据表。下图展示了DeepDB是如何计算“年龄小于30岁的欧洲顾客人数”的：

目前的困难和未来研究方向

第一点，尽管目前的方法能比传统方法更准确，但也耗费了大量时间训练模型，如何在准确率和效率之间取舍是应用这些方法的数据库使用者需要考虑的问题。

第二点，大部分的模型都很难适应更新环境。当有大量数据插入或删除是，这些模型很难追踪这些改动，因此需要重新训练，这在OLTP环境中是需要改进的。

第三点，这些模型在多表连接的场景下估计效果仍然很差。多表连接时，不同表之间的依赖性难以捕捉，给基数估计带来了较大的困难。这在2021年实验论文[11]中也有介绍。

最后，推荐感兴趣的读者阅读实验论文[11]，其比较了多个学习型方法在各个场景下的性能和效率，对基数估计的研究有一定指导价值。

参考文献

[1] Viktor Leis, Bernhard Radke, Andrey Gubichev, Alfons Kemper, and Thomas Neumann. 2017. Cardinality Estimation Done Right: Index-Based Join Sampling. In CIDR.

[2] Tanu Malik, Randal C Burns, and Nitesh V Chawla. 2007. A Black-Box Approach to Query Cardinality Estimation.. In CIDR. Citeseer, 56–67.

[3] Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In 9th Biennial Conference on Innovative Data Systems Research, CIDR 2019, Asilomar, CA, USA, January 13-16, 2019, Online Proceedings. www.cidrdb.org.

[4] Ji Sun and Guoliang Li. 2019. An end-to-end learning-based cost estimator. Proceedings of the VLDB Endowment 13, 3 (2019), 307–319.

[5] Max Heimel, Martin Kiefer, and Volker Markl. 2015. Self-tuning, GPU-accelerated kernel density models for multidimensional selectivity estimation. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 1477–1492.

[6] Martin Kiefer, Max Heimel, Sebastian Breß, and Volker Markl. 2017. Estimating join selectivities using bandwidth-optimized kernel density models. Proceedings of the VLDB Endowment 10, 13 (2017), 2085–2096

[7] Zongheng Yang, Eric Liang, Amog Kamsetty, Chenggang Wu, Yan Duan, Xi Chen, Pieter Abbeel, Joseph M Hellerstein, Sanjay Krishnan, and Ion Stoica. 2019. Deep unsupervised cardinality estimation. Proceedings of the VLDB Endowment 13, 3 (2019), 279–292.

[8] Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2020. NeuroCard: one cardinality estimator for all tables. Proceedings of the VLDB Endowment 14, 1 (2020), 61–73.

[9] Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, and Carsten Binnig. 2020. DeepDB: learn from data, not from queries! Proceedings of the VLDB Endowment 13, 7 (2020), 992–1005.

[10] Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou, and Bin Cui. 2021. FLAT: fast, lightweight and accurate method for cardinality estimation. Proceedings of the VLDB Endowment 14, 9 (2021), 1489–1502.

[11] Wang, Xiaoying, et al. "Are we ready for learned cardinality estimation?." Proceedings of the VLDB Endowment 14.9 (2021): 1640-1654.