【论文翻译】FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation

FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation

摘要

基于基数估计的技术用于规划查询执行计划，在数据库优化领域具有重要地位

一、介绍

基数估计(CardEst)作为现代数据库管理系统(DBMS)和分析引擎中的重要组成部分[1,47]。它的主要功能是在SQL查询计划执行前估算结果规模，并在此过程中发挥核心作用。基数估计的主要职责在于高效地计算满足特定条件的数量，在一张表T中获取相关信息。通常采用以下两种方法：

1. 查询驱动：建立一个映射关系, 使查询Q对应于概率P. 因此需要大量的执行查询来构成训练样本集. 只有在未来的输入数据满足与当前工作负载相同的数据分布情况下, 这种映射关系才能体现出良好的泛化性能.
2. 数据驱动: 构建无监督学习模型Pr(T)——表示表T中属性的联合概率密度函数(PDF).

基数估计的挑战和状态

基于实际需求分析可知, 一种符合数据驱动原则的CardEst方案需同时满足以下三项关键标准: 评估阶段的质量必须尽可能精准, 因此优化器能够有效识别并避免选择次优查询执行计划[17,51]. 此外, 由于该方案在优化查询执行计划[10]的过程中会频繁调用CardEst算法, 因此计算过程需具备高效性. 最后, 在存储资源方面具有更高的效率是该模型的重要特征. 然而, 当应用于建模真实世界中的复杂数据集时, 现有方案仍存在若干局限性. 图1展示了当前CardEst方案的实际性能表现.

简而言之，在数据表T上构建无监督模型主要包含三个核心策略。第一个策略是直接进行数据压缩与存储Pr(T)的所有实体信息然而这种完全压缩的方式会导致较高的存储开销并且不可避免地会牺牲一定的估计精度因此这种方法难以满足实际应用需求。第二种策略基于抽样或者核密度估计的方法通过样本进行粗略的概率分布估算这种方法能够在一定程度上降低计算复杂度但对于高维数据而言如果样本数量不足可能导致估算结果不够准确或者因计算量过大而影响效率尤其在样本规模有限的情况下这一缺陷显得尤为明显第三种策略则是采用分解技术将复杂的条件概率模型拆解为多个低维子模型这些子模型的组合能够近似地表示高维空间中的概率分布关系这种方法的优势在于能够有效降低计算复杂度并通过灵活组合实现对高维问题的有效建模然而现有的一些无损分解方法虽然能够实现无损分解但其计算效率显著下降因此这种完全可逆的方法在实际应用中往往难以平衡高效性和准确性之间的关系为此我们需要深入探讨现有数据驱动的基础估计方法及其适用性。

我们的贡献

在本文中，我们更全面地解决了基数估计问题，以满足所有这三个标准。我们观察到:条件分解可以准确地分解PDF，但概率计算是昂贵的，反之亦然，独立分解。为了吸收它们的优点，我们设计了一个新的图形化模型，称为分解和分裂积网络(FSPN)。它的关键思想是根据属性的依赖程度适应性的分解Pr(T)。具体来说，通过条件分解将高相关属性和弱相关属性的联合PDF无损分离，并建立相应的模型。对于高度相关的属性，不同维度的值为相互依赖的，因此，它们的联合PDF可以很容易地建模为多元PDF。对于弱相关属性，将它们的联合PDF分割成多个小区域，每个小区域的属性相互独立。我们证明了FSPN包含直方图、和积网络和贝叶斯网络，并充分利用了它们的优点。
基于FSPN模型，我们提出了一种快速、轻量化、准确的基数估计方法FLAT，如图1所示。在单个表上，FLAT采用了一种有效的离线方法来构建FSPN的结构，并利用FSPN进行了一种高效的在线概率计算方法。FLAT的概率计算复杂度几乎是线性的。此外，FLAT还支持在底层数据更改时快速增量更新FSPN。
对于多表连接查询，FLAT使用了一个新的框架，它比现有的工作更加通用和适用[13,16,19,55]。在脱机阶段，将表划分为几个组，并为每个组构建一个FSPN。在联机阶段，FLAT以一种快速的方式组合子查询的概率以获得最终的结果。
在我们的评估中，与所有现有的方法相比，FLAT在单表和多表情况下都实现了最先进的性能。综上所述，我们的主要贡献如下:

