文献导读：Two-Level Sampling for Join Size Estimation

对连接结果大小的估计是查询优化中一个关键的步骤，中间结果大小是影响查询计划成本（CPU时间，I/O开销，分布式查询处理过程中的通信开销）的一个主要因素，数据库系统在查询时根据各种统计信息对连接结果大小进行先验估计。

对连接结果大小的估计目前主要有以下三种方法：

（1）在连接属性上为每一个表构建一个草图，同时忽略其他属性。

（2）在所有属性定义的多维数组中的数据上构建一个概要，采用信号处理技术（例如小波变换）对数据进行有损压缩。

（3）随机抽样方法。

本文提出的连接大小估计方法依旧是基于抽样进行的，作者总结了现有工作中抽样方法的不足，并利用各种方法的特点和优势提出了一种新的被称为两层抽样的方法，从而更准确的估计连接结果的大小。

本文对现有抽样方法进行如下分析：

1. Independent Bernoulli sampling.

特点：这是最简单的抽样算法，每个元组以相同的概率p独立采样。

不足：不考虑连接关系，估计不准确。

如下图例所示，表A和表B根据相同的连接属性b进行连接。分别对两个表以3/7的概率进行抽样，得到两表的样本分别为SA和SB。最后根据样本连接结果大小以及抽样概率p计算得到对两表连接结果大小的估计。

2. Correlated Sampling

特点：根据哈希函数h : [u] → [0, 1] 将连接属性值映射到[0,1]之间。若h(v)

不足：当每个连接属性上的连接结果不均衡时偏差较大。

如下图例所示，表A和表B在连接属性b=2，b=3时的连接结果大小远大于b=4时。

3. End-biased Sampling

特点：为每一个连接属性值v分配一个pv，取pmin(v)=min(av/KA，bv/KB，1)。av和bv是v在A，B表中的频数，KA，KB是人工分配的系数。若h(v)

不足：加入对频率的考虑避免漏掉连接结果较大的属性值，依旧无法避免不均衡的影响。

基于以上问题作者提出了两层抽样方法。

Level 1：确定被抽样的连接属性值。利用哈希函数，对于每一个连接属性v，以概率pv进行抽样。若h(v)

Level 2：对每个Level 1中选定的连接属性值对应的元组以概率q进行均匀抽样，同时，为避免Level 1中选定的连接属性值在Level 2的抽样过程中丢失，从每个连接值对应的所有元组中以等概率选一个元组使其Level 2概率为1（确保每个Level 1中选定的连接值对应元组在样本中至少出现一条）。

特点：

（1）考虑了数据的连接关系，避免两表样本中连接属性值不匹配带来的极大误差。

（2）通过第二层采样，减少样本中每一个选定的连接属性值对应的元组数，从而可以再相同的样本量前提下，使样本中涵盖更多不同的连接属性值，使样本更具有代表性。

（3）两层采样在操作上并不复杂，可以利用蓄水池抽样的方法在一次扫描数据的过程中完成。

以上内容及样例仅基于笔者对此文献的解读和梗概梳理，着重介绍了两层抽样的主要思想。对于两层抽样概率pv和q的计算，文中是以方差最小为优化目标，以样本量为约束条件通过最优化方法计算得到的，文中针对不同连接属性值频率已知和未知两种情况进行了讨论，对于未知的情况提出利用统计量来弥补信息的不足的想法也是值得借鉴的。

https://dl.acm.org/citation.cfm?id=3035921

“大数据与数据科学家”公众号

主编：王宏志

副主编： 丁小欧

责任编辑： 齐志鑫，宋扬

编辑： 陶颖安

-精彩内容，记得分享到朋友圈-