本文系东北大学在读博士生方伯阳所著，本篇也是 OceanBase 学术系列稿件第五篇。
「方伯阳：东北大学计算机科学与工程学院在读博士生，主要研究方向是数据存储与管理相关，现在正在 AI4DB 的基数估计领域中努力探索。」
今天分享的论文是 —— Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation. PVLDB, 15(1): 85 - 97, 2022. doi:10.14778/3485450.3485459
希望阅读完本文，你可以对学习型基数有新的收获。
今天分享的这篇论文是李国良教授的团队今年发表的一篇综述，主要内容是从现有的学习型基数估计论文中抽象出 3 种统一工作流程，并对各个种类的基数估计方法中选择效果明显的几种作为代表，从多个方面进行全面的测试。
图1. 不同方法的统一工作流程
统一工作流程
首先是对查询的建模，数据库 D 中，在一个查询 Q 和它对应的基数|Q(D)|直接学习一个映射模型 f(Q)。这一类模型把基数估计问题作为ML中的典型回归问题，并且这类模型只能是有监督的。图 a 是这种模型的统一工作流。首先是模型训练。所有有监督的基数估计方法都需要构造一个训练查询生成器，在模式中采样查询表和列，再从谓词的每一列中采样值。还需要建立一个统一的参数优化器训练模型，以及查询特征提取器，查询编码器和查询模型。具体来说查询特征提取器首先决定哪些特征在一个查询中对于基数估计是有用的，然后查询编码器需要将所有特征编码在单独的向量中，如使用 one-hot 编码，在这之后选用合适的查询模型建模。其次是模型推理，推理阶段的过程与训练阶段的过程是相同的。训练数据是一个三元组的集合，元组包括一个查询，数据集，和真实的基数。
然后是对数据的建模，这一类方法是将基数估计视为密度估计问题，为每个数据点学习联合数据分布。给定一个 SQL 查询，这类方法抽样满足这个查询的数据点，然后把这些被抽样的数据点的概率相加估计基数。通常来说有 2 种方法学习数据分布，分别是有监督的和无监督的。有监督的是使用 SQL 查询和对应的真实基数来训练模型，而无监督的是直接使用数据训练。在训练完模型后，估计一个模型的基数通常通过均匀采样元组，并估计在样本中被选中的元组的累积概率。
b 图显示了有监督数据模型的统一工作流。在模型训练中，也需要和有监督查询方法同样的训练查询生成器，此外有一个统一的查询转换器，对于任意元组可以把查询谓词中命中的输出 1 否则输出 0。在这种方法中，首先通过数据采样模块使用随机采样或基于查询的采样从数据集中抽样，然后基于这些样本建立数据模型。在模型推理阶段，数据抽样模块可以选择一个不同于训练阶段使用的抽样方法，所有被命中样本的累计密度被用于估计选中率，从此可以简单地推导出基数。对于连接查询，相关模块可以根据不同的连接模式联合模型或进行连接分解。
c 图显示了无监督数据模型的统一工作流。在模型训练阶段，这种方法也使用了和有监督数据方法同样的查询转换器，数据抽样模块首先均匀地抽样合理数量的数据集，然后将数据输入数据模型学习数据分布。如果数据集的规模太大无法全放在内存中，还要考虑在线抽样。无监督的模型推理阶段与有监督数据方法的模型推理阶段一样。
实验设计
图2. 高水平学习型基数估计方法的总结
图 2 显示了接下来的实验中使用到的，每一个种类中最优秀的几个学习型基数估计方法(Bayesian[1], NeuroCard[9], Naru[10], DLM[2], DeepDB[4], Feedback-KDE[3], Quicksel[8], LocalXGB[6], MSCN[5], LocalNN[7])，以及每种方法对应的参数优化器，查询转换器，抽样方法，连接分解方法，特征提取器和编码器。
表 1 中打对号的表示被测的每类方法所需要的技术。后续实验所用数据集包含真实数据集和合成数据集，如表 2 所示，前 4 种为真实数据集。前 2 个(Forest, Power)[11] 被广泛用于基数估计的测试，其数据格式全部为整数，这些数据集的使用主要是为了可以将实验集中于性能分析。IMDB[12] 数据集的特点是其高偏斜和高相关性的特征，常用于连接操作的查询优化和开销估计的测试。XueTang[13] 是一个关于在线教育的真实世界 OLTPbenchmark。合成数据集根据表3中的四个方面的参数产生 256 个不同的数据集。使用 q-error 作为性能评估的一项指标。总共进行了 9 组实验，实验一比较了这些学习型方法在真实数据集上的结果；实验二研究了数据集中列的数量会如何影响学习型方法的正确率；实验三测试了独立值的数量如何影响学习型方法的正确率；实验四比较了列之间的不同相关性对学习型方法的正确率的影响；实验五研究了列中数据的偏斜程度对各类方法正确率的影响；实验六讨论了训练集的大小会如何影响有监督方法的正确率；实验七是关于连接抽样的大小如何影响无监督方法的正确率；实验八对比了各个方法在训练过程和推理过程中的效率；实验九的内容是关于各个方法增量数据更新的效率。
实验结果和分析
表4. 在真实数据集上所有方法的正确率对比
表 4 的内容是实验一的测试结果。在单表 Forest 和 Power 中无监督学习的 DeepDB 和 Naru 的效果最好，原因在于这两种方法可以更好的计算数据分布和列的相关性。在需要多表连接的 IMDB 数据集上，MSCN 的性能最佳，原因可能是多表连接可能产生较大尺寸的结果，对于其他方法很难从连接中学习数据分布。在 xuetang 数据集上 Bayesian 和 MSCN 的效果最好，但 Bayesian 比其他方法慢很多。
图3. 在合成数据集上改变列值后的基数错误(#distinct value=1000, correlation=0.6, skew=0.6)
图 3 显示了实验二中各个方法的表现。LocalNN, Naru 和 DeepDB 的性能超过其他方法，原因在于其他方法没能有效建模数据或查询，MSCN 编码操作时对每个谓词而不是值的范围使用 one-hot 向量。但 MSCN，Naru 和 DeepDB 在数据集的列数为 8 的情况下仍然表现很好。
图4. [IMDB]改变列数后的基数估计错误率(median, quantile, max)
图5. [XueTang] 改变列数后的基数估计错误率(median, quantile, max)
图 4 和图 5 分别显示了在 IMDB 和 xuetang 数据集下改变表的列数对错误率影响的测试结果。对所有方法来说，越多列都会导致越高的错误率。在这两种数据集上，有监督方法的 MSCN, LocalXGB 和 LocalNN 在多列数的情况下，列数为 8 或 10 时表现强于无监督方法的 DeepDB 和 NeuroCard，因为 DeepDB 和 NeuroCard 在学习时使用均匀抽样的方法而不是从全部的数据集，样本的稀疏性导致了正确率的降低。MSCN 效果最好的原因在于它使用了一个可以适配所有连接查询的模型，对于改变的连接模式有更好的泛化能力。
图6. [Synthetic]改变唯一值对基数错误率的影响(correlation=0.6, column=4, skew =0.6)
图7. [IMDB] 改变唯一值对基数错误率的影响(median, quantile, max)
实验三的结果如图 6 和图 7 所示。随着值域的增加，基于查询模型的方法正确率会显著下降，原因在于更大的值域使查询空间更离散，训练集无法覆盖。在较大值域的情况下，DeepDB 是表现最好的学习方法，在 5% 错误率的分位点中随着值域的增加错误率还在下降，可能是因为较大的值域更容易划分出独立的分区。图 7 是关于 IMDB 的，可以看出 MSCN 和 NeuroCard 会显著地受到值域范围的影响。
图8. [Synthetic]改变相关性对基数错误率的影响(#distinct value=1000, column=4, skew=0.6)
实验四测试相关性的结果如图 8 所示。DeepDB 在较大相关性的数据集上正确率会下降，因为它会在列之间做独立性假设，Naru 在高相关性的数据集上表现最好，因为它所用的自回归模型可以做到无损分布分解，可以学习数据的相关性，但还是会随着相关性增大而正确率下降。有监督方法的正确率也随着相关性的增加而降低，是因为训练集无法满足所有连接分布。
图9. [Synthetic]改变偏斜程度对基数错误率的影响(#distinct value=1000, column=8, correlation=0.6)
实验五验证的是数据偏斜对各方法正确率的影响，结果如图 9。Naru 和 DeepDB 的中位数和 5% 的错误率都会随着偏斜程度的增加而增加，原因在于 Naru 在进行回归采样时会面临 0 元组的问题，即低频率的值会被丢失，DeepDB 叶节点上的频率表在采样时同样也有这个问题。有监督方法 MSCN 和 LocalXGB 在所有的偏斜率情况下都有相似的错误中位数，因为谓词中大多数的值都会出现在训练集中，而 LocalNN 可以更好的计算低频率的值，所以可以随着偏斜的增加而减低错误率。
图10. [Synthetic] 改变训练集大小后错误率的变化 (correlation=0.6, skew=0.6, #columns=8, #distinct=1000)
实验六验证有监督学习方法的正确率和在合成数据集上的训练查询的数量的关系。在图 10 中可见错误率会随着训练数据的增加而显著减少。对于错误中位数，LocalXGB 在所有尺寸的训练集上都是最大错误率的，因为其使用的模型能力不如神经网络。LocalNN 在 2500 的情况下比 MSCN 的错误率大，但 5000 后具有非常显著的优势，应归因于神经网络结构和对于单表查询的明确的谓词范围特征。在错误率 5% 分位点下也具有同样的趋势。
图11. [IMDB]改变连接抽样对错误率的影响
实验七说明了连接样本的大小显著影响了正确率，图 11 中可以看出如果没有足够的样本数据模型会产生较大的错误，随着样本数量的提升正确率也会提升很多。
图12. [Synthetic] 改变列的数量对训练时间的影响 (correlation=0.6, skew=0.6, #dis tinct=1000)
图13. [IMDB] 改变列的数量对训练时间的影响
图14. [XueTang] 改变列的数量对训练时间的影响
图15. [Synthetic] 改变唯一值的数量对训练时间的影响 (correlation=0.6, skew=0.6, column=4)
实验八着重于不同方法的效率，即训练时间和估计时间。首先是训练时间。图 12，13，14 分别显示了合成数据集，IMDB 和 XueTang 上对于不同列的各方法的性能表现。图 12，13 和 14 有同样的趋势，越多数量的列数需要越多的训练时间，原因在于 DeepDB 需要更多的分区和参数，Naru 的输入包含更多的值和更多的参数需要优化，LocalXGB 和 LocalNN 的输入查询向量更长和更多的参数需要优化，MSCN 需要编码和计算更多的谓词。图 15 则显示了各方法的训练时间和不同尺寸值域上的关系。可以看出 Naru 随着值域的增加需要更多的训练时间，原因在于 Naru 的嵌入尺寸随着值域的增加而增加，对于有监督方法则没有太大的影响，因为它们不在数据分布上直接建模。
图16. [IMDB]不同的列数对估计时延的影响
图17. [XueTang] 不同的列数对估计时延的影响
图18. [Synthetic] 不同的列数对估计时延的影响(correlation=0.6, skew=0.6, distinct=1000)
图19. [Synthetic] 不同数量的唯一值对估计时延的影响(correlation=0.6, skew=0.6, columns=4)
图 16，17 和 18 反应了不同数据集上列数的变化对各方法的估计时间的影响。在图 19 中可以看出 Naru 和 LocalXGB 的估计时间严格地随着列数的增加而增加，因为对于一个查询 Naru 需要计算更多的条件概率，LocalXGB 需要访问更深的回归树。图 16，17 可以看出所有方法都随着列数的增加而增加估计时间，因为查询中涉及到表的数量也在增加，由于表的增加，MSCN 要计算更多的表和样本的位图，DeepDB 要计算更多的分区，NeuroCard 计算更多的条件概率。图 19 显示了不同方法的估计时间在合成数据集上在不同值域下的表现。Naru, DeepDB, 和 LocalXGB 的估计时间都是随着值域的增加而增加的，因为对于每个查询 Naru 的回归采样需要涉及更多的唯一值，DeepDB 在每列上要查询更多的概率， LocalXGB 查询更深的回归树。
表5. 不同更新方式所需时间的对比
实验 9 研究的是不同学习方法在 5%，10% 和 20% 数据量下的模型更新时间。Inc代表的是增量训练模式，没有的则代表重训练。从表 5 中可以看出，在 5% 这种小范围更新，相比重训练的时间效率高出 30%-1500%。在 IMDB 数据集下更新较大的数据量，增量的 DeepDB 反而会花费更多时间，这主要和它的更新方式有关。通常来说，基于查询的方法会比基于数据的方法花费更多时间，是因为查询标签的升级十分花费时间。
最后这篇论文总结出了关于学习的基数估计方法有关的 8 条发现：
(1)数据模型 DeepDB 和 Naru 对于单表来说是最有效率的方法；
(2)对于复数表，查询模型 MSCN 是最有效率的方法；
(3)查询模型比数据模型更高效；
(4)数据模型比查询模型更稳定；
(5)训练用的查询对于查询模型非常重要；
(6)采样方式对查询模型非常重要；
(7)基于神经网络的估计器比基于统计的估计器有更高的正确率；
(8)基于统计的估计器的效率最高。
*参考文献：
[1]Getoor, L., Taskar, B., and Koller, D. Selectivity estimation using probabilistic models. In Proceedings of the 2001 ACM SIGMOD international conference on Management of data, Santa Barbara, CA, USA, May 21-24, 2001 (2001), S. Mehrotra and T. K. Sellis, Eds., ACM, pp. 461–472.
[2]Hasan, S., Thirumuruganathan, S., Augustine, J., Koudas, N., and Das, G. Deep learning models for selectivity estimation of multi-attribute queries. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020 (2020), D. Maier, R. Pottinger, A. Doan, W. Tan, A. Alawini, and H. Q. Ngo, Eds., ACM, pp. 1035–1050.
[3]Heimel, M., Kiefer, M., and Markl, V. Self-tuning, gpu-accelerated kernel density models for multidimensional selectivity estimation. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015 (2015), T. K. Sellis, S. B. Davidson, and Z. G. Ives, Eds., ACM, pp. 1477–1492.
[4]Hilprecht, B., Schmidt, A., Kulessa, M., Molina, A., Kersting, K., and Binnig, C. Deepdb: Learn from data, not from queries! Proc. VLDB Endow. 13, 7 (2020), 992–1005.
[5]Kipf, A., Kipf, T., Radke, B., Leis, V., Boncz, P. A., and Kemper, A. 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 (2019), www.cidrdb.org.
[6]Tzoumas, K., Deshpande, A., and Jensen, C. S. Lightweight graphical models for selectivity estimation without independence assumptions. Proc. VLDB Endow. 4, 11 (2011), 852–863.
[7]Ortiz, J., Balazinska, M., Gehrke, J., and Keerthi, S. S. An empirical analysis of deep learning for cardinality estimation. CoRR abs/1905.06425 (2019).
[8]Park, Y., Zhong, S., and Mozafari, B. Quicksel: Quick selectivity learning with mixture models. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020 (2020), D. Maier, R. Pottinger, A. Doan, W. Tan, A. Alawini, and H. Q. Ngo, Eds., ACM, pp. 1017–1033.
[9]Yang, Z., Kamsetty, A., Luan, S., Liang, E., Duan, Y., Chen, P., and Stoica, I. Neurocard: One cardinality estimator for all tables. Proc. VLDB Endow. 14, 1 (2020), 61–73.
[10]Yang, Z., Liang, E., Kamsetty, A., Wu, C., Duan, Y., Chen, P., Abbeel, P., Hellerstein, J. M., Krishnan, S., and Stoica, I. Deep unsupervised cardinality estimation. Proc. VLDB Endow. 13, 3 (2019), 279–292.
[11]Dua, D., and Graff, C. UCI machine learning repository, 2017.
[12]IMDb.com. https://www.imdb.com/, 2019.
[13]XueTang, T. https://www.xuetangx.com/global, 2019.
————————————————————————————————————————————
社区版官网论坛
社区版项目网站提 Issue
欢迎持续关注 OceanBase 技术社区，我们将不断输出技术干货内容，与千万技术人共同成长！！！
搜索🔍钉钉群（33254054），或扫描下方二维码，还可进入 OceanBase 技术答疑群，有任何技术问题在里面都能找到答案哦～
