FLAT,一个轻量且高效的基数估计模型

引言

原文发表于 VLDB 2021,见:FLAT:Fast, Lightweight and Accurate Method for Cardinality Estima效率的拼音tion (vldb.org)。

准确的基数查询对数据库查询优化至关重要。基数查询的核心问题在于如何构建可靠的联合分布以应对复杂的连接查询,而难点在于如何有效处GitHub理属性之间,乃至表之间的关联性。近几github中文官网网页年的研究中,人们开始尝试借助 ML 模型解决这一问题,但目前而言,大部分的模型要么过python基础教程于简单以至于准确率不足,要么过于复杂导致时间成本高昂。

FLAT 提出了 FSPN 模型 —— 一个基于数据驱动,基于 SPN 的无监督模型。理想的基数估python编程计模型应当同时满足高精确,快反应,低存储三大特点数据库设计,而 FSPN 模型在这三面均有卓越的表现。总体的思路可以归纳为:

  1. 在单表内,将强关联属性和弱关联属性区分开来,并分别建模。
  2. 在涉及多表的查询中,则效率高发票查验将相关的多个表聚合为一个节点并建模。

该模型天然地支持对属性的范围查询 ( 但本文不讨论 LIKE 模糊查询 ),同时支持单表查询和多表查询,支持增量更新。

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

为了说明问题,这里举一个简单的例子。以此条简单的查询 QQ 为例:

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

假设表中有 10 条数据,但仅有 1 条数据同时满足这两个谓词。在独立性假设成立的条件下,事件 E1={name=me}E_1={name=me} 和事件 E2={id=10001}E_效率计算公式2={igithub汤姆d=10001} 相互独立,则查询 QQ 的命中率可简单计python怎么读算为:

P(Q)=P效率英文翻译(name=me)⋅P(igithub汤姆d=10001)=0.01P(Q) = P(name=me)P(id=10001)github永久回家地址=0.01

然而,该计算结果明显和实际情况不符,原因是没有考虑到这两个属性列之间潜在的关联性。考虑到现实场景,namenameidid 两属性列可被认为是存在函数依赖的关系。在此合理假设 P(name=me∣id=效率英文翻译10001)P(name=me|id=10001) 的概率为 1,使用条件概率计算可得:

P(A)=P(name=me∣id=10001)⋅P(id=10001)=github直播平台永久回家0.1P(A)=P(name=me|id=10001)P(id=10001) =0.1

尤其是对于 data-driven 的基数估计而言,其核心任务是借助模型对条件概率 P(A∣C)P(A|C) 做准确估计。在这个例子中, P(A)数据库管理系统P(A) 被分解成多项式乘积的形式,该python是什么意思过程也称因子分解。

本文指出,目前的因子分解可以分为独立因子分解 independent factorization 和条件因子分解 conditional factorization。对于独立因子分解,目前流行的方法有 Histogram,SPN 模型等,虽然性能达标,但属于有损分解;对于条件因子分解而言,目前提出的方法有深度自回归网络123,贝叶斯网络45等,虽然可实现无损分解,但是时间成本更高。本文则提出综合利用两种因子分解:对于弱关联属性使用独立因子分解;对于强关联属性则使用条件因子分解,以此在准确率和时延之间找到一个最佳平衡。

本文提出的 FSPN 模型全称是 Factorize – Split – Sum –数据库系统工程师 Product Network,是一个基数据库于 SPN 树构建的模型python保留字。本文的核心创新点在于使用 factorize 节点对强 / 弱相关的属性集分别建模,同时使用 split 节点对强相关属性集内部进行建模。

整个模型分为工商银行三个部分:离线训练,在线分析,增量更新。从抽象的层级来看,功能如下:

  1. 离线训练接受输入表 TT 及其数据,训练出的模型记作 FTmathcal{F}_T,输出 PT(A)widehat{P_T(A)}
  2. 在线分析模块接受外部的查询 QQ,该查询作用在 TT效率 表上。调用模型 FTmathcal{F}_T ,输出 PT(Q)⋅∣T∣P_效率是什么意思T(Q)|T| 作为近似的基工龄越长退休金越多吗数估计。

构建 FSPN 树