1. 基于以下三个标准（见第2章），我们系统性地探讨了现有数据驱动基数估计方法的发展现状。
2. 本研究中，我们开发出了一种新型无监督图形模型FSPN，在融合现有技术优点的基础上实现了自适应性设计。
3. 在单表查询及多表连接查询（如第4章至第5章所述）场景下，我们设计出了一种名为FLAT的新基数估计算法。该算法具备高效的概率计算能力、精确的估计精度以及较低的存储开销。
4. 为验证所提出方案的有效性与适用性，在Postgres数据库平台上展开了系统性实验并进行了全面评估。

二、问题定义和背景

本节中我们将详细阐述基数估计问题的基本概念，并探讨数据驱动方法的特性。基于以上分析我们将归纳出几个对我们研究工作具有重要意义的成果。

基数估计问题

T 是一个表格，在其中包含 K 个属性 {A₁, A₂, …, A_K} 的集合 T 可以是一个单一表格或者由数据库中多个表格通过关联操作连接而成。为了不失一般性性起见我们假定属性 A 的定义域为 {LB_i UB_i}。
在本文讨论中我们暂且忽略字符串上的 LIKE 查询操作此类特定场景下的处理方法。任何选择性查询 Q 可以表示为规范形式中的多个区间端点其中每个区间端点都可能被设定为开放或闭合状态。
该类查询涵盖了两类基本类型即点式查询与区间式查询对于那些存在间隔区域的部分则可以通过分解处理将其转换为多个规范形式区间端点相关的子查询。
基于纯粹的数据驱动方法无监督基数估计问题得以解决并可正式表述如下：

离线训练：

假设我们有一个表T以及一组属性A。我们的目标是生成一个模型来模拟表T在属性A中的联合概率分布函数。

在线概率计算：

将该模型和一个查询Q作为输入，输出概率乘以表的条数作为估计基数。

数据驱动的CardEst方法分析：

基于三项指标（模型的精度、概率计算效率与存储消耗），我们对现有方案进行了评估。

有损压缩机制的FullStore[11,40]通过压缩技术将Prt(A)中的所有条目存储起来，在属性数量上呈指数级增长并变得难以处理。
基于样本与核的技术：从表T中进行抽样，并采用以采样点为中心的平均核来估计Prt(Q)。
直方图方法假设各属性之间相互独立。
深度自回归模型利用链式法则将联合概率密度函数分解为多个低维条件概率模型。
贝叶斯网络通过构建有向无环图来表示各属性间的依赖关系。
该系统采用了卷积神经网络（CNN）作为核心组件

灵感

在深入分析后发现, 数据库领域尚未开发出一种既能实现准确、快速又兼具轻量级特性的综合有效解决方案CardEst.这一困境的核心原因在于现有方法均采用单一类型的因式分解方案.其中, 基于直方图和SPN的方法主要依赖于独立性因式分解技术.然而, 每一特定的因式分解方案仅能满足基准体系中的一个或两个关键指标:一方面, 独立因子分解法具有低成本优势及高效的计算能力, 但其精度存在较大局限;另一方面, 条件因子分解法则能精确建模概率密度函数(PDF), 但在实际应用中往往伴随较高的计算开销.因此, 这两种不同技术路线在适用场景上呈现出互补特性.由此提出一个问题:是否能够设计出一种自适应的方法框架, 同时兼顾这些基准要求?为此我们提出了一种无监督学习模型FSPN(Factorized Sum-Product Network), 它集成了上述两种技术的核心优势

三、FSPN模型

