关于数据库:学术加油站｜FLAT一个轻量且高效的基数估计模型

编者按

本文系东北大学李俊虎所著，本篇也是「OceanBase 学术加油站」系列稿件第七篇。

「李俊虎：东北大学计算机科学与工程学院在读硕士生，课题方向为数据库查问优化，致力于利用 AI 技术改良传统基数预计器，令数据库抉择最优查问打算。」

明天分享的主题是《FLAT，一个轻量且高效的基数预计模型》，次要介绍了 FLAT 提出的 FSPN 模型，提出了数据库查问优化的新思路。心愿浏览完本文，你能够对这个话题有新的播种，有不同认识也欢送在底部留言探讨。

* 原文《FLAT：Fast, Lightweight and Accurate Method for Cardinality Estimation》，发表于 VLDB 2021。

精确的基数预计对数据库查问优化至关重要。基数预计的外围问题在于如何构建牢靠的联结散布以应答简单的连贯查问，而难点在于如何无效解决属性之间，乃至表之间的关联性。近几年的钻研中，人们开始尝试借助 ML 模型解决这一问题，但就目前而言，大部分的模型要么过于简略以至于准确率有余，要么过于简单导致工夫老本昂扬。

FLAT 提出了 FSPN 模型 —— 一个基于数据驱动，基于 SPN 的无监督模型。现实的基数预计模型该当同时满足高准确，快反馈，低存储三大特点，而 FSPN 模型在这三面均有卓越的体现。总体的思路能够演绎为：

• 在单表内，将强关联属性和弱关联属性辨别开来，并别离建模。
• 在波及多表的查问中，则将相干的多个表聚合为一个节点并建模。
• 该模型人造地反对对属性的范畴查问 (但本文不探讨 like 含糊查问)，同时反对单表查问和多表查问，反对增量更新。

属性关联对基数预计的影响

为了阐明问题，这里举一个简略的例子。以此条简略的查问 Q 为例子：

SELECT * FROM stu WHERE name='me' AND Id='10001'

假如表中有 10 条数据，但仅有 1 条数据同时满足这两个谓词。在独立性假如成立的条件下，事件 E1={name=’me’} 和事件 E2={Id=’10001’} 互相独立，则查问 Q 的命中率可简略计算为：P(Q)= P(name=’me’)·P(Id=’10001’}=0.01。

然而，该计算结果显著和理论状况不符，起因是没有思考到这两个属性列之间潜在的关联性。思考到事实场景，name 和 id 两属性列可被认为是存在函数依赖的关系。在此正当假如 P(Id = ‘10001’ | name = ‘me’) 的概率为 1，则 P(name=’me’, id = ‘10001’) = P(Id = ‘10001’ | name = ‘me’)·P(name = ‘me’) = 0.1

尤其是对于 data-driven 的基数预计而言，外围工作是借助模型对条件概率 P(A|C) 做精确预计。在这个例子中，P(A) 被合成为多项式乘积的模式，该过程也称因子合成。

本文指出，目前的因子合成能够分为独立因子合成 independent factorization 和条件因子合成 conditional factorization。对于独立因子合成，目前风行的办法有 Histogram，SPN 模型等，尽管性能达标，但属于有损合成；对于条件因子合成而言，目前提出的办法有深度自回归网络 1[3]，贝叶斯网络 4 等，尽管可实现无损合成，然而工夫老本更高。本文则提出综合利用两种因子合成：对于弱关联属性应用独立因子合成；对于强关联属性则应用条件因子合成，以此在准确率和时延之间找到一个最佳均衡。

本文提出的 FSPN 模型全称是 Factorize – Split – Sum – Product Network，是一个基于 SPN 树构建的模型。本文的外围翻新点在于应用 factorize 节点对强 / 弱相干的属性集别离建模，同时应用 split 节点对强相干属性集外部进行建模。

整个模型分为三个局部：离线训练，在线剖析，增量更新。从形象的层级来看，性能如下：

• 离线训练承受输出表及其数据，输入模型 f。
• 在线剖析模块承受内部的查问 Q，该查问作用在 T 表上。调用模型 f，求得概率之后再乘以原表的基数作为近似的基数预计。

构建 FSPN 树