本文先以一张单表 TT 的 FSPN 模型构建过程为例子。属性集记作龚俊 A={A1,A2,python123平台登录A3,A4}A={A_1,A_2,A_3,A_4},将 AiA_i 视作是 r.v,则表 TT 的基数估计问题可转化为求多元概率密度模型 p.d.f. P(A)P(A) 的问题。这里令 A3A_3A4A_4 是两个强相关属性,而 A1,A2A_1,A_2 则是弱相关属性,则属工商银行性集 AA 可被划分为弱相关属性集 W={A1,A2}W={A_1,A_2},强相关属数据库性集 H={A3,A4}H={A_3公司让员工下班发手机电量截图,A_4}

FLAT,一个轻量且高效的基数估计模型

将表 TT 视作是根节点 N1N_1,它将作为 factorize 节点:根据 H,WH,效率集W 两个属性集将表 TT 垂直数据库原理划分出了两个子表并建立子节点 N2,N3N_2,N_3

进一步划分效率的英文 N2N_2 节点:A1A_1A2A_2 属性互为弱相关,但非完全独立。对于python123平台登录 SPN 及衍生的模型6而言,可以通过合适的聚github中文官网网页簇 — 分片方式消弭弱相关关系,使得属性python是什么意思之间局部独立龚俊,这个过程被称之为 “上下文独立” ( context independent )。

比如,以宫颈癌 A2&lpython编程t;50A_2<50 作为分片条件,将 N2N_2 节点github直播平台永久回家的子表再github中文社区次划分为 T1,T2T_1,T_效率集2。在每个 TiT_i 内部,A1A_1A2A_2数据库软件 被认为 ( 局部 ) 独立。对 TiT_i 继续效率做垂直分片,可以划分出 L1,L2,L3,L4L_1,L_2,L_3,L_4 四个区域数据库软件,如图 2 所示:

FLAT,一个轻量且高效的基数估计模型

每一github开放私库LGitHubiL_i 只包含一个属性列,因此被称之为 uni-leaf 节点。可得:

P(A1,A2)=PT1公司让员工下班发手机电量截图+PT2=w1⋅公司让员工下班发手机电量截图PT1(A1)⋅PT1(A2)+w2⋅PT2(A!)⋅PT2(A2)bpython保留字egin{aligned} P(A_1, A_2) &= P_Go{T_1} + P_{T_2} \ &=w_1P_{T_1}(A_1)P_{T_1}(A_2) + w_2P_{T_2}(A龚俊_!)Ppython编程_{T_2}(A_2)\ end{alignpython是什么意思ed}

其中效率意识方面存在的问题wi=∣Ti∣/∣T∣w_i={|数据库设计T_i|} / {|T|}。从公效率公式式中可知 N2N_2sum 节点。

对于 N3N_3 节点,需要python怎么读计算 P(A3,A4∣A1,A2)P(A_3,A_4|A_1,A_2),即 P(H∣W)P(H|W)。本文提出github汤姆根据 WWHH 进行划分,假定划分出了子集 H1,H2,…H_1,H_2github官网登陆入口,… ,在同一个 HiH_i 内部,无需考虑 WW 的影响,此时可认为 P(Hi∣W)=P(Hi)P(H_i|W)=P(H_i) 。本文称这种方式为数据库查询语句上下文条件移除 contextuapython123平台登录l condition remov数据库设计alpython123平台登录。此时将 N3N_3 记作 split 节点。

在当前的例子中,A3,A4A_3,A_4 通过谓词 A1<0.9A_1 < 0.9 划分出了两个子PythonL5L_5L6L_6,并由此产生了两个新的包含多个属性列的叶子节点,被称之 multi-lea公积金f 节点。

FLAT,一个轻量且高效的基数估计模型

以上是完整的 FSPN 树构建过程,如下图 ( 对应原文 Figure 1 ) 所示:

FLAT,一个轻量且高效的基数估计模型

处理工龄差一年工资差多少外部查询

建模得到的 FTmathcapython怎么读l{F_T} 模型可以处理来自外界的查询 QQ。这里考虑的是范围查询,对于涉及到的属性 AiA_i,假设它的域为 [Li,Ui][L_i,U_i],则 QQ公积金身可以被看作是 hGitHubyper-rect效率的英文angle range:

Q={A1∈[L1,U1]∧A2∈[L2,U2],..github下载.Ak数据库∈[Lk,Uk]}Q={A_1 in [L_1,U_1] ∧ A_2 in [L_2,U_2],…A_k in [L_k,U_k]}

假设每个属性 AiA_i 的域是 [LBi,UBi][LB_i,UB_i],则 LBi≤Li≤Ui≤UBiLB_i ≤ L_i ≤ U_i ≤ UB_i。特殊地,对于等值查询,认为 Li=UiL_i=U_i。现有一个到达的 QQ 如下图 ( 见原文 Fi数据库有哪几种gure 2 ) 所示:

FLAT,一个轻量且高效的基数估计模型

按照模型,将 QQ 划分出两个等价子查询数据库 Q1Q_1Q2Q_2 。两个子查询可以视作和事件:

PT(Q)=PT(Q1)+PT(Q2)P_T(Q) =P_T(Q_1)+P_T(Q_2)

其中,PQ1(H∣W)P_{Q_1}(H|W)python语言数据库系统工程师 PQ2(H∣Wpython基础教程)P_{Q_2}(H|W) 分别可以从模型 FTm数据库软件athcal{F}_T N3N_3 节点的左右python怎么读两个github是什么 mul工龄越长退休金越多吗ti工资超过5000怎么扣税-leaf 叶子节点获得。而 PQ1(W)P_{Q_1}(W)P宫颈癌Q2(W)P_{Q_2}(W) 则可以通过模型的 N2N_2数据库管理系统 节点获得。最终,这个模型当中的 PT(Q)P_T(Q) 将是可计算的。展开可得:

PT(Qgithub是什么)=w1⋅PQ1(H∣W)⋅PQ1(W)+w2⋅PQ2效率符号(H∣W)⋅PQ2(W)P_T(Q)=w_1P_工资超过5000怎么扣税{Q_1}(H|W)P_{Q_1}(W) + w_2P_{Q_2}(H|W)P_{Q_2}(W)

模型更新

当新的数据 TDelta T 到达时,F效率计算公式LAT 可以自上而下地实时更新表 TT 对应的 FSPN 模型。模型的不同节效率是什么意思点将有不同的行为:

  1. factorize: 将 TDelta{T} 向下广播到各个节点。
  2. sum: 将 TDelta{T} 的每一条数据分发到相应的分片内。
  3. split:工资超过5000怎么扣税 类似 s数据库查询语句um 节点。
  4. uni-leaf: 在该叶子节点中,仅需要简单更新模型参数即可。可选用的方法有Python 1-D Histogram7,高github是什么斯混合模型等。
  5. product: 在更新模型后google,检查左右两部分的独立性是否被破坏。若否,则仅简单更新模型;否则,对该节点重新进行建模。
  6. multi-leaf: 在更新模型后,需要检效率英文翻译查左右两部分的独立性是否被破坏。工龄差一年工资差多少若否,则仅简单更新模型;否则,将该节点视作 split 节点,重新建模。数据库软件

离线建模

FSPN 的构造是一个递归的过程。每个节点本质上是四元组 (AN,CN,TN,O效率的拼音N)(A_N,C_N,T_N,O_N)

  1. TNT_N 表示当前节点所包含的数据,它又被称之为节点 NN 的上下文。
  2. ANA_NCNC_N 分别代表该节点的两组属性。如果 CN=∅C_N = varnothing,则该节点的建模过程可以用符号标记为 P(AN)P(A_N),反github官网之,则标记为 P(AN∣CN)P(A_N|C_N)。在 FSPN 模型中,根节点的 AN=A,CN=∅,TN=TA_N=A,C_N=varnothing,T_N=T。它代表的联合分布记为 P(A)P(A)
  3. ONOgoogle_N 代表了该节点的性质,即它属于:fact公积金orizesumgithub官网splituni-leafproductmulti-leaf 节点的其中一个。

本文使用 RDC8 方法 ( 全称 Randomized Dpython语言ependence Coefficient ) 对属性集 AA 内的所有工资超过5000怎么扣税属性 Ai,AjA_python123平台登录i, A_j 进行成对检验。这里设github中文官网网页定一个阈值 htau_h,若能成功分割出强相关属性集 HH ,则该集合并为非空集合。此时,属性集合 AA 被划分为 HHA数据库系统概论第五版课后答案−HA-H,并产生左右两个节点。