在本节里, 本文将介绍一种新型的树状结构图形模型, 该模型能够通过自适应的方式来描述一组属性的联合概率密度函数（PDF）。本文首先通过一个具体的实例来阐述了该模型的核心概念, 接着对其形式化的数学定义进行了阐述。最后部分我们将该方法与之前讨论的其他模型进行了对比分析, 以评估其性能优势和适用范围。

FSPN的关键思想

FSPN能够对高低相关程度的不同属性进行分解。特定因子分解方法被用来将高相关属性与弱相关属性区分开来。随后，在模型中直接整合高度相关属性，并对弱相关属性应用独立因子分解方法逐步逼近其结构。图2(a)展示了表T的一个实例：包含水浊度(A1)、温度(A2)、波高(A3)以及风力(A4)等属性。图2(b)则详细说明了构建其FSPN的过程。

我们首先考察表T中各对属性之间的相关性程度。观察发现A3与A4的相关性极为紧密（即它们之间存在高度相关关系），因此在不将表T划分为极小簇的情况下（即不将这些高度相关的属性单独分离出来）无法实现它们的有效分解。相反，在这种情况下我们可以尽可能早地无损地将它们从其他属性中分离出来，并分别对每个部分进行处理。为此我们定义集合H包含{A3,A4}而集合W则包含{A1,A2}。随后我们采用条件因子分解方法对Prt(A)进行建模即Prt(A) = Prt(W)*Prt(H|W)，其中Prt(W)与Prt(H|W)分别以不同的方式进行建模以满足特定需求。

值得注意的是，在W中的两个属性A1和A2并非相互独立（尽管它们之间的相关性较为微弱）。因此在某些特定条件下我们可以对这些属性进行特殊的处理以实现更为精确的结果。具体而言如果我们按照某个阈值将所有记录T划分为子集T1和T2则在子集内部（即对于同一子集内的任意记录）这两个变量之间不再存在显著的相关关系从而使得它们能够被视作相互独立变量在这种情况下我们就称这种情况为上下文无关状态因而可以简化计算过程并直接使用边缘概率分布来描述变量间的依赖关系即Prt₁(W)=Prt₁(A₁)*Prt₁(A₂)以及Prt₂(W)=Prt₂(A₁)*Prt₂(A₂)等式成立这一假设下我们可以基于上述边缘分布来进行后续的概率建模工作

对于条件概率密度函数Prₜ(H|W)我们无需为每一个具体的w值单独建立完整的概率模型而是可以通过递归划分原始数据集从而构建一系列子区域在每个子区域内H变量与W变量之间满足严格的条件独立关系也就是说在特定区域内的任何两个点如果其对应的w值相同那么对应的h值也必定相同从而使得Prₜⱼ(H|W)在整个区域内保持恒定状态

FSPN的思想

四、单表基数估计方法

在本节中，我们提出了一种高效、紧凑型且高精度的基数估计算法。随后，在第4.1节中将详细阐述该算法如何在线计算其在FSPN上的概率。接着，在第4.2节中将展示该算法如何自动生成其对应的FSPN数据。最后，在第4.3节中我们将探讨该算法如何更新模型。

4.1 在线概率计算

FLAT能够通过一种分层的方法在FSPN中计算出任意查询Q的概率。为了阐述这一过程的基本思路或方法,我们先通过一个实例来具体说明概率计算的基本策略,随后详细阐述了相应的算法,并评估了该算法的时间复杂度

基本策略

如前所述，在第2节中提到，我们可以用规范形式来表示查询Q。显然地，在属性空间中选择一个超矩形范围的概率计算是必要的。如图3所示，在其中我们提供了一个查询的具体例子。

如前所述，在第2节中提到，我们可以用规范形式来表示查询Q。显然地，在属性空间中选择一个超矩形范围的概率计算是必要的。如图3所示，在其中我们提供了一个查询的具体例子。

算法描述：

详细阐述了在线概率计算算法。由一个FSPN模型和查询Q构成。按照以下规则递归地计算发生概率：

详细阐述了在线概率计算算法。由一个FSPN模型和查询Q构成。遵循以下规则递归地计算发生概率：

