细微处见匠心—2018 SIGMOD论文之SQL领域解读

小蚂蚁说：昨天日照带来的《

关于数据库顶级会议 SIGMOD 2018，这可能是“最”有看点的一篇了！

》反响热烈，还没关注的同学们可以先回顾一下昨天的内容。今天的内容将从“传统SQL”方向切入，带您一同解读SIGMOD顶会中传统数据库领域的前瞻性研究。

接下来几天，OceanBase公众号将为大家持续带来SIGMOD系列论文解读，以下是精彩预告：

1.人工智能新时代—从 2018 SIGMOD 看蚂蚁OceanBase智能化

2. Joining the best—2018 SIGMOD论文之JOIN系列

3. 新硬件的舞台—2018 SIGMOD论文之硬件发展下的数据库系统

本文作者：柏泽

现任蚂蚁金服OceanBase团队资深技术专家，负责OceanBase的并行查询和新一代OLAP引擎。曾就职于美国Oracle公司，负责Oracle数据库并行查询研发工作并有多项专利申请。

2018年的SIGMOD会议于6月12-14日在休斯顿举行，这也是SIGMOD这个数据库领域的顶级会议第一次在这个南方石油城召开。今年会议中发表的论文很多都在Machine Learning和人工智能与数据库的结合上做文章，传统领域的文章相对较少，研究的课题相对都比较具体，有较好的实用性。

笔者有幸参加了这次会议，在这里跟大家分享一些传统数据库领域的文章，希望能给大家传递到数据库领域的一些最新研究。

查询改写方向

Joins over Union All queries in Teradata

Teradata的这篇论文里面介绍了他们实现的一个比较具体的工程优化，对union all的结果参与join的查询，可以把join下推到union all的分支里面去。如下的查询：

SELECT a1, a2, a, cFROM t1, t2, (SELECT a3, c3 FROM t3 WHERE b3=3

UNION ALL

SELECT a4, c4 FROM t4 WHERE b4=4) dt(a, c) WHERE c1=c2 AND d1=a;

可以把d1=a这个条件分别下推到union all的两支，用t1表去和各个分支去做join，这就是一种可能。这显然是一个要基于代价去做的决定。围绕这个问题，在论文中一共提出了如下几点考虑：

join pushing：连接下推，把关系，或者关系的连接下推到union all的分支中

branch grouping：把某些union all的分支聚在一起，然后再去处理join，搜索空间比较大，采用了一些经验和规则去决定

iterative join decomposition：对于join有多列条件的，可以分别每次join一列，或者有索引的，可以先和索引join再和基表join

geography adjustment：根据数据的分布调整一些策略，以减少数据的重分布

multisource join：进行多表连接，可以缓解因为join push和decomposition带来的增加join算子数量的问题，例如在同一个hash表被多次创建的情况下，用multisource join可以做一次的多表连接

在代价模型的参与下，可以较好的判断出何时下推以及如何下推，从而可以更好的执行这种类型的查询。这个优化的点，对于相关的优化器的实现有一定的参考意义。

近似查询方向

Verdict DB: platform independent AQP system

近似查询在近些年是个比较热门的话题，今年SIGMOD上，Verdict DB带来了自己的一个解决方案。鉴于各大数据库厂商对于修改内核支持近似查询的动作不是很快，他们提出了一个基于采样来建立采样表，然后将查询改写为对于采样表的查询，最后再把结果做一定的处理，例如对于sum的操作会做相应的scale等等，把近似查询结果返回。这个方案是以一个中间件的形式，对接各个数据库，创建采样表，从而支持一些查询的改写可以去做近似查询。基本的架构如下图所示：

目前主要支持的查询有：

这个方案的好处在于可以不用修改数据库的代码，就能够执行近似查询，还是有一定的价值。

老牌厂商新动向

RAPID -- In-Memory Analytical Query Processing Engine with Extreme Performance perWatt

Oracle Labs做的一个基于专用的数据处理芯片的SQL执行优化框架，基本的思想是通过实现专用的DPU（Data Process Unit），在芯片上实现相应的数据库常用算法，例如tablescan，filter操作，group by操作，top-k操作，以及window function， 数据分区(partitioning)， hash join等，通过将相应的操作和数据offload到专用的DPU芯片上来达到查询优化加速的目的。

设计的思路类似于采用GPU加速的设计思路，不同之处在于设计了专用的DPU，为数据库的一些常见操作做了更好的支持。在整个的设计中，强调了软件和硬件协同设计的思路，采用内存数据存储，列式存储格式和向量处理的方法，充分利用现代硬件的一些特性，提高性能。在软件实现层面，通过采用并行算法，向量处理算法和适应新算法的代价模型，对查询性能进行提升。从论文中提供的数据来看，同样能耗下，新的算法在DPU上的执行效率比对比测试系统高出10x以上，在纯软件实现的情况下，性能也有2.5x的提升。

从Oracle方面了解到的信息来看，专用的硬件前途不是很确定，软件实现的这些算法，对某些算子进行向量处理的引擎，不会在Oracle本身的内核中集成，但是很有可能会集成到未来MySQL的版本中。

并行执行优化方向

Submodularity of Distributed Join Computation

