不一致弱可用数据近似计算可行性判定问题

刘雪莉 李建中

摘 要： 给定一个查询结果的一致性程度阈值，可行性判定判断不一致数据上查询结果的一致性程度是否大于给定的阈值。若不是，则查询结果对用户来说是没有意义的，此查询不可行。对于数据量大，查询开销较大的应用中，若是能在查询之前预估查询结果的准确度，则能在很大程度上节省查询的开销以及用户的时间。在查询密集型场景，判定查询的可行性具有重要的意义。查询可行性的判定等价于预估查询结果的一致性。本文采用抽样方法预估查询结果的一致性。抽样算法分别对一致的数据部分和不一致的数据部分采样，使得保证抽出的样本大概率下满足查询条件并且服从不一致数据的分布。 根据抽出的样本，本文给出了估计一致性程度的算法，证明了一致性程度的估计是渐进无偏的。

关键词： 不一致弱可用数据；聚集查询；上下界；近似

Abstract： When the consistency degree of the query results exceeds the user tolerable threshold the query results for the user is invalid. This query could be called not feasible. If the query can be estimated before implementation by a relatively small price the efficiency of query processing will improve greatly. It gets more gains for larger data sets and larger query overhead. This paper designs a sample method to estimate the query results consistency degree. The sample method take samples separately from consistent part and inconsistent part of inconsistent data by different sample strategy. Then based on the samples the consistency degree is estimated. It is proved that the estimate is gradually unbiased Also It is proved that the estimate is a＼ epsilon ＼ delta） estimate.

Key words： inconsistent weak available；aggregation query；upper and lower bound；approximate

引言

當查询结果的一致性较低时，查询结果对用户的指导意义随之降低。如果能在计算查询结果之前判断查询的结果是否有意义，就避免了在原始不一致数据上进行查询以及对查询结果估计的开销，尤其当数据量较大时，判定查询是否可行具有重要的意义。

由于查询和数据相关，数据的不一致性程度对不同的查询具有不同程度的影响。显然，若是生成查询结果的数据在整个数据集中是一致的，则数据的不一致性程度对此查询结果的一致性并没有影响。此外，即使生成查询结果的数据是不一致的，其结果也可能是一致的。这为预估查询结果的一致性带来了挑战。首先需要确定查询结果的一致性是否受不一致数据的影响。其次，若查询结果的一致性受到了不一致数据的影响，如何预估其影响程度，即预估查询结果的一致性。

本文采用抽样方法解决了合取查询上的上述问题，主要贡献如下：

（1）类似于一致性查询中一致性查询结果的定义，本文中定义了查询结果的强一致性：若查询结果是一致的，查询结果满足不一致数据的所有修复。即对不一致数据的任意一个修复，在该修复下进行查询，一定包含一致性的查询结果。此外，还定义了查询结果的弱一致性：通过一个查询结果满足修复的比例来定义查询结果的一致性。

（2）给定一个查询，当查询不满足其结果的一致性与不一致数据无关的充分条件时，本文设计了基于抽样的算法预估查询结果的一致性。抽样算法分别对数据集中一致性和不一致性的数据部分分别采样，最后通过对样本进行查询结果一致性计算，估计查询结果的一致性。

（3）本文证明了估计的无偏性以及其置信区间，即给定一定的样本，估计的误差率不超过一定的范围。

（4）实验验证了算法的有效性。

1 问题形式化定义

首先定义合取查询。合取查询包含查询处理中的3种最基本的操作：选择、投、等值连接，均为查询处理中最常用到的查询类型，其形式化定义如下。

4 多表查询

多表查询涉及到多表连接，其基本思想同2表查询相同。需要做如下处理。

在数据预处理阶段，假设一个表A的2个属性C，D分别与其它表的属性做连接，研究中在对其统计连接属性值时，对C，D值做联合处理，即若有一条元组其C属性为c，D属性为d 则对（c，d）做统计。在抽样阶段，对A表进行抽样时，先抽取（c，d）的概率，接着按q抽样。其余处理保持不变。