本文先以一张单表 T 的 FSPN 模型构建过程为例子。属性集记作 A={A1, A2, A3, A4}，将每个属性视作是 r.v.，则表 T 的基数预计问题可转化为求多元概率密度模型 p.d.f. P(A) 的问题。这里令 A3, A4 是两个强相干属性，而 A1, A2 则是弱相干属性，则属性集 A 可被划分为弱相干属性集 W={A1, A2}，强相干属性集 H={A3, A4}。

图 1 通过 factorize 辨别强弱关联属性集

首先，将表 T 视作是根节点 N1，它将作为 factorize 节点：依据 H 和 W 两个属性集将表 T 垂直划分出了两个子表并建设子节点 N2，N3。

进一步划分 N2 节点：A1 和 A2 属性互为弱相干，但非齐全独立。对于 SPN 及衍生的模型 [6] 而言，能够通过适合的聚簇 — 分片形式消除弱相干关系，使得属性之间部分独立，这个过程被称之为 “ 上下文独立 ” (context independent)。

比方，以 A2<50 作为分片条件，将 N2 节点的子表再次划分为 T1，T2。在每个 Ti 外部，A1 和 A2 被认为部分独立。对 Ti 持续做垂直分片，能够划分 L1, L2, L3, L4 四个区域，如图 2 所示：

图 2 通过聚簇对子表进行分片

每一个 Li 只蕴含一个属性列，因而被称之为 uni-leaf 节点。可得：

公式 1 A1，A2 列计算公式

其中，每个权值 w 为子表行数和原表 T 的比值。从公式中可知 N2 是 sum 节点。

对于 N3 节点，须要计算 P(A3, A4|A1,A2)，即 P(H|W)。本文提出依据 W 对 H 进行划分，假设划分出了子集 H1, H2, …，在同一个 Hi 外部，无需思考 W 的影响，此时可认为 P(Hi|W) = P(Hi)。本文称这种形式为上下文条件移除 contextual condition removal。此时将 N3 记作 split 节点。

在以后的例子中，A3, A4 通过谓词 A1 < 0.9 划分出了两个子表 L5 和 L6，并由此产生了两个新的蕴含多个属性列的叶子节点，被称之 multi-leaf 节点。

图 3 通过 split 分类强相干属性集数据

以上是残缺的 FSPN 树构建过程，如图 4 (原文 Figure 1) 所示：

图 4 建设 FSPN 模型的残缺过程

解决内部查问

失去的模型 F 能够解决来自外界的查问 Q。这里思考的是范畴查问，对于波及到的属性 Ai，假如它的域为 [Li,Ui]，则 Q 可示意为：

公式 2 hyper-rectangle range

假如每个属性 Ai 的域是 [LBi,UBi]，则 LBi ≤ Li ≤ Ui ≤ UBi。非凡地，对于等值查问，认为 Li=Ui。现有一个达到的 Q 如下图 5 (见原文 Figure 2) 所示：

图 5 应用模型解决查问 Q

依照模型，将 Q 划分出两个等价子查问 Q1 和 Q2。两个子查问能够视作和事件。其中，子查问 Q1 能够通过模型的 N2 节点子树以及 N3 节点的 L5 multi-leaf 节点计算，子查问 Q2 能够通过模型的 N2 节点子树以及 N3 节点的 L6 multi-leaf 节点计算，开展可得：

公式 3 将查问 Q 合成为 Q1 和 Q2

模型更新

当新的数据 ΔT 达到时，FLAT 能够自上而下地实时更新表 T 对应的 FSPN 模型。模型的不同节点将有不同的行为：

1. factorize: 将 ΔT 向下播送到各个节点；

2. sum: 将 ΔT 的每一条数据散发到相应的分片内；

3. split: 相似 sum 节点；

4. uni-leaf: 在该叶子节点中，仅须要简略更新模型参数即可。可选用的办法有 1-D Histogram[7]，高斯混合模型等；

5. product: 在更新模型后，查看左右两局部的独立性是否被毁坏。若否，则仅简略更新模型；否则，对该节点从新进行建模。

6. multi-leaf: 在更新模型后，须要查看左右两局部的独立性是否被毁坏。若否，则仅简略更新模型；否则，将该节点视作 split 节点，从新建模。

离线建模

FSPN 的结构是一个递归的过程。每个节点实质上是四元组 (AN,CN,TN,ON)：

• TN 示意以后节点所蕴含的数据，它又被称之为节点 N 的上下文；

• AN，CN 别离代表该节点的两组属性。如果 CN 为空集，则该节点的建模过程能够用符号标记为 P(AN)，反之，则标记为 P(AN|CN)。在 FSPN 模型中，根节点的 AN=A，CN 为空集，TN=T。它代表的联结散布记为 P(A)；