规则1(第2-3行):当N为单一叶子节点时，在单变量联合概率分布中计算Q的概率。
规则2(第4-11行):对于和节点或积节点的情况(N₁,N₂,…,N_t均为其子节点)，我们可以分别获得每个子节点对应的PDF值。然后根据具体情况采用加权求和(用于和节点)或乘法运算(用于积节点)的方式计算目标变量的概率。
规则3(第12-18行):当N为因式分解模型时，请令LC和RC分别为其左右子模型Prt(W)与Prt(H|W)。其中RC的所有后代均为分割型或多叶子型结构。令L₁,L₂,…,L_t代表RC所有多叶子型子树的所有父结点，则假设这些分割型结点按照网格方式划分属性域空间范围；这样在指定超矩形区域内即可维护从RC到Li路径上所有相关联变量的多元PDF值。

4.2 离线结构构建

我们详细阐述了平面离线算法中FSPN的构建过程。其中整体流程可参考图4

以自上而下的方式工作。我们简要扫描其主要程序如下:

1. 在第2-8行中，在条件为空的情况下，FLAT-Offline 首先识别是否存在一组高度相关的 H 属性（因为 FSPN 的原理旨在尽早将它们与其他属性区分开来）。我们通过计算每对属性之间的相关性来确定 H 的存在与否，并设定一个阈值参数。若 H 集合不为空，则将其作为分组节点处理，并将 N 的左子节点和右子节点分别递归调用模型 PrTn(An−H) 和 PrTn(H|An−H)。
2. 在第9-19行中：当 Cn 为空且 H 为空时（即 An 为空），我们的目标是将 Prtn(An) 划分为更小的区域（以便 An 的属性在局部范围内达到独立状态）。具体而言：
   • 如果 An 中仅包含一个属性（|An|=1），则 N 节点成为一个叶子节点（Leaf-PDF），并使用现有工具对单变量 PDF 进行建模。
   • 在我们的实现中，默认选择直方图[40]和参数高斯混合函数[41]来分别建模分类属性和连续属性的概率密度函数。
3. 在第21-30行中：在分析所有属性与 Cn 之间的成对相关性后发现：
   • 如果 An 属性与 Cn 独立，则 N 节点设置为一个多叶子节点（multi-leaf node）。

4.3 增量更新

在表T发生变化时，在确保估计精度较高的前提下节省更新成本。我们尝试最大限度地保持原始FSPN模型，并通过微调参数来提升拟合效果。FLAT更新可在数据库管理系统中后台执行。描述了数据插入的方法；类似地进行数据删除操作：当新记录增加时，在自顶向下方法中修改FLAT：对于每个分解节点N而言，在任何情况下条件因子分解都是联合概率密度函数的无损分解；因此可以直接传递给其子节点。对于每个拆分节点而言；我们根据拆分条件将更新的信息分配到相应的子节点中去。在处理原始多叶节点L时；我们需要再次验证条件独立性是否依然成立：如果成立，则只需更新其多元PDF的主要参数；否则将其重置为一个新的拆分节点并执行第12至19行以进一步划分域空间以获取更高精度模型。显然，在不改变数据分布的情况下；平面更新通常不会影响原始的FSPN模型：如果发生重大变化如属性插入或删除；则需通过调用FLAT-Offline重建相应的FSPN子结构以适应新的分布情况

五、多表基数估计方法

在本节中, 我们致力于探讨如何将FLAT算法扩展至多表连接查询. 起始我们将从宏观概述我们的方法入手, 在后文中则会详细阐述其中的关键技术.

主要思想

为了克服现有方法的不足[16]，本方案借鉴了其核心理念，并构建了一个小型本地模型体系。然而，在实质上扩展了这一方法框架以提高通用性和实用性。首先开发了一个新的PDF纠正范例以支持多种类型的连接关系（如内部或外部以及多对多），具体内容参见下文的技术一。其次特别优化了基于FSPN模型的概率计算与矫正流程（如技术二所示）。最后针对数据变化特征设计了一种增量更新机制（如技术三所述）。