5 实验分析

实验测试中使用了多种采样方法，内容展开如下：

（1）使用伯努利抽样方法对整个数据集抽样，不区分一致数据和不一致数据，记为Bernoulli1[2]。

（2）使用伯努利抽样方法对一致性数据进行抽样，使用蒙特卡洛抽样不一致数据集，记为Bernoulli2。

（3）使用相关采样方法对整个数据集抽样，不区分一致数据和不一致数据，记为Correlated1[3]。

（4）使用相关采样对一致性数据进行抽样，使用蒙特卡洛抽样不一致数据集，记Correlated2。

（5）使用end-biased[4]采样对整个数据集抽样，不区分一致数据和不一致数据，记为End-biased1。

（6）使用end-biased采样对一致性数据进行抽样，使用蒙特卡洛抽样不一致数据集，记为End-biased2。

（7）使用两层采样方法对整个数据集抽样，不区分一致数据和不一致数据，记为Two-Level1。

（8）使用两层采样方法对一致性数据进行抽样，使用蒙特卡洛抽样不一致数据集，记为Two-Level2。

为了验证估计算法的效率，测试过程中还实现了根据原始数据计算查询集合的一致性，记为Batch。

每次实验重复采样过程500次，计算其和真实结果一致程度的相对误差，实验图返回最终的平均值。

5.1 数据集

实验采用TPC-H数据集测试预估算法的性能。其中，规则集合＼Sigma采用TPC-H中已有的主键约束。此外，研究加入20个常数函数依赖。TPC-H数据集的规模因子设为10。由于实验涉及到不一致数据，因此就在TPC-H数据中人工注入不一致信息，对于主键约束，随机追加一些元组使其与主键约束相违背，针对常数函数依赖，修改元组的属性值，使其出现不一致信息。2种类型注入不一致信息，数量比值为10∶1。注入不一致信息的规模从数据规模的5%到20%，每次递增5%。

为了分析数据偏斜对预估结果的影响，研究重新生成了lintitem表，使其服从Zipf分布。其中，偏斜的程度受Zipf的参数＼alpha的影响，则使其从0变化到2 每次变化0.5。Zipf分布导致有少量的供应商提供了大量的产品，大量的供应商只提供了很少的产品。

查询的设计包括2种类型：两表连接和三表连接。其中，两表连接涉及到表lineitem和supplier，连接属性l＼_suppkey = s＼_supperkey。选择操作为discount=x和shipdate=y，投影操作包含2种类型。一种是投影所有的属性，即查询不涉及到投影操作；另外一种投影lineitem到l＼_suppkey和quantity属性，supplier到name和address属性。三表连接设计到表customer＼Join^borders＼Join^b，前2个表在custkey上做连接，后2个在orderkey上做连接。选择操作为nationkey=z，discount=x和shipdate=y。投影为在customer上投影l＼_suppkey 和nationkey，lineitem上投影l＼_suppkey和quantity，order上投影orderkey和totalprice。

5.2 实验脉络

实验从以下几个方面验证了抽样预估的性能，分别涉及两表查询和三表查询。详情内容分述如下。

（1）通过比较抽样预估与查询结果后估计一致性验证了抽样预估的效率。

（2）抽样算法的相对误差。

所有实验均在一台频率为1.90 GHz的4核CPU，内存32 G的机器上运行，不一致数据集的抽样在Matlab軟件上研究呈现，其余所有的算法使用C++实现。

5.3 抽样预估的效率

首先通过与Batch算法的比较，测试了抽样方法估计查询结果一致性的效率。设不一致数据占数据集的比例为5%，分别在2个表以及3个表的查询上设计测试。测试了当抽样样本的规模为原始数据的0.03%、0.05%、0.1%、0.5%、1%时估计算法的运行时间。需要注意的是，这里并不考虑抽样时间和数据预处理时间。

实验结果如图1和图2所示。从图1中可以分析得出如下结论：