对于弱相关属性集的节点,特殊地,若 ∣AN∣=1|A_N| = 1 ,则该节点被划分为 uni-leaf 节点。uni-leaf 节点的概率模型可以使用简单的方法进行建模,比如 Histogram 方法。

否则,设定阈值 ltau_l 来决定 ANA_N 内部的属性之间是否独立。若是,则该节点可作为 product 节点;否则,将该节点设置为 sum 节点,通过聚簇方式 ( 如 K-means9 ) 切分多个子表以消除上下文的影响。在每个子表内,认为属性之间是局部独立的,再进而使用 product 节点进python保留字行组织。

对于 facto公司让员工下班发手机电量截图rize 节点划分出的右子节点,它的概数据库系统的核心是率模型记作 P(AN∣CN)P(A_N|C_N),即 CN≠∅C_python编程N ngithub开放私库eq varnothing。若 ANA_NCNC_N 集合相互独立,可被直接认为是 multi-leaf 节点,通过建立分效率集段模型 piecewise regression 得到 P(AN)P(A_N)

否则,python编程使用 d-way 分区方法对 TNT_N 做一步 split ,目前的节数据库管理系统点即为 split 节点。假定分出了子簇 T1,T2,github官网登陆入口…,TdT_1,T_2,…,T_d,随后通过 FLAT-Of公司让员工下班发手机电量截图fline 模型对每一簇进行建模得到 PTigithub下载(AN∣CN)P_{T_i}(A_N|C_N),其中 1≤i≤d1 ≤ i ≤d

多表基数估计

首先github官网是离线构建过程。将 DD 内所有的表根据它们的连接关系组织成一个效率计算公式树形结构,记作python编程 JJJJ 内部的每一个节点代表一张表,每一条边表示两个表的连接关系。

本文提出,高度相关的表能够划分到一个组 group 内,而组间的表是弱相关数据库的。以一条边 (A,B)(A,B) 为例子,系统首GitHub先从 A⟗BA ⟗ B 表中做取样,并检测两表之间是否存在高度相关的属性列。如果部分列之间的相关性高于某个阈值,则直接对 A⟗BA ⟗ B效率意识方面存在的问题 表 ( 记作 Tmathcal{T} ) 进行建模,或者称将 A,B{A,B} merge 为一个节点。

整个 merge 的过程将递归执行,直到没有再需要 merge 的节点为止。每一个节点 TiT_i 将表示单表,或者多表的全外连接。

其次是在线构建过程。令 E={T1,T2,…,Td}E={T_1,T_2,…,T_d} 表示某一个查询 Q工龄差一年工资差多少Q 所命中的 Jgithub永久回家地址J 树的所有节点数据库有哪几种QQ 将根据 EE 切分出对应的子查询 QiQ_i。在本文的假设当中,每个 Qpython语言iQ_iE=A1⟗A2⟗…⟗Apython123平台登录dmathcal{E}= A_1效率的拼音 ⟗ A_2 ⟗ … ⟗A_d 都是独立的,这意味着只需简单计算 ∏iP(Qi)prod_{i}P(Q_i) 即可得到 P(Q)P数据库系统概论(Q)

多表查询github汤姆对基数估计的影响

现假定有一个python安装教程 JJ 的结构数据库设计如下,A,BA,B 表被划分为同一个组:

FLAT,一个轻量且高效的基数估计模型

当存在一个 QQ 的谓词仅与表 AA 相关时,直接从 T1T_1 节点的 T1mathcal{T_1} ( 即 A⟗B A ⟗ B ) 进行查找。需要注意的是,在全外连接的过程中,由于 AA 表的记录可能会和 BB 表发生一对多连接,python编程从而产生更多的数据行,因此基于 T1mathcal{T_1} 表计算的基数被高估了。为了抵消这种影响,需要对估计到的基数进行下调 ( scale-down ) 修正。

FLAT,一个轻量且高效的基数估计模型

另一个例子则是:查询 QQ宫颈癌BBCC 相关,但两表并不在一个分组内,因此不能面向 B⟗CB ⟗ C 表进行基数估计。实际上,这会导致估计到的基数偏小,此时需要进行上调 ( scale-up ) 修正。