• ON 代表了该节点的性质，即它属于：factorize，sum，split，uni-leaf，product，multi-leaf 节点的其中一个。

本文应用 RDC[8] 办法 (全称 Randomized Dependence Coefficient) 对属性集 A 内的所有属性 Ai, Aj 进行成对测验。这里设定一个阈值 th，若能胜利宰割出强相干属性集 H，则该汇合并为非空集合。此时，属性汇合 A 被划分为 H 和 A – H，并产生左右两个节点。

对于弱相干属性集的节点，非凡地，若 |AN| = 1，则该节点被划分为 uni-leaf 节点。uni-leaf 节点的概率模型能够应用简略的办法进行建模，比方 Histogram 办法。

否则，设定阈值 tl 来决定 AN 外部的属性之间是否独立。若是，则该节点可作为 product 节点；否则，将该节点设置为 sum 节点，通过聚簇形式 (如 K-means[9] ) 切分多个子表以打消上下文的影响。在每个子表内，认为属性之间是部分独立的，再进而应用 product 节点进行组织。

对于 factorize 节点划分出的右子节点，它的概率模型记作 P(AN|CN)，CN 为空集。若 AN 和 CN 汇合互相独立，可被间接认为是 multi-leaf 节点，通过建设分段模型 piecewise regression 失去 P(AN)。

否则，应用 d-way 分区办法对 TN 做一步 split，目前的节点即为 split 节点。假设分出了子簇 T1, T2, …,Td，随后通过 FLAT-Offline 模型对每一簇进行建模失去概率密度。

多表基数预计

首先是离线构建过程。将 D 内所有的表依据它们的连贯关系组织成一个树形构造，记作 J。J 外部的每一个节点代表一张表，每一条边示意两个表的连贯关系。

本文提出，高度相干的表可能划分到一个组 group 内，而组间的表是弱相干的。以一条边 (A,B) 为例子，零碎首先从 A ⟗ B 表中做取样，并检测两表之间是否存在高度相干的属性列。如果局部列之间的相关性高于某个阈值，则间接对 A ⟗ B 表进行建模，或者称将 {A,B} merge 为一个节点。

整个 merge 的过程将递归执行，直到没有再须要 merge 的节点为止。每一个节点 Ti 将示意单表，或者多表的全外连贯。

其次是在线构建过程。令 E={T1, T2,…,Td} 示意某一个查问 Q 所命中的 J 树的所有节点。Q 将依据 E 切分出对应的子查问 Q_i。在本文的假如当中，每个 Qi 在 A_1 ⟗ A_2 ⟗ … ⟗A_d 都是独立的，这意味着只需简略计算并累乘子查问的概率即可失去 P(Q)。

多表查问对基数预计的影响

现假设有一个 J 的构造如下，A, B 表被划分为同一个组：

图 6 多表下的连贯树构建

当存在一个 Q 的谓词仅与表 A 相干时，间接从 T1 节点的连贯表 (即 A ⟗ B) 进行查找。须要留神的是，在全外连贯的过程中，因为 A 表的记录可能会和 B 表产生一对多连贯，从而产生更多的数据行，因而基于连贯表计算的基数被高估了。为了对消这种影响，须要对预计到的基数进行下调 (scale-down) 修改。

图 7 多表下的基数预计误差

另一个例子则是：查问 Q 和表 B 和 C 相干，但两表并不在一个分组内，因而不能面向 B ⟗ C 表进行基数预计。实际上，这会导致预计到的基数偏小，此时须要进行上调 (scale-up) 修改。

为了给基数修改留下足够的线索，本文提出：在原表中新增名为 scattering coefficient 的额定属性列信息。

增加两个额定的列：S_{A,B} 和 S_{B,A}。其中，S_{A,B} 属性列示意：对于 A 表的每一条记录，B 表可提供多少可供连贯的行数，反之亦然。这两个属性列用于修改因连贯非相干表而须要下调基数预计的状况。此外，本例还需新增一列 S_{T1,{T1,T2}}，以应答 C 表与 A ⟗ B 进行连贯的状况，以便进行基数上调。

表里的每一条数据可能同时须要进行上调 (记作 e) 和下调 (记作 s)，则它满足查问 Q 查问的概率被系数 e/s 修改。本文默认设定 e 和 s 的最小值为 1 而非 0，起因是每条数据肯定会在全外连贯的表中呈现至多一次，残缺计算过程，见 [10]。