这篇论文提出了一个在并行执行inner join算法的时候，因为数据倾斜带来的执行长尾和执行资源浪费的问题。并行join，最常见的一种做法是用hash/hash的方式将两表的数据做重分布然后做hash join，显而易见，当左右表存在数据倾斜的情况时，具有大量相同值的行会被reshuffle到同一个worker上去执行，这个问题也已经有过很多的研究，基本的思路就是通过将相关倾斜数据复制多份分组的方式，打散到多个worker上去执行，用增加计算总量的方法，来减少整体计算时延。常见的方法有broadcast一边到所有worker和partition另外一边，或者 BKS算法，基于hypercube的算法将重复值比较多的行，以一定的公式复制到若干个worker上，这些worker将负责某一个重复值比较多的行的join操作，等等。

本文在分析现有这些解决方法的基础上，提出了一个新的算法，叫ExpVarTri，一个简单贪心的策略。同时提出了一个代价模型，能够量化复制多份数据和减少执行的不均衡间的代价，从而能够达到平衡和最优的策略。SimpleGreedy的算法如下：

在此之后，通过传统代价模型，计算不同分组情况下的join执行代价，不断迭代，找到最优的分组情况，整个模型算法如下：

作者称在使用了他们的代价模型后，原本的几种解决join skew的方案性能都有提升，而他们自己提出的这种SimpleGreedy的算法，效果是最好的。相关实验数据如下：

这个对于实现并行查询解决join skew问题有比较好的参考价值。

主流存储结构优化方向

SuRF: Practical Range Query Filtering with Fast Succinct Tries

这是今年的best paper。论文主要从当今流行的LSM存储架构出发，提出了一种有效的能够同时做范围和点查询过滤的数据结构，Fast SuccinctTrie。目前在LSM架构中使用的比较多的就是bloomfilter。Bloom filter对于点查询的过滤性毋庸置疑，但是在面对范围查询时，bloom filter就无能为力。

本文提出的Succinct Range Filter，是一个能够提供快速的点查询，范围查询以及近似的count查询的比较精简的过滤器。他采用LOUDS(Level OrderedUnary Degree Sequence)方式编码，采取了共用结构比较多的层使用稠密编码以及往下到叶节点的几层采用稀疏编码的混合编码方式，以10个bit编码一个节点的代价构建了SuccinctRange Filter。混合编码的一个示例图如下所示：

在具体的filter实现上，通过对Trie做截断然后添加不同方式的后缀的形式，实现了Base SuRF，在Base的基础上添加额外hashkey作为后缀的SuRF，在Base的基础上额外添加真实的key作为后缀的SuRF，以及一种Mixed的SuRF，可以根据参数调节额外存储的hashkey和realkey长度，Hashed Key SuRF和Real Key SuRF可以看作是mixed SuRF的两种极端情况。

LOUDS FST支持如下几种基本操作：

• ExactKeySearch(key): 查找一个单值

• LowerBound(key): 返回指向最小的满足k ≥ key条件的iterator

• MoveToNext(iter): 移动iterator到下一个值

在此基础上，SuRF实现了如下操作：

build(keyList): 构建过滤器

result = lookup(k):

iter, fp_flag = moveToNext(k):

count, low_fp_flag, high_fp_flag = count(lowKey,highKey)

在此基础上，可以实现get(key), seek(lk, hk)以及count()的操作。所以相印的点查询，范围查询操作全部通过先经过SuRF结构，判断是否需要访问相应的块数据，从而减少大量的不必要的IO操作。论文展示了使用Hashed Key suffix和Real Key suffix的SuRF与经典的bloom filter方案的过滤技术的比较，结果也证明了设计的理论，在点查询的场景中，bloomfilter的方案吞吐量会显著优于SuRF的方案，但是因为SuRF的false positive rate不会太高，所以单个操作的IO还是可以接受的。在范围查询场景下，SuRF能够起到更好的过滤作用，基于Real Key的SuRF方案的吞吐量和IO都会是最优的。

SuRF提出了一种比较少内存占用的过滤方案，能够很好的解决传统bloom filter不能解决范围过滤的问题；与此同时，在点查询场景下不会比bloomfilter的方案差太多。为了对用户不同场景有所侧重，提出了基于Hashed Key和Real Key后缀方案的SuRF结构和MixedSuRF结构，可以对不同的用户场景尽量做到更好的效果。对于使用LSM存储结构的系统，是一个较好的参考。

关心OceanBase的小伙伴们可能知道，OceanBase的存储架构也是基于LSM Tree的哦~

精彩预告

是不是还觉得意犹未尽？后面的几天时间里我们还将为大家持续带来SIGMOD系列论文解读，以下是精彩预告：

1.人工智能新时代—从SIGMOD看蚂蚁OceanBase智能化

2. Joining the best—2018 SIGMOD论文之JOIN系列

3. 新硬件的舞台—2018 SIGMOD论文之硬件发展下的数据库系统

欢迎大家关注OceanBase公众号，持续关注SIGMOD2018独家报道！

想了解更多 SIGMOD 2018大会看点？

想跟本文作者柏泽深入交流吗？

想认识蚂蚁金服OceanBase团队的一线技术专家吗？