为了python可以做什么工作给基数修正github官网登陆入口留下足够的线索,本文提出:在原 Tmathcal{T} 表中新增名为 scaGottering coefficient 的额外属性列信息。

添加两个额外的列:SA,Bgithub中文社区S_{A,B}SB,AS_python怎么读{B,A}。其中,SA,BS_{A,B} 属性列表示:对于 AA 表的每github官网一条记录,BB 表可提供多少可供连接的行数,反之亦然。这两个属性列用于修正因连接非相关表 ( 对于 QQ 查询而言 ) 而需要下调工龄越长退休金越多吗效率的拼音数估计的情况。此外,本例还需新增一列 ST1,{T1,T2}S_{T_1,{T_1,T_2}},以应对 TCT_CTA⟗TBT_A数据库管理系统⟗T_B 进行连接的情况,以便进行基数上调。

表里的每一条数据可能同时需要进行上调 ( 记作 ee ) 和下调 ( 记作 ss ),则它满足查询 QQ 查询的概率被系数 e/se/s 修正。本文默认设定 eess 的最小值为 1 而非 0,原因是每python123条数据一定会在全外连接的表 T mathcal{T} 中出现至少一次,完整计算过程,见10

简而言之,scattering coefficient 列的数量和 DD 中的表数目成线性关系。对于连接树 JJ 的任意一个节点 TiT_i ,其 scattering coeffi效率英文翻译cient 列的各种信息将在构建 FSPpython123平台登录N 模型 FTimathcal{F}_{T_i} 时一同计算,见11

多表模型的更新

当节点 TiT_i 中的任意一张子表有新数据到达时,会导致 Timathcal{T_igithub中文官网网页} 更新数据。下面是一个简单的示例:

FLAT,一个轻量且高效的基数估计模型

效率符号 BB 表有新数工资超过5000怎么扣税BDelta B 到达时,它可以与原表 AA 产生新的连接关系,将这部分新增数据记作:F+Deltamathcal{F_+};而 Fmathcal{F} 表原有的数据也需要进行检查:有部分数据的 scatterin效率的拼音g coefficien宫颈癌t 列需要进行更新,记作 F∗Deltamathcal{数据库系统概论第五版课后答案F_*}。同时,原本没有连接关系的行可能已经失效,需要被及时删除,记作 F−Deltamathcal{F_-}。如下图所示:

FLAT,一个轻量且高效的基数估计模型

为了加速多表模型的更新过程,将 Tmathcal{T} 表的所有 scattering c工龄越长退休金越多吗oefficient 列记作 STS_{mathcal{T}},将数据库原理所有属性效率英文翻译列记作 ATA_{mathcal{T}} ,则概率模型 P(ST,AT)P(S_{mathcal{T}},A_{math工商银行cal{T}}) 可以被视为 split 节点,左右节点分别为 P(SA)P(S_{mathcal{A}})P(ST∣AT)P(S_{mathcal{T}}|A_{math效率集cal{T}})。对于左节点,可以直效率是什么意思接将增量数据 F+−F−+F∗Deltamathcal{F龚俊_+}-Deltamathcal{F_-}+Deltamathcal{F_*} 传播到 FSPN 模型,而 STS_{mathcal{T}} 的更新则是耗时操作,本文则选择通过异步方式进行更新,以此提高模型效率

性能对比

本文对已有python怎么读的其它方法进行对比:Histogram,Naru,NeoroCard ( Naru 在多表查询的拓展 ),BN,DeepDB,SPN-Multipython基础教程,MaxDiff,Sample,KDE,MSCN。Fpython怎么读SPN 的 RDC 阈值设定为 l=0.3tau_l=0.3 ( 低于此值认为独立 ),h=0.7tau_h=python是什么意思0.7 ( 低于此值认为弱相关 )。性能的评测指标选择广泛使用的 q-error。计算方数据库系统概论式为:

q-error=max{Card(T,Q)Card(T,Q数据库管理系统),Card(T,Q)Card(T,Q)}text{q-error}=max{frac{Card(T,Q)}{widehat{Card(T,Q)}},frac{widehat{Card(T,Q)}}{{Cardgithub官网登陆入口(T,Q)}}}

本文的算法基于 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 数据源:UCI Machine Learning Repository: Gaspython基础教程 sensor array temperature modulation Data Set

