Deep Upsupervised Cardinality Estimation 解读(2019 VLDB)

Deep Upsupervised Cardinality Estimation

  • 本篇博客是对Deep Upsupervised Cardinality Estimation的解读,原文连接为:https://dl.acm.org/doi/pdf/10.14778/3368289.3368294
  • 本文介绍了如何使用深度自回归模型(如:MADE、transformer)来进行基数估计的任务(利用模型训练拟合数据分布)
  • 特征:
  • 使用autoregressive model,无监督学习
  • 没有独立性假设
  • 支持范围查询

选择性(基数)估计问题定义

  • selectivity——选择度。本文针对的是给定谓词,估计其可以估计数据表中满足该谓词的元组的比例,有如下定义:sel%28%5Ctheta%29%3A%3D%7C%5C%7B%5C%20x%20%5Cin%20T%20%3A%5Ctheta%20%28x%29%3D1%5C%7D%7C/%7CT%7C
    其中分母T就是表的总行数,分子是满足选择谓词的行数。

选择性与数据联合分布的关系

  • 文中给出联合分布(joint distribution)的定义:
    P%28a_1%2Ca_2%2C...%2Ca_n%29%3A%3Df%28a_1%2Ca_2%2C...%2Ca_n%29/T
    其中分母T仍表示表行数,f为满足a1,a2…an条件的行数。因此实际上联合分布和选择度有着十分紧密的联系(基本一致)。同时联合分布还可以通过因式分解(factorization)写成:
    P%28A_1%2CA_2%2C...A_n%29%3A%3D%5Chat%7BP%7D%28A_1%29%20%5Chat%7BP%7D%28A_2%7CA_1%29...%5Chat%7BP%7D%28A_n%7CA_1%2CA_2%2C...A_%7Bn-1%7D%29
    这个公式没有做任何独立性假设,并且保留了属性之间的相互关系,所以要得到一个比较准确的选择度,实际上需要建立一个可以计算上述公式的模型。

深度自回归模型如何计算joint distribution

  • 作者选用Autoregressive Model进行对数据联合分布的拟合。以某一列为例。对于一列数据的分布,模型的input为前几列值的组合(因为是条件概率),输出的是在前几列的条件下,改列的分布概率。例如一张表travel_checkins含有三个属性:city、year、stars。给定一行作为输入::
  • 0%5Crightarrow%20M%28city%29
    E_%7Bcity%7D%28Portland%29%5Crightarrow%20M%28year%29
    %28E_%7Bcity%7D%28Portland%29%5Coplus%20E_%7Byear%7D%282017%29%29%20%5Crightarrow%20M_%7Bstar%7D

上式的三个输出依次是条件概率:%5Chat%7BP%7D%28city%29%2C%5Chat%7BP%7D%28year%7Ccity%29%2C%5Chat%7BP%7D%28star%7Ccity%2Cyear%29

  • 下图显示了模型工作流程的简化表示
    image

编解码策略

在训练模型时,我们必须将数据表中的每个元素编码成机器可以理解的语言。当模型输出时,我们必须对编码进行解码以获得各种概率。下面介绍作者提出的编解码策略。

  • small-domain:
  • encodding:one-hot
  • decoding:一个全连接层FC(F,|Ai|),其中F为隐藏层大小,|Ai|第i列的值域大小。输出一个长度|Ai|的向量,每个元素表示位于该值的概率。
  • large-domain:
  • encodding:Embedding,通过词嵌入将各值映射为一个固定长度h的向量
  • decoding:Embedding reuse。当属性值域太大时,向上面一样使用一个全连接层产生一个非常长的向量,这在空间上和计算复杂度上都十分低效。在这里作者提出Embedding reuse,同样使用一个全连接层FC(F,h),其中F还是隐藏层的大小,h为Embedding规定的向量长度,这样神经网络就会生成一个长度为h的向量H,接着通过计算HE_i%5ET并对其进行标准化处理,我们就能得到一个代表选择度的度量值。

具体实现

