共计 8307 个字符，预计需要花费 21 分钟才能阅读完成。
欢送拜访 OceanBase 官网获取更多信息：https://www.oceanbase.com/
本文来自 OceanBase 社区分享，仅限交换探讨。原作者巩李成，东北大学计算机科学与工程学院在读硕士生，课题方向为数据库查问优化，致力于利用 AI 技术改良传统基数预计器，令数据库抉择最优查问打算。
原文：《FactorJoin: A New Cardinality Estimation Framework for Join Queries》，发表于 SIGMOD 2023。
基数预计是查问优化中最为重要和最具挑战性的问题。传统办法和学习型办法在预计多表连贯查问的基数时都没有令人满意的体现。它们或依赖于简略的假如导致有效的预计；或构建过大的模型来了解多表的联结散布，从而使得模型布局工夫较长并不足泛化能力。
本文提出了一个新的多表连贯基数预计办法——FactorJoin。FactorJoin 将传统的连贯直方图 [1] 与学习型办法相结合以捕捉表间的关联性进而进行基数预计。具体地说，离线训练时，FactorJoin 先建设单表预计模型以学习单表的散布。当解决连贯查问时，FactorJoin 首先根据已学习到的散布将查问建模为因子图 [2]（Factor Graph），而后应用变量打消[3]（Variable Elimination，VE）算法进行推理。因只需单表的统计信息即可预计出多表连贯的基数，FactorJoin 在查问的端到端解决工夫优于其它学习型办法[4,5,6] 的状况下，模型大小、训练及更新工夫比它们低了一至两个量级。
多表基数预计办法
给定 A,B 两表上的查问 Q：
SELECT * FROM A, B WHERE Id1 = Id2 AND A1>0 AND B1>0图 1 两表连贯示例
别离介绍上面四种预计办法。
Selinger 模型
Selinger 模型 [7] 在预计时作了两点假如：属性独立假如以及连贯键均匀分布假如。首先根据属性独立假如计算两属性的联结概率密度 PA(A1 > 0) PB(B1 > 0)；而后应用连贯键均匀分布假如预计两表连贯的大小：|A ⋈ B| = |A| |B| / max{num uniques in A.Id1, num uniques in B.Id2}。
图 2 Selinger 模型预计示例
图 2 给出了 Selinger 模型以图 1 所示数据进行预计的过程：
PA(A1 > 0) PB(B1 > 0) = 1/2 1/2，|A ⋈ B| = 8 * 8 / 3 = 21
|Q| = PA(A1 > 0) PB(B1 > 0) |A ⋈ B|
= 1/2 1/2 8 * 8 / 3
= 5
该查问的实在基数为 4 * 4 = 16，能够看到 Selinger 模型因其所作的两点假如导致预计后果存在较大的误差。
连贯直方图
连贯直方图在预计时仍旧采纳了属性独立假如与连贯键均匀分布假如。与 Selinger 模型不同的是，在预计两表连贯大小的时候对连贯键进行了划分。如图 3 所示，对应连贯键中的雷同值被划分到具备雷同下标的桶中（如值 a 被划分到桶 1，值 b 和 c 被划分到桶 2）。在计算两表连贯大小时，间接将该连贯键上所有桶中的对应元素的连贯数目加和即可。
图 3 连贯直方图预计示例
如图 2 所示，|A⋈B| = 4 4 / 1 + 4 4 / 2 = 24，
|Q| = 1/2 1/2 24 = 6
能够看到，连贯直方图的预计误差同样很大，但因其在预计两表连贯大小时在连贯键上划分了一些桶，因此不须要遍历所有元素，进而使得预计工夫大大减少。
学习型数据驱动的办法
学习型基数预计办法根据应用的数据类型可分为两类：查问驱动的办法与数据驱动的办法。其中，查问驱动的办法在解决多表基数预计时仅将连贯类型作为特色之一，并同其它特色一起送入网络中进行训练以结构出从查问到基数的映射函数。这种办法并未对多表基数预计进行非凡解决，因而不多赘述。
数据驱动的办法在解决多表基数预计时大多会学习多表的联结散布。如 DeepDB、FLAT 等会将关联性较强的两表通过全外连贯的形式进行联合并学习全外连贯表的散布状况。而后根据学习到的联结散布进行抉择度的预计。
图 4 数据驱动的办法示意图
图 4 给出了数据驱动的办法的示例，表 A 和表 B 通过连贯键 Id1 与 Id2 连贯后被送入模型以学习其散布。最初失去的后果与真值极为靠近。
本文提出的办法
因数据驱动的办法须学习多表的联结散布，所以模型较大、训练及更新工夫较长，所以作者想在仅晓得单表统计信息的状况下预计出多表查问的基数。因而，作者采纳了连贯直方图的思维，即别离统计出参加连贯的两表满足对应谓词的元组散布状况，并在连贯键上进行分桶，而后将所有桶中对应值的连贯数目加和即可。该办法的预计过程如图 5 所示。为了提高效率，作者将其与概率图模型相结合，具体情况如后文所述。
图 5 本文办法的示意图
多表连贯基数预计的新框架
两表连贯基数预计示例
如图 6 所示，查问 Q 须要对表 A 和表 B 在连贯键 A.id 与 B.Aid 上进行连贯。连贯直方图这类办法在预计两表的基数时会别离筛选出合乎两表谓词的元组 A |Q(A)与 B |Q(B)，而后在筛选出的元组上进行相应的连贯操作。可算出最终的连贯后果为：8 6 + 4 5 + 3 * 5 = 83。
图 6 两表预计示意图
这一步骤示意成公式则如公式（1）所示。其中，PA(A.id = v | Q(A))示意值 v 在表 A 中满足谓词 Q(A)的元组中的散布状况。
多表预计示例
给定查问 Q2：
SELECT * FROM A, B, C, D
WHERE A.id = B.Aid AND A.id2 = C.Aid2
AND C.id = B.Cid AND C.id = D.Cid
AND Q2(A) AND Q2(B) AND Q2(C) AND Q2(D)如图 7 所示，在解决查问 Q2 时，首先将查问波及到的表示意成图 6（ii）的模式。其中，矩形暗影局部示意查问波及到的表，椭圆代表波及到的连贯键，实线示意对应的连贯关系。同种色彩实现连接起来的各连贯键被称为等价键簇，后文在优化算法时会用到这个概念。
图 7 四表基数预计示意图
同两表预计的思维个别，一一对每个等价键簇中的值在各表中作等值连贯。该计算过程示意成公式则如公式 2 所示。其工夫复杂度为 O(n3)。为了升高复杂度，作者将查问示意成图 6（iii）所示的因子图。其中，变量节点 V1 示意等价键簇 1；因子节点示意表，该节点中存有表中元素的散布信息 PA(V1, V2 | Q2(A)) * |Q2(A)|；实线示意表中该查问波及到该表在对应连贯键上的连贯操作。
因子图的推理是概率图模型中通过充沛钻研的问题，罕用的推理方法有变量打消和信念流传 8 这两种办法。本文采纳了变量打消这种办法，此时的工夫复杂度为 O(N * |D|max(|JK|)))，其中，N 示意等价键簇的数量，|D| 示意所有连贯键中最大的域的长度，max(|JK|)示意单表领有的最大连贯键的数量。在图 7 中，max(|JK|)的值为 2。在事实世界的数据库中，这种复杂度还是不可承受的，因为 |D| 可能达到百万级别，而 max(|JK|)可能比 4 还要大，因而是不可承受的。为了升高复杂度，作者对这两个点别离进行了优化，具体过程如下文所述。
整体的工作流程
图 8 FactorJoin 的工作流
整体的工作流程如图 8 所示。在离线训练时，FactorJoin 先别离在各表上建设单表预计模型并根据数据模型对所有连贯键进行分桶并统计相应信息。在线推理时，FactorJoin 先将查问示意成因子图，而后别离在单表上进行预计，最初应用变量打消算法对各表的连贯后果进行预计。值得一提的是，FactorJoin 预计的是查问的基数下限，而非具体的基数值。这是作者降本提效的一种伎俩，详情如下文所述。
晋升效率的两种办法
上文提到，应用变量打消算法对因子图进行推理的复杂度为 O(N * |D|max(|JK|))。其中影响较大的有最大的属性域的长度 |D| 以及单表领有的最多的连贯键的数量 max(|JK|)。作者从这两个方面动手，别离进行了优化，使复杂度进一步升高。
概率下限算法
在以连贯直方图预计多表连贯的大小时，须要对连贯键进行遍历以将两表连贯键上对应的值进行连贯。在事实的数据库中，连贯键的域很大，能达到百万级别。为了晋升效率，作者借鉴了基于概率下限办法的思维，即预计出基数的下限而非具体的值。
图 9 应用分桶策略的量表预计示例
图 9 给出了两表预计的例子。如图，别离在表 A、表 B 中筛选出合乎相应谓词的元组后，统计连贯键上的值散布状况并在连贯键上划分桶，使得两表连贯键上雷同的值落在同一个下标的桶中。而后别离预计每个桶的连贯下限，即先找出桶中的最频繁值（most frequent value, MFV）及桶蕴含的元组数目。如在表 A 的桶 1 中，值 a 呈现的次数最多，为 8 次；桶 2 中 MFV 呈现的次数为 6 次，则两桶中同一个值作等值连贯最多产生 48 个连贯后果。表 A 的桶 1 中总元组数目为 16，则其桶 1 中最多蕴含两个 MFV；对应地，表 B 的桶 1 中最多蕴含 4 个 MFV。因而能够预计出两桶对应值作等值连贯的数目下限为：min(2, 4) 8 6 = 96。比照真值为 8 6 + 4 5 + 3 * 5 = 83。示意成公式则如公式 3 所示。
在连贯键上进行分桶时，须要思考两个问题：划分多少个桶以及把哪些值放入同一个桶内。作者别离对这两个问题进行了解决。
基于工作流决定桶的数量 k
桶的数量 k 对 FactorJoin 的性能有显著影响：较少的桶将连贯键域中更多不同的值聚合到每一个桶，因而模型的准确性较低但效率更高。作者提出了一种基于工作流分桶的办法，在给定桶的数量下限 K = ∑ki 的状况下，根据等价键簇在工作流中呈现的次数多少，对每个不同的等价键簇调配不同的桶数量；呈现的次数越多，则调配的桶的数目越多。
分桶策略
传统的分桶策略有等宽划分和等高划分，但这两种办法在极其状况下会呈现较大的误差，且等价键簇中所有的连贯键共用一个分桶后果，所以为了升高每个连贯键上桶的方差，作者提出了一种贪心的分桶策略（greedy binning selection algorithm , GBSA）。
GBSA 算法如算法 2 所述。GBSA 首先在每个等价键簇中生成次优的分桶后果(line 1)，而后对每个等价键簇执行算法 2 所示的过程(line 2-14)。以等价键簇中连贯键域的长度递加的程序进行排序(line 3)。用一半数量的桶升高第一个连贯键的方差(line 4)。在单属性上取得具备最小方差的划分后果时，可将属性排序后以等深策略进行划分。而后，GBSA 将在以后连贯键上的分桶后果一一利用到它前面的连贯键中，计算各个桶的方差并以递加的形式排序(line 6-9)，用残余的可调配桶的数目的一半数量优化以后的桶方差，行将相应的桶一分为二(line 10-12)。
捕捉属性间的依赖关系
在应用因子图计算多表的基数时，工夫复杂度为 O(N * |D|max(|JK|))，|D| 为所有连贯键中最长的域的长度，已通过概率下限算法进行优化；指数项 max(|JK|)示意单表领有的最多连贯键的数量，在 IMDB 数据集中，该值能大到 4，所以作者对这一项进行优化。
因为因子图须要晓得单表中连贯键的联结散布，单表的连贯键数量就决定着该局部推理的复杂度。如对领有六个属性的表 A{id1, id2, id3, id4, attr1, attr2}（idi 示意各个连贯键），因子图须要预计 PA(id1, id2, id3, id4 | Q(A))。即便曾经采纳概率下限算法，该局部时空复杂度也达到了 k2。然而，可用贝叶斯网络构建各连贯键的依赖关系并应用变量打消算法进行推理。此时，仅需进行如下模式的计算：
PA(id1 | Q(A)) PA(id2 | Q(A)) PA(id3 | id1) * PA(id4 | id3)
这种模式效率更高因为它最多只波及二维散布上的乘积。时空复杂度升高为了 O(N * k2)。
子打算预计后果的重用
因为优化器在抉择查问打算时，可能会预计多达上千个打算的代价。但这些打算可能存在一些雷同的子打算，所以为了进一步晋升效率，作者将各子打算的后果保留用作其余部分的预计。
试验
数据集
Baselines
PostgresSQL[10]：应用基于直方图的办法
JoinHist[1]：传统的基于连贯直方图的办法
WJSample[11]：在多表中应用基于随机游走的 wander join 办法生成样本
MSCN[4]、BayesCard[9]、DeepDB[5]、FLAT[6]：最具代表性的学习型办法
PessEst[12]：SOTA 的基于下限的办法，利用随机哈希和数据画像来使下限尽量靠近真值
U-Block[13]：应用 top-k 统计数据来预计基数界线
总体体现
表 3 表 4 别离给出了众模型在 STATS-CEB 与 IMDB-JOB 上的端到端工夫的试验后果。在 STATS 数据集上，少数办法的端到端工夫优于 Postgres，FactorJoin 达到最优的成果；值得注意的是，DeepDB、FLAT 的端到端工夫尽管略长于 FactorJoin，但二者的打算工夫比 FactorJoin 高了一个量级，应是在解决 CEB 蕴含的查问时会产生多种执行打算，DeepDB 与 FLAT 须要把每种打算都推理一遍，因而比拟耗时。
表 4 给出了在 IMDB 数据集上的端到端工夫的试验后果。能够看到，除了 MSCN 和 FactorJoin 外其它办法的成果均没有 Postgres 的好。因为相较于 STATS 数据集，IMDB 的体量更大，IMDB 领有更多的表、更大的属性域以及更简单的连贯关系。且 IMDB 含有较多的简单字符类数据，而 BayesCard、DeepDB 以及 FLAT 仅反对可枚举的字符型数据，所以并未进行相应的试验。值得一提的是，FactorJoin 的端到端工夫在 STATS 数据集上与 TrueCard 相近，但在 IMDB 数据集上则与之相差较远。这是因为 IMDB 领有更简单的连贯，而 FactorJoin 在连贯键上进行下限预计，当连贯键增多时谬误也会累积。MSCN 相较于 Postgres 也有晋升，因为查问驱动的办法对数据集的大小不敏感而更依赖于训练所应用的查问的品质。
图 10 给出了多个模型在两个数据集上的端到端工夫、模型大小以及训练工夫的试验后果。能够看到，FactorJoin 在各个试验内容上都达到了最优的成果，且其模型大小与训练工夫比 DeepDB 与 FLAT 低了两个量级。
图 10 在两个数据集上的总体体现
详细分析
图 11 给出了几个模型在 CEB 的 146 个查问上预计的相对误差。能够看到，PessEst 生成准确的下限并且从不低估。FLAT 应用更大的模型来了解连贯模式的散布并产生最精确的预计。FactorJoin 能够为超过 90% 的子打算查问输入基数下限。大多数边际低估都十分靠近实在基数。
图 11 在 STATS 上的相对误差
图 12 在 STATS 上单个查问的体现
图 12 给出了各模型在 STATS-CEB 上单个查问的体现。能够看到，在工夫较短的查问里，少数模型的体现不如 Postgres。随着查问的端到端的工夫的晋升，几种办法的成果开始优于 Postgres，因为随着查问的端到端工夫的减少，用于打算的工夫占比升高，执行工夫占比增大，而其余办法相较于 Postgres 有更高的准确度进而会产生代价更低的打算。
融化试验
图 13 给出了 FactorJoin 在不同的 k 值下的体现。能够看到，随着桶数量的减少，模型预计的端到端工夫以及相对误差在逐渐升高并逐步趋于稳定。而单查问的推理时延、训练工夫以及模型大小在疾速减少。
图 13 不同桶的数量（k）对模型的影响
表 6 给出了在应用不同分桶算法的状况下模型的端到端工夫。能够看到，等宽划分和等高划分的成果相近，而本文提出的 GBSA 优于这两种办法。
表 8 给出了应用本文提出的两种办法相较于传统的连贯直方图的端到端工夫比照。能够看到，本文提出的两种办法都能晋升模型的预计成果以使优化器抉择更优的执行打算。
总结
本文提出了一种用于连贯查问的基数预计框架 FactorJoin，该框架将经典的连贯直方图与学习型单表基数预计联合成一个因子图。该框架将传统的基数预计问题转化成因子图的推理问题，且只须要晓得单表的散布。作者还提出了两种优化算法以晋升模型的效率。最终，FactorJoin 在查问的端到端工夫优于其它 SOTA 算法的状况下，模型大小、训练及更新工夫比 DeepDB 及 FLAT 低了两个量级。
参考文献
[1] Alberto Dell’Era. 2007. Join Over Histograms. Available on www. adellera.it/investigations/join_over_histograms (2007).
[2] H-A Loeliger. 2004. An introduction to factor graphs. IEEE Signal Processing Magazine 21, 1 (2004), 28–41.
[3] Daphne Koller and Nir Friedman. 2009. Probabilistic graphical models: principles and techniques. MIT press.
[4] Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2019. Learned cardinalities: Estimating correlated joins with deep learning. In CIDR.
[5] Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, and Carsten Binnig. 2019. DeepDB: learn from data, not from queries! In PVLDB.
[6] 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. VLDB 14, 9 (2021), 1489–1502.
[7] P Griffiths Selinger, Morton M Astrahan, Donald D Chamberlin, Raymond A Lorie, and Thomas G Price. 1979. Access path selection in a relational database management system. In SIGMOD. 23–34.
[8] Frank R Kschischang, Brendan J Frey, and H-A Loeliger. 2001. Factor graphs and the sum-product algorithm. IEEE Transactions on information theory 47, 2 (2001), 498–519.
[9] Ziniu Wu, Amir Shaikhha, Rong Zhu, Kai Zeng, Yuxing Han, and Jingren Zhou. 2020. BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation. arXiv e-prints (2020), arXiv–2012.
[10] Postgresql Documentation 12. 2020. Chapter 70.1. Row Estimation Examples. https://www.postgresql.org/docs/current/row-estimation-exampl… (2020).
[11] Feifei Li, Bin Wu, Ke Yi, and Zhuoyue Zhao. 2016. Wander join: Online aggregation via random walks. In SIGMOD. 615–629.
[12] Walter Cai, Magdalena Balazinska, and Dan Suciu. 2019. Pessimistic cardinality estimation: Tighter upper bounds for intermediate join cardinalities. In SIGMOD. 18–35.
[13] Axel Hertzschuch, Claudio Hartmann, Dirk Habich, and Wolfgang Lehner. 2021. Simplicity Done Right for Join Ordering. CIDR (2021).
欢送拜访 OceanBase 官网获取更多信息：https://www.oceanbase.com/
