犀牛鸟视野｜现场报道 SIGMOD 2019数据库领域顶级会议 (上篇)

ACM SIGMOD/PODS 2019 数据管理国际会议6月30日到7月5日在荷兰首都阿姆斯特丹召开。会场位于阿姆斯特丹市的一座建筑Beurs van Berlage，在1896年至1903年期间曾是证券和商品交易所，现在用来举办音乐会、展览和会议。每年SIGMOD大会都会吸引来自全球各国的数据库领域牛人大咖参会交流，这将是一场精彩纷呈的数据库领域研究分享及交流切磋的盛会，今年大会全球有超过1000名与会者，美洲占 35%、欧洲占 44%、亚洲占 20%。

SIGMOD 2019会场建筑-Beurs van Berlage

SIGMOD 和 PODS 都是数据库领域的顶级会议，从 1991 年开始二者一直是一起举办。相对而言，PODS 更侧重于数据库的理论研究。与此同时，会议期间还有很多的专题 Workshop，它们大多也是有很多年历史的学术活动，例如专注于数据管理领域的 AI 技术应用的 aiDM，侧重于新硬件上的数据管理技术的 DaMoN，关注数据管理中的端到端的机器学习的 DEEM。也还有金融和经济数据集宏观模型的数据科学会议 DSMM、图数据管理和网络数据分析的联合会议 GRADES-NDA、人机共生（Human-In-the-Loop）数据分析会议 HILDA、语义大数据会议 SBD 等。

当然，会议的重头戏还是 SIGMOD 和 PODS，集中在中间的四天举办。PODS 今年Keynotes 是关于差分隐私（Differential Privacy）的研究，它可以追溯到几十年前的统计数据库研究，此类研究实际上也用到了很多统计算法。同时，今年大家关注的SIGMOD 的 Keynotes主题为“Responsible Data Science”，由来自加利福尼亚大学的Lise Getoor教授分享，主要研究如何解决数据技术的复杂依赖和非确定问题，如何解决道德和社会性问题，涉及到算法技术、社会科学等以及很多统计原理，例如数据的关联性和因果性等。

SIGMOD Keynote：Responsible Data Science

SIGMOD 第一天的日程很满，除了 Keynotes 和 Panel 之外，分为三个研究主题，以及一个工业主题。研究主题分别涉及数据库领域的热门研究方向：查询处理和查询优化、隐私/区块链、信息抽取。午餐期间还公布了会议的奖项，看到了 Facebook 数据库的熟人 Mark 的名字，也发现了学术大牛 Andrew Pavlo 等的身影。

特别值得关注的是，工业主题中有来自腾讯和北京大学合作发表的论文“PS2: Parameter Server on Spark”，在 Spark 上实现了一个工业级别的参数服务器。

我们重点关注了查询处理和优化主题，下面将做一些简要总结。

1.1 Cache-oblivious High-performance Similarity Join

相似连接（similarity join）及其类似的近邻连接（k-nearest-neighbor join）是非常重要的数据库连接操作，常用于高效的聚类、异常检测或者大量数据的分类。很多现有方案并没有为运行在多核系统上、有复杂内存层级的系统进行优化。该论文提出了一种优化方案，进一步提高了缓存局部性，进而提升了性能。

现代多核系统包含了很深的Memory层级，包括RAM、CPU缓存以及寄存器。作者提出了一种新的空间填充曲线FGF-Hilbert curve，对于每次迭代都有常量的空间和时间复杂度。同时，这种方法可以将传统的数据迭代方法转换成缓存参数无关（cache-oblivious）算法。

几种方法效果对比如下所示。可以看出FGF-Hilbert方法有更好的性能、更高的缓存命中率。

1.2 Exact Cardinality Query Optimization with Bounded Execution Cost

查询优化器常常会基于不精确的基数（cardinality）统计产生较差的执行计划。通过查询的探测性执行获取精确的基数可以产生更优的计划（ECQO，exact cardinality query optimization）。本论文为ECQO提出了一种新的算法，可以限制精确统计产生的额外探测代价。主要思想为不生成全部的中间结果，而是基于部分结果确定基数的取值边界。这种方法可以预先剔除一些代价过大的中间结果，并且根据依赖关系进行进一步剔除。

该算法是非侵入式的，可以运行在任何支持LIMIT语句的数据库系统上。论文证明了探测代价可以控制为较优代价的函数；同时，算法带来了平均6倍，最高69倍的性能提升。

1.3 Iterative Query Processing based on Unified Optimization Techniques

这是一篇优化存储过程的查询处理的论文。多语句查询的优化是经典的查询优化问题，对循环等结构的优化又是经典的程序设计语言优化问题。结合过程性语言和声明性语言二者的优势进行统一的优化是非常必要的。本文提出了一种新的思路，定义了query motion来支持将查询在循环内外移动，同时，论文还针对循环执行以及查询定义了新的代价模型。采用标准的决策支持类负载TPC-DS以及实际业务负载MRP都观察到了很好的性能改进效果。

SIGMOD 第二天也将有三个研究主题和一个工业主题，其中分布式数据管理研究主题中的第一个报告就是腾讯云架构平台部CDB数据库团队和华中科技大学-腾讯联合实验室周可教授团队合作的学术论文“An End-to-End Automatic Cloud Database Tuning System Using Deep Reinforcement Learning”。我们将在下一篇报道中跟大家详细解读。