DMV 数据源:Vehicle, Snowmo效率bile, and Bo效率的拼音at Registrations – CKAN (data.gov)

对于每一个数据集,本文随数据库管理系统机生成了 1 万条查询,每个属性列被选择的概率均为 0.5。下表 ( 对应原文 Table 1) 展示了不同算法的 q-error 分布。

FLAT,一个轻量且高效的基数估计模型

总而言之,从准公司让员工下班发手机电量截图确率的角度分析,排名依次为:FLAT ≈ Naru12 ≈ SPN-Multi > BN >龚俊 DeepDB >> Sample/MSCN13 >> KDE14 >> MaxDiff/Histogram。细节如下:

  1. Naru 的高准确率源于它基于 AR 的分解方法,以及庞大的 DNN 网络。
  2. SPN-Multigithub下载 同样达到了一个高准确率,因为它抛弃了属性之间完全独立的假设。
  3. BN 和效率符号 DeepDB 的准确率逊色于 FLAT。BN 的性能受到了其结构的制约,而 DeepDB 似乎并不能很好地处理高度关联工商银行的数据集。
  4. MSCN 和 Sample 的表现并不稳定。考虑到 MSCN 是一个 query-d效率高发票查验riven 的模型,它的表现取决于查询负载和训练的查询样本是否足够相似。
  5. FLAT 的性能远超 Histogram,Ma工商银行xDiff 和 KDE:Histogram 和 MaxDiff 仅做了粗粒度的独立性假设;KDE 则无法有GitHub效地用核方法处理高维度数据 ( high-dimensional data )。

下方的图表展示了不同方法的Go平均延迟时间,为了公平起见,这里仅比较了基于github中文官网网页 CPU 的方法。排名依次google为:Histogram ≈ FLAT > MSCN > SPN-Multi/DeepDB > KDE/Sample >> 其它。

FLAT 在两个数据集的估计延时分别为 0.1ms 和 0.5ms,远超其它的方法。这证明了 FSPN 是高性能的数据库系统概论第五版课后答案模型。除此之外,效率英文翻译MSCN 在这里仅需要对 DNN 做一次前向效率意识方面存在的问题传播,因此也python基础教程取得了不错的成绩。

DeepDB,SPN-Multi,KDE 和 Sa数据库软件mple 需要 10ms 去处理每一条查询。DeepDB 和数据库系统工程师 SPN-Multi 同样是基于 SPN 的模型,而它们在本次测试中均构建出了约 800+ 个节点的树结构。而 FSPNgithub汤姆 使用了更加轻量,紧凑的模型,相比之下只构建了 200 个节点。额外的,KDE 和 Sample 需要大量的样本进行检测,这有损了它们的性能。

Table 1 还反应出 FSPN 模型的训练时间要比其它模型更小。这得益于 FSPN 的模型,同时又不需要像基于 SGD 的 DNN 训练那样需要迭代式的梯度更新。

多表工龄差一年工资差多少性能比较

本文使用经典的 IMDB 数据集测试多表查询的场景。同时,创建了包含了 7GitHub0 个简单查询的轻量级 JOB-light,以及包含 1500 个复杂查询的 JOB-weight。表 2 ( 对应原文 Tgithub下载able 2 ) 展示了各个估计模型在 JOB-light 查询集的表现情况。

FLAT,一个轻量且高效的基数估计模型

FLAT 在准确率方面仍有显著优势。从存储方面,FLAT 仅仅位列 Histogram 和 BN 之后。数据库软件但相较于工商银行单表情形,FSPN 模型变得十分庞大 —— 因为在多表情况下要构数据库有哪几种建 scattering coefficient 列并维龚俊护。

在 JOB-ours 查询集下,其它方法的性能发生了显著下降,但是 FLAT 仍然能够保持相对最佳的性能。下图 ( 对应原文 Figure 7 ) 表明了数据库有哪几种 FSPN 模型在两种工作负载下的查询延迟均在 5ms 左右,仅稍次于 Histogram 方法。

FLAT,一个轻量且高效的基数估计模型

更新性能

本文提取了 IMDB 前 80% 的数据用于训练模型,并用剩下 20% 的数据用于测试数据github汤姆更新的场景。如下表 ( 对应效率集原文 Table数据库系统的核心是 4 ) 展示:数据库系统概论