本文提供的方法支持点查询和范围查询,一般来说sel%3DP%28X_1%5Cin%20R_1%2CX_2%5Cin%20R_2%2C...X_n%5Cin%20R_3%29

  • 点查询,即等价查询,将上式转化为:sel%3DP%28X_1%3Dx_1%2CX_2%3Dx_2%2C...X_n%3Dx_3%29
  • 范围查询:对于范围查询,本文采用渐进抽样的方法对数据表进行抽样,估计概率
  • wildcard-skipping:这里提到的通配符不是指like查询,而是指age = any,也就是age可以为任何值,即范围查询age = [0, Di]。所以这里提到的通配符是为了满足有些条件没有filter的处理。
    为了达到这个目的,作者设计了特殊的token,Xi = MASKi,如age这一列的token为MASK_age。训练的时候,会把每一列用这个token替换掉,进行训练(这样就需要训练n次?n为列的个数,相当于数据被复制了n份,每一份把一列的值替换为token)。
    实际操作的时候,会随机sample一个tuple,age对应的值换成MASK_age,表明age取所有值,其他值的条件概率就是当age取所有值的情况下,其条件概率为多少,作为label。至于sample多少条数据,这个要看具体效果了。
    另外要根据实际的query确定哪些列需要有这个通配符。再举个具体的例子,一个表有三列a b c,查询为a=1,那么模型训练的时候必须要有b=MASK_b,c=MASK_c,查询的输入为a=1, b=MASK_b,c=MASK_c。再如a<10,一种方法是sampling,还有一种方法是模型训练的时候要有a=MASK_a, 这样查询的时候输入是a=MASK_a, b=MASK_b,c=MASK_c,a的输出会得到所有的值,再把<10对应的值的概率加起来。
    所以,这个通配符是非常有用的,因为在真实查询中,不可能保证所有列上都有条件,那么没有条件的列就用通配符替代。当然也可以用sampling的方式,但是通配符的查询效率更高。

属性顺序

从上面的分析中可以看到每列实际上是有顺序的,比如模型的输入是列a b c,输出是条件概率,既然是条件概率,那么b的概率是给定a得到,c的概率是给定a和b得到。所以这个顺序要提前定好,如果查询是b=1 a=2,需要把顺序调整成a=2 b=1输入到模型。

均匀和渐进式采样

两种sampling策略是为了解决范围查询的选择度估计问题。
假设一个范围查询字段R%3DR_1%5Ctimes%20R_2%20%5Ctimes%20...%20%5Ctimes%20R_n,如果用等价的方法来处理这个问题,在一些更糟糕的情况下,查询字段可能会很大(比如可能是%7CA_1%7C%5Ctimes%20%7CA_2%7C%20...%20%7CA_n%7C),这样很费时又占空间——消耗。为了解决这个问题,本文尝试了两种解决方案:

  • uniformly sampling
  • 从R(查询域)中均匀随机抽样出x%5E%7B%28i%29%7D,接着将该x%5E%7B%28i%29%7D输入模型,计算出该样本在数据表中的概率:%5Chat%7Bp_i%7D%3D%5Chat%7BP%7D%28x%5E%7B%28i%29%7D%29,基于朴素蒙特卡洛,对于S个样本,我们可以将%5Cfrac%7B%7CR%7C%7D%7BS%7D%5Csum_%7Bi%3D1%7D%5E%7BS%7D%5Chat%7Bp_i%7D作为期望密度的无偏估计。简单来说,该方案是将点随机扔到目标区域R中,以探测其平均密度。
  • 均匀采样的缺点:考虑这样一个情况,数据表T有n个属性列,但每一列的数据都非常倾斜,有99%的数据只集中在前1%的值域中,剩下1%的数据分散到后99%的值域内。在这种情况下,如果我们想进行值域前50%的范围查询。通过随机抽样我们大概率只能抽到1%-50%内的数据,计算出的结果会严重失真。如果要保持准确性,我们必须抽1/%280.01/0.5%29%5En%3D1/0.02%5En个样本才能都取到数据高密度区域。真实的数据集中,这样倾斜的数据常有出现,当均匀抽样遇到这样的数据会很快崩溃,产生非常大的误差如下图左,这里我们使用下文提出的渐进采样来决绝该问题。
    image
  • progressive sampling
  • 渐进式采样。在均匀抽样中,我们在查询域中随机选择一组样本。但实际上,我们可以更有选择性地挑选样本。具体来说,我们可以使用模型生成每个属性的概率分布,同时根据生成的概率分布进行采样。因为采样是逐渐进行的,所以称为渐进式采样。通过渐进式采样,我们可以轻松地对数据密度高的区域进行采样,如上图右侧所示。进行如下操作:
    image

(*^▽^*)
(*^▽^*)
(*^▽^*)
(*^▽^*)
(*^▽^*)

作者的解读并不简单。如果有帮助,请给作者点个赞(*^▽^*)
欢迎与作者交流相关问题!

版权声明:本文为博主茶柒每天要学习原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/Y_HEyEwuyuE/article/details/123264173

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
社会演员多的头像社会演员多普通用户
上一篇 2022年3月4日 下午5:09
下一篇 2022年3月4日 下午5:28

相关推荐