算法描述

将数据库D与查询Q作为输入参数传递，在离线阶段(1-7行)中进行以下操作：首先构建一个树状数据结构J（tree structure），该结构基于数据库D中各表之间的关联关系（associative relationships）进行构建。在这个过程中，默认情况下每条树边代表两个表之间的关联关系（associative relationship）。特别地，在本研究中我们假设不考虑自连接（self-connection）以及循环（cyclic）连接的情况。基于此构建的树状数据结构J中每条边代表两个表之间的关联关系（associative relationship）。在此基础上我们对数据库D中的所有表进行分组划分：在同一组内的表之间具有较强的关联性（strong associative relationship），而不同组内的表之间相关性则较弱（weak associative relationship）。具体操作如下：对于树状数据结构J中的每一条边(A,B)，我们从A或B所在表中随机采样一定数量的数据记录，并执行外部连接操作（external join operation），随后计算两两属性之间的相关系数值(A,B)。如果检测到某些属性对的相关系数值超过设定阈值，则将这两张表(A,B)合并到同一个节点下；否则维持现状。如此反复操作直至所有节点都无法进一步合并为止。此时不同节点之间假设其外部连接数据是相互独立且互不干扰的（independent external join datasets）。经过上述合并操作后得到树状数据结构J中的每个节点T代表一组独立的原始表集合；对于每个节点T其对应的外部连接表中增加了若干散射系数列变量（scattering coefficient variables），用于校正PDF分布情况（PDF distribution correction）。这些散射系数变量的具体计算方法将在下面的技术二中详细阐述。随后通过Flat-offline算法对 Flat 模型进行训练并建立完整的 Flat 模型架构。（如图5所示）以三个表格为例：Tb与Tc之间存在多对多关联关系(many-to-many association)，Ta与Tb之间存在较强的关联性(have strong associative relationship)，因此Ta与Tb被合并到同一个父节点1下；随后分别构建两个Flat SpatioTemporal Network (FSPN)模型

2. 在线处理（第8-12行）：针对在线查询Q，在线系统会使用E来代表其中涉及的所有节点。随后将整个查询依次分解为若干个子查询，在线处理过程中假设每个子查询均能在各自独立的表内运行。基于我们所做的假设，在局部模型中可引入一种新方法来有效纠正每条子路径的概率值。通过综合所有各子路径的概率值进行计算和乘积运算后得出最终的数据估计结果。

六、评价结果

我们进行了充分的实验以验证我们提出的FLAT算法的优势。首先介绍了实验设置之后，在第6.1节及第6.2节分别报道了基于单表与多表场景下采用CardEst算法所获得的评价结果。而在第6.3部分则呈现了更新效果的相关数据。最后，在第6.4节中将FLAT技术整合至Postgres[7]中的查询优化器中并评估了其端到端查询优化性能。

基线方法

我们将FLAT与各种有代表性的基数估计算法进行比较，包括:

1. 直方图:在DBMS中广泛使用的最简单的方法，如SQL Server[29]和Postgres[7]。
2. Naru:[55]中提出的基于DAR的算法。我们采用了作者在[56]上编写的源代码，并采用了var-skip加速技术[26]。该算法利用5个隐层(512、256、512、128、1024个神经元单元)的DNN来近似pdf文件。抽样大小设置为2000，这是作者的默认值。我们不比较[13]中的类似方法，因为它们的性能很接近。
3. NeuroCard [54]: Naru在多表情况下的扩展。我们也采用了作者的[31]源代码，并将采样大小设置为8000作为作者的默认值。
4. BN:基于贝叶斯网络的算法。我们使用基于ChowLiu树[4,12]的实现构建BN结构，因为它的性能比其他的要好[9,51]。
5. DeepDB:[16]中提出的基于SPN的算法。我们采用作者的[15]源代码，并应用相同的超参数，将RDC独立性阈值设置为0.3，并以至少1%的输入数据分割每个节点。
6. MaxDiff:该方法使用有损压缩技术[40]在联合PDF中存储所有条目。我们使用[56]源代码库中提供的实现。
7. 抽样:该方法对大量记录进行统一的抽样，以估计基数。我们将抽样大小设置为数据集的1%。应用于MySQL[42]、MariaDB[46]等数据库管理系统。
8. KDE:基于核密度估计的CardEst方法。我们已经使用scikit学习模块[28]实现了它。
9. MSCN:[19]中描述的最先进的查询驱动的基数估计算法。对于每个数据集，我们用与工作负载相同的方式生成的105个查询来训练它。