FLAT,一个轻量且高效的基数估计模型

再训练模型 ( retrained model ) 的准确率最高,而代价是最长的训练时间。由于增量数据导致概率密度发生变化,那些不支持更新模型的方法的准确率github下载在当前场景下是最低的。相比较而言,本文的 FSPN 模型在准确率和更新时延之间保持了良好的平衡。

结语

Go文提出了一个基于 SPN 的改进模型 —— FSPN,一个轻量且高效的无监督图模型。它最大的亮点效率符号在于可以灵活根据属性列之间不同的依赖程度 ( 独立,弱相关,强相效率是什么意思关 ),综合利用独立因子分解和条件因子github直播平台永久回家分解的思路进行建模,同时保证了系统的准确性和时效性。

不同场景下的对比实验均验证了 FSPN 模型的高效数据库查询语句性和稳定性,相信该模型在未来能够在数据库相关的工作效率是什么意思中充当更加重要的角色。

参考文献


  1. Shohedul Hasan, Saravangithub官网登陆入口an Thirumuru效率的拼音ganathan, Jees Aug数据库ustine, Nick Koudas,and Gautam Das. 2019. Multi-github永久回家地址attribute selectivity estimation using公司让员工下班发手机电量截图 deep lpython安装教程earning.In SIGMOD数据库原理.↩
  2. Zongheng Yang, Amog Kamsetty, S公积金ifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2021. NeuroCard: One Cardinality Estimat数据库设计or for All Tables. PVLDB 14, 1 (2021), 61–python123平台登录73.↩
  3. Zongheng Yang, Eric Liang, Amog Kamsetty, Chenggang Wu, Yan Duan, Xi Chen, Pieter Abbeel, Joseph M Hellerstein, Sanjagithub直播平台永久回家y Krishnan, and Ion Stoica. 2019. Deep unsupervi效率是什么意思sed cardinality estimation. PVLDB (2019).↩
  4. Lispython语言e Getoor, Benjam效率的拼音in Taska数据库软件r, and Daphne Koller. 2001. Selectivity estpython怎么读imation 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), 85python123平台登录2–863.↩
  6. Benjamin Hilprecht, Andreas Schmidt, Morgithub官网登陆入口itz Kulessa, Ale数据库系统的核心是jandro Molina, Kristian Kersting, and Carstpython安装教程en Binnig. 2019. DeepDB: learn from data, not from quergithub开放私库ies!. In PVLDB.↩
  7. P Griffiths Selinger, Morton M Astrahan, Donald D Chamberlin, Raymond A Lorie, and Thomas G Ppython语言rice. 1979. Access path selection in a relational database manag公司让员工下班发手机电量截图ement syste效率符号m. In SIGMOD. 23–34.↩
  8. David Lop效率集ez-Paz, Philipp Hennig, and Berngithub官网hard Schlkpython编程opf. 2013. The ran效率意识方面存在的问题domized dependence coefficient. In效率集 NIPS. 1–9.↩
  9. K Krishna and M Narasigithub汤姆mha 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, Apython怎么读ndreas Pfadler, Zhengping Qian, Jingren Zhou, and Bin Cui. 2020. FLAT: Fast, Ligpython编程htweight and Accurate Me效率高发票查验thod for Cardinality Estimatio效率集n [Technical Report]. arXigithub汤姆v preprint arXiv:2011.09022 (2020).↩
  11. Zhgithub汤姆uoyue Zhao, Robert枸杞 Christensen, Feifei Li, Xiao Hu, and Ke Yi. 2018. Rangithub汤姆dom效率意识方面存在的问题 sampling over joins revisited. In SIGMOD. 1525–1539.↩
  12. Zongheng Yang and Chenggagithub汤姆ng Wu. 2019. Github repository: naru projePythonct.githu数据库系统概论b.co效率的英文m/naru-projec… (2019).↩
  13. Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2019. Learned cardinalities: Esgithub中文官网网页timating cor数据库系统工程师related joins with deep learning. In CIDR.↩
  14. Luch Liu. 2020. Github repositpython安装教程ory: scikit-learn. github.com/scikit learn/spython编程cikit-le数据库arn (2020)效率意识方面存在的问题.↩

发表评论

提供最优质的资源集合

立即查看 了解详情