（1）抽样预估的时间要远远小于Batch算法的时间，此处验证了使用抽样预估准确率的可行性。即，可以在较小的时间内预估查询结果的一致性，若一致性过低时，避免了在原始数据上的查询及一致性计算。具体地，当样本数据从 0.0%增至1%时，估计算法比Batch算法快了9～80倍。

（2）Bernouli预估的时间要小于其他抽样预估的时间，是因为 Bernouli产生的样本是均匀随机的，相同样本量下生成的结果集要小于其它采样方法，但相对误差较高，将在下一组实验中进行说明。

（3）对不一致和一致数据进行分别采样的估计算法时间要略高于统一采样的时间，因为统一采样时，不一致数据由于其占据的比例较低，获选采到的可能性较小，其计算一致性多花费的时间较少。

（4）Two-Level采样预估的时间要高于其它抽样算法，这是因为Two-Level算法采样的结果集满足查询条件的大小要超过其它采样方法，使得计算结果集以及计算一致性的时间增大。

（5）三表查询的执行时间要高于两表查询。

（6）随着抽样样本的增多，估计的时间也随之增加。

图2的结果与图1的结果保持一致。

5.4 抽样预估的有效性

固定不一致的数据比例不变，同样变化样本规模，从0.03%、0.05%、0.1%、0.5% 到1% 接下来将分别在两表查询和三表查询上测试抽样方法，预估查询结果一致性的相对误差。实验结果如图3和图4所示。

从图3的运行结果可以推得如下研究结论：

（1）对不一致和一致数据进行分别采样的估计误差要低于统一采样的误差。总地来说，平均要高25%。因为统一采样时，对不一致数据的采样并不符合不一致数据的分布，降低了估计一致性的准确率。

（2）Two-Level采样预估算法的相对误差要低于其它采样方法的相对误差，这是由于Two-Level采样能够更准确地估计查询结果。

（3）采樣方法的误差最大不超过20%，各种抽样方法的误差对于两表查询，都是可以接受的。

（4）随着抽样样本的增多，抽样误差随之减小。当抽样在1%时，所有的抽样算法都具有较好的准确率。

同上，由图4不难得出实验分析结论可见如下：

（1）对不一致和一致数据分别采样的估计误差平均低于统一采样的误差，基本可达20%。

（2）Two-Level采样预估算法的相对误差要低于其它采样方法的相对误差，对于其它不同的采样方法，准确率高出20%到35%。

（3）三表查询的相对误差要高于两表查询的相对误差，这是因为随着查询连接表的增加，查询结果估计的误差随之增加。但是Two-Level2抽样估计算法依然具有较好的准确率，其相对误差在15%之内。

（4）同图3的结果一致，随着抽样样本的增多，抽样误差随之减小。

6 结束语

本文提出了一种基于抽样的算法，预估了不一致数据集合取查询的结果一致性。该算法对不一致数据集合和一致性数据集合分别采样：对未知分布的不一致数据采用MCMC抽样方法 对一致性数据采用两层抽样方法。 两层抽样方法能够很好地估计查询结果，MCMC抽样保证了抽取的不一致数据服从不一致数据在整个数据集中的分布。采用该采样方法，证明了查询结果不一致估计的渐进无偏性。并使用中心极限定理给出了误差的保证。此外，实验验证了预估一致性的可用性以及其相对误差在涉及到3个表的查询时，误差率低于20%。

参考文献

[1] CHEN Yu YI Ki. Two-level sampling for join size estimation[C]// ACM International Conference on Management of Data. Chicago USA： ACM 2017：759-774.

[2] CARLITZ L. q-Bernoulli numbers and polynomials[J]. Duke Mathematical Journal 1948 15（4）：987-1000.

[3] LIPTON R J NAUGHTON J F. Query size estimation by adaptive sampling （extended abstract）[C]//PODS′90 Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems. Nashville Tennessee USA： ACM 1990：40-46.

[4] ESTAN C NAUGHTON J F. End-biased samples for join cardinality estimation[C]// International Conference on Data Engineering. Atlanta GA USA： IEEE 2006：20.