不建议将该方法与IBJS等其他算法进行比较。鉴于现有研究表明其他算法表现较为逊色这一事实。具体而言，在第4.2节所述的FLAT超参数设置中，我们采用了RDC阈值Tl=0.3和Th=0.7来区分独立属性与高度相关属性。与DeepDB类似地，在节点的数据量少于输入数据的1%时，则不会进行拆分。

评价指标

在第1节中已经阐述了相关背景知识的基础上，在本节中我们将重点考察以下三项核心指标：其中涉及的主要评估维度包括估计精度、时间效率以及存储开销这三个方面。其中对估计精度这一维度的评估将采用目前学术界广泛认可的q-error度量方法，并其计算公式被定义为：

该模型的最佳性能达到理论极限值1。
本研究系统性地记录了各个工作负载下的q误差分布情况（包括50%
、
90%
、
95%
、
99%
及
100%
分位数的数据指标）。
在保证系统响应效率的前提下, 本研究详细分析了查询延迟与训练时间的表现。
在内存资源方面, 在确保模型准确性的同时, 本研究对所需的内存空间进行了详细评估。

环境

包括所提到的所有算法均使用Python实现。所有实验均在CentOS计算平台上运行。该计算平台采用Intel Xeon Platinum 8163处理器（型号），配备64核心、128GB DDR4内存以及一块容量达1TB的SSD存储介质。

6.1 单表评价结果

我们使用两个单表数据集，即GAS和DMV。GAS是从UCI数据集[43]获得的真实气体传感数据，包含3,843,159条记录。我们提取信息最丰富的8列（时间，湿度，温度，流量，加热电压，R1, R5和R7），DMV[36]是一个真实世界的车辆登记信息数据集，包含11,591,877元组。我们用和[56]一样的11列。对于每个数据集，我们生成一个包含105个随机生成的查询的工作负载。对于每个查询，我们使用0.5的概率来决定是否应该包含某个属性。如第2节所述，每个属性A的域映射到一个区间，我们对两个值进行均匀抽样l和h。

估计精度

表1展示了不同基数估计算法及其对应的q-error分布情况。这些算法在精度上表现出FLAT ≈Naru>BN>DeepDB>>Sample/MSCN >>KDE >> MaxDiff/Histogram的具体表现，请参见以下详细信息。

1. 全部的：FLAT的估计精度很高。在这两个数据集中，中位数q误差(1.001和1.002)非常接近1，最优值。在GAS中，FLAT达到最高的精度。Naru的精度与FLAT相当，在DMV上略优于FLAT。Naru的高精度源于基于AR的分解和代表pdf文件的大型DNN。
2. BN和DeepDB的精度比FLAT差。在95%分位数，FLAT比BN表现更好3.6×并且DeepDBby71×在GAS。BN的误差主要来自于它的近似结构。DeepDB似乎无法分离高度相关的属性。因此，对于涉及这些属性的查询，它会导致相对较大的估计误差。

查询延迟

6.2多表评价结果

该算法在IMDB基准数据集上的多表场景评估结果表明，在处理复杂数据时表现出色。其在先前研究中被证实具有良好的基数估计能力。本研究通过实验采用两种不同的工作负载进行测试：一种基于70个查询的小型工作负载（JOB-light），另一种则包含了1500个更为复杂的查询（JOB-ours）。每个JOB-light查询仅涉及6个表，并且所有其他参与查询的表均仅与标题字段（title）建立连接。