简而言之，scattering coefficient 列的数量和 D 中的表数目成线性关系。对于连贯树 J 的任意一个节点 Ti，其 scattering coefficient 列的各种信息将在构建 FSPN 模型时一起计算，见 [11]。

多表模型的更新

当节点 Ti 中的任意一张子表有新数据达到时，会导致连贯表更新数据。上面是一个简略的示例：

图 8 T1 节点的表构造

当 B 表有新数据 ΔB 达到时，它能够与原表 A 产生新的连贯关系，将这部分新增数据记作：ΔF+；而表内原有的数据也须要进行查看：有局部数据的 scattering coefficient 列须要进行更新，记作 ΔF*。同时，本来没有连贯关系的行可能曾经生效，须要被及时删除，记作 ΔF-。如下图所示：

图 9 新增数据导致节点更新

为了减速多表模型的更新过程，将连贯表的所有 scattering coefficient 列记作 St，将所有属性列记作 At，则概率模型 P(St|At) 能够被视为 split 节点，左右节点别离为 P(At) 和 P(St|At)。对于左节点，能够间接将增量数据流传到 FSPN 模型，而 St 列的更新则是耗时操作，本文则抉择通过异步形式进行更新，以此进步模型效率。

性能比照

本文对已有的其它办法进行比照：Histogram，Naru，NeoroCard，BN，DeepDB，SPN-Multi，MaxDiff，Sample，KDE，MSCN。FSPN 的 RDC 阈值设定为 tl=0.3 (低于此值认为独立)，th=0.7 (低于此值认为弱相干)。性能的评测指标抉择宽泛应用的 q-error。计算形式为：

公式 4 q-error 计算公式

本文的算法基于 python 实现，试验环境为 CentOS 零碎，64 核 Intel Xeon Platinum 8163 2.50 GHz，128 Gb DDR4 内存，以及 1 Tb SSD。

▋ 单表性能比拟

本文应用 GAS 和 DMV 两个事实的数据集进行性能评测。GAS 蕴含了 3,843,159 条数据，而 DMV 蕴含了 11,591,877 条数据。

GAS 数据源：

https://archive.ics.uci.edu/m…

DM 数据源：

https://catalog.data.gov/data…

对于每一个数据集，本文随机生成了 1 万条查问，每个属性列被抉择的概率均为 0.5。表 1 (对应原文 Table 1) 展现了不同算法的 q-error 散布。

表 1 各模型在单表下的基数预计性能

总而言之，从准确率的角度剖析，排名顺次为：FLAT≈Naru[12]≈ SPN-Multi >BN>DeepDB>>Sample/MSCN[13]>>KDE[14]>> MaxDiff/Histogram。细节如下：

Naru 的高准确率源于它基于 AR 的合成办法，以及宏大的 DNN 网络。

SPN-Multi 同样达到了一个高准确率，因为它摈弃了属性之间齐全独立的假如。

BN 和 DeepDB 的准确率逊色于 FLAT。BN 的性能受到了其构造的制约，而 DeepDB 仿佛并不能很好地解决高度关联的数据集。

MSCN 和 Sample 的体现并不稳固。思考到 MSCN 是一个 query-driven 的模型，它的体现取决于查问负载和训练的查问样本是否足够类似。

FLAT 的性能远超 Histogram，MaxDiff 和 KDE：Histogram 和 MaxDiff 仅做了粗粒度的独立性假如；KDE 则无奈无效地用核办法解决高维度数据 (high-dimensional data)。

下方的图表展现了不同办法的均匀延迟时间，为了偏心起见，这里仅比拟了基于 CPU 的办法。排名顺次为：Histogram ≈ FLAT > MSCN > SPN-Multi/DeepDB > KDE/Sample >> 其它。

图 10 各模型的训练时延

FLAT 在两个数据集的预计延时别离为 0.1ms 和 0.5ms，远超其它的办法。这证实了 FSPN 是高性能的模型。除此之外，MSCN 在这里仅须要对 DNN 做一次前向流传，因而也获得了不错的问题。

DeepDB，SPN-Multi，KDE 和 Sample 须要 10ms 去解决每一条查问。DeepDB 和 SPN-Multi 同样是基于 SPN 的模型，而它们在本次测试中均构建出了约 800+ 个节点的树结构。而 FSPN 应用了更加轻量，紧凑的模型，相比之下只构建了 200 个节点。额定的，KDE 和 Sample 须要大量的样本进行检测，这有损了它们的性能。

表 1 还反馈出 FSPN 模型的训练工夫要比其它模型更小。这得益于 FSPN 的模型，同时又不须要像基于 SGD 的 DNN 训练那样须要迭代式的梯度更新。

▋ 多表性能比拟

本文应用经典的 IMDB 数据集测试多表查问的场景。同时，创立了蕴含了 70 个简略查问的轻量级 JOB-light，以及蕴含 1500 个简单查问的 JOB-weight。表 2 (对应原文 Table 2) 展现了各个预计模型在 JOB-light 查问集的体现状况。

表 2 各模型在 Job-light 下的性能

FLAT 在准确率方面仍有显著劣势。从存储方面，FLAT 仅仅位列 Histogram 和 BN 之后。但相较于单表情形，FSPN 模型变得非常宏大 —— 因为在多表状况下要构建 scattering coefficient 列并保护。

在 JOB-ours 查问集下，其它办法的性能产生了显著降落，然而 FLAT 依然可能放弃绝对最佳的性能。图 10 (对应原文 Figure 7) 表明了 FSPN 模型在两种工作负载下的查问提早均在 5ms 左右，仅稍次于 Histogram 办法。

图 11 多模型在不同测试集的均匀提早

▋ 更新性能

本文提取了 IMDB 前 80% 的数据用于训练模型，并用剩下 20% 的数据用于测试数据更新的场景。如表 3 (对应原文 Table 4) 展现：

表 3 增删数据对各模型的性能影响

再训练模型 (retrained model) 的准确率最高，而代价是最长的训练工夫。因为增量数据导致概率密度发生变化，那些不反对更新模型的办法的准确率在以后场景下是最低的。相比较而言，本文的 FSPN 模型在准确率和更新时延之间放弃了良好的均衡。

写在最初

本文提出了一个基于 SPN 的改良模型 —— FSPN，一个轻量且高效的无监督图模型。它最大的亮点在于能够灵便依据属性列之间不同的依赖水平 (独立，弱相干，强相干)，综合利用独立因子合成和条件因子合成的思路进行建模，同时保障了零碎的准确性和时效性。

不同场景下的比照试验均验证了 FSPN 模型的高效性和稳定性，置信该模型在将来可能在数据库相干的工作中充当更加重要的角色。

* 参考文献：

[1] Shohedul Hasan, Saravanan Thirumuruganathan, Jees Augustine, Nick Koudas,and Gautam Das. 2019. Multi-attribute selectivity estimation using deep learning.In SIGMOD.
[2] Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2021. NeuroCard: One Cardinality Estimator for All Tables. PVLDB 14, 1 (2021), 61–73.
[3] 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. PVLDB (2019).
[4] Lise Getoor, Benjamin Taskar, and Daphne Koller. 2001. Selectivity estimation using probabilistic models. In SIGMOD. 461–472.
[5] Kostas Tzoumas, Amol Deshpande, and Christian S Jensen. 2011. Lightweight graphical models for selectivity estimation without independence assumptions. PVLDB 4, 11 (2011), 852–863.
[6] Benjamin Hilprecht, Andreas Schmidt, Moritz Kulessa, Alejandro Molina, Kristian Kersting, and Carsten Binnig. 2019. DeepDB: learn from data, not from queries!. In PVLDB.
[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] David Lopez-Paz, Philipp Hennig, and Bernhard Schölkopf. 2013. The randomized dependence coefficient. In NIPS. 1–9.
[9] K Krishna and M Narasimha Murty. 1999. Genetic K-means algorithm. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 29, 3 (1999),433–439.
[10] Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou, and Bin Cui. 2020. FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation [Technical Report]. arXiv preprint arXiv:2011.09022 (2020).
[11] Zhuoyue Zhao, Robert Christensen, Feifei Li, Xiao Hu, and Ke Yi. 2018. Random sampling over joins revisited. In SIGMOD. 1525–1539.
[12] Zongheng Yang and Chenggang Wu. 2019. Github repository: naru project.https://github.com/naru-proje… (2019).
[13] Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2019. Learned cardinalities: Estimating correlated joins with deep learning. In CIDR.
[14] Luch Liu. 2020. Github repository: scikit-learn. https://github.com/scikit learn/scikit-